20Jun CF&AT 练题汇总
[CF1076E]-Vasya and a Tree
· 巧妙的dfs
没有数据结构可以直接维护，数据范围是3e5所以考虑dfs（？） 到达节点 x 时将 x 的操作执行掉（方法：根据深度维护一个树状数组，回溯时统计答案并消除影响）
[CF731F]-Video Cards
· 利用“倍数”
· 观察数据范围：ai <= 2e5!!!
y 要减到 x 的 k 倍时，y 在 xk ～ x(k + 1) - 1 的区间内。所以只要记录每个区间有几个数就可以算了，前缀和正解！！
再抽象化。求的是 sum{ 下取整(ai / x) * x }，那么枚举 下取整(ai / x) 就好了。
所以是.. nlogn?
P.S. 注意重复的 a[i] 别重复枚举qwq，200000个 1 就炸飞了啊嗷？
[CF1163C1]-Power Transmission(Easy Edition)
恶·心的计算题
[CF981D]-Bookshelves
·位运算+dp
从高位到低位chk：能否在已chk的高位取 1/0 的情况下，该位取 1。
[CF599D]-Spongebob and Squares
推式子题，算出 m 关于 k 和 n 的关系式。枚举 n，算出 m。根据式子可得，n 大约是 1e6 级别的，所以不会 T！
[CF148E]-Porcelain
·分组背包
先处理第 i 组容量为 j 时的最大价值和 val[i, j], 再注意到每组只能取一个 val[]，想到分组背包。
【惊！1e8 竟然可以 AC？
[CF1311F]-Moving Points
·树状数组+离散化
分类讨论，可得出结论：xi < xj 且 vi < vj，i 和 j 就不能相遇了（代价为 xj - xi）。
于是用树状数组计算 xj - xi 之和。
[CF1043E]-Train Hard, Win Easy
·妙题！
min(xi + yj, xj + yi) 这样子涉及到不同组的就很不爽，没法处理
xi + yj - (xj + yi) = (xi - xj) - (yi - yj)
讨论 (xi - xj) - (yi - yj) 的正负就好了
[CF1360H]-Binary Median
·二分
m 才 60。。要注意编号计算，很恶心
[CF1157D]-N Problems During K Days
·构造
只要想到“在 1 2 .. k 的基础上修改”就好了，注意“2倍关系”的限制
[CF1015E2]-Stars Drawing (Hard Edition)
·套路题
并没有数量限制啊，凡是上下左右都有’‘的位置都可以画十字啊，size根据上下左右’‘的长度来定，别忘了check是否完全覆盖，，，
[CF792D]-Paths in a Complete Binary Tree
·找规律
把每个数分解成 2 的幂次乘奇数的形式
[CF1012C]-Hills
·DP
设置的状态包括位置（第 i 个山坡）、已修建房屋数量（j）、当前位置是否受上一座房屋影响（k）
[CF19B]-Checkout Assistant
·背包
选了 k 个, 时间为 T, T = t1 + t2 + … + tk,
T >= n - k, T + k >= n
所以 (t1 + 1) + (t2 + 2) + … + (tk + k) >= n.
由此想到将 ti ++。
问题转化为：选择总体积 >= n 的物品使得总费用最小，01背包
[CF9D]-How many trees?
·DP
设计状态应包含节点数(i), 高度(j)
好写好调OvO
[CF730J]-Bottles
·背包
第一问比较好想，贪心，优先用 b[i] 大的杯子，算出答案为 k；
第二问是在第一问基础上的，设 tot = sigma(a[i]), 选中的杯子 a[i] 之和为 A，b[i] 之和为 B
那么必须满足 tot - A <= B - A, 即 tot <= B
现在有三条：
- 选 k 个杯子；
- B >= tot；
- A 最大。
背包！写的时候数组开错了，越界，各种灵异事件 ಥ_ಥ 时间复杂度其实是 1e8 的，但 93ms 就过了，emm？
[CF946G]-Almost Increasing Array
·树状数组维护dp
经典题，撇开“去掉一个”的限制，严格增加就是 j > i, a[j] > a[i], a[j] - a[i] >= j - i 即 a[j] - j >= a[i] - i; 那么维护一个 LIS 就好了
枚举去掉的位置，该位置后面的 要从 a[i] - i 变成 a[i] - i + 1（哎呀就这意思你懂的吧
倒腾倒腾就出来了
[CF478D]-Red-Green Towers
·线性DP
最大高度要先算qwq，f[i, j] 表示从上往下数第 i 层，用了 j 个红色的方案数，然后滚动数组优化空间
[CF1132F]-Clear the String
·区间DP
（完了我怎么简单题也不会
考虑当前字符，两种删除方法：1. 直接单个删除 2. 和后面同色的一起删除
所以就是 f[l, r] = min(f[l + 1, r] + 1, f[l + 1, i - 1] + fi, r)
[CF1344A]-Hilbert’s Hotel
·喵题！
观察样例第三组，找规律：
区间 [0, 1, 2, 3] 变为 [5, 6, 7, 4]
区间 [4, 5, 6, 7] 变为 [9, 10, 11, 8]
…
区间 [0 + nk, 1 + nk, 2 + nk, 3 + nk] 变为 [5 + nk, 6 + nk, 7 + nk, 4 + nk]
如果集合 [5 + nk, 6 + nk, 7 + nk, 4 + nk] 含有相同的数字那就是 NO 啦
若 k 相同时，这四个数有 % n 同余的，那就是 NO
为什么呢？a + nk = b + nk (% n) => a + nk’ = b
[CF140A]-New Year Table
几何题，最近也看了高中数学必修四的三角函数，正好用到！吸吸。注意，c++函数都是弧度制，pi = acos(-1)。
[CF141C]-Queue
考虑把 1 ~ n 作为身高分给 n 个人。每个人的排名只受前面人的影响，所以我们倒着来分。
[CF141D]-Take-off Ramps
一眼最短路。注意：起点 x - p, 终点 x + d, 费用 p + t
容易想到起点向终点连边，但是题目还可以不选跳板，甚至逆行。不用从一个位置向其他每个位置连边，那样时空都是 n^2 的！考虑到每次徒步走都是有目标的，没有无缘无故的逆行，只要在出发点和目标之间连边就好了。
[CF145B]-Lucky Number 2
·找规律
最基本的性质：4开头7结尾：47比74多1； 7开头4结尾：74比47多1； 4开头4结尾 / 7开头7结尾：相同
因此 |num(47) - num(74)| > 1 的情况都是无解。再根据 num(47) 和 num(74) 的大小关系进行分讨（呕
[CF242E]-XOR on Segment
·数据结构康复训练（
维护区间异或和。因为区间和无法直接异或，我们想到对二进制每一位分别开线段树！异或变成 0/1 个数的转换了。
[CF380C]-Sereja and Brackets
刚开始想到是 r 前的对数 - l 前的对数 - 过交界处的对数，但是最后一项不会维护T T
区间括号配对数直接线段树维护就好了嘛，记录每个区间多余的 ‘(‘’)’ 个数和已配对的个数
[CF1244C]-The Football Season
x = (p - yd) / w.
因此要满足两个限制：1. x为整数 2. x + y <= n
第一个用 exgcd 应该也能做。。但 w 很小呀，枚举 y = 0 ~ w - 1 也能过
[CF1359D]
枚举最大值，统计每个连续自序列的最大值
[CF181D]-Word Cut
可以发现就是一个字符串不断循环。n^2 找出 s 与 t 相配的所有位置，dp就可以了
[CF176C]-Playing with Superglue
需要手玩的一道题。容易发现 max(abs(x1 - x2), abs(y1 - y2)) > 4 的时候是后手赢，= 4 且 min = 3 或 4 的时候是后手赢，其余时间都是先手，至于为什么。。这跟这个游戏的规则有关系。
[CF180E]
套路——用vector维护同一颜色的位置，查找就很方便
[CF148D]
期望概率什么的 Qaq dp算是最善良的了。。
f[i, j] 表示袋子里还有 i 个白的、j 个黑的，公主赢的概率，转移方程不难，因为在一轮转移中龙的情况一并考虑掉了。
还有一种方法，因为有精度限制，枚举几千轮模拟操作也是可以过的，，
[CF453B]
b不会 >= 59, 因为选 1 必然不会更差！
58 以内有 16 个质数，每个只能用一次。想到什么了？状压dp. （3e8 2000ms丝毫不慌
[CF453C]
思路不难想，来回震荡着走。选一个走奇数次的点作为根结点，dfs，每次走出子树时保证子树的点都满足要求了，子树的根结点就和它的父亲震荡，根结点和儿子震荡，可以证明这样一个节点最多走 4 次（
[CF182C]
正着倒着各做一遍，对于每个区间，维护正负性相反的数中绝对值 K 大的。说白了就是动态维护 K 大和，我们用小根堆维护（注意实现的时候用两个 multiset，细节多
[CF187B]
想法是 f[i, j, T] 表示 i 到 j 转换了 T 次，f[i, j, T] = min(f[i, k, T - 1] + f[k, j, 0])
floyd 大有学问啊（
[CF198E]
x和y的限制可以缩为距离初始点(x, y)的距离的限制
所以就是对于队列中每个(r, p) 找到还没被删除的点集中 dis <= r 且 m <= p 的点，删除并加入队列
可以线段树 + set 维护，每个 dis 处都有个 set，迷惑操作但是很好写（
这是题解做法，要是真比赛碰到我八成会杠二维数点，留坑待填