OI 支线：决战 *2800

lzqy_ · 2023-12-01 13:57:03 · 个人记录

初三心血来潮的决定，居然坚持到了退役/ll

重新整理一遍，按照括号里的做题日期排序。

目前进度：70，持续更新。

CF908G New Year and Original Order

（2022-01-23）

计算 0\sim 9 每个数在每一位的贡献，数位DP即可。

CF1648D Serious Business

线段树优化DP。

设 f_{x} 表示走到 (2,x) 的最大价值，用两个线段树分别维护转移方程中的两部分。

（2022-05-14）

CF1609F Interesting Sections

（2022-05-15）

跑一遍单调栈后按照 \text{popcount} 的值分类讨论，用线段树维护同时含有 \max\min 的位置个数。将区间插入线段树中时用平衡树维护。

CF325E The Red Button

（2022-05-16）

考虑 i,i+\frac{n}{2} 本质相同，先随便向 2i,2i+1 连边，后合并环（交换 i,i+\frac{n}{2} 的连边）。

CF1322D Reality Show

（2022-05-17）

考虑从后往前转移。若最大选的数为 a_i，显然最大能合并到 a_i+\text{log}n-1。所以 f_{i,j} 表示从后往前选，选了第 i 个，且 [a_i,a_i+\text{log}n-1] 内数的状态。范围内的暴力转移，范围外的用树状数组维护最值。

暴力转移时对每个权值的后 i 位维护个最值即可。O(n^2\text{log}n)。

CF1625E2 Cats on the Upgrade (hard version)

（2022-05-25）

对括号序列建树，每个点维护不拆分子节点的合法序列数，查询变为树上 \text{dfn} 序连续的一段，修改变成单点修改，时间复杂度 O(n\log n)。

CF335E Counting Skyscrapers

（2022-05-29）

看到 Bob 的诡异样例和诡异的不可做程度，很容易猜到答案就是 n。

对于 Alice 部分期望DP，时间复杂度 O(nh^3)，吸氧可过。

CF1400F x-prime Substrings

（2022-06-01）

转移第 i 位的时候显然只和前面未删除的，且总和 < x 的数有关。直接存状态转移就好。

有 x 真因数的区间直接舍去减少状态。

CF983E NN Country

（2022-06-03）

对于深度单调的链显然可以贪心爬，所以跑一遍树剖先处理出每个点经过一次航线能到达的深度最小的点，然后倍增跑出 f_{i,j} 第 i 个点经过 2^j 次航线能到达的深度最小的点。

对于拐点处，答案只能减少 1，所以将两条链都少跳一步，问题就转换为二维数点。用主席树即可。

CF794F Leha and security system

（2022-06-10）

简单DS，但很考察对lazytag的理解。

在一棵线段树上对 0\sim 9 的数值分别维护即可。

注意，打懒标记时是有顺序的，但下传时懒标记的顺序会丢失，且不一定适用于下一层。

CF613D Kingdom and its Cities

（2022-06-25）

（这种白痴的虚树板子是怎么上的 \mathbf{2800} 啊/yun）

建虚树后用类似最大独立集的方式DP即可，记得链上的点之间还要多放一个点。

CF1039D You Are Given a Tree

（2022-06-28）

根号分治初学。

CF1383D Rearrange

（2022-07-01）

傻逼构造，但是不会。

降序填数去除后效性，对于 S 内的数新开 行/列 填，对于不在 S 内的数紧贴着已填的数填。

CF794E Choosing Carrot

（2022-07-01）

将 n 为偶数也转换为 n 为奇数的情况，发现最终的答案之和中心点有关，而删除元素可以看做中心点的移动，找出移动范围之后用ST表维护即可。

CF1442D Sum

（2022-07-12）

简单贪心，但是找错了突破点qwq

考虑至多有一个数组取了一部分，分治转移即可。

CF1327G Letters and Question Marks

（2022-07-18）

？贺的我草。

CF1208G Polygons

（2022-08-10）

？我草又是贺的。

CF1404E Bricks

（2022-09-01）

比较显然的二分图，但由于不可重叠的限制，建模时先假设每个位置放一个矩形，然后反向合并。

CF869D The Overdosing Ubiquity

（2022-09-29）

日常做不出nt题。

一眼虚树，但是需要根据深度特点进行加点。

CF1098D Eels

（2022-10-01）

先找到不带修改的结论，然后找到分块的性质，最后用平衡树动态维护每个可能的块的分割点。

CF652F Ants on a Circle

（2022-10-16）

一个典是遇到掉头可以看做交换序号。

先求出最终位置和相对位置，然后求出其中一只蚂蚁的位置即可。

CF1413F Roads and Ramen

（2022-11-05）

发现答案的一个端点一定和直径重合，分讨端点之后拿树剖维护即可。

CF1379E Inverse Genealogy

（2022-11-11）

考虑先建出出花费点数最少的构造方式，然后在最后一个点的底下插入剩余点组成的完全二叉树。如果不是满二叉树，再把 1,2 插到完全二叉树里，或者 4​ 下面即可。

CF1267D DevOps Best Practices

（2022-11-14）

先分析一通，把是否安装CT的部分确定下来，然后直接跑Prim。

CF1473G Tiles

（2022-11-15）

把每一组 (a,b)​ 放在一起讨论，用范德蒙德卷积+NTT优化转移即可。

CF913F Strongly Connected Tournament

（2022-11-16）

这怎么只有 2800 的。

设 dp_i 表示 i 个点的答案，枚举最弱连通分量大小，则该连通块内部为完全图且外部所有点向内连边。

然后就可以困难转移。

CF838C Future Failure

（2022-12-12）

先自信猜先手胜的充要条件是初始字符串排列方式的奇偶，然后猜对了。

问题转化为判断 {n\choose a_1,\dots,a_k} 的奇偶。一个结论是它等价于 a_1,\dots,a_k 在二进制下没有两个数同时在某一位是 1，证明考虑卢卡斯定理。

然后 FMT 即可。

CF842E Nikita and game

（2023-04-04）

树上所有直径的交一定不为空。

可以通过这个特点将直径端点划分为两个集合。

CF521D Shop

（2023-09-06）

赋值有用的只有 \max，这可以变成加；加排序后又可以变成乘。然后直接贪心就好。

CF555E Case of Computer Network

（2023-09-06）

首先边双肯定合法所以缩点成树，于是问题转化为每次给一条路径定向看是否合法，树剖维护即可。

CF1142D Foreigner

（2023-09-15）

考虑向一个好数后面加数字 c 的影响，简单 DP 转移。难点在读题。

CF633G Yash And Trees

（2023-09-15）

观察到 m 很小，直接 O(\frac m \omega\log n) 暴力修改即可。

CF575I Robot protection

（2023-09-19）

对直角三角形拆成多部分容斥，二维树状数组维护。

CF568D Sign Posts

（2023-09-19）

将 >k 点共线的位置钦定选择，点数降至 O(k^2) 后暴力。

CF196D The Next Good String

（2023-09-19）

将所有不含回文串的 [1,r] 的 r 提出，此时答案具有单调性，二分填数即可。

CF1749F Distance to the Path

（2023-09-20）

到 u 距离为 d 可以转化为到 fa_u 距离为 d-1 或到 son_u 为 d-1，容斥一下后维护即可。

CF1635F Closest Pair

（2023-09-27）

发现有效的支配对是 O(n) 的，拉下来维护即可。

CF1606F Tree Queries

（2023-10-07）

对 k 根号分治，一部分树形DP一部分树形背包。

CF1316F Battalion Strength

（2023-10-14）

将答案用式子表达出来，在线段树上维护 \sum a,a\sum b,a，难点在 lztag 的下传。

CF757F Team Rocket Rises Again

（2023-10-23）

在最短路图上跑支配树即为答案。

CF762F Tree nesting

（2023-11-02）

直接状压，子树匹配时 3^k 枚举子集即可。

CF1827D Two Centroids

（2023-11-10）

发现答案等价于求 |2S_i-n|_\min。暴力将绝对值拆开，用两个线段树维护 2S_i>n 和 2S_i<n 的情况。发现每次加点时，两个线段树最多交换 O(1) 个点，证明考虑重心。

CF288E Polo the Penguin and Luck Numbers

（2023-11-14）

考虑将 a_ia_{i+1} 的贡献用 a_i 表达出来，然后数位DP。

CF620F Xors on Segments

（2023-11-14）

摁上回滚莫队套 01Trie 就过了。

CF377E Cookie Clicker

（2023-11-14）

考虑找到建厂的顺序。发现最优策略可以按照时间为第一关键字，金币为第二关键字决策，而这是有决策单调性的，分治转移即可。

CF513F2 Scaygerboss

（2023-11-21）

显然通配棋子是傻逼，去掉之后二分答案，内部是网络流模型。

CF1419F Rain of Fire

（2023-11-22）

先二分答案，然后 O(n^2) 暴力合并能合并的点，接着考虑哪些点可能是有用的，这个点数是 O(n^2) 的，暴力判断即可。

CF600F Edge coloring of bipartite graph

（2023-11-22）

发现染色数为 c 等价于可以把图拆成 c 个匹配。

先猜答案是 c=\max\{d_i\}，每次拆匹配钦定拿 d_{\max}，通过霍尔定理证明这一定是可行的。

实现用上下界网络流。

CF1578A Anti-Tetris

（2023-11-23）

把整个过程倒着做，发现没有后效性然后直接删即可。

CF859F Ordering T-Shirts

（2023-11-27）

可以通过奇怪的建模将问题转化为二分图完美匹配，考虑用霍尔定理判定，最终的式子可以用单调栈维护。

CF601E A Museum Robbery

（2023-11-27）

弱智线段树分治。

CF516D Drazil and Morning Exercise

（2023-11-27）

一个暴力的想法是对 f 双指针，用树剖或者 LCT 维护连通块大小，但这是过不去的。

考虑 f 的性质。若从大到小双指针，那么每次删掉的一定是连通块的叶节点，这就可以并查集了。

CF1654F Minimal String Xoration

（2023-11-28）

一个很妙的转化是不去对着 rk=1 构造字符串，而是对着字符串去维护 rk。这个过程类似于后缀数组。

CF1310C Au Pont Rouge

（2023-11-28）

把所有子串取出来之后钦定 rk，对这个 rk 二分后DP即可。

CF547E Mike and Friends

（2023-11-28）

直接合起来在 Parent Tree 上线段树合并即可。

CF30E Tricky and Clever Password

（2023-11-28）

发现中心回文串极长肯定是优的，提前用哈希处理出每一段后缀的最早出现位置，枚举中心回文串之后二分查询即可。

CF163E e-Government

（2023-11-28）

把串拍到AC自动机上，发现操作等价于链加，树剖维护。

CF10D LCIS

（2023-11-29）

傻逼DP。可能远古场DP反推方案还没普及。

CF204E Little Elephant and Strings

（2023-11-29）

把 S 拼起来建SAM，求出 Parent Tree 上每个节点向上的第一个合法节点，然后就能统计答案了。

CF1393E1 Twilight and Ancient Scroll (easier version)

（2023-11-30）

暴力设 f_{i,j} 表示转移到第 i 个字符串，状态是删除第 j 个字符的方案数，分四段区间两个tag转移，细节极多。

CF1615F LEGOndary Grandmaster

（2023-12-20）

考虑引入“预支操作”的定义，那么一个位置要么预支 0\rightarrow 1 要么预支 1\rightarrow 0，设 f_{i,j,0/1} 然后转移即可。

CF418D Big Problems for Organizers

（2023-12-22）

取出 \{u\rightarrow v\} 路径的中点，那么 u 支配一个子树 x ，v 支配 T/\{subtree(x)\}，这在 dfn 序上都是连续的区间。离线之后 dfs，动态维护到每个点的距离即可。

CF348E Pilgrims

（2023-12-23）

处理出每个关键点的最远关键点集，如果祖先和子树都有即不合法，否则处理出点集 lca，可覆盖的区域是一条路径，路径取交即可。

CF1386C Joker

（2023-12-27）

看到奇环没想到二分图只会 dfs 树上返祖边我是什么几把。

题目等价于对于每个 L 求出 R_{\min} 满足加入 [L,R_{\min}] 之间的边后不是二分图。一种做法是 LCT + 双指针，但还有更优美的类似于整体二分的做法。

由于 R_{\min} 单调，整体二分时只需要求出 R_{mid} 即可。摁求是 O(R-l) 的，这是无法接受的。但是观察到 [r+1,l-1] 在外层递归中一定有过属于 [l,r] 或 [L,R] 的时刻。所以每次向下递归时先并查集 merge 一下 [r+1,l-1] 然后复杂度就对了。

CF671C Ultimate Weirdness of an Array

（2023-12-28）

从大到小枚举 \gcd，设 S=\{x\in A|x\bmod g=0\}，那么 g 能贡献到的区间为 [1,S_{cmax}),(S_{\min},S_{\max}),(S_{cmin},n]。然后线段树随便维护一下。

CF639E Bear and Paradox

（2024.1.4）

随便贪一下得到排序顺序是 \frac p t，算出每个 p 的最大最小 p' 然后 chk 即可。

CF1608E The Cells on the Paper

（2024.1.5）

马桶分讨，但是不会。

CF1698F Equal Reversal

（2024.1.24）

发现翻转不会影响相邻数对，大胆猜测这是充要的。

对于 \{x,c.....\}（要复原 c\rightarrow b），有 bx 就直接翻，有 xb 就在两侧找到相同的数翻成 bx。感觉很对然后就过了。

CF850D Tournament Construction

（2024.1.24）

兰道定理板子。