四些做过的题

狂风之息 · 2025-03-16 15:59:37 · 个人记录

• 模拟 0316-A
  • 容易发现每次取重心就是最优解;
  • ? 找到修改后树的重心就可以求答案了;
  • 一次操作可以规约到：给新加的边的一端点到根的链的子树大小加上一个值 v，然后从这个端点起向上找到深度最浅的满足子树大小不大于二分之一的点 -> 因为子树大小有单调性，所以这个点的位置有单调性，所以可以并查集维护。
• 模拟 0316-B
  • 容易发现应当优先选对各维度求和的值最大的点;
  • 决策部分是容易的，注意到：选择了一个点后，与它相邻的点就不能选
  • ! -> 联想博弈论：一个必胜状态，能到达它的都不是必胜状态
  • -> 用 sg 函数是否为 0 刻画是否会被取到
  • -> 发现各个维度是独立的，考虑类似 Nim 游戏，将各维度的 sg 值异或起来即可。
  • …… 具体的对值的计算并不容易
• [P11845] Min Max Subarrays “所有子区间求最值和”的处理方法：枚举这个值求边界
  • 和相对大小有关的带决策的题目，尝试从 01 序列的角度考虑：容易猜到大部分情况只有最大值/次大值可以取到，经过手模/讨论可以验证;
  • 需要对长为奇数的区间求最大值，长为偶数的区间求次大值。最大值/次大值考虑类笛卡尔树的结构，枚举最大值/次大值稍微讨论即可。
• [P11847] True or False Test 贪心/决策中带有“分界点”的决策单调性想法及处理
  • 容易想到按 a_i+b_i 和从大到小处理，发现存在一个分界点，其前面取 k 个而后面全取
  • -> 枚举分界点不现实，有两种想法：分界点满足贪心类性质，容易证明不行；分界点关于 k 有性质，可以猜想并证明是单调性。
• [P11846] Transforming Pairs “多元组变换”中对决策唯一性的考虑；利用形如“轮换式”中变量类似关系的化归思想
  • 对于 a,b 同号的部分，考虑反向操作。发现为了保持符号，反向时的逆向操作方案唯一，可以直接辗转相除处理;
  • ? 对于异号且最终状态也异号的部分，可以化归到同号上;
  • 对于最终状态同号的部分，必然会有第一次转化成同号的时刻
  • -> 预处理出能到达最终状态的状态，在转化到同号的时候即可求出答案
  • ? 怎么预处理的
• [P11815] 领地 / Terytoria 我不认可
  • 注意到每种生物都一定能放到至少两个对角上，所以枚举这组对角，把只能放到一段的放上去，再把都能放的堆到多的一端即可；
  • 还需要考虑一个非角落的点，将所有能放的都放上去即可，剩余部分同上。
• [P11816] 摆棋 / Pionki “一一对应”的“判定”向二分图完美匹配的转化；hall 定理转最优化；轮廓线 dp 的入门
  • > 无论是“棋子”还是“箱子”什么的，都可以看出从“若干个起点”到“若干个终点”的形式，这种形如“移动物品”的存在性问题是典型二分图完美匹配！
  • 起点到终点，联想到二分图后考虑 hall 定理，尝试让左部点集合极大，发现形如把长方体切成两块，取靠近终点的那块
  • -> 由 hall 定理想到向最优化转化：最大化左部点个数减去右部点个数。因此取 c=a-b，最大化块内的 c 和即可;
  • 对 A 维逐位枚举，每个切面可以被一条线分为两半，即被选/不被选。容易发现切面的状态数很少
  • -> 直接枚举两个切面转移不合理，考虑把每个切面分成若干列进行轮廓线 dp，每次枚举上一个切面当前列的高度转移即可。
• 模拟 0317-A
  • … 我打表找规律过的哈哈哈
  • 考虑将每个数中的二的次幂提出来，则恰好要选择 1,3,\dots,2n-1 乘上一个二的次幂各一个
  • -> 注意到每个数对应的幂次必须大于其倍数的幂次，对这些奇系数从大到小决定次幂即可。
• 模拟 0317-B
  • … 为啥又是缩小 dp 范围的题
  • 很容易想要 dp 求解，但是对着正方形不容易，所以尝试把四边拆开，发现枚举一下对角线的归属就可以了;
  • > 这题的 dp 需要和 aliens 区分开来：那题的每个点都必须取，决策是唯一的。这题的状态设计很难优化转移，是一般题目中需要避免的。
  • 同样转化到区间上。因为决策不唯一，所以状态的转移必须从相邻位置转移，也就是 f_{i,*} 只能转移到 f_{i+1,*}
  • -> 不能考虑优化转移，只能考虑压缩状态。容易发现因为答案值不大，所以第二维的范围非常小。
• 模拟 0317-C
  • … 有人想了一个小时后缀树怎么按字典序排序(微笑)
  • “每个子串”比较“字典序”考虑把反串扔进 SAM 建出后缀树，然后对每个儿子按照字典序排序，跑出来的 dfs 序就是字典序;
  • <- 如何比较儿子的字典序：两个儿子第一个不同的地方即为第 len_u+1 位，所以对每个点维护 \operatorname{endpos} 集合中的一个位置，即可倒推出这一位。
  • 后缀树上每个叶子都对应一个后缀，处理出第一个 0/第一个 1 的位置即可求出这个后缀的贡献区间，在后缀树上链加即可预处理出每个节点能贡献的长度范围;
  • 答案串对应的节点即为在 dfs 序上第一个前缀和大于等于 k 的位置，求出这个位置之后可以树状数组（区间加/单点查）加二分处理;
  • 对于题目给定的 l,r 限制，可以直接建主席树差分处理。需要注意，继承的时候直接单点修改是不合理的，可以直接维护一个以 r_0 为变量的一次函数，从 i 继承到 i+1 时只需要对一次函数变化的位置单点修改即可。
  • <- 这里一次函数会变化的位置只有：每个节点对应的头尾两端/每个后缀能贡献的范围两端。这些都是线性量级的。
• 模拟 0309-A
  • 显然考虑减去不合法方案数。令 f_{i,j} 表示长为 i 的序列值域为 [1,j] 的合法方案数，枚举一个分界点 p 及两侧最值 k 并钦定其为最后一个分界点，则方案数为分界点前后两部分乘起来。
  • 两边独立计算。分界点前：只钦定了最大值，方案数即 k^p-(k-1)^p；分界点后：钦定了最小值，且不存在合法分界点，即其为合法方案，等价于原问题的子问题。因为钦定了最小值，所以要在值域上差分一下，方案数为 f_{i-p,j-k+1}-f_{i-p,j-k}。
  • ! 注意到贡献方式形如 -[k^p-(k-1)^p](f_{i-p,j-k+1}-f_{i-p,j-k})\to f_{i,j}。把左侧中括号拆开，贡献形如 (k-d)^p(f_{x,y+1}-f_{x,y})\to f_{x+p,y+k}。枚举 y,k 和 d=0/1，在 x+p 增大的过程中左侧的部分只会同时乘定值，也就是说可以前缀和优化。
  • 因为值域很大，所以考虑求出钦定恰好用了 x 个不同值时的答案，乘上一个组合数即可。具体地，用二项式反演即可。
• 模拟 0309-B
  • 异形题目考虑直接入手：对操作分析具体影响，发现是将路径对称再对称
  • -> 发现对称轴的位置不多，所以可能的状态只有 m^2 种，可以直接预处理出对应的结果;
  • 对正反两种状态都预处理出答案，讨论一下进行一些加加减减即可。
• [P11820] 健身房 / Siłownia “区间选点”最优化类贪心
  • 右端点各不相同时，按常规的“区间选最少点”的做法，能托就拖即可;
  • 有右端点相同时，按左端点排序，将左端点较前的区间的右端点向前推即可，这个是可以用 set 维护的。
• 模拟 0314-A
  • … 其实是线段树合并分裂板子题
  • 对采摘时间不同的位置分别建线段树维护，把每次采摘的部分分裂出去，把时间大于 a 天的线段树合并起来即可。
• 模拟 0314-B
  • > 事实证明树上走恰好 k 步在没有对 k 的大小特殊限制的时候只能转到图论上。
  • 直接转到图论，暴力建边 bfs 不合理，考虑优化建图，有淀粉质建图和长剖建图两种
  • -> 因为走恰好 k 步也是一种 “路径问题”，所以考虑淀粉质是比较自然的
  • -> 对每个深度建超级源汇，处理新的子树时，每个点向对应的超级汇连边，对应的超级源再向它连边。然后对每个存在的深度新建超级源汇，直接与原有的超级点连边继承，再与子树内对应深度的点连边即可。
  • -> 注意到淀粉质的过程和深度有关。和长度/深度有关，考虑长剖也是合理的。
  • -> 长剖的做法和淀粉质类似，只是每次合并的是两条长链对应的超级点，并且父亲直接继承了重儿子的超级点。注意需要考虑当前节点向 a 级超级点的连边。
• 模拟 0314-C
  • … 对涉及子集的东西为什么这么难理解呢
  • 同 CF1773G 转化为期望，然后做 \texttt{AND} 卷积，可以做到 O(m^22^m)
  • ? -> 根据卷积过程，发现是高维前缀和/点乘/高维前缀和，于是考虑在线做高维前缀和，使得只用做一次前缀和。高维前缀和的转移是 DAG，所以建出来，按照对应的集合大小依次确定 DAG 上的值即可。
• [CF1773G] Game of Questions
  • … 如果没有记错的话我似乎做过这题来着
  • 把题目转化为有若干操作，按照某种顺序执行它们。对于一个状态，我们只关心会对它造成影响的操作，为了忽略剩余部分，转化为期望;
  • 尝试预处理出转移系数。钦定一个不属于 S 的元素 p，能使得 S 转移到 T 操作有两类：包含 p 和不包含 p，分别对应 S+p\to T 和 S+p\to T+p。因此随意取一个 p 就可以预处理出可以转移的操作数，再除以有效操作数得到转移系数。
• [P7152] Bovine Genetics “分段”类 dp 在线性方向的思路
  • > 笔记贡献到 02-01
  • 题目中的操作唯一，所以一个结果串的一个操作序列对应一个原串。因此直接考虑对结果串进行划分即可;
  • 对串分段的问题考虑 dp，因为是线性复杂度，所以考虑逐个字符加入并二选一决策：加入末尾段/另起一段。稍微分析一下即可。
• [P8193] Sleeping in Class 基于因子个数的高维前缀和
  • 容易想到求可以被整除的前缀和个数。发现一个数只能贡献到总和的因子，因此对总和分解质因数后高维前缀和一下即可。
  • -> 对 10^{18} 范围的数分解质因数并拒绝某 P 开头大数分解算法：将 10^6 范围内的质因子除掉，剩下的部分要么是一个大质数要么是两个大质数相乘，拿出去特殊处理即可
• 模拟 0319-A
  • 很容易注意到 t 正/负的部分可以分开，并且一定可以调整到有一个点的时刻为 0，考虑分开处理之后枚举分界点求解;
  • 因此我们需要从点 1 和点 n 跑单源最短路。考虑一个 t_i 对答案的影响，因为和 t 有关的贡献在点上，容易想到贡献与在它之前经过的点数有关。因此直接拆点做就行了。
  • <- 注意到这个分层图最短路 其实是 DAG 上求最短路，所以不需要堆优化，直接更新最小值即可。
• > 模拟赛 B 题是推柿子 O(n^2k)，C 题是保序回归板子题。
• [AGC065D] Not Intersect “凸多边形划分”和 Raney 引理的关系
  • > 笔记贡献到 0?-01
  • 把凸多边形划分的过程映射到栈上，根据点数的变化，可以看成和为 1 的一个 +1/-k 序列，根据引理容易知道有贡献的序列恰好占序列总数的若干分之一，直接对和为 1 的序列计数即可。
  • <- 这里对序列计数分两步：把负数部分分成和固定的若干非 0 数；把这些数插到 +1 的空隙中。这些都是组合数学容易处理的。
• [P6240] 好吃的题目 背包的“合并”；猫树分治板子
  • > 笔记贡献到 0?-02
  • 一次合并背包并查询，直接枚举其中一个背包占的容量即可。所以只需要让查询时只有一次合并即可，可以猫树分治做;
  • 猫树分治：维护可以左右合并的信息，常数次查询，n\log 次插入（预处理部分）。具体的，对于每个分治区间 [L,R]，维护所有 [l,mid],(mid,r] 的信息。对于跨过 mid 的询问，合并对应的 l,r 的信息处理，否则向下递归处理。
• [P7624] 地铁 差分约束在“存在性”上的应用；“合法取值个数”的联想
  • > 笔记贡献到 01-02
  • 限制很具有差分约束的特征，全部转化成小于等于后，发现刻画不了点 1,n 的限制，所以考虑断环为链做，需要设一个变量表示环长;
  • 涉及“合法取值个数”，大致有几类：枚举取值，数学推导，合法取值为区间。联系题目考虑微调长度，容易推出合法取值为区间;
  • -> 求合法区间端点通常用二分/数学，本题模型复杂考虑二分。二分需要能够判断不合法点在合法区间左/右，在差分约束上考虑从负环入手;
  • -> 发现左/右与负环上环长的系数正负有关，同时因为保证有解，所以所有负环对应的正负相同。因此随意拎出一个负环即可。
• [P9697] Canvas 被我秒了的简单题
  • 观察权值范围发现只有 2，容易往二分图方向联想;
  • 把不相关的部分扔掉（没被涉及的变量/两个 1 的操作），再把必然有贡献的部分处理掉（两端权值为 2），再考虑剩下的 1/2 共存的部分;
  • 沿用建图思想，直觉告诉我们联想 SCC，发现缩点后没有入度的点恰好有一个变量不能取到 2，于是直接左即可。
• [P4610] KAMPANJA 很精妙的对着特殊形态 dp 的题目
  • 题目所求的是一种特殊最短路，正常的最短路算法难以使用，所以属于非常规题。考虑观察形态，发现形如环套环，考虑对此形态 dp。
  • 因为“路径”(或者“环”)的信息并不好存，所以直接加入一个环不现实。考虑逐个加入点，令 f_{x,y,z} 表示考虑到了 x\to T,T\to y 且最新的两个环相交的部分是 x\to z，此时消耗的最少点数。
  • -> 转移分四类是容易的：新增一个点连向 x；y 连向一个新增点；把 z 拉到 x；把 y 拉到 z，要求 x=y。注意到转移时权值有且仅有 0/1 可以 01 bfs 做。
• [P10517] 国土规划 典爆了的圆方树题
  • “删点可达”明摆了的圆方树，建出圆方树后考虑什么点可删：包含关键点的极小子树外的所有点/子树内不包含关键点的点。都是可以直接处理的。
• [P2371] 墨墨的等式 同余最短路以及用“同余”把计数转最优化
  • > 原来这就是同余最短路。本质上就是根据模意义分等价类，等价类内有单调性/分界点(这里是从零变成一)，求出这个分界点，也就是转成了最优化。
  • 所有可以表示出的数都对应一个 x_1=0 时能表示出的数，称之为最小值。所以我们对于所有 p\in[0,a_1) 求出模 a_1 值为 p 的最小值即可。
  • <- 具体的，对每个 p 建点，根据每个 a_i，连边 p\to(p+a_i)\bmod a_1，边权为 a_i 即可。直接跑最短路求出最小值，分别计数即可。
• [AGC010D] Decrementing “轮流减一”直到不能操作类题目和奇偶性的关系
  • 考虑没有操作二时，和的奇偶性决定胜负。再考虑操作二对奇偶性的影响：除以奇数无意义，除以偶数会改变奇偶性。
  • -> 因此处于劣势的一方一定会尝试改变奇偶性，优势方不改变奇偶性。经过分析就会发现，先手当且仅当有恰好一个非一奇数时可以改变奇偶性，且如果其处于劣势则一定会改变。
  • -> 因此决策唯一，直接模拟即可。
• 模拟 0323-A
  • 发现序列的顺序没用，考虑把每位的取值范围求出来然后对每一位分开决策，变成在若干区间内各自选点;
  • > 我本来考虑贪心或者 dp，但是发现根本没法把这些区间排序（有包含关系并且消不掉），于是换思路了。
  • 注意到一个数对答案的贡献随着次数的增加是凸的，再联系到是最优化，发现可以对次数拆点然后上 flows。
• 模拟 0323-B
  • … 数论推式子，居然看懂了，但是也没啥好记的。
  • 转化成对 i^2 的约数个数求和，直接考虑莫反，以下是比较常规的部分：
  • -> 写成 \gcd=1 的形式;
  • -> 把外层“被整除”的数的枚举变成一个下取整。枚举了两个整除它的数，因此带了一个 \operatorname{lcm}，但是 \gcd=1 所以可以去掉它;
  • -> 莫反把 \gcd=1 消掉，然后换一下枚举顺序把带着 \mu 的式子往前提，再经典地枚举 \gcd 把 d|x 变成枚举 d 的倍数(d\cdot k_x=x);
  • -> 最后把一定等于 0 的部分去掉，缩小枚举范围。
  • ! 一个下取整除以一个整数，可以把这个整数除进去，这样方便做数论分块。
  • 把小的数拎出来暴力，大的数数论分块做就行了。
• 模拟 0323-C
  • 首先每条路径的长度都是关于 T 的一次函数，所以只有两端 T=1,T_0 有用，跑两遍就好。
  • 因为可能变成完全图，所以不能对着边做，堆优化 dij 做不了。因此考虑朴素 dij 点对点转移，把可以用的点扔到堆里就行;
  • -> 直接做很慢的原因是出现了太多“访问但没法转移”的点。减少这种情况的做法是让能转移的优先被访问，访问到不能转移的就退出，也就是钦定一个顺序然后跑指针之类的。
  • -> 先考虑上树的情况：可以淀粉质，按照到分治中心的距离排序，这样能转移的就是一段前缀，对于每个点记录一下和它有关的分治中心，直接做就行。
  • 剩余部分是树上加若干边。不经过特殊边的可以直接做，经过特殊边的一定经过其一端，因此把每条边的一端拎出来当作一个分治中心做就行。