CF杂题选做
wuhao2005
·
·
个人记录
前言：
主要是配合题单来的，大部分题没有必要隆重的新写一篇博客，只需要简单记一笔即可
题目：
CF5E Bindian Signalizing
数组复制两倍，正反各跑一次单调栈，注意到除特殊情况外能看到彼此信号的看守人中间不会隔着一座最高峰，所以对于一对符合条件的不涉及最高海拔的山，是不会被重复考虑到的
CF8E Beads
分前后两半考虑即可，大力分讨
CF10E Greedy Change
设找零钱的最小表示为 M(x) ，贪心表示为 G(x) ，最小不满足 M(x)=G(x) 的值为 w
如题中 input2，M(6)=\{0,2,0\}, G(6)=\{1,0,2\}
设 M(w) 第一个非 0 元素在位置 i ，最后一个非 0 元素在位置 j
有这么一个结论：
M(w)$ 和 $G(a[i-1]-1)$ 从 $1$ 到 $j-1$ 位都相等， $M[j]=G[j]+1
于是可以通过枚举 i,j 求出 w 的值
CF11D A Simple Task
状压 dp ， f_{i,j} 表示二进制状态为 i 下，以 i 中下标最小的点 p 为起点（目的是为了去重）的终点为 j 的路径方案数
显然，如果 j 有一条路径通回 p ，那么就可以更新答案了，即 ans++
CF1153D Serval and Rooted Tree
经典套路题，设最终答案为 x ，那么令我们假设所有大于等于 x 的数字都为 1 ，小于 x 的数字都为 0 ，可以树形 dp 出为了使根节点为 1 的最小填 1 数 x（即在叶子节点使用 1 的个数）
树形 $dp$ 过程是若非叶子节点为 $\max$ ，则选择子节点中 $f$ 值最小的，若为非叶子节点标记为 $\min$ ，则将子节点中所有 $f$ 值相加
那么答案就是 $k-x+1
CF1265E Beautiful Mirrors
根据题目列期望 dp 方程即可，像解方程那样移项，得到 dp_{i+1} 关于 dp_i 的表达式
dp[i+1]=1+dp[i]*100/pi
CF938G Shortest Path Queries
加边删边什么的，直接线段树分治即可
和最小路径异或和套路一样，因为保证图联通，所以任意点可达，并且可以选择任意环到达，异或上整个环的权值（因为过来和回去的路径上的权值会被异或两遍，等于没走）
而且不需要找到所有环，因为某些相交的简单环异或起来就可以表示一些复合环
所以只要找到一条 x 到 y 的路径，得到其异或和，然后不断选择一些环进行异或，得到最小异或和（相当于在原图上令其改道）
最小异或和丢进线性基里就完事，因为线性基也就 32 位左右，所以不用可删改类型的，只要递归两个子问题时复制一份就可以了
找到某条路径异或和可以用 LCT ，也可以用按秩合并并查集（因为我们回溯时要根据栈来撤销）
因为异或优美的性质，所以我们可以用 xor[x] 表示到它并查集上父亲所需要的异或路径长度，用 sum[x] 表示它到并查集根的异或路径长度（一路爬上去即可）
那么如果新加上一条边 (u,v,w) 将两个并查集的根合并的话（假设 fu 连向 fv ），那么 fa[fu]=fv,xor[fu]=sum[u]\oplus sum[v]\oplus w
原因是异或路径走重复边没关系，相当于走过去走回来抵消了，上面那句话是从 fu\rightarrow u\rightarrow v\rightarrow fv
接下来对于同一并查集的两点异或距离就是 sum[u]\oplus sum[v] ，就是 u\rightarrow root \rightarrow v
CF156C
注意到只要字符和一样就是合法的序列，稍微处理下即可
CF780F
注意到有关 2^s ，所以 dp 状态与倍增有关
令 f[t][i][j] 表示有从 i 到 j 长度为 2^t 的前半部分串，g[t][i][j] 表示有从 i 到 j 的后半部分串
然后用 pre[k][0][i] 表示从 i 开始以前半部分开头不超过 2^k 的路径的最大长度， pre[k][1][i] 表示从 i 开始以后半部分开头不超过 2^k 的路径的最大长度
先把 f 和 g 两个数组搞出来，然后枚举 i,j 查询 i 到 j 是否有一条长度为 2^k 的路径，或者是长度为 2^{k-1} 的路径拼接上从 j 开始的最长后半部分前缀，bitset 位运算优化求 f 和 g 的过程就可以了（就是不用每个二进制位都写个 n^3 的 floyed 了）
CF982E
化曲为直，每次碰壁转弯都看成将矩阵对折，一直走一条直线，直到遇到 (a\ast n,b\ast m)
exgcd 求解同余方程即可，对于 a,b 奇偶和一开始行走方向大力分讨即可
CF982D
有个显然的套路：每个联通块 siz 相等 等价于联通块 siz 最大值，最小值相等；或者 siz 最大（小）值乘上联通块个数等于总个数
这里直接上第二种思路即可
CF771C
换根 dp 即可
CF1151E
点减边即可
CF1030E
等价条件为区间二进制位个数之和为偶数，且二进制位最多的个数小于等于区间内剩余二进制位个数和
原因是极端情况是等于区间内剩余二进制位个数和，那么只要一一不重的对应就可以了，因为奇偶性对应，每次相应消掉两个就行了
由于二进制位最多的个数为 64 ，所以很容易看出不满足条件的区间很少，直接枚举即可原因是区间内元素个数超过 64 个，只要满足奇偶性就是满足的区间，因为每个至少提供一个二进制位
CF900D
题意：输入 x,y ，求有多少个数列满足其 gcd 为 x，和为 y
首先忽略 gcd 的限制，令 f(x) 表示和为 x 的方案数，考虑用隔板法， g(x)=\sum_{i=0}^{x-1} \binom{x-1}{i} = 2^{x-1}
同时， g(x)=\sum_{d|x}f(d) ，其中 f(d) 表示和为 d , gcd 为 1 的方案数
所以可以考虑递归求解，
f(x)=g(x)-\sum_{d|x,d>1}f(d)
由于一个数的因子也一定是这个数的因子，所以是根号级别的
另外还有莫比乌斯反演的做法，看 Siyuan 博客
CF1303F
由于 c_i 递增，我们可以不妨单独考虑每种颜色的贡献，用并查集正反各扫一遍就可以了
CF780G
考虑用线段树维护每个点有多少个球，每个叶子节点用一个 map 表示有多少个从高度为 x 掉下来的球
因为每次都会合并一些球，只要证明插入和查询的此数是 O(n) 的，这也很显然，因为每个板子最多新插入两个球（把相同的合并起来后），插入是 O(n) 的，删除也是 O(n) 的，相当于用线段树这个数据结构及时避免不必要的访问查询
CF388D
求本质不同的线性基个数
看 cly_none博客 吧