十月杂题选做
十月杂题选做
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
预处理出每种颜色的最左最右位置，即求最多保留多少不移动。
设 f_i 表示 [i,n] 中最多有多少无需移动，s_{i,j} 表示 [j,n] 中，颜色为 i 的数量。
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 的权值的差。
发现其实没必要枚举每个人取到哪一行/列进行转移，只需要一行行一列列转移时注意是否要交给对方即可。
O(N^2) 。
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
爆搜。
首先判掉叶子节点过少的情况，爆搜的话按照子节点数多的从大往小先摆着，之后的点考虑连到之前的点中。
可以证明这个是能过的。
P1330 封锁阳光大学
每个连通块单独考虑，分别黑白染色，取黑白中数量较小即可。
CF436E Cardboard Box
对于每个关卡，分成两类：
- 2a_i\leq b_i ：将选两个点拆成 a_i 与 b_i-a_i ，有 a_i < b_i - a_i
- 2a_i > b_i$``$b_i 排序，此时一定先选两个更优。
一类点直接拆散按从小到大排序选即可。
考虑枚举选一类点 i 个，则剩余 m-i 个点填二类点分 m-i 的奇偶性判断：
- m-i 为偶数：恰好选前 (m-i)/2 个两个即可。
- m-i 为奇数：选 (m-i-1)/2 个两个，再加上一个一个；或选 (m-i+1)/2 个两个，再将其中一个两个转为一个。
显然奇数情况记前/后缀最小/大值即可。
AcWing 359. 创世纪
在一内向基环树森林上选若干点，使每个点必有一个儿子没选，求权值和最大。
表示当前点选/不选的最大值。
考虑非树边 x\rightarrow y ，有两种情况：
- 不选 y ，则 x 无限制。
- 选 y ，对 x 无影响，可直接将 x\rightarrow y 断开。
两者取最大即可。
P2664 树上游戏
对于每个点，每种颜色，其单独答案贡献可转化为 n-siz_{x,c} 。
其中 siz_{x,c} 代表从点 x 出发，不经过颜色 c 的点，所构成的连通块大小。
考虑对于所有 siz ，均挂在深度最小的节点上，之后树上差分统计即可。
若碰到与当前颜色相同的点，之后该子树将失效，贡献更新。
注意根节点父亲颜色应设为“全彩”，特殊考虑即可。
CF916E Jamie and Tree
首先求 u,v 在以 r 为根意义下的 lca 即为 lca(u,v)、lca(u,r)、lca(v,r) 中深度最大的点，证明不难通过讨论 u,v 是否在 r 子树内求得。
其次求点 x 在以 r 为根意义下的子树。
- x 即为 r ：则即为整棵树。
- x 是 r 的子树 或 x 不是 r 的祖先：则即为 x 的子树。
- 其他情况：即为 x 的子节点中子树包含 r 的子树。
CF432E Square Tiling
按顺序从上到下从左到右贪心，首先对该格子的限制一定是上下左右四个格子，显然该格子一定染最小的与其不同的颜色。
接下来考虑是否向右下拓展：注意到向外拓展一层的几个条件：
- 上一行对应列点必须与其不同色。
- 不能已经被染过不同颜色。
- 上一行对应列点不能与其相差超过 1 。
- 上一行对应列点不能与其均不为
A。
CF1343F Restore the Permutation by Sorted Segments
暴力枚举第一个数，再将所有限制中包含该数的删掉该数，显然从删过的限制之中会产生一个只剩一个元素的限制，于是其为第二个数。
再将所有限制中包含第二个数的删掉，循环该步骤即可。
最后判一下是否合法。
CF553D Nudist Beach
二分答案，check 先把所有都标记为能选，再将所有不合法的点依次剔除。
可以证明这一定最优。
The 2022 ICPC Asia Regionals Online Contest (I)
经过一定分析可以发现合法数很少，写个爆搜+剪枝把所有答案先跑出来，查询二分即可。
O(?X+Q\log X)
Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest. Problem C. StalinSort Algorithm
很容易设出一个简单的 DP，设 f_{i} 表示当前子序列结尾为 a_i ，且保证最终一定含 a_i ，长度最大值。
设 g_{i,j} = \min { j> i \land a_j > a_i}
有转移：
其中，
其中 a_j>a_i$``$a_i 从小到大枚举即可。
线段树辅助转移。
特别注意，初始合法的点仅为 [1,g_1] 。
O(n\log n)
2021“MINIEYE杯”中国大学生算法设计超级联赛（6）. Problem 1007. Power Station of Art
每个连通块独立，分别考虑。
根据提示，容易想到按图是否为二分图分类。
若该连通块为二分图，将该图黑白染色，两图的左黑+右白、右黑+左白数量相等，容易证明这是充要的。
若该连通块不为二分图，即其必含奇环，注意到变换之和为偶数，故黑、白点奇偶性相同，且权值集合相同，容易证明这是充要的。
京都大学プログラミングコンテスト 2021. Problem F. One Yen Coin
只需要考虑 1\times x+ 5\times y 即可。
贪心地想，容易发现每次只会选一个物品。
综合上述，一个代价为 a_i 的物品价值为 5\lceil \frac {a_i}5\rceil-a_i ，其新代价为 \lceil \frac {a_i} 5\rceil ，而总新容量为 \lfloor \frac m5\rfloor ，初始答案为 m\bmod 5 。
注意到价值很小，可以将价值放到状态里，设 f_{i,j} 表示考虑所有代价 \leq i 的物品，获得价值为 j ，所需要的最小代价。
显然其满足决策单调性，将所有代价为 i 的物品抽出来排序求前缀和，转移即可。
O(n\log n)
ABC163F path pass i
至少一个点颜色为 k ，显然可以转化为求不含颜色 k 的路径。
对于一个大小为 s 的连通块，若其均不含颜色 k ，贡献即为 \frac {s(s+1)}2 。
对于每个点颜色 c_x ，只需求其所有儿子的子树中不包含 c_x 的连通块大小之和即可。
注意考虑与根节点颜色不同的点在根部分的答案。
CF1754E Wish I Knew How to Sort
的期望操作数。
177581574
CF1754F The Beach
显然将其转化为空位的移动，注意到最后两个相邻的空位一定会由不同的点转移过来。所以直接将所有空位丢入起点，一起跑一遍最短路即可。
注意建图是单向边。
CF1732D2 Balance (Hard version)
不妨先看 Easy Version，没有删除操作。
容易发现直接对每个询问记忆化答案，暴力往上跳复杂度是对的。
加入删除操作，考虑对每个询问跳过的点记下来，删除的话就对所有经过该点的询问打个标记。之后若询问到有标记的点，则输出标记中的最小值即可，插入的时候把对应标记删除。
这个感性理解一下，复杂度大概也是对的，因为每个询问跳的点必定是已经有过的点，所以点数是 O(N) 的，总复杂度大概是两个 \log 级别？177713494
CF1732E Location
分块，对于整块修改只需暴力枚举 \gcd 更新答案即可，显然这同约数一样可提前预处理。
O(\frac nk+ K\gcd)
CF223E Planar Graph
取一个极远的点为根，任意建一棵树。
一次询问的答案即为出环的边数-入环的边数，分别对每个点相邻两条边算贡献，注意到环内的点一定在其极角排序后一段连续的区间内。因此直接做前缀和查询即可。
注意贡献有正有负且环上点必须按照同种顺序排序，叉积判断即可。
CF1188C Array Beauty
先对 a 排序，考虑转化为计算 \min \ge c 的方案数：
的方案数，转移：
可以前缀和优化。
而 \min \leq \frac V {k-1} ，所以总复杂度 O(kn) 。
P4804 [CCC2016] 生命中的圆
段的状态，转移：
注意到，
可数学归纳法简单证明。
O(N\log T)
CF1455G Forbidden Value
设 f_i 表示 x=i 时的最小花费。对于题目的嵌套，显然可以看作合并操作。
对于 set，f_y = \min f_i, f_i +=v \ (i\not =y) 。
动态开点线段树+线段树合并即可。