Atcoder Grand Contest 选做
| (A) | (B) | (C) | (D) | (E) | (F) | |
|---|---|---|---|---|---|---|
| (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) | ✔ | * | * |
(11.08)
之前的题都写在 好题胡扯 里了，以后大概会把 agc 和其他的题分开更。
AGC044C Strange Dance
我居然会
考虑先取 (lceil frac n2 ceil) 位暴力跑，然后后 (lfloor frac n2 floor) 位进位次数不多，可以暴力做。复杂度暂时不会证。
*AGC044D Guess the Password
出题人 nb!
(A=|alphabet|=62)，发现可以先用 (A) 次询问得到每个字母的出现次数。
Key Observation: 若 (|T|le |S|)，删除的次数为 (|S|-|T|)，那么 (|T|) 为 (|S|) 的子序列。
由性质可以用 (|f(A)|+|f(B)|-1) 合并 (A,B)，将两个 (S) 的子序列合并为一个。这样用不超过 (Llceil log(A) ceil-A+1) 次询问即可合并，总的询问次数最多为 (Llceil log(A) ceil+1=769) 次。
*AGC044E Random Pawn
先找到最大值，破环为链。
算了复读题解没啥意义，不写了
然后就变成凸包面积求和了。
(11.09)
*AGC013E Placing Squares
恭喜你发现了一个组合意义都想出来了没想到矩阵快速幂的 sb......
总结：
求 (n) 个位置的划分方案数，有两种形式：
- 求所有划分的方案数
- 求划分 (m) 次的方案数
前者因为没有划分的限制，所以考虑快速算，而不是先枚举分多少段，不然会多个 (n)。。。
后者和前者相反，通常可以从全局入手，用组合数算，不行再考虑枚举几段。
(11.12)
AGC043B 123 Triangle
Fading 大爷推给我的题，成功找规律找了快 40 分钟，总算会了。
这个 B 怎么这么难啊，我要自闭了
先将序列差分一次，此时序列只有 (0,1,2)。
理性分析一下，发现答案是 (2) 的时候原序列没有 (1)，所以我们只用考虑存在 (0) 和 (2) 的序列。
其他情况只和答案的奇偶性有关，那么用卢卡斯定理算一算 (n-1choose i-1) 的奇偶性即可。
答案是 (2) 的情况用类似奇偶性的方法算一算即可。
(11.16)
*AGC036D Negative Cycle
转差分约束模型，找性质。
(11.22)
化身鸽子.jpg
*AGC003F Fraction of Fractal
先讨论上下边界的连通情况。
都连通答案是 (1)，都不连通答案是 (cnt^{k-1})，只有一边连通可以矩阵快速幂。
我才不会告诉你我没看到所有黑格四连通
(11.25)
AGC009D Uninity
好题!
要求点分树最大深度最小，即所有点有一个权值，使得 (=k) 的权值路径中一定一个点权值 (>k)。（这里的权值指点分树子树的最大深度）
可以贪心，用位运算优化。说的太麻烦了，看代码吧。
void dfs(int u,int ff)
{
int lim=0;
for(auto v:g[u])
if(v!=ff)
dfs(v,u),lim|=bit[u]&bit[v],bit[u]|=bit[v];
int mx=30;
while(mx>=0 && !(lim&(1<<mx))) mx--;
mx++;
while(bit[u]&(1<<mx)) mx++;
ans=max(ans,mx),bit[u]|=(1<<mx),bit[u]=(bit[u]>>mx)<<mx;
}
AGC009E Eternal Average
前几天做的。
将选的过程抽象成一棵操作树，将进位转成判断数位和的大小和模 (k-1) 的余数。
看 litble 的题解好了，懒得讲了
*AGC004F Namori
树是结论，奇环是调整出合法解，偶环是中位数。