「Solution」友谊赛
今天友谊赛题解，上届巨佬写的，搬上了方便查看。
A-Rainyrabbit 爱邮递
算法 1
每次重建快递站后直接深搜一遍累加贡献就好了，然后 $\mathcal{O}(1)$ 回答。
你可以获得 10pts 的好成绩。
算法 2
菊花图，这个很简单啊。
如果加的是花心，相当于其他城市都加 $1$，否则就是花心的城市加 $1$，其他城市加 $2$。
结合算法 1 可以获得 30pts 的好成绩。
算法 3
一条链的话也是送的，直接拆拆贡献用棵线段树维护即可。
结合算法 1,2 可以获得 60pts 的好成绩。
算法 4
做法 1
考虑树怎么做，很套路的可以将 $dis(x,y)$ 拆成 $dep_x+dep_y-2dep_{\operatorname{lca}(x,y)}$，但是拆了还是不好做，修改最坏还是 $\mathcal{O(n)}$ 的。
发现 $dep_{\operatorname{lca}(x,y)}$ 这个玩意可以借助 [LNOI2014]LCA 的思想，将树根 $1$ 到 $x$ 上的边都加上一次这条边的权值，然后节点 $y$ 往上爬，途中边排边累加该边的贡献，爬到根后就是 $dep_{\operatorname{lca}(x,y)}$ 的值。
于是便有了一个新的算法，对于重建快递站到 $u$，直接将 $u$ 往上爬，并更新每条边新的贡献，查询的话就跟刚才一样的往上爬就好了。
暴力往上爬的话可以过数据随机的点，然后结合算法 1,2,3 就能获得 80pts 的好成绩。
正解直接用树链剖分优化即可。
时间复杂度 $\mathcal{O}(n\log^2 n)$。
1 |
|
做法 2
来自巨佬 WY 的做法，cdq 分治+虚树。
B-Rainyrabbit 爱回文
很遗憾，因为数据过水，导致有 5 人 AC，但是本质上只有 3 人写的正解，其他的时间复杂度都是错的。
多次询问一个字符串 $s$，问构造若干字符串 $t_1,t_2,\cdots ,t_k$ 使得 $s=t_1t_2\cdots t_k$ 并且 $\forall i \in [1,k],t_i \geq 2$ 并且是回文串的方式是否存在。$T \leq 10,|s| \leq 10^6$。
首先每次选最大的回文串肯定是错的。具体看这个串 ababallllllab。
先求出 $f$，$f_i$ 为以字符 $i$ 为开头的最短回文串长度。
考虑这个辅助数组的作用。假设我们的合法划分方案，在这里的划分出来的回文串长度是 $d$，那么这个 $f_i$ 与 $d$ 的关系是什么呢？
首先，显然 $f_i \leq d$。分类讨论：
- $f_i = d$：那没事儿了。
- $f_i < \dfrac{d}{2}$：显然我们可以将这个字符串 $d$ 看成三个回文串，也就是一段 $f_i$，以最后一个字符为中心对称过去，或者是再恰一个字符再对称，或者是直接对称过去；
- 否则这种情况是不可能的，因为这样我们能够找到更小的前缀回文串。可以自行理解。注意这个更小的前缀回文串可能是一个字母，需要特判。
综上，以 $i$ 开头的回文串长度的选择只有四个：$f_i,2f_i-1,2f_i+1,2f_i$。可以证明其可以涵盖所有情况。剩下的工作就是做个 dp。
考虑求出这个 $f$ 数组。有三种做法，时间复杂度分别是 $O(n \log n),O(n \alpha(n))$。标程给的是 $O(n\log n)$ 的做法。$O(n \alpha(n))$ 做法由 @chihik 提出。
理论上来说有 $O(n)$ 的做法，但是我太菜没听懂 @crashed 再说啥。
$O(n \log n)$
考虑对于每一个字符，求出以它为中心（中心可以是和下一个字符结合也可以是一个字符，这个是两类）的最长回文串，在其左端点打上标记。标记记录三个值，表示其起始位置，有效长度及中心是和下一个字符结合还是一个字符。做法是 hash 二分。你高兴也可以 manacher。
这个东西的意义是，我们选择的 $f_i$，一定是离有效范围内结束最近的那个位置的距离。于是处理三个东西，可以发现这个东西可以全部拍进 set 里面选最小的且合法的。具体处理方法看代码。
代码有个小补丁，就是要处理两个相邻字符相同的情况。这个时候直接把 $f_i$ 设为 $2$ 即可。
1 | /* |
$O(n \alpha (n))$ By @chihik
考虑回文自动机。一样的思路，求出以某位为起点的最长回文串。暴力回跳。显然 T，于是并查集优化即可。
$O(n)$ By crashed / LY（初二）
本意是选联赛范围考察。但是因为大家都会回文自动机所以被踩了。反正其实我也不会。
具体做法是链上排一次序（基排 By crashed）。
C-Rainyrabbit 爱求和
菜鸡出的垃圾套路题。/kk
算法 1
测试点 $1$ 随便手玩。
期望得分 4 分。
算法 2
测试点 $2\sim 3$ 按照题意模拟。
期望得分 12 分。
算法 3
测试点 $4\sim 5$ 先在外面直接算然后直接回答。
期望得分 20 分。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
using namespace std;
const int mod=998244353;
int dec(int x, int y) { return x >= y ? x - y : x + mod - y; }
int mul(int x, int y) { return 1ll * x * y % mod; }
int add(int x, int y) {
if (x + y >= mod)
return x + y - mod;
return x + y;
}
int qkpow(LL a, LL b) {
int res = 1;
for (; b; b >>= 1, a = mul(a, a))
if (b & 1)
res = mul(res, a);
return res;
}
int t,mem[105][105][105];
LL a,b,c;
LL lcm(LL a,LL b){
return a/__gcd(a,b)*b;
}
LL sigma(LL n,LL k){
LL ans=0;
for(int i=1;i<=n;i++){
if(n%i==0)ans=add(ans,qkpow(i,k));
}
return ans;
}
LL f(LL n,LL m,LL k){
LL ans=0;
for(LL i=m;i<=n;i+=m)ans=add(ans,sigma(i,k));
return ans;
}
signed main(){
cin>>t>>c;
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
for(int k=0;k<=c;k++)
mem[i][j][k]=k==0?f(i,j,0):add(mem[i][j][k-1],f(i,j,k));
for(int i=1;i<=100;i++){
for(int j=1;j<=100;j++){
mem[i][j][c]=add(mem[i][j][c],add(mem[i][j-1][c],mem[i-1][j][c]));
mem[i][j][c]=dec(mem[i][j][c],mem[i-1][j-1][c]);
}
}
while(t--){
cin>>a>>b;
cout<<mem[a][b][c]<<endl;
}
return 0;
}
/*
5 5
4 1 3 6 2
1 2 4
2 1 3
0 0 3 2
1 1 2
2 2 4
*/
算法 4
送分结束。
来推一推 $f$ 函数。
$$ f(n,m,k)=\sum_{d=1}^n d^k \lfloor\dfrac{n}{\operatorname{lcm}(d,m)}\rfloor=\sum_{d=1}^n d^k \lfloor\dfrac{\dfrac{n}{d}}{\lfloor\dfrac{m}{\gcd(d,m)}\rfloor}\rfloor $$这个东西是有意义的，$\sum_{d=1}^n d^k \lfloor\dfrac{\dfrac{n}{d}}{\lfloor\dfrac{m}{\gcd(d,m)}\rfloor}\rfloor=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[id|m]$
然后拆回来
$$ f(n,m,k)=\sum_{m|i}^n \sum_{d|i}d^k=\sum_{m|i}^n \sigma_k(i) $$结论就推完了。
代回去
$$ \sum_{k=0}^c\sum_{i=1}^a\sum_{j=1}^b\sum_{j|p}^i\sigma_k(p) $$ $$ \sum_{k=0}^c\sum_{p=1}^a\sigma_k(p)(a-p+1)\sum_{j=1}^b[j|p] $$ $\sigma_k(p)$ 那里可以直接把 $\sigma_0(p),\sigma_1(p)...,\sigma_c(p)$ 都累加到一坨，然后直接 $\mathcal{O}(n^2)$ 计算即可。 跟刚才一样的操作，先在外面都算出来再回答，可以获得 36pts 的好成绩。 ### 算法 5 发现 $b$ 的那个求和并不需要一个一个算，直接调和级数复杂度算就好了，然后就能获得 40 pts。 ### 算法 6 $c$ 太大了，推一推怎么算 $\sum_{i=0}^c \sigma_i(p)$。 $$ \sum_{i=0}^c \sum_{d|p}d^i $$发现对于每一个因子的贡献都是一个等比数列。
$$ \sum_{d|p}\dfrac{d^{c+1}-1}{d-1} $$线性筛后调和级数算就好了，然后就能获得 68 pts 了。
算法 7
发现 $b$ 超过 $a$ 的范围以后是不会有任何贡献的，于是取个 $\min$ 算，至此就能获得 80 pts 的好成绩。
算法 8
这东西并不好多组询问，$a,b$ 变来变去的很烦。
考虑离线，将每一个询问按照 $b$ 排序。当 $b=i$ 时能影响到的位置是 $\dfrac{n}{i}$ 个，直接树状数组修改即可。修改完后，直接查询就好了。
时间复杂度 $\mathcal{O}(a\ln a+T\log T+\min(a,b)\ln \min(a,b)\log a+T\log a)$。
由于这东西并跑不满，跑 $10^6$ 是跑的过的。代码及其好写。
1 |
|
D-Rainyrabbit 爱染色
本场比赛的防 AK 题。其实思维难度不算太大，只是极其难写。
算法 1
爆搜即可。可以获得 10 pts。
算法 2
考虑 $\mathcal{O}(nm)$ 的做法。
考虑贪心，每次选择只由该关键点覆盖的节点个数最多的关键点拿来染色，选完后重新更新一下（因为选了一个关键点染色），重复以上步骤 $m$ 次，期间更新一下答案就好了，容易证明得出的答案一定是最优的。
期望得分 40 pts。
算法 3
先来考虑优化链的情况。
发现每个关键点控制的范围都是一个连续的区间，用一棵线段树维护即可。
菊花图就更简单了，如果花心 $d_i\ge 1$ 全部都能控制到，其他的点如果 $d_i=1$ 就只能控制花心，$d_i=2$ 就能控制所有的点。随便更新一下就好了。
结合算法 2 期望得分 60pts。
算法 4
发现复杂度瓶颈在于怎么快速找到只由该关键点覆盖的节点个数最多的关键点及其更新。
先来看看 $d_i\in{0,1}$ 的情况，因为每个关键点能覆盖的节点是散开的，不好处理。于是考虑将树从上到下每一层从左到右编个号，然后你会惊奇的发现对于 $d_i=1$ 的关键点能染到的点可以看成一个连续的区间和该关键点父亲的编号。于是可以想到用线段树维护，用每一个点的编号建树，但是发现不太好维护，因为要知道是哪一个关键点，而不是最多的点数，于是想到在线段树的每一个节点上都开一个 set 维护这个区间编号的节点有哪些关键点能够染到，找到后删除的话就直接 erase 就好了。现在的问题，怎么找？？？？考虑直接从根节点往下搜，直接暴力找肯定会 T，考虑对于线段树上的每一个节点都维护一个区间最小值，表示这个区间至少有多少个关键点覆盖，如果关键点个数大于 $1$ 或者已经被选过的关键点染过就不搜了，否则就拿出 set 里的关键点，往下搜，搜到 $l=r$ 时就将该关键点的 $cnt$ 加一，放进堆里就好了。
关于找最小字典序的序列也很简单，每次选个数最多编号最小的关键点就好了，然后跟上面一样跑。
期望得分 70pts。
算法 5
现在来玩 $d_i=2$ 的情况，发现也可以拆分成几个编号连续的区间。该关键点的下面两层，它的父亲的父亲，它的父亲的父亲下面那一层。然后跟上面那样一样做就行。
时间复杂度 $\mathcal{O}(m\log^2 n\sim m\log^3n )$。
1 |
|
The End「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」