Loading...
NOI2021 加油！
A. 序列分割容易发现分割顺序并不影响答案。因为你确定下来最终状态后，设每段的和分别为 $x_1,x_2,\ldots x_m$，发现你这个分割实际上是统计了 $\prod_{i < j} x_ix_j$。（每次都是统计跨过某个点的所有对，然后递归）所以我们可以设计一个 dp：$f_{i,j}$ 表示分了 $i$ 段，第 $i$ 次分的位置是 $j$ 的答案。记前缀和为 $s_i$，转...
因为某些原因晚了半小时打，然后就疯狂挂题，从前二（或许？）挂到了倒一A可以考虑哈希。这里可以给每个值随机一个哈希值，合并操作定义为异或。考试的时候写的N模好像 T 飞了。。事实上这个数据一模数就能过#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define s...
A前面的 # 都贪心只填一个 )，用最后一个 # 调整即可。还是最后扫一遍判断比较靠谱。。尝试 $O(1)$ 特判挂了。。B设 $f_i$ 表示最后一个区间右端点选在 $i$ 的概率，我们对于每个点 $i$，处理出 $l_i$ 表示最大的数满足 $[l_i,i]$ 包含串 $T$（可以用哈希/kmp轻松处理）。然后转移的话先枚举这一段在哪里结束，再枚举下一段在哪里开始，转移是但是值域太大了怎...
A发现限制形如选了一条边之后，不能选和它端点相同的边。我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 $1$ 就一定有环，所以这种情况下更有环。我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 $2$ 种染色方式...
A类似后缀数组算本质不同串的思路，考虑 $S$ 的第 $i$ 个前缀和第 $i+1$ 个前缀有多少个都会被计算，发现被算重的后缀等价于 $T$ 中 $S[i+1]$ 的出现次数。举个例子：abc abc 第 1 个前缀和第二个前缀都会算到 abc,原因是第一个前缀是 "a"+"bc"，第二个是 "ab"+"c"...