tc

oi

SRM 592

循环卷积，DFT
由于序列是对称的，所以只需要搜索一半的正负性即可。

SRM 600

几何形式与代数形式的转化
通过几何的角度，得到答案即是求每次加入后的交点数。从代数角度解决（即求解方程之后的 $x$ 解数）。

SRM 602

仔细观察，归纳性质
可以发现充要条件：存在环，或者半环（本质上是其中一面进行了90度旋转）。
进而可以归纳不能存在形如

/\
\?

的模式。容斥即可?
直接状压DP复杂度有点爆炸，注意到只需要记录上边极长的\与下边极长的/就能多项式DP了。对于最终的公式，可能需要猜测最终的形式再配系数。

SRM 603

min(a,b)的贡献拆分，随机
由于是随机的，所以重复出现很多次的数很少。
$\min(a,b)$变成$i\le a 并且 i\le b$的对数，就容易计数了。

SRM 607

二分答案
发现可以简化为4种贡献，A,B或C(改变方向)，DP处理出方案数。
注意到答案关于A,B,C指数级增长，所以有用的A,B,C范围不大。最后二分答案即可。
注意inf的处理。

SRM 608

相对关系的转化，把机器人移动看作上下边界移动
然后发现对于上下边界差相同的，可以$O(1)$转移得到

SRM 609

二分图匹配 DP
注意是连续的一段染色（读题要仔细），可以转化为 $dp[i][j][k]$ 表示对于子树 $i$，$j/k$ 处开始能否满足条件。可以通过二分图匹配转移（由于长度相同，只是改变了顺序）。
注意到对于每个点，每个分界点，最多只会对状态产生1的贡献。所以总状态数是$O(np)$的

SRM 611

分类讨论DP
考虑3种情况。

• 不存在某个方向覆盖全部，直接枚举最长的递归下去就行。
• 存在一个方向情况下，枚举另外两边。中间就是取最大和次大的。
• 否则可以枚举4个量来组合：
  

容易发现复杂度是 $O(n^4)$ 的

SRM 613

DP
如果直接从左往右DP，发现还需要记录左边是否选择的状态。
由于所有前缀的左端点均相同，所以考虑转移的时候只需要决定是否选择，在一个前缀结束的时候进行决策即可。

SRM 618

贪心
首先注意到字典序递增，考虑按位得到最后的结果。每次选择第一个 $y1[j] \in (y2[i],y1[i])$ 最小的 $j$，不会减少交换能力。

SRM 627

最小割
比较有趣的最小割。考虑到每个点至多有两个塔攻击到，于是联想去对应到源与汇，构造割就能使得塔两两不交。割的权值就是一个塔可以攻击到的最大权值减去这个前缀的最大权值，最小割即可。

SRM 628

DP
由于所有关一定都要通，所以不妨先一直尝试直到通关。此时可能还未达到目标，显然就是要按照 $y$ 从大到小去争取两颗星。容易发现，每个关额外的贡献仅仅取决于 $y$ 更小的关的情况，于是按照 $y$ 排序后DP即可。

SRM 635

脑补一下 $0,1$ 很多的情况，发现肯定有很多形如 $0,1,0,1,0,1,0,1,\cdots$ 的连续段。而且这些连续段 $0,1$ 的数量差至多为 $1$。所以我们直接来安排 $2,3$，记录一下划分的段数及差，可以得到一个 $O(n^4)$ 的DP。
事实上，我们可直接算将 $0,1$ 划分为 $k$ 段的方案数，枚举一下相同的段数，可以得到另外两种方式的个数。可以优化到 $O(n^2+50000)$。（从这个角度理解，相当于题目限制了段数的上界）

SRM 636

不是很容易想到，这题一个关键点是：两个集合分别放在序列的左右两边，之间产生的贡献与内部顺序无关。
于是这样就能在复杂度里除掉 $(n/2)!$ 了

SRM 637

网格图上不存在四连通路径，一定存在一条八连通路径阻隔了源与汇。
由阻断源汇，很容易联想到割。可以每个点设流量上限后跑网络流。
但是无法保证一个源能到指定的汇。
发现两条八连通路径必然存在一个 2*2 的矩形内相交，枚举之后跑拆点网络流即可。

SRM 645

容斥
考虑暴力状压，复杂度是 $O(c \cdot 5^n)$ 的（其中 $c$ 应该可以从 $k$ 优化到 $n$），枚举可重集的子集过于浪费时间。
考虑外层暴力容斥，发现内层只需要考虑有交的集合并且每个有交集合至多作用一次，这样阶段数就能减少到 $n$ 了。复杂度 $O(n\cdot 4^n)$。

SRM 647

经典最小割模型
考虑最小割，对于边 $(u,v,w)$ 对应连上 $(u,v,w),(v,u,\inf)$，后者保证了一条路径上至多割一次。注意，对于无法到达目标的边，不能连边。
ISAP被卡了...

SRM 648

点双计数，容斥
关键在于 $n$ 个点的点双计数。考虑枚举其中一个桥，发现两边是个子问题，可以直接算。一张含有 $k$ 个桥的图会计算 $k$ 次，最后除以 $k$ 即可。顺便可以得到没有桥的图的数量。

SRM 651

DFT优化卷积，前缀积及其逆元
可以注意到一个性质：$W = \sum w_{ij} \le 2500$，这样，我们考虑每行暴力背包预处理复杂度是有保证的（大概是 $O(nmW)$）。可以通过启发式合并FFT做到 $O(nmW+QW\log^2 W)$（大概是4次方带两个log）。
这样还不够，考虑从卷积的角度进行优化。一个想法就是处理每个位置对应的点值（至多 $W$ 个），预处理前缀积就能 $O(W)$ 回答询问了。由于这个多项式很特殊，只有两个非零值，可以 $O(W)$ 暴力预处理。复杂度是 $O(nmW+QW)$ 的。

SRM 653

高斯消元的小trick
考虑我们可以列出 $9$ 个变量，和一些限制。会得到两个自由元，暴力枚举自由元再带入很可能会超时。
一个小trick是我们先将矩阵变成上三角的，这样求解的复杂度就是平方了。
复杂度 $O(9^3+9^2\cdot n)$。

SRM 654

性质观察，区间DP
考虑一颗树的情况，只需要DP然后子树组合数合并即可。假定第一个删除链上的点是 $p$，那么 $p$ 子树的答案可以最后乘，但是发现两边不好合并。
但是每次扩展一次是可行的。于是考虑直接区间DP，每次将新加入节点子树中的点插入序列即可。

SRM 655

凸包DP，优化
按照pair排序，每次取一个后缀。强制第一个点为起点做凸包DP，是否把蓝色包含在内可以用射线法。这样常数和复杂度都比较大。

SRM 656

分类讨论，状态数计算
发现与实际高度无关，用A,B代表（总是假设第一个为A）。
段数>=6时，只有1种或0种操作；段数<=3时，状态数是 $O(n^3)$，记忆化即可；段数=4时，至多6种操作；段数=5时，至多3种操作。
每次段数至少减少1，爆搜即可。

SRM 658

匈牙利算法
发现题目中描述的本质上是更换匹配失败。所以在求出最大匹配之后选择一个未匹配的点尝试增广，遍历到的点就满足条件；否则完美匹配也是满足的。

SRM 662

构造半群，映射，$\rho$
一个性质是：题目已知的乘法是对于左边固定的一行给出的。一般地，我们只需要构造其余的映射 $f_a: x \rightarrow ax$ 即可。下面记 $f = f_0$
将映射 $f$ 建图，是一个基环内向树森林。 $0$ 能到达的点是个 $\rho$，记一开始滑行距离为 $d$，之后进入长为 $l$ 的环。这样，对于 $\rho$ 里面的映射都能唯一确定了。
注意到 $0^{d+1} = 0^{d+l+1}$，即 $f^{d+1}=f^{d+l+1}$！也即长度大于 $l+d$ 后每 $d$ 个 $f$ 可以相消。
考虑其他弱连通块，环长是 $l$ 的倍数 以及 外链长至多为 $d+1$ 都是必要的。存在构造方法使得这也是充分的。
对于 $\rho$ 外的点，只需要令 $f_i$ 恒映射到 $i$ 即可。归纳证明任何表达式都能变成 $f^af_b$ 的形式。

SRM 663

手动高消
假设第0个元素为A，把 $[1,n)$ 中等于A的称为good，显然终止条件为所有数都变为good。
然后一个显然的结论是：对于恰好有 $x$ 个good点的情况是等概率分布的。然后手动高消即可。

SRM 665

构造 直接构造一条链，接一些额外的点。可以构造 $625$ 以内的所有答案，似乎大于就一定构造不出来了。