• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

Day 1

A. 树

考虑现在确定哪个叶集是第一个,其余的是第二个。也就是说,需要计算第一个叶集是这个的方案的个数。手工制作一套很容易。第一棵树是每个点前面的非叶数相乘(第二棵树也差不多),所以可以选一个不能是叶集公差的。

所以大概是这样的:

\[(\sum_{}(-1)^{|s|} \时报w(s))(\sum_{}(-1)^{|t|} \时报w(t))

\]

然后你扩展了一下,发现也是可以的,说明你们可以一起包容,一起排斥。其实很明显。

所以就dp而言,在决定每个点是哪片叶子的同时,另一棵树可以选择,也算是叶子公差。

从数字从小到大考虑,\(f_{x,y}\)表示当前位置(包括这一个)之前的第一棵树前面有\(x\)个非叶子,当前位置(不包括这一个)之后的第二棵树有\(y\)个非叶子。

开始时\(f_{1,i}=i\),结束时\(ans=\sum_{i} f_{i,1 } \乘以i\)

每次迭代加一,假设前一个是\(f'\),考虑对当前\(f\)的贡献:

考虑第一棵树的当前叶子。

指定第二棵树是叶隐忍:\ (-f' _ {x,y} \ x \ y \右箭头f _ {x,y } \)

第二棵树是叶子:\ (f' _ {x,y } \ times x \ times(y-1)\ right arrow f _ { x,y-1} \)

考虑第二个树叶集合是这样的。

秦指定的第一棵树是叶隐忍:\ (-f' _ {x,y} \ x \ x \ y \右箭头f _ {x,y } \)(哈哈,和刚才一样,厉害!

未决定:\ (f' _ {x,y} \乘以x \乘以y \ rightarrow f _ {x 1,y} \)

复杂性\(o(n ^ 3)\)。

代码应该是正确的吧?计算问题。

//SKyqwq

#包含位/标准数据。h

#首先定义fi

#定义se秒

#定义mp生成对

#定义按钮推回

使用命名空间std

typedef pairint,int PII;

typedef long long LL

模板typename T bool inline chkMin(T x,T y) { return (y x)?x=y,1 : 0;}

template typename T bool inline chk max(T x,T y) { return (y x)?x=y,1 : 0;}

模板类型名T void inline read(T x) {

x=0;int f=1;char s=getchar();

while(s ' 9 ' | | s ' 0 '){ if(s=='-')f=-1;s=getchar();}

while (s='9' s='0') x=x * 10 s - '0 ',s=getchar();

x *=f;

}

const int N=505

int P,N,f[N][N],g[N][N],ans

void inline add(int x,int y) {

x=y;

if(x=P)x-=P;

}

void inline del(int x,int y) {

x-=y;

if(x ^ 0)x=P;

}

int main() {

读(n),读(P);

for(int I=1;I=n;I)f[1]=I;

for(int I=2;I=n;i ) {

ans=0;

for(int j=1;j=n;j ) add(ans,1ll * f[j][1]* j % P);

printf('%d\n ',ans);

memcpy(g,f,sizeof f);

memset(f,0,sizeof f);

for(int x=1;x=n;x ) {

for(int y=1;y=n;y ) {

如果(!g[x][y])继续;

int w=g[x][y];

add(f[x][y - 1], 1ll * w * x % P * (y - 1) % P); del(f[x][y], 1ll * w * x % P * y % P); add(f[x + 1][y], 1ll * w * x % P * y % P); del(f[x][y], 1ll * w * x % P * y % P); } } } return 0; }

D2T2 众数

都有众数了,,,感觉就不能 polylog!

就是选一段区间,算出他里面的众数 + 外面的众数最大值,然后这个贡献是外面众数颜色的。

考虑对每种颜色大小根号分治,暂且以 \(\sqrt{n}\) 为界。

对于 \(> \sqrt{n}\) 的颜色,可以 \(O(n)\) 暴力做,先预处理关于这个颜色的前缀和,可以快速求出一段区间有多少这个颜色,可以枚举每种另外一个颜色,然后用 \(O(这个颜色大小)\) 的复杂度算出他在两边或者在中间的贡献。复杂度 \(O(n \sqrt{n})\)

于是我们只剩下了两两都是 \(\le \sqrt{n}\) 的。

考虑我们可以暴力枚举选的区间左右端点了,因为如果两边都有数,两边外面都是这个颜色一定不劣。考虑扫描线,枚举选的右端点,然后暴力枚举这个颜色前面所有出现的位置当左端点。

然后我们要快速算这之间的众数,似乎不太能做,但其实我们只用考虑出现次数 \(\le \sqrt{n}\) 的颜色就行,答案也肯定不超过根号。

于是我们可以开个数组 \(S_i\) 表示现以 \(i\) 为左端点的众数(只管次数小于根号的),考虑更新的时候也是暴力枚举他的之前所有颜色的位置 \(j\),考虑之间有 \(k\) 个这个颜色的,需要做的就是对 \(S_{1 \sim j}\) 对 \(k\) 进行 \(\text{chkMax}\),我们发现 \(S\) 数组是不增的,并且值域不超过根号,那其实能 \(\text{chkMax}\) 就往前跳,不能就停就好了,考虑每次 chkMax 至少使 \(S\) 总和 \(+1\),而最终 \(S\) 总和不会超过 \(n \sqrt {n}\),那么复杂度就是对的。

综上,因为两侧都达到了上届,所以分块界是合适的(这范围也不太可能有 \(\log\) 了。。

还要注意一些细节,例如两边可能只有一边有这个颜色,还得正反扫一遍?

总复杂度 \(O(n \sqrt {n})\)

// Skyqwq
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}
const int N = 2e5 + 5;
int n, a[N], b[N], len, d[N], t, ans, w[N], B, s[N], pos[N], L[N], R[N], loc[N], cnt[N];
int S[N];
int inline get(int x) {
    return lower_bound(b + 1, b + 1 + len, x) - b;
}
vector<int> c[N];
void inline pr() {
    for (int i = 1; i <= n; i++) b[i] = a[i];
    len = n;
    sort(b + 1, b + 1 + len);
    len = unique(b + 1, b + 1 + len) - b - 1;
    for (int i = 1; i <= len; i++) w[i] = 0;
    for (int i = 1; i <= n; i++) a[i] = get(a[i]);
    for (int i = 1; i <= n; i++) loc[i] = c[a[i]].size(), c[a[i]].pb(i);
    B = sqrt(n);
    // B = 1;
    for (int i = 1; i <= n; i++) {
        pos[i] = (i - 1) / B + 1;
        if (!L[pos[i]]) L[pos[i]] = i;
        R[pos[i]] = i;
    }
}
// x 在两边,x 前缀和 s,y 在中间
void inline wk1(int x, int y) {
    int v = -1e9, ret = 0;
    for (int A = 0; A < (int)c[y].size(); A++) {
        chkMax(v, -A + s[c[y][A] - 1]);
        chkMax(ret, v + A + 1 + s[n] - s[c[y][A]]);
    }
    chkMax(w[x], ret);
}
// y 在两边,x 在中间,x 前缀和 s
void inline wk2(int x, int y) {
    int v = -1e9, ret = 0;
    for (int A = 0; A < (int)c[y].size(); A++) {
        chkMax(ret, v + s[c[y][A] - 1] + (int)c[y].size() - A + 1);
        chkMax(v, A + -s[c[y][A]]);
        chkMax(ret, s[c[y][A] - 1] + (int)c[y].size() - A);
        chkMax(ret, A + 1 + s[n] - s[c[y][A]]);
    }
    chkMax(w[y], ret);
}
void inline big() {
    for (int i = 1; i <= len; i++) {
        if ((int)c[i].size() > B) {
            for (int j = 1; j <= n; j++) s[j] = 0;
            for (int v: c[i]) s[v] = 1;
            for (int j = 1; j <= n; j++) s[j] += s[j - 1];
            for (int j = 1; j <= len; j++)
                if (i != j) wk1(i, j);
            for (int j = 1; j <= len; j++)
                if ((int)c[j].size() <= B) wk2(i, j);
        }
    }
}
void inline upd(int x, int y) {
    while (x && S[x] < y) {
        S[x] = y;
        --x;
    }
}
void inline small() {
    for (int i = 1; i <= n; i++) {
        if ((int)c[a[i]].size() <= B) {
            // do calc
            int val = (int)c[a[i]].size() - loc[i] + S[1];
            for (int j = loc[i] - 1; j >= 0; j--) {
                int p = c[a[i]][j];
                chkMax(val, j + 1 + (int)c[a[i]].size() - loc[i] + S[p + 1]);
            }
            chkMax(w[a[i]], val);
            // do upd
            for (int j = loc[i]; j >= 0; j--)
                upd(c[a[i]][j], loc[i] - j + 1);
        }
    }
    int mx = 0;
    for (int i = n; i; i--) {
        chkMax(w[a[i]], mx + loc[i] + 1);
        cnt[a[i]]++;
        chkMax(mx, cnt[a[i]]);
    }
}
void inline out() {
    ans = 0;
    for (int i = 1; i <= len; i++)
        chkMax(ans, w[i]);
    for (int i = 1; i <= len; i++)
        if (w[i] == ans) d[++t] = b[i];
    printf("%d\n", ans);
    sort(d + 1, d + 1 + t);
    t = unique(d + 1, d + 1 + t) - d - 1;
    for (int i = 1; i <= t; i++) printf("%d\n", d[i]);
}
void inline clr() {
    for (int i = 1; i <= len; i++) c[i].clear();
    for (int i = 1; i <= n; i++) cnt[i] = 0, S[i] = 0, pos[i] = L[i] = R[i] = w[i] = 0;
    ans = 0;
    t = 0;
    len = 0;
}
int main() {
    //freopen("mode.in", "r", stdin);
    //freopen("mode.out", "w", stdout);
    int T; read(T);
    while (T--) {
        read(n); 
        for (int i = 1; i <= n; i++) read(a[i]);
        pr();
        big();
        small();
        out();
        clr();
    }
    return 0;
}
Link to comment
Share on other sites