十月杂题选做
CF1254
P3147 [USACO16OPEN]262144 P
的右端点。
88502520
ARC097D Monochrome Cat
需要遍历的点一定是在最小的包含白点的连通块内。
剩余的树上每个点都必须经过。因此除了起点与终点之间路径上的边会被经过恰好一次以外，其余所有边都会被经过恰好两次。
不妨先设所有边都经过了两次，若无修改每个点颜色即为初始颜色异或度数奇偶性，只需在其为白时进行一次修改操作。
然后考虑起点与终点之间的路径，它的影响是让路径上的点（包含起点但不包含终点）都被少经过一次。
容易发现，原本为白操作次数减 2 ，原本为黑色操作次数不变。
于是类似找树的直径即可。
88504488
P4183 [USACO18JAN]Cow at Large P
设 g_i 为 i 到最近叶子的距离。
如果 u 为根，d_ige g_i 则 i 子树内仅需贡献 1 即可拦截 u ，注意到如果 i 的父节点 f_i 能拦截 u 则没必要动用 i ，所以我们令 d_ige g_i land d_{f_i}< g_{f_i}
考虑点分治，根据分治重心我们可以划分成一个点及若干子树。
考虑每个子树对子树外的贡献，以及分治重心对所有子树的贡献。
注意一下一开始钦定的限制条件，不然可能重复计算。
88502426
P6931 [ICPC2017 WF]Mission Improbable
考虑俯视图限制显然是有数的则至少要有 1 ；主视图、侧视图限制即为每行每列的最大值仍然保留。
贪心地保留每行每列的一个最大值，其余的全削减至 1 。
注意到可以有一个数同时占行列的最大值的情况。
于是跑一次二分图匹配即可。
88937221
AGC024B Backfront
顺序显然可以随意移，最后剩下必须连续，求最长上升子序列即可。
35588799
CF1481E Sorting Books
预处理出每种颜色的最左最右位置，即求最多保留多少不移动。
设 f_i 表示 [i,n] 中最多有多少无需移动，s_{i,j} 表示 [j,n] 中，颜色为 i 的数量。
106631440
P5779 [CTSC2001]聪明的学生
几个结论：
- 如果两个相等，则另一个一定为其之和。
- 另两个人中较大者未能在相应的回合猜出，则其可能猜中。
- 最大的人一定先猜到。
设 f_{i,a,b,c} 表示 a,b,c 数，在第 i 次是否能猜中。转移根据结论 1,2,3 即可。
89498503
CF536D Tavas in Kansas
首先从 s,t 分别跑一次最短路，容易发现答案仅与其相对大小有关，因此先离散化。
容易将其抽象成一个表格，其中第 i 号点位于 (d_{s,i},d_{t,i}) ，权值为 p_i ，两人分别从 上/左 取若干 行/列。
注意到 nleq 2times 10^3 ，考虑 dp，设 f_{k,i,j} 表示在各自最优策略下当前小 X/小 Y 先手，剩余的点为 (i,j) 及其右下角范围，小 X 的权值与小 Y 的权值的差。
发现其实没必要枚举每个人取到哪一行/列进行转移，只需要一行行一列列转移时注意是否要交给对方即可。
O(N^2) 。
159692208
ARC102D Revenge of BBuBBBlesort!
被操作的点仅可能是 a_i=i 的点。
显然相邻且均满足 a_i=i 的两个位置无法操作，所以原序列可分为若干交替是否满足 a_i=i 的子串。
每个子任务单独考虑，必须满足 a_i 在可交换的区间内且需要交换的数最长下降子序列长度不能超过 2 。
90297746
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 的剩余部分即可。
90346563
P5957 [POI2017]Flappy Bird
满足：
所以即需求
90332163
CF1340C Nastya and Unexpected Guest
设 f_{i,j} 表示第 i 秒到达第 j 个绝对安全至少经过多少个周期。
转移的边仅有相邻两个，于是直接 01-BFS。
O(mg)
176863749
CF778D Parquet Re-laying
操作可逆，考虑将起始状态与结束状态转移到一个中间的状态。
不妨设长为偶数，设构造中间状态所有地砖都是横的。
能旋转就旋转，发现一定可以转到。
176863439
P5956 [POI2017]Podzielno
容易发现 X 是 B-1 的倍数的充要条件是 X 的各位之和是 B-1 的倍数。
注意到 a_ige 1 ，所以只需要删除一个数即可，剩余的数从大到小排列。
注意不用删数的情况。
90466898
P5847 [IOI2005]mea
容易将 S_{n 1} 用 S_n 表示。
根据 S_ileq S_{i 1} ，可列出不等式，即可容易解得 S_i 取值范围。
最终 S_1 最后范围即为答案。
注意无解输出 0 。
90469236
CF429C Guess the Tree
爆搜。
首先判掉叶子节点过少的情况，爆搜的话按照子节点数多的从大往小先摆着，之后的点考虑连到之前的点中。
可以证明这个是能过的。
176992784
P1330 封锁阳光大学
每个连通块单独考虑，分别黑白染色，取黑白中数量较小即可。
90701973
CF436E Cardboard Box
对于每个关卡，分成两类：
- 2a_ileq 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 个两个，再将其中一个两个转为一个。
显然奇数情况记前/后缀最小/大值即可。
177110807
AcWing 359. 创世纪
在一内向基环树森林上选若干点，使每个点必有一个儿子没选，求权值和最大。
表示当前点选/不选的最大值。
考虑非树边 xrightarrow y ，有两种情况：
- 不选 y ，则 x 无限制。
- 选 y ，对 x 无影响，可直接将 xrightarrow y 断开。
两者取最大即可。
18236699
P2664 树上游戏
对于每个点，每种颜色，其单独答案贡献可转化为 n-siz_{x,c} 。
其中 siz_{x,c} 代表从点 x 出发，不经过颜色 c 的点，所构成的连通块大小。
考虑对于所有 siz ，均挂在深度最小的节点上，之后树上差分统计即可。
若碰到与当前颜色相同的点，之后该子树将失效，贡献更新。
注意根节点父亲颜色应设为“全彩”，特殊考虑即可。
90681495
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 的子树。
177124474
CF432E Square Tiling
按顺序从上到下从左到右贪心，首先对该格子的限制一定是上下左右四个格子，显然该格子一定染最小的与其不同的颜色。
接下来考虑是否向右下拓展：注意到向外拓展一层的几个条件：
- 上一行对应列点必须与其不同色。
- 不能已经被染过不同颜色。
- 上一行对应列点不能与其相差超过 1 。
- 上一行对应列点不能与其均不为
A。
177130361
CF1343F Restore the Permutation by Sorted Segments
暴力枚举第一个数，再将所有限制中包含该数的删掉该数，显然从删过的限制之中会产生一个只剩一个元素的限制，于是其为第二个数。
再将所有限制中包含第二个数的删掉，循环该步骤即可。
最后判一下是否合法。
177263802
CF553D Nudist Beach
二分答案，check 先把所有都标记为能选，再将所有不合法的点依次剔除。
可以证明这一定最优。
177266621
The 2022 ICPC Asia Regionals Online Contest (I)
经过一定分析可以发现合法数很少，写个爆搜 剪枝把所有答案先跑出来，查询二分即可。
O(?X Qlog X)
56740
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(nlog n)
56884
2021“MINIEYE杯”中国大学生算法设计超级联赛（6）. Problem 1007. Power Station of Art
每个连通块独立，分别考虑。
根据提示，容易想到按图是否为二分图分类。
若该连通块为二分图，将该图黑白染色，两图的左黑 右白、右黑 左白数量相等，容易证明这是充要的。
若该连通块不为二分图，即其必含奇环，注意到变换之和为偶数，故黑、白点奇偶性相同，且权值集合相同，容易证明这是充要的。
56887
京都大学プログラミングコンテスト 2021. Problem F. One Yen Coin
只需要考虑 1times x 5times y 即可。
贪心地想，容易发现每次只会选一个物品。
综合上述，一个代价为 a_i 的物品价值为 5lceil frac {a_i}5rceil-a_i ，其新代价为 lceil frac {a_i} 5rceil ，而总新容量为 lfloor frac m5rfloor ，初始答案为 mbmod 5 。
注意到价值很小，可以将价值放到状态里，设 f_{i,j} 表示考虑所有代价 leq i 的物品，获得价值为 j ，所需要的最小代价。
显然其满足决策单调性，将所有代价为 i 的物品抽出来排序求前缀和，转移即可。
O(nlog n)
56896
ABC163F path pass i
至少一个点颜色为 k ，显然可以转化为求不含颜色 k 的路径。
对于一个大小为 s 的连通块，若其均不含颜色 k ，贡献即为 frac {s(s 1)}2 。
对于每个点颜色 c_x ，只需求其所有儿子的子树中不包含 c_x 的连通块大小之和即可。
注意考虑与根节点颜色不同的点在根部分的答案。
35854775
CF1754E Wish I Knew How to Sort
的期望操作数。
177581574
CF1754F The Beach
显然将其转化为空位的移动，注意到最后两个相邻的空位一定会由不同的点转移过来。所以直接将所有空位丢入起点，一起跑一遍最短路即可。
注意建图是单向边。
177594371
CF1732D2 Balance (Hard version)
不妨先看 Easy Version，没有删除操作。
容易发现直接对每个询问记忆化答案，暴力往上跳复杂度是对的。
加入删除操作，考虑对每个询问跳过的点记下来，删除的话就对所有经过该点的询问打个标记。之后若询问到有标记的点，则输出标记中的最小值即可，插入的时候把对应标记删除。
这个感性理解一下，复杂度大概也是对的，因为每个询问跳的点必定是已经有过的点，所以点数是 O(N) 的，总复杂度大概是两个 log 级别？177713494
CF1732E Location
分块，对于整块修改只需暴力枚举 gcd 更新答案即可，显然这同约数一样可提前预处理。
O(frac nk Kgcd)
177713521
CF223E Planar Graph
取一个极远的点为根，任意建一棵树。
一次询问的答案即为出环的边数-入环的边数，分别对每个点相邻两条边算贡献，注意到环内的点一定在其极角排序后一段连续的区间内。因此直接做前缀和查询即可。
注意贡献有正有负且环上点必须按照同种顺序排序，叉积判断即可。
177955681
CF1188C Array Beauty
先对 a 排序，考虑转化为计算 min ge c 的方案数：
的方案数，转移：
可以前缀和优化。
而 min leq frac V {k-1} ，所以总复杂度 O(kn) 。
177961978
P4804 [CCC2016] 生命中的圆
段的状态，转移：
注意到，
可数学归纳法简单证明。
O(Nlog T)
91629629
CF1455G Forbidden Value
设 f_i 表示 x=i 时的最小花费。对于题目的嵌套，显然可以看作合并操作。
对于 set，f_y = min f_i, f_i =v (inot =y) 。
动态开点线段树 线段树合并即可。
