十月杂题选做
十月杂题选做
yzxoi
2022-10-19 (Updated: 2022-10-19)
CF1254
P3147 [USACO16OPEN]262144 P
的右端点。
88502520
ARC097D Monochrome Cat
需要遍历的点一定是在最小的包含白点的连通块内。
剩余的树上每个点都必须经过。因此除了起点与终点之间路径上的边会被经过恰好一次以外，其余所有边都会被经过恰好两次。
不妨先设所有边都经过了两次，若无修改每个点颜色即为初始颜色异或度数奇偶性，只需在其为白时进行一次修改操作。
然后考虑起点与终点之间的路径，它的影响是让路径上的点（包含起点但不包含终点）都被少经过一次。
容易发现，原本为白操作次数减 2 ，原本为黑色操作次数不变。
于是类似找树的直径即可。
P4183 [USACO18JAN]Cow at Large P
设 g_i 为 i 到最近叶子的距离。
如果 u 为根，d_i\ge g_i 则 i 子树内仅需贡献 1 即可拦截 u ，注意到如果 i 的父节点 f_i 能拦截 u 则没必要动用 i ，所以我们令 d_i\ge g_i \land d_{f_i}< g_{f_i}
考虑点分治，根据分治重心我们可以划分成一个点及若干子树。
考虑每个子树对子树外的贡献，以及分治重心对所有子树的贡献。
注意一下一开始钦定的限制条件，不然可能重复计算。
P6931 [ICPC2017 WF]Mission Improbable
考虑俯视图限制显然是有数的则至少要有 1 ；主视图、侧视图限制即为每行每列的最大值仍然保留。
贪心地保留每行每列的一个最大值，其余的全削减至 1 。
注意到可以有一个数同时占行列的最大值的情况。
于是跑一次二分图匹配即可。
AGC024B Backfront
顺序显然可以随意移，最后剩下必须连续，求最长上升子序列即可。
CF1481E Sorting Books
P5779 [CTSC2001]聪明的学生
几个结论：
- 如果两个相等，则另一个一定为其之和。
- 另两个人中较大者未能在相应的回合猜出，则其可能猜中。
- 最大的人一定先猜到。
设 f_{i,a,b,c} 表示 a,b,c 数，在第 i 次是否能猜中。转移根据结论 1,2,3 即可。
CF536D Tavas in Kansas
首先从 s,t 分别跑一次最短路，容易发现答案仅与其相对大小有关，因此先离散化。
容易将其抽象成一个表格，其中第 i 号点位于 (d_{s,i},d_{t,i}) ，权值为 p_i ，两人分别从 上/左 取若干 行/列。
注意到 n\leq 2\times 10^3 ，考虑 dp，设 f_{k,i,j} 表示在各自最优策略下当前小 X/小 Y 先手，剩余的点为 (i,j) 及其右下角范围，小 X 的权值与小 Y 的权值的差。
发现其实没必要枚举每个人取到哪一行/列进行转移，只需要一行行一列列转移时注意是否要交给对方即可。
ARC102D Revenge of BBuBBBlesort!
被操作的点仅可能是 a_i=i 的点。
显然相邻且均满足 a_i=i 的两个位置无法操作，所以原序列可分为若干交替是否满足 a_i=i 的子串。
每个子任务单独考虑，必须满足 a_i 在可交换的区间内且需要交换的数最长下降子序列长度不能超过 2 。
P3685 [CERC2016]不可见的整数 Invisible Integers
考虑设 f_{S,x,xi,y,yi} 表示已满足的限制的状态 S ，从右往左正在满足的是 x ，满足到 xi 位，从左往右正在满足的是 y ，满足到 yi 位，最少的元素个数。
不妨从左向右考虑，对于所有向右得到的序列 i ，若能接在 y 后面，则满足 y 的剩余部分可以被 i 覆盖，于是之后只需要考虑 i 即可。
对于 x ，若已被填满，对于所有向左得到的序列 i ，若可以接上，则满足 i 的接入部分可以被 x 覆盖，于是之后考虑 i 的剩余部分即可。
P5957 [POI2017]Flappy Bird
CF1340C Nastya and Unexpected Guest
设 f_{i,j} 表示第 i 秒到达第 j 个绝对安全至少经过多少个周期。
转移的边仅有相邻两个，于是直接 01-BFS。
O(mg)
CF778D Parquet Re-laying
操作可逆，考虑将起始状态与结束状态转移到一个中间的状态。
不妨设长为偶数，设构造中间状态所有地砖都是横的。
能旋转就旋转，发现一定可以转到。
P5956 [POI2017]Podzielno
容易发现 X 是 B-1 的倍数的充要条件是 X 的各位之和是 B-1 的倍数。
注意到 a_i\ge 1 ，所以只需要删除一个数即可，剩余的数从大到小排列。
注意不用删数的情况。
P5847 [IOI2005]mea
容易将 S_{n+1} 用 S_n 表示。
根据 S_i\leq S_{i+1} ，可列出不等式，即可容易解得 S_i 取值范围。
最终 S_1 最后范围即为答案。
注意无解输出 0 。
CF429C Guess the Tree
爆搜。
首先判掉叶子节点过少的情况，爆搜的话按照子节点数多的从大往小先摆着，之后的点考虑连到之前的点中。
可以证明这个是能过的。
腾讯云开发者
