省流：上分场，但是补题补入迷了导致 20:33 才想起来有 ABC。
G（个人感觉蓝）
题意
前置知识线段树、动态开点。
强制在线，N 次往一个多重集合中插入 x_i，每次插入后求排序后奇数项元素的和。
N \le 3\times 10^5,1\le x_i\le 10^9
题解
考虑建值域线段树，区间 [L,R] 保存信息：
- 当前在区间 [L,R] 的点的数量；
- 区间 [L,R] 所有数排序后奇数项的和；
- 区间 [L,R] 所有数排序后偶数项的和。
发现左右儿子可以 O(1) 合并到父亲区间，正确性显然。
因为值域在 [1,10^9]，所以要使用动态开点。时间复杂度 O(Q\log x _i)。
代码
int n,x,rt = 1,cnt = 1,num[20000000],ls[20000000],rs[20000000];
long long ans,s[20000000][2];
inline void push(int x){
num[x] = num[ls[x]] + num[rs[x]];
if(num[ls[x]] & 1) s[x][0] = s[ls[x]][0] + s[rs[x]][1],s[x][1] = s[ls[x]][1] + s[rs[x]][0];
//左半边有奇数个，左半边的奇数项+右半边的偶数项=整个区间的奇数项
else s[x][0] = s[ls[x]][0] + s[rs[x]][0],s[x][1] = s[ls[x]][1] + s[rs[x]][1];//左半边有偶数个，同理
}
void upd(int &k,int l,int r,int aim){
if(!k) k = ++ cnt;
if(l == r){
num[k] ++;//区间的数字个数
s[k][0] = 1ll * num[k] / 2 * l,s[k][1] = 1ll * (num[k] + 1) / 2 * l;//区间排序后奇数项偶数项和
return;
}
int mid = l + r >> 1;
if(aim <= mid) upd(ls[k],l,mid,aim);
else upd(rs[k],mid + 1,r,aim);
push(k);
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
scanf("%d",&x);
x = (x + ans) % maxv + 1;
upd(rt,1,maxv,x);//单点元素数+1
printf("%lld\n",ans = s[rt][1]);//询问整个区间的奇数项和
}
return 0;
}
F（绿）
题意
给一个数 N，输出最短的表达 N 的字符串表达式 S。S 仅能由 1、(、+、) 构成，例如 111+(1+1+1)*(1+1+1)。
1\le N\le 2000
题解
动态规划。
浅讲一下怎么实现，细节还请自行补全：首先，我们假设 f_i 表示构成 i 的 S 的最短长度。
初始 f_1\leftarrow1,f_{11}\leftarrow2,f_{111}\leftarrow3,f_{1111}\leftarrow4。
然后对于后面的每个数字 i ：f_i\leftarrow \min f_{j}+f_{i-j}+1
算乘法的时候发现了问题，由于优先级要加括号，根据现在 f 的定义我们没有办法快速地知道我们转移的时候要不要专门加括号。因此我们增加 g，f_i 为 S 表示 i 且最后一层运算为加法时的最短长度；g_i 则最后一层是乘法，或没有运算（单独一个数字），或加了括号。
然后有转移：
- 由
1组成的数字初始化； - f_i 从一个数字加上 1、11、111、1111 得到；
- g_i 从两个数字相乘得到；
- g_i 由 f_i 加上括号得到。
形式化地：
时间复杂度 O(N^2)。啥还要输出 S？那我们再为 f_i 和 g_i 分别统计它们值的来源，然后分类讨论递归输出，这部分比较难讲实在想不懂看代码吧。
代码
int n,f[3000],g[3000],ff[3000],gf[3000];
void output(int x,int kind){
if(kind){
if(!gf[x]) printf("%d",x);// 这个数是由 1 构成的
else if(gf[x] == x) printf("("),output(x,0),printf(")");// g[x] 来自 f[x]
else output(gf[x],1),printf("*"),output(x / gf[x],1);//g[x] 是由 gf[x] 和 x / gf[x] 相乘得到的
}
else{
if(ff[x] == x) printf("%d",x);// 这个数是由 1 构成的
else if(!ff[x]) output(x,1);// f[x] 来自 g[x]
else output(ff[x],0),printf("+"),output(x - ff[x],0);//f[x] 是由 ff[x] 和 x - ff[x] 相加得到的
}
}
int main(){
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
if(i == 1) f[i] = g[i] = 1,ff[i] = 1,gf[i] = 0;
else if(i == 11) f[i] = g[i] = 2,ff[i] = 11,gf[i] = 0;
else if(i == 111) f[i] = g[i] = 3,ff[i] = 111,gf[i] = 0;
else if(i == 1111) f[i] = g[i] = 4,ff[i] = 1111,gf[i] = 0;
else{
for(int j = 1;j < i;j ++) if(f[j] + f[i - j] + 1 < f[i]) f[i] = f[j] + f[i - j] + 1,ff[i] = j;
g[i] = f[i] + 2,gf[i] = i;//f 加上括号，变成 g
for(int j = 2;j < i;j ++) if(i % j == 0) if(g[j] + g[i / j] + 1 < g[i]) g[i] = g[j] + g[i / j] + 1,gf[i] = j;
if(g[i] < f[i]) f[i] = g[i],ff[i] = 0;//g 条件限制比 f 严格，故可以把 g 赋到 f 上
}
}
output(n,0);
return 0;
}
E（绿）
题意
初始给定两个字符串多重集合 X 和 Y，之后 Q 个时刻往两个集合之一加入一个字符串 S_i，每个时刻加入字符串后你需要回答 Y 中有多少个字符串，它的任何前缀都没有在 X 中出现过。
Q\le 3\times 10^5,\sum \vert S_i\vert\le 5\times 10^5
题解
算法上讲感觉是所有题里面最难的一道？（
前置知识字典树。
我们发现可以对 X 中的所有字符串构建字典树，之后可以在 O(\vert S\vert) 的时间里检验一个字符串 S 是否存在前缀在 X 中。
Y 中的一个字符串在某个时间之前一直不存在前缀在 X 中，某个时刻开始它的一个前缀被加入了 X，称作过期时间，这是可以二分的。但是字典树的构建只能按时间构建，除非你对它进行可持久化，而二分不能保证查询的时间一直在变大。
所以可以考虑整体二分。什么是整体二分？具体讲过程：
- 假设一开始所有要加入 Y 的字符串已经全部加入，它们的过期时间在 [1,Q]。
- 开一个查询序列，记录所有字符串查询二分的时间（目前为 \frac{Q}{2} ）。
- 按时间顺序往字典树里加入 X 中的元素，当到了某个字符串的查询时间时，进行 O(\vert S\vert) 的查询，记录查询结果。
- 容易证明，上述过程的时间复杂度是 O(\sum \vert S_i\vert) 的，因为每个 X 中的字符串被加入字典树了一次，每个 Y 中的字符串同样被线性查询了一次。
- 根据查询结果，缩小 Y 中字符串的过期时间范围，在这一轮中有的变成了 [1,\frac{Q}{2}]，有的变成了 [\frac{Q}{2},Q]。
- 重复上述过程直至所有的字符串过期时间所在的区间长度为一。
这要跑 O(\log Q) 轮，然后我们统计每个 Y 中的字符串的贡献即可，它从出现到过期这一段产生了 1 的贡献，考虑用差分数组计算，是 O(Q) 的。精细实现总时间复杂度 O(\sum\vert S_i\vert\log Q)。
int q,t,n,m,tx[Q],ty[Q],l[Q],r[Q],nt,cnt,sn[sum_s][size_c],rt,c[Q],ans;
bool wrk,suc[Q],tag[sum_s];
string s[Q],x[Q],y[Q];
vector<int>chc[Q];
inline void init_trie(){//清空字典树
for(int i = 1;i <= cnt;i ++){
for(int j = 0;j < 26;j ++) sn[i][j] = 0;
tag[i] = false;
}
rt = cnt = 1;
}
inline void insert(int w){//往字典树中插入 X 的第 w 个字符串
int u = rt;
for(int i = 0;i < x[w].size();i ++){
int c = x[w][i] - 'a';
if(!sn[u][c]) sn[u][c] = ++ cnt;
u = sn[u][c];
}
tag[u] = true;
}
inline bool find(int w){//查询字典树中有否 Y 的第 w 个字符串的前缀
int u = rt;
for(int i = 0;i < y[w].size();i ++){
int c = y[w][i] - 'a';
if(!sn[u][c]) return false;
u = sn[u][c];
if(tag[u]) return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
cin >> q;
for(int i = 1;i <= q;i ++){
cin >> t >> s[i];
if(t == 1) x[++ m] = s[i],tx[m] = i; //X 的字符串
else y[++ n] = s[i],ty[n] = i;//Y 的字符串
}
for(int i = 1;i <= n;i ++) l[i] = 1,r[i] = q + 1;//二分域初始化
tx[m + 1] = q + 1;
while(true){
wrk = false;
for(int i = 1;i <= q;i ++) chc[i].clear();
for(int i = 1;i <= n;i ++) if(l[i] < r[i]) wrk = true,chc[(l[i] + r[i]) / 2].push_back(i);//(l[i]+r[i])/2 时刻要检查 Y[i] 是否过期
if(!wrk) break;//如果所有的二分都完成就退出
init_trie();
for(int i = 1;i < tx[1];i ++) for(auto j : chc[i]) suc[j] = false;//加入第一个字符串前 X 为空， 故此时任何字符串不过期
for(int i = 1;i <= m;i ++){
insert(i);
for(int j = tx[i];j < tx[i + 1];j ++) for(auto k : chc[j]) suc[k] = find(k);//检查所有字典树这个状态下的询问
}
for(int i = 1;i <= n;i ++){
if(l[i] < r[i]){//处理二分的结果
if(suc[i]) r[i] = (l[i] + r[i]) / 2;
else l[i] = (l[i] + r[i]) / 2 + 1;
}
}
}
for(int i = 1;i <= n;i ++) if(ty[i] < l[i]) c[ty[i]] ++,c[l[i]] --;//差分统计答案
for(int i = 1;i <= q;i ++){
ans += c[i];
printf("%d\n",ans);
}
return 0;
}
D（黄）
题意
给一个长为 N 的数列 A 和一个非负整数 D，问至少要从 A 里删除多少个元素才能使得 A 里面没有差为 D 的两个元素。
1\le N\le 2\times 10^5,0\le D\le 10^6,0\le A_i\le 10^6
题解
动态规划，以 D=1 的情况为例，f_{i,0/1} 表示 [1,i] 的值域区间已经被删到合法，同时数列里存不存在 i 的至少删除次数，则有
推广一下，D>1 的情况就把 0,D,2D,3D,\cdots 放在一起做一次上述操作，1,D+1,2D+1,3D+1\cdots 做一次，以此类推。特判 D=0，每种数字留存一个。
时间复杂度 O(N+A_i)。
代码
int n,cnt[2000000],a,d,ans,f[2000000][2];
int main(){
scanf("%d%d",&n,&d);
for(int i = 1;i <= n;i ++){
scanf("%d",&a);
cnt[a] ++;
}
if(d){
for(int i = 0;i < d;i ++){//对 i,i+D,i+2D,i+3D... 进行 DP
f[0][0] = cnt[i];
for(int j = 1;j * d + i <= 1000000;j ++) f[j][0] = min(f[j - 1][0],f[j - 1][1]) + cnt[j * d + i],f[j][1] = f[j - 1][0];
ans += min(f[(1000000 - i) / d][0],f[(1000000 - i) / d][1]);
}
}
else for(int i = 0;i <= 1000000;i ++) ans += max(0,cnt[i] - 1);
printf("%d",ans);
return 0;
}
C（橙）
题意
AtCoder 上有 N 个用户和 M 个页面，初始所有用户都没有任何页面的浏览权限。接下来 Q 个时刻，每个时刻你要处理以下三种事件：
1 x y用户 x 获得了页面 y 的浏览权限；2 x用户 x 获得了所有页面的浏览权限；3 x y询问用户 x 是否有页面 y 的浏览权限。
1\le N,M,Q\le 2\times 10^5。
题解
一种做法是用 p_{x,y} 记录用户 x 是否被授予 y 的浏览权限，g_x 记录用户 x 是否被授予过全部页面的浏览权限，查询时查询二者的或值，但是这样空间复杂度是 O(NM) 的，会爆。
这个时候可以使用 STL 中的 map，它用一个对数复杂度换取了可以动态往里面添加查询键值对的可能性，定义一个 map<pair<int,int>,bool>p，修改、查询 p[{x,y}] 即可。时间复杂度 O(Q\log Q)。
代码
int n,m,q,op,x,y;
bool g[300000];
map<pair<int,int>,bool>p;//定义 map
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i = 1;i <= q;i ++){
scanf("%d%d",&op,&x);
if(op == 1){
scanf("%d",&y);
p[{x,y}] = true;//map 可以用下标的形式访问
}
if(op == 2) g[x] = true;
if(op == 3){
scanf("%d",&y);
if(g[x] || p[{x,y}]) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
B（橙）
题意
给出字符串 T,U，由小写字母组成，但是 T 中有四个字母被替换成了 ?，给你替换后的 T，问 U 有没有可能是原先的 T 的连续子串？
1\le \vert U\vert \le \vert T\lvert\le 10
题解
暴力从 T 的每一个位置 i 开始找，看 T_{i\cdots i+\vert U\vert-1} 有没有可能全等于 U_{1\cdots\vert U\vert}，如果中途出现了 T_j 是一个字母并且和对应的 U_k 对不上，那就不等，否则没出现过就是可能全等。
时间复杂度 O(\vert T\vert\vert U\vert)，可以用 KMP 做达到 O(\vert T\vert + \vert U\vert)。
代码
int n,m;
char t[20],u[20];
bool fal,suc;
int main(){
scanf("%s%s",t + 1,u + 1);
n = strlen(t + 1),m = strlen(u + 1);
for(int i = 1;i <= n - m + 1;i ++){
fal = false;
for(int j = 1;j <= m;j ++) if(t[i + j - 1] != '?' && t[i + j - 1] != u[j]) fal = true;
if(!fal) suc = true;
}
if(suc) printf("Yes");
else printf("No");
return 0;
}
A（红）
题意
给你一个长度为 N 的数组 A，询问其中奇数项的和。
1\le N,A_i\le 100
题解
按题意模拟即可。
代码
int n,a[200],ans;
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
scanf("%d",&a[i]);
ans += (i & 1) * a[i];
}
printf("%d",ans);
return 0;
}