初赛

考虑把这些数分成 $n$ 组，每组内部比较，然后大的那些选最大，小的那些选最小。答案为 $3n-2$。

double 除 int 或者 int 除 double 的返回值都是 double，而 int 除 int 会向下取整。

300iqContest2 B

题目链接

首先考虑 $a_i\oplus a_j\le x$ 这个限制不好做，考虑转化，经过分类讨论，异或有以下性质：

$$
a\le b\le c\Rightarrow \min(a\oplus b,b\oplus c)\le a\oplus c
$$

证明：

$a=c$ 是平凡的。若 $a\not c$，设 $w$ 是 $a,c$ 最高的二进制下不同的一位，因为 $a\le b\le c$，所以 $b$ 从 $w+1$ 及以上的这些位置 $a,b,c$ 都是一样的。所以异或结果这些位上全是 $0$。考虑位 $w$，显然 $a$ 为 $0$，$c$ 为 $1$，而 $b$ 不管这一位选什么总会导致 $a\oplus b,b\oplus c$ 某一个 $w$ 位变成 $0$。综上可知等式成立。

所以题目限制可以转化为相邻两个数的异或大于等于 $x$，于是可以设计一个 DP，设 $f_i$ 表示以 $i$ 结尾的合法序列个数，则转移应该为：

$$
f_i=\sum\limits_{a_i\oplus a_j\ge x,j\le i-1} f_j+1
$$

利用 Trie 树优化可以做到 $O(\log V)$ 的转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int n,X,a[N],f[N];

struct Trie{
    struct Node{
        int ch[2],val;
        inline Node(){ch[0]=ch[1]=0;val=0;}
        inline int operator [] (int id){return ch[id];}
    }p[N*60];
    int tot;
    inline Trie(){
        tot=1;
    }
    inline void Insert(int x,int v){
        int now=1;
        dec(i,0,60){
            int k=(x>>i)&1;
            if(!p[now][k]) p[now].ch[k]=++tot;
            p[now].val=(p[now].val+v)%mod;
            now=p[now][k];
        }
        p[now].val=(p[now].val+v)%mod;
    }
    inline int Ask(int x){
        int ans=0,now=1;
        dec(i,0,60){
            if(!now) break;
            int xk=(X>>i)&1;
            int aik=(x>>i)&1;
            if(!xk){
                (ans+=p[p[now][aik^1]].val)%=mod;
                now=p[now][aik];
            }
            else{
                now=p[now][aik^1];
            }
        }
        ans=(ans+p[now].val)%mod;
        return ans;
    }
}tr;

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(X);rep(i,1,n) read(a[i]);
    sort(a+1,a+n+1);
    rep(i,1,n){
        f[i]=(tr.Ask(a[i])+1)%mod;
        tr.Insert(a[i],f[i]);
    }
    int ans=0;
    rep(i,1,n){
        ans=(ans+f[i])%mod;
        // printf("f[%lld]=%lld\n",i,f[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

ZR 2022.9.20 赠送赛 A

如果能处理一下两种询问，那么这道题就做完了：一棵树内所有点到某个点的路径之和。一棵树内两个点的距离之和。

容易发现在本题中，询问中任意的点都应该是题目中给定的点，且设 $a$ 由 $b,c$ 组成，那么 $a$ 中的点会在 $b,c$ 出现，但是 $b,c$ 中点不会在 $a$ 中出现，是满足左边条件的题目中给定的带你。容易发现，这样的点一共有 $m^2$ 个。

考虑第一个询问，可以通过第二个询问把第一个询问规模缩小，且最多缩小 $m$ 次，所以仅考虑第二个询问时间复杂度即可。

考虑第二个询问只可能是以后的一个点与这一层这个点之间的询问，所以总的询问个数应该是 $m^3$ 的。

所以加上记忆化，总的复杂度应该是 $m^3$ 的。

ZR 2022.9.21 赠送赛 B

场上有一个 $n^3$ DP，设 $f_{i,j}$ 表示玩了 $i$ 轮，有 $j$ 个人还活着的概率是多少，转移式是显然的，每次枚举选了那个人，死了几个人即可。

但是发现所有人都是等价的，如果我们给每个点标上号，设题目中小 R 所在的点编号为 $n$，那么我们可以认为选点序列是从 $1$ 到 $n$ 选，这样做实际上是钦定了小 $R$ 一定是最后一个，那这样做的概率是 $\frac{1}{n}$，最后给答案乘上这个数即可。

接下来，设 $f_{i,j}$ 表示该考虑 $i$，$i$ 到 $n$ 被攻击了 $j$ 次的概率是多少。转移只需要考虑 $i$ 是否已经被攻击没了。

CF812Div2E

首先考虑主对角线，也就是对角线上所有点的横纵坐标之和一样的对角线，发现每次一个物体移动都会从一个对角线移动到另一个对角线，这同时表明了不可能存在某一时刻，一个对角线上存在两个物体，也就是说，合并是不可能存在的。

现在考虑一个询问 $t,x,y$，显然如果 $t<x+y$，那么肯定是没有任何物体到达 $x+y$ 这条对角线，所以一定是 NO，现在考虑 $t\ge x+y$，那么可能到达 $(x,y)$ 的那个位置一定是 $t-x-y$ 时刻被放在 $(0,0)$ 的，所以 $t-x-y-1$ 时刻之前的 $t-x-y$ 放的都可能会对这个时刻的东西的路径产生贡献。

观察可以得到，我们可以对一些球一起做，来得到 $x+y$ 这条对角线上每个位置的东西的个数，如果 $(a,b)$ 放了 $k$ 个东西，那么等价于 $\lfloor\frac{k}{2}\rfloor$ 往下走，$\lceil\frac{k}{2}\rceil$ 往右走。这样我们只需看 $t-x-y$ 情况下 $(x,y)$ 放的东西个数，和 $t-x-y+1$ 情况下 $(x,y)$ 放的东西个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int Q,t,x,y;
int a[N][N];

inline void Calc(int x,int y,int c){
    rep(i,0,min(120ll,x+y)){
        rep(j,0,min(120ll,x+y)){
            a[i][j]=0;
        }
    }
    a[0][0]=c;
    rep(i,0,x+y-1){
        // printf("i=%lld\n",i);
        rep(j,max(i-119ll,0ll),min(119ll,i)){
            int nowx=j,nowy=i-j;
            // printf("a[%lld][%lld]=%lld\n",nowx,nowy,a[nowx][nowy]);
            if(a[nowx][nowy]){
                if(nowx<119) a[nowx+1][nowy]+=a[nowx][nowy]/2;
                if(nowy<119) a[nowx][nowy+1]+=(a[nowx][nowy]+1)/2;
                a[nowx][nowy]=0;
            }
        }
    }
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(Q);
    while(Q--){
        read(t);read(x);read(y);
        if(t<x+y){puts("NO");continue;}
        Calc(x,y,t-x-y);int nowa=a[x][y];
        Calc(x,y,t-x-y+1);int nownowa=a[x][y];
        // printf("nowa=%lld nownowa=%lld\n",nowa,nownowa);
        if(nowa==nownowa){
            puts("NO");
        }
        else puts("YES");
    }
    return 0;
}

ZR 2022.9.21 C

我的 DP 是真的不行了。

考虑枚举最小的那个塞不下去的物品，那么比它小的都要放进去，比它大的，就是一个 $01$ 背包求方案数的 DP。如果 DP 已经做不了的事情，不妨加一点限制，多是枚举一个值。

XOR

这个题没有给题目链接。题目如下：

把所有 $a_i\oplus b_i$ 加入 Trie 树。

首先要去掉绝对值号，考虑枚举 $x$ 的最高位，如果是 $0$，那么最高位为 $1$ 对应的子树的所有 $a,b$ 之间的最大最小值就已经确定了，剩下的我们在子树里面暴力搜索。如果 $x$ 最高位填 $1$，同样暴力搜索。然后可以接着往下递归去做。

暴力搜索怎么算贡献？只需要在每个节点上统计经过这个点的数有多少个，就可以知道在某一位选择 $0$ 还是 $1$ 会有多大的贡献。

显然，一个点在搜索中被访问的次数是其祖先的个数。所以总的复杂度应当是 $O(n\log^2 V)$。

AGC044C

两个操作哪个都不会维护。

题解比较巧妙，考虑把所有的数放进三进制 $Trie$ 中，第一个操作等价于我们交换每个节点的 $1,2$ 儿子，而第二个操作需要我们把 $1$ 儿子改成 $1$ 儿子，$1$ 儿子改成 $2$ 儿子，$2$ 儿子改成 $0$ 儿子，然后别忘了进位，所以我们要从低位到高位建立 $Trie$ 树。

进位的处理只需要递归到子树接着处理即可。复杂度是 $\log$ 的，而第一个操作只需要打标记和标记下传。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
int pw[13],n,ans[N],cnt;
inline void Init(){
    pw[0]=1;
    rep(i,1,12) pw[i]=pw[i-1]*3;
}

struct Trie{
    struct Node{
        int ch[3],End,tag,dep;
        inline int& operator [] (const int id){return ch[id];}
    }p[N];
    int tot;
    inline Trie(){
        tot=1;Init();mset(p,0);
    }
    inline void C(int k){
        swap(p[k][1],p[k][2]);p[k].tag^=1;
    }
    inline void PushDown(int k){
        if(p[k].tag){
            rep(i,0,2) C(p[k][i]);p[k].tag=0;
        }
    }
    inline void Insert(int x){
        int now=1;
        rep(i,0,n-1){
            int k=(x/pw[i])%3;
            if(!p[now][k]) p[now][k]=++tot;
            p[p[now][k]].dep=p[now].dep+1;
            now=p[now][k];
        }
        p[now].End=x+1;
        // printf("now=%d\n",now);
        // printf("p[now].End=%d\n",p[now].End);
    }
    inline void R(){
        C(1);
    }
    inline void dfs(int k){
        if(!k) return;
        PushDown(k);
        int c2=p[k][2];
        p[k][2]=p[k][1];
        p[k][1]=p[k][0];
        p[k][0]=c2;
        dfs(p[k][0]);
    }
    inline void Inc(){
        dfs(1);
    }
    inline void Dfs(int k){
        if(!k) return;
        PushDown(k);
        rep(i,0,2) Dfs(p[k][i]);
    }
    inline void PushDownAll(){
        Dfs(1);
    }
    inline void ddfs(int k,int sum){
        // rep(i,0,2){
        //     printf("p[%d][%d]=%d\n",k,i,p[k][i]);
        // }
        if(!k) return;
        PushDown(k);
        if(!p[k][0]){
            // printf("k=%d\n",k);
            // printf("p[k].end=%d\n",p[k].End);
            assert(p[k].End);
            // printf("%d\n",p[k].End-1);
            ans[p[k].End-1]=sum;
            return;
        }
        rep(i,0,2){
            ddfs(p[k][i],sum+pw[p[k].dep]*i);
        }
    }
    inline void Print(){
        PushDownAll();
        ddfs(1,0);
    }
}tr;

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);
    string s;cin>>s;
    rep(i,0,pw[n]-1){
        tr.Insert(i);
    }
    // tr.Print();
    // // exit(0);
    int len=(int)s.length()-1;
    rep(i,0,len){
        if(s[i]=='S') tr.R();
        else if(s[i]=='R') tr.Inc();
        else assert(0);
    }
    tr.Print();
    rep(i,0,pw[n]-1){
        printf("%d ",ans[i]);
    }
    return 0;
}

SOJ #41

我愿称这种操作为区间覆盖加。

区间赋值是可持久化平衡树可以做的虽然我不会，但是考虑这个题是一个加法的操作。

加法！这提示我们想到卷积，考虑把一个区间 $l,r$ 加到上面，只需要让 $cnt_l$ 变成 $1$ 然后对两个数组做差卷积即可。

但是这里并不是直上直下的加法，考虑 $n$ 为 $10^5$，我们自然想到分块。散块直接处理了。对于整块的贡献，考虑枚举每一个块，然后对于每一个操作计算它对这个块的贡献，维护一个 $cnt$ 数组，然后把 $cnt$ 和 $a$ 数组做一个差卷积即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 600010
#define M 1000100
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=1004535809;
const int g=3;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct FastIO
{
    #define MB (1<<20)
    char ib[MB+100],*p,*q;
    char ob[MB+100],*r,stk[128];
    int tp;

    FastIO(){p=q=ib,r=ob,tp=0;}
    ~FastIO(){fwrite(ob,1,r-ob,stdout);}

    char read_char()
    {
        if(p==q)
        {
            p=ib,q=ib+fread(ib,1,MB,stdin);
            if(p==q)return 0;
        }
        return *p++;
    }
    template<typename T>
    void read_int(T& x)
    {
        char c=read_char(),l=0;
        for(x=0;!isdigit(c);c=read_char())l=c;
        for(;isdigit(c);c=read_char())x=x*10-'0'+c;
        if(l=='-')x=-x;
    }

    void write_char(char c)
    {
        if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);
        *r++=c;
    }
    template<typename T>
    void write_int(T x) 
    {
        if(x<0)write_char('-'),x=-x;
        do stk[++tp]=x%10+'0';
        while(x/=10);
        while(tp)write_char(stk[tp--]);
    }
}IO;

int n,m,a[N],posi[N],Len,cnt[N],b[N];
int tr[N];
int A[N];

struct Ope{
    int l,r,L;
}q[M];

inline int gel(int id){return (id-1)*Len+1;}
inline int ger(int id){return min(n,id*Len);}
inline void Gettr(int len){
    rep(i,0,len-1) tr[i]=(tr[i>>1]>>1)|((i&1)?(len>>1):0);
}
inline int ksm(int a,int b,int mod){
    int res=1;while(b){if(b&1){res=1ll*res*a%mod;}a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int x){return ksm(x,mod-2,mod);}
inline void NTT(int *f,int n,int op){
    rep(i,0,n-1) if(i<tr[i]) swap(f[i],f[tr[i]]);
    for(int i=2;i<=n;i<<=1){
        int tg=ksm(g,(mod-1)/i,mod);
        if(op==-1) tg=inv(tg);
        for(int j=0;j<n;j+=i){
            int now=1;
            for(int k=j;k<j+i/2;k++){
                int tt=now*f[k+i/2]%mod;
                f[k+i/2]=(f[k]-tt+mod)%mod;
                f[k]=(f[k]+tt)%mod;
                now=now*tg%mod;
            }
        }
    }
    if(op==-1){
        int invn=inv(n);
        rep(i,0,n-1) f[i]=f[i]*invn%mod;
    }
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    IO.read_int(n);rep(i,1,n) IO.read_int(a[i]);
    IO.read_int(m);
    rep(i,1,m){
        // read(q[i].l);read(q[i].r);read(q[i].L);
        IO.read_int(q[i].l);IO.read_int(q[i].r);IO.read_int(q[i].L);
    }
    Len=ceil(sqrt(log2(n)*n)*2.0);
    rep(i,1,n){
        posi[i]=(i-1)/Len+1;
    }
    rep(i,1,posi[n]){
        int l=gel(i),r=ger(i);
    }
    rep(j,1,m){
        int bl=q[j].L,br=min(n,q[j].L+q[j].r-q[j].l);
        int blid=posi[bl];
        int brid=posi[br];
        if(blid==brid){
            rep(i,bl,br){
                b[i]+=a[i-q[j].L+q[j].l];
            }
        }
        else{
            rep(i,bl,ger(blid)){
                b[i]+=a[i-q[j].L+q[j].l];
            }
            rep(i,gel(brid),br){
                b[i]+=a[i-q[j].L+q[j].l];
            }
        }
    }
    int len=1;
    while(len<(n+1)*2) len<<=1;
    Gettr(len);
    NTT(a,len,1);
    rep(i,1,posi[n]){
        int l=gel(i),r=ger(i);
        mset(cnt,0);
        rep(j,1,m){
            int bl=q[j].L,br=min(n,q[j].L+q[j].r-q[j].l);
            int blid=posi[bl];
            int brid=posi[br];
            if(blid<i&&i<brid){
                int len=l-bl+1;
                cnt[q[j].l+len-1]++;
            }
        }
        reverse(cnt+1,cnt+n+1);
        NTT(cnt,len,1);
        rep(j,0,len) cnt[j]=cnt[j]*a[j]%mod;
        NTT(cnt,len,-1);
        rep(j,l,r){
            int val=cnt[n+1+(j-l)];
            b[j]=(b[j]+val)%mod;
        }
    }
    // rep(i,1,n) printf("%lld\n",b[i]);
    rep(i,1,n){
        // printf("b[i]=%d\n",b[i]);
        IO.write_int(b[i]);
        IO.write_char('\n');
    }
    return 0;
}

Zhengrui 2022ABDay1 A

其中 $n\le 2e5$

闵可夫斯基和裸题。显然函数 $f(k)$ 是一个凸函数。极差不好做，进行转化：分成 $k$ 段，每段里面有一个 $1$，一个 $-1$，其余都是 $0$，问带权和最大是多少。

考虑如何合并，需要知道最左边和最右边两个区间是否都为 $1$，是否都为 $-1$，以及是不是 $1,-1$ 都有。合并时注意我们不认为只有 $1$ 和 $-1$ 的区间是一个完整的区间，其次，有可能会出现一个区间里面没有任何贡献，要处理这种合并只需要直接把左右儿子区间传上来即可。

其余的合并都是平凡的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n,a[N];
vi v[N<<2][3][3],t[3][3];

#define ls(k) k<<1
#define rs(k) k<<1|1
inline void Merge(vi b,vi c,vi &d,int o){
    int n=(int)b.size()-1,m=(int)c.size()-1;
    for(int i=0,j=0;i<=n&&j<=m;){
        cmax(d[i+j+o],b[i]+c[j]);
        if(j==m||(i<n&&b[i+1]-b[i]>c[j+1]-c[j])) i++;
        else j++;
    }
}
inline void PushUp(int k){
    rep(i,0,2)rep(j,0,2){
        Merge(v[ls(k)][i][0],v[rs(k)][1][j],v[k][i][j],1);
        Merge(v[ls(k)][i][1],v[rs(k)][0][j],v[k][i][j],1);
        Merge(v[ls(k)][i][2],v[rs(k)][2][j],v[k][i][j],0);
    }
}
inline void Divid(int k,int l,int r){
    rep(i,0,2)rep(j,0,2) v[k][i][j].resize(r-l+1+1,-INF);
    if(l==r){
        v[k][2][2][0]=v[k][2][2][1]=0;
        v[k][0][2][0]=v[k][2][0][0]=-a[l];
        v[k][1][2][0]=v[k][2][1][0]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Divid(ls(k),l,mid);Divid(rs(k),mid+1,r);
    rep(i,0,2)rep(j,0,2){
        rep(o,0,mid-l+1) cmax(v[k][i][j][o],v[ls(k)][i][j][o]);
        rep(o,0,r-mid) cmax(v[k][i][j][o],v[rs(k)][i][j][o]);
    }
    PushUp(k);
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n) read(a[i]);
    Divid(1,1,n);
    rep(i,1,n){
        printf("%lld\n",v[1][2][2][i]);
    }
    return 0;
}