2024.07.16 Day1 个人赛报告
2024 Nowcoder Multi-University Training Contest 1 Mirror
提交情况（5 + 3）
赛题分析
A - A Bit Common
考虑所有二进制表示第零位为 1 的项，满足条件的序列必然满足这些项的 AND 结果为 1，我们考虑枚举 $n$ 个数中有 $t$ 个第零位为 1，然后逐个考虑每一个二进制位的方案数量，对于 $t$ 项来说方案为 $2^t - 1$（不能含有全 1 方案），对于其他 $n - t$ 项来说方案为 $2^{n - t}$，乘上组合数后相加即可。
B - A Bit More Common （补）
在上一题基础上加上了“至少有两个子序列满足 AND 结果为 1”的条件，那么考虑用上一题的结果减去“恰好仅有一个子序列满足 AND 结果为 1”的数量即可。发现此条件等效于“所有第零位为 1 的数的 AND 结果为 1，且删去任意数后 AND 不为 1”。发现此条件相当于要求每个数都有至少一位满足“仅在此数上为 0，在其他数上均为 1”，即称此位属于此数。现在有 $m - 1$ 个位，需要每个数都至少有一位属于他，一位可以以 $2^t - 1 - t$ 的方案数不属于任何数。容斥即可，求出每个数均为对应位的方案数。
比赛中没有注意答案为 $0$ 的情况，在此情况下最终循环不应从 $1$ 开始枚举，改为从 $2$ 开始循环枚举即可通过此题。
C - Sum of Suffix Sums
一个数对后缀和之和的贡献为它的值乘上它及它前面的元素数量。维护这一贡献的总和即可。
D - XOR of Suffix Sums （补）
关注到后缀和等于总和减去前缀和，其中前缀和为定值。考虑以某一方式维护前缀和信息，并使用序列总和进行询问得到最终答案。由于为异或，考虑逐个二进制位统计其出现次数。令总和为 $s$，某一前缀和为 $v$，则该后缀和在第 $t$ 位上为 1 即为 $s - v bmod 2^{t + 1} ge 2^t$，对每一个二进制位维护一个树状数组，在对 $2^{t + 1}$ 取模意义下维护所有的 $-v$，每次需要求解时使用 $s$ 查询即可。
F - Career Path （补）
模拟题，读懂题意之后容易发现仅是各部分计算规则复杂，但是不难于想到正解思路。使用 $f[i][j][k][0/1]$ 表示已经度过前 $i$ 年，一共有 $X + j$ 年工作经验，上一家公司为 $k$，中间是否有 Gap Year 的最大收入。暴力枚举转移，将自然语言翻译为程序语言即可。
H - World Finals
将两场比赛的排名表分别排序，然后统计一下哪些队伍能够同时参加两场比赛。枚举本队参加哪场比赛，将排在前面的同时参加两场比赛的队伍赶走后即为我在此场中能够得到的最高名次。两个答案取最大值即可。
I - Mirror Maze
维护状态 $(i, j, 0/1/2/3)$ 表示“以某一方向进入 $(i, j)$ 格子”状态，对于不同的镜子形态将对应光路的状态连边即可。注意光路可逆，因此所有边均为双向边。不难发现连通块仅有环和链两种情况。由于记录路径上反射的镜子数量需要去除重复经过同一镜子，因此可以先分别预处理所有的环和链。便可应对询问。
J - 2D Travel
不难发现两维可以分别独立处理。
考虑 $x \to f(x)$ 图像，记录在经过若干操作之后每个输入数的输出，不难发现其必然为一个“先横，再斜向上，再横”的形状。发现可以将此图像通过描述斜边起终点，及斜边偏移量来描述。经过一定的思考可发现该图像信息可轻松合并。可以使用线段树、倍增等方法在 $O(n log n)$ 复杂度内维护区间合并信息。
由于同时要求维护运动距离，维护图像时额外记录运动距离即可。合并略微烧脑，仔细举例思考可以得出。
2024.07.18 Day2 个人赛报告
提交情况（7 + 1）
赛题分析
A - ^&^
签到题。逐个考虑每个二进制位，若两数在此位均为 1 则此为为 1，否则为 0。需注意特判答案为 0 的情况。
B - array
我使用了根号做法，对值域分块，对每一个值域块预处理每个位置的答案，询问时对整块查询预处理答案，对于不足一块的部分暴力即可。
C - K-th occurrence
考虑使用后缀自动机，可以发现在 parent 树上一个子串的所有出现位置一定位于其对应 endpos 位置的子树上。我们可以在以 $i$ 位置结尾的前缀所在 endpos 结点上记录权值 $i$，可以发现所求即为 parent 子树内第 k 小。我使用了线段树合并加线段树二分的做法，可以在 $O(n log n)$ 复杂度内完成。
D - path
发现 $K$ 很小，考虑复杂度与 $K$ 相关的做法。发现边权为正，可以贪心。初始将所有长度为 $1$ 的链加入优先队列，每次取出当前长度最小的链并考虑枚举下一条边进行延长然后将所有可能的结果加入优先队列。发现在菊花情况下可能会被卡掉，但不难想到同时进行下一条边的扩展和最后一条边兄弟边的扩展，这样每次更新只会加入最多 2 条新链，复杂度可以接受。
F - Shuffle Card
发现靠后的修改操作影响更大，在时间轴上从后往前依次考虑每个修改操作，遇到新的修改数字就将其加入到队列末尾，最后顺序扫描原序列并将没有修改的结点依次加入队列末尾，即可得到答案。
G - Windows Of CCPC
签到题，每次将矩阵切为四份递归即可。
H - Fishing Master
不妨考虑先忽略钓鱼的时间，将所有烤鱼的时间相加组成初始方案。再考虑从中凑出 $n$ 个钓鱼时间。先尽量在所有烤鱼时间内塞满钓鱼事件，若仍然不够钓鱼则考虑在烤鱼时间后插入空挡时间，空挡时间为最短的时间使得此段时间能够多插入一次钓鱼。按空挡时间递增排序，从前往后尽量取即可。若仍不够则再添加若干长度为 $k$ 的时间即可。
I - Kaguya
发现 $n$ 非常小，考虑高维 DP 方法。令结点有标号，钦定进行计算的结点为左侧和右侧的 1 号结点。考虑按照从起点至每个点的距离对图进行分层，然后逐层往下 DP 构造方案。考虑 $f[d][l][r][s]$ 表示当前构造至第 $d$ 层，此时左侧已使用 $l$ 个点，右侧已使用 $r$ 个点，最后一层使用 $s$ 个点的所有方案的概率和。$O(n^5)$ DP 即可。
2024.07.19 U1 Day3 陈佳鹏、戴士博、徐子恩 组队赛报告
提交情况（7 + 0）
赛题分析
A - 循环位移
签到题，对所有可能的 $A$ 循环位移后的结果进行双哈希，之后将 $B$ 的所有可能合法子串带入查询即可。
B - 星星
签到题，裸的背包，直接 $O(n ^ 2)$ DP 即可。
C - 树
由于同时有最大值与绝对值，考虑固定两个权重的大小关系。
可以使用线段树合并，每次合并两个结点时观察某一个结点左子树与另一结点右子树内所有权值对的贡献和。只需要维护区间和，区间平方和，区间元素数量即可。
D - 传送
由于每一条边的插入操作有时间区间，考虑使用线段树时间轴分治将此问题化简为仅有插入和撤销。
为了维护连通性，我们可以使用可撤销并查集维护连通块信息。在线段树分治至叶结点时还需对根节点所在连通块进行权值加操作，可以考虑在并查集结点上插入永久化标记。每次合并或者撤销时注意将子树至新根节点路径上权值和累加至子树根节点即可。
E - 博弈
发现在总字符数为偶数时，若存在字符数量为奇数，则双方不可能平局，且此时双方局势对称，此时胜率为 $frac 1 2$。若不存在字符数量为奇数，则我们可以计算出平局概率 $p$，胜率即为 $frac {1 - p} 2$。计算平局概率时我们可以使用合法方案数除以总方案数，总方案数为“有 $i$ 颜色球 $a_i$ 个，问打乱为序列的方案数”，计算合法方案数可以将相同字符两两配对后再行计算，即“有 $i$ 颜色球 $frac {a_i} 2$ 个，问打乱为序列的方案数”。
对于总字符数是奇数的情况，可以枚举 Alice 最后一个字符的种类，对剩下的字符集执行上述偶数情况操作，判断 Alice 获胜或平局的概率，即为此时 Alice 的胜率。
H - 位运算
签到题，不难发现位间独立，每一位运算出零或一的方案数均固定，根据 $n$ 每位的值乘上每位上的不同方案即可。
L - 并
可以发现被覆盖次数相同的面积对答案的期望计算方法是相同的。可以使用扫描线统计出所有可能的覆盖次数对应的总面积，进行计算即可。
2024.07.22 U1 Day4 陈佳鹏、戴士博、徐子恩 组队赛报告
提交情况（8 + 1）
赛题分析
A - 鸡爪
经历了大量的手模构造后可以发现所有点尽量连接到 1、2、3 即可。具体可以考虑，我们不妨将所有点均连接到 1 号点。在此基础上考虑在新增三条边后选取一个编号尽量小的点，以它作为新的图案的中心匹配新点，此过程中可利用原先它与 1、2 号点已经连接的边，仅需为 1、2 号点提供他们所需要的新的边即可。
B - 梦中的地牢战斗
容易发现可以将扣血替换为等效的扣钱，因此仅需记录金币数量即可描述一个状态。发现数据范围相当小，不妨考虑 $f[x][y][S]$ 表示当我位于 $(x, y)$，已经击杀怪物的集合为 $S$ 时的最大获得金币。注意到在计算最大路径时会同时遇到正负边，可以分层计算，也可以将正边（击杀怪物奖励）提出并于计算答案时加回。
C - 绝对不模拟的简单魔方
发现无论魔方打乱情况如何，魔方八个角的颜色组合顺序必定是固定的。考虑固定一个顺序，如左手持魔方时“上、前、右”的顺序描述一个面对自己的角。容易发现三种这个角的不同旋转状态描述在循环替换情况下都相同。因此可以记录正常魔方的八个角的最小字典序描述。对于输入的魔方，根据对应数组位置取出八个角的最小字典序描述，与正常模仿的所有情况对应匹配即可。若能够匹配则说明该角正常，若不能则说明该角贴纸方案错误。
F - 传奇勇士小凯
签到题。发现某个点的期望用时即为 $frac {15} {p_i}$，取树上最大前缀和即可。
G - URL划分
签到题，按照斜杠位置分割字符串即可。需要注意判断后面的子串是否为 xxx=yyy 形式。
H - 成长，生命，幸福
发现断边操作对本题并无大的影响，一条选定的路径不可能经过一个多边形上面的所有边，因此一个选定路径上的点在生长后，新的路径必然经过这个多边形上所有的点，并断掉剩下未经过的边。容易发现在一次生长之后图中的所有点度数都不超过三。然后可以具体计算出一个初始度数为 $d$ 的点，在 $m$ 时间后会生长为 $(d - 1) times (2^m - 1)$。然后就转化为一个有点权有边权的树求直径的问题。发现权值可能过大不能直接记录，但容易发现其显然为 $x times (2^m - 1) + y$ 的形式，使用 $(x, y)$ 二元组即可记录此数。比大小时可以取 $C = min(2^m - 1, 10^8)$，比较两数 $x times C + y$ 的大小即可。
J - 女神的睿智
签到题，模拟即可。
L - 图计算 （补）
考虑对于每个点，将其在每个图中的祖先哈希并记录为一个值。每次更新一条边时只需要启发式合并两个连通块，对于较小的连通块更新每个结点的哈希值即可。可以使用 map 记录某一哈希值对应的结点数量，并以此维护总答案。
2024.07.23 Day5 个人赛报告
2018-2019 ICPC Southwestern European Regional Programming Contest (SWERC 2018)
提交情况（8 + 1）
赛题分析
A - City of Lights
签到题，模拟即可。
B - Blurred Pictures
容易发现行数越多情况越劣，考虑使用双指针维护当前矩形的首行和尾行，枚举首行并在答案能够增加的条件下将尾行尽量向下推即可。
D - Monument Tour
自下而上枚举选中的行，维护每一列是否在上和是否在下存在点即可。
E - Rounding
计算出每一项的上下界，枚举每一项，使用其他所有值同时使用下界和同时使用上界的情况判定此值的取值范围，若范围为空则无解。
F - Paris by Night （补）
（结束后才发现是水题，场上没有人开题所以没有仔细阅读并思考这一个题目）
枚举每一个点，将其他所有点以极角排序，双指针维护半平面即可。
G - Strings
考虑反向处理，将询问从最后一层向第一层传。考虑将每一个询问化为前缀询问。使用二元组 $(x, t)$ 表示前缀 $x$ 乘上 $t$ 后贡献至总答案。为每一层开一个数组存储所有可能的二元组。
初始时仅最后一层有一个二元组，然后从最后一层向前推。若当前一层为 SUB 操作，将所有此层二元组 $x$ 加上 $l$ 后插入上一层，并将数量相同的 $l - 1$ 以负贡献记入上一层；若当前一层为 APP 操作，将询问按照目标位置分配至两个上层，并根据右侧层插入的数量为左侧层添加等量的全层和即可。
每一层只会为总二元组数量增加一，复杂度显然为 $O(n ^ 2)$。
H - Travel Guide
从三个点开始分别为所有点求最短路，然后三维数点即可。由于不需要数出来具体有几个点，而只需要询问是否有点，可以使用线段树套 set 快速实现。
I - Mason's Mark
将所有噪点去除，然后将所有外围的黑色像素也去除，之后所有的黑色像素均组成字符，逐块判断即可。
K - Dishonest Driver
区间动态规划，提前预处理每个区间的内部循环节即可快速转移。
2024.07.25 Day6 个人赛报告
2019-2020 ACM-ICPC Latin American Regional Programming Contest
提交情况（10 + 0）
赛题分析
C - Cut Inequality Down
是 此题 的简化版。
由于此题没有修改，还可以使用分块等更为好写的做法。或者继续像上题一样使用线段树维护区间上下边界和偏移量。
D - Dazzling Stars
枚举每一对亮度不同的点对，考虑他们之间对总答案的限制。容易发现把总答案角度限制在一个范围之内。将所有范围区间交起来即可判断是否有解。
E - Eggfruit Cake
签到题。枚举每一个 E，考虑它为块内第一个 E 的方案数即可。
F - Fabricating Sculptures
不妨考虑自下而上逐层动态规划，容易发现这样不需要关心层数，可以减去一个维度。令 $f[i][j]$ 表示当前还有 $i$ 个方块没有放置，当前最高一层块数为 $j$ 的方案数。转移如下：
$$
f[i][j] = \sum_{k \ge j} f[i + j][k] \times (k - j + 1) = \sum_{k \ge j} f[i + j][k] \times k + (1 - j) \times \sum_{k \ge j} f[i + j][k]
$$
使用后缀和即可解决后面两个求和符号，这样就可以在 $O(n ^ 2)$ 复杂度内完成动态规划。
G - Gluing Pictures
对原串建立后缀自动机，扫描查询串并在每次向后缀自动机内插入尽可能长的串即可。
H - Hold or Continue?
发现数据范围很小，令 $f[i][j][k]$ 表示当前我的权值为 $i$，对方的权值为 $j$，当前我的回合已经拥有权值 $k$ 时的胜率。但是发现计算此权值时会在 max 函数内访问到 $f[j][i][0]$，而 $f[j][i][k]$ 的计算过程中又需要用到 $f[i][j][0]$，出现了循环依赖。此时可以二分答案 $f[i][j][0]$，以此值推导出 $f[j][i][k]$，从而计算出 $f[j][i][0]$，再以此值计算出 $f[i][j][k]$，并再次推导出 $f[i][j][0]$，通过此值与二分指定的值比较大小即可判断二分值过大或过小，相应调整即可。
I - Improve SPAM
签到题。题意保证为 DAG，拓扑即可，或者记忆化升读优先搜索均可。
K - Know your Aliens
发现权值均为偶数，让我们想到可以使用穿线法，在种类变化处插入一个零点，并以此计算整个多项式。容易发现这样的构造可以让多项式长度最短。
L - Leverage MDT
二分答案，然后对于整个矩形内的每个位置判断是否有可能作为正方形的左上角即可。
M - Mountain Ranges
签到题，模拟即可。
2024.07.26 Day7 陈佳鹏、曾添琪、徐子恩 组队赛报告
提交情况（7 + 0）
赛题分析
A - 深度自同构
每一个结点下面的每个子树形状均相同，因此该结点子树大小必然为其孩子结点子树大小的整数倍加一。$O(n \log n)$ 枚举倍数转移此 DP 即可。
B - 旅行
考虑树形 DP，$f[i][j]$ 表示以 $i$ 为根子树内方案且一条链颜色为 $j$ 且穿过子树根结点继续向上的最优方案，$g0[i]$ 表示以 $i$ 为根子树内方案且根节点不被占用，$g1[i]$ 表示以 $i$ 为根子树内方案且根节点被占用但不向外连链。通过这三个 DP 数组配合一定的加法及 max 操作即可完成转移。
考虑到不能够直接建出 DP 数组，可以使用动态开点线段树维护此数组第二维。合并时对于完整的不重叠子树标记区间加标记，对重叠的叶子结点进行转移合并即可。
G - 单峰数列
维护此数列的差分序列，对于查询单增单减，只需判断区间内是否均为正或者均为负。具体地，可以通过记录区间最大值最小值来完成上述查询。对于单峰查询，可以线段树二分出区间内最左侧的负数点，然后判断其左右是否分别均为负与均为正即可。
H - 比特跳跃
为了处理跳跃操作，我们可以建立一张新图，为每一个二进制集合状态维护入点与出点，在某一个状态对应的入点向出点连接一条对应代价的单向边，然后将所有入点对应集合单向连接至所有包含他的集合对应结点，对于所有出点对应集合连接至所有被他包含的集合对应结点。最后从源点开始跑单源最短路即可。
L - 死亡之组
签到题，模拟实现即可。
2024.07.29 Day8 陈佳鹏、于文阔、徐子恩 组队赛报告
提交情况（7 + 0）
赛题分析
C - 最优 K 子段
发现我们需要最大化最小值，考虑二分答案，对于二分阈值，要求每个不交子段和均大于此阈值即可。
考虑动态规划转移细节，令 $f[i]$ 表示 $i$ 前缀最多能够分配几个子段。发现 $f[r]$ 增加仅当存在一个对应的左端点 $l$ 满足 $f[l - 1] = f[r]$ 且 $[l, r]$ 区间和大于阈值且区间长度为质数。考虑对于所有满足 $f[l - 1] = f[r]$ 的左端点 $l$，以其前缀和作为权重加入 set 自小向大排序。每次枚举到 $r$ 时，按照 set 中权重增序枚举，直到找到区间长度为质数的区间，或区间和小于阈值。容易发现若枚举的区间满足区间和均大于阈值，其有较大概率满足区间和为质数，因此复杂度在期望情况下并不大，且随机性仅关系至运行时间，算法正确性始终保持正确。
D - 分组
首先可以考虑二分四个集合的权重的 min，以此作为阈值，要求四个集合的权重均不小于此阈值，在此条件下分配四个集合使得最大权重最小。可以考虑将四个集合分为两份，每一份包含两个集合，两份方案对称，因此我们只需要考虑单侧的情况。考虑设 $f[S]$ 表示使用集合 $S$ 内的元素分为两个集合，两个集合权重较大值最小是多少。发现可以枚举子集 $O(3^n)$ 实现转移。此做法时间复杂度 $O(3^n \times m)$。
考虑优化，发现题目刻意在异或和外增加权重数组，我们没有办法对异或和进行拆解，必须得到每个集合完整的异或和，因此枚举子集难以优化。考虑优化最小值二分。发现我们可以在枚举子集的同时完成最小值的枚举。考虑将所有集合按照其集合对应权重从大到小排序，依次枚举并加入每一个集合，加入一个集合时枚举其补集的子集，以此转移至包含它的一个集合。并且我们要求此补集的子集权重大于此子集，这样即可保证当前所有动态规划状态仅考虑到权重不小于当前集合权重的集合，即我们可以使用当前集合权重作为四个集合的最小值。更新一个动态规划状态时将它与它的补集取较大值更新总答案，即可完成总答案维护。总时间复杂度 $O(3^n)$。
F - 延时操控
考虑同时考虑我方角色的第 $i$ 轮移动与敌方角色的第 $i + k$ 轮移动，因为这两轮双方移动方法相同，此方法便于进行动态规划转移。令 $f[t][x][y][dx][dy][hp]$ 表示状态“进行 $t$ 轮后，我方位于 $(x, y)$，敌方相比于预计位置（在不被障碍影响情况下应当移动到的位置）两轴上相差 $dx$ 与 $dy$，且地方剩余血量为 $hp$”状态下的方案数，枚举四个移动方向转移即可。
当移动至某一步敌方死亡时，实际我方还剩余 $k$ 步需要移动，可预处理 $g[t][x][y]$ 表示移动 $t$ 轮，从 $(x, y)$ 位置开始的方案数，与上述方案相乘即可计算答案。
I - 昵称检索
可在正向与反向两个方向上为字符串构建序列自动机。
枚举所有的日期，从反方向进入自动机即可找到最靠右的可以匹配的后缀，在此位置加一。完成后进行后缀和即可计算出每个后缀可以匹配多少日期。
对于每一个可能的用户名，从正方向进入自动机，即可找到最靠左的可以匹配的前缀，取出剩余的后缀内可匹配的日期计入答案即可。
2024.07.29 Day9 陈佳鹏、于文阔、徐子恩 组队赛报告
提交情况（6 + 1）
赛题分析
A - 玲
容易想到一个贪心：预处理出每个堆需要二分查询的次数，从大到小排序，先从大到小整堆整堆询问得到在哪一堆中，确定在某一堆中后再在此堆中二分查询。发现能够被 hack，如 ${3, 1}$。
发现我们可以先按照先前的贪心方法，再通过在瓶颈处省去整堆询问而尝试让答案减小最多一。考虑判断答案能否减小一。我们考虑将所有堆按照二分查询次数分组，对于每一组，不难发现仅需要考虑最小的一堆是否构成瓶颈，构成瓶颈时是否需要省去整堆查询以减小答案。若构成瓶颈，则将此堆大小二进制表示最高位取出，将剩余部分按照其对应查询次数重新塞回至后面的堆中即可。
实现方面，为了去除时间复杂度中的 log，考虑使用 ST 表查询某一组内最小值位置。为了对二进制串进行大小比较，可以使用基数排序。发现直接建立 ST 表会导致复杂度再带 log，发现虽然 ST 表有很多，但长度和较小，考虑对每个组按照组内堆数大小建立 ST 表。但发现这样就无法直接将询问区间转化至某一组的元素标号区间，额外预处理每个组的前缀出现次数即可。
实现较为复杂，时间复杂度 $O((n + q) \times m)$。
B - 珑
- 当两个条件都存在时，除了 1x2 的情况，发现一定无解。
- 当不存在限制时，发现仅需总格子数量为偶数即可。
- 当仅存在长边限制时，发现仅有 1x2n 情况合法。
- 当仅存在短边限制时，发现能够组成除了 1xn 以外的任意情况。
分类讨论即可
E - 安
发现当 $a_i \neq b_i$ 时，一定是较大的一方能够存活。对于 $a_i = b_i$ 的情况，则是先手能够存活。因此只需要数出前者的数量，加上后者数量除以二上取整的结果即为答案。
H - 入
发现选取一条路径，且路径满足除路径上相邻点外无点对相邻即为满足条件。因此可以进行暴搜，搜索所有的路径，且记录当前路径相邻点的集合。发现度数大时单层搜索时间长但层数浅，度数小时搜索层数深但单层时间短，可以通过此题。
2024.08.01 Day10 陈佳鹏、于文阔、徐子恩 组队赛报告
提交情况（8 + 0）
赛题分析
A - Cake
考虑在第二步骤中 Oscar 会如何操作。发现他一定会选取一个最优的前缀，满足一在其中的比例最小，然后将蛋糕切成前缀长度那么多份，最终答案即为该比例。
因此我们先对树上每个点求出从根到它的零一串中的一的占比，然后对每个点进行前缀 max 求出每个叶子结点对应零一串的最终答案。然后再进行 DP，根据当前操作方选择孩子结点中最小或是最大的状态进行转移即可。
H - Genshin Impact's Fault
签到题，模拟即可。
I - Intersecting Intervals
考虑两层之间的转移，发现记录区间信息并不容易。但是发现两个区间有交必然代表存在至少一个纵坐标，满足其同时存在于两个区间中。考虑通过这个坐标完成状态转移。
令 $f[i][j]$ 表示已经完成了前 $i$ 行构造，且第 $i$ 行区间包含 $j$ 的最佳答案。从 $f[i][j]$ 转移至 $f[i + 1][k]$ 只需要考虑取出一个最大的包含 $[j, k]$ （假设 $j < k$，另一情况与此对称）的区间。发现我们只需要对这一行进行前缀和，然后取出 $k$ 右侧的最大值与 $j$ 左侧的最小值相减即可。将这两部分分开，便可以令 $j, k$ 独立，即可 $O(n ^ 2)$ 完成转移。
K - The Great Wall 2
考虑一个显然的暴力 DP：令 $f[i][j]$ 表示我考虑了前 $i$ 个元素，已经构成了 $j$ 个区间的最佳答案。考虑优化暴力转移。
发现转移过程中关心枚举出来的新区间的最大值与最小值，考虑使用数据结构维护此信息，但发现常数可能过大。考虑使用分治，每次分治先递归左区间，然后考虑左区间对右区间状态的影响，再递归右区间。由于跨过中轴的所有区间可以被分为一个左区间的后缀与一个右区间的前缀，可以预处理这两部分的最大值与最小值，然后取两者较大值与较小值即可获得此区间的最大值与最小值。转移时考虑分类讨论最大值与最小值分布在哪一侧的四种情况。发现对于某一种情况，若以增序枚举右侧某一个点，考虑可以转移至此点的左侧区间，发现其必然为一个左右端点向左移动的窗口，使用单调队列即可维护窗口内最大值。
时间复杂度 $O(n^2 \log n)$。
2024.08.02 Day11 组队赛报告
提交情况（9 + 1）
赛题分析
C - 捆绑魔方
大模拟，维护魔方方块的颜色与之间的连接状态，模拟六种旋转方式即可。必要情况下可以使用双向搜索。
F - 猫罐头游戏
发现最终情况一定为 1 1 1，此时先手败。发现若开场局势为三个奇数，则先手操作一次之后必然为一个偶数加两个奇数，后手可以再将其变为三个奇数，并最终变成必败局面。因此这种情况下先手必败。对应的，可以一步转化到此状态的一奇两偶和一偶两奇都是先手必胜状态。而三个偶数的情况，发现可以一步再转移到三个偶数情况，无法直接判断胜负。但发现第一次无法转化为三个偶数情况时，先手必败，即先前的操作必然为保持三个偶，也就是可以将它等效为三个数均除以二之后的结果，递归判断即可。
G - 猫咪军团
一个想法是我们可以在树上通过两只猫依次控制相邻的两条边，以此一步一步将狗逼入绝境。仔细思考后发现，我们可以为猫边的每一个连通块染色，然后观察一条树边的两个点所属连通块。若这两个连通块不同，则只需要每个连通块内留有一只猫，即可完成这两个点的控制；若这两个连通块相同，则观察是否有猫边直接连接这两个点，若是，则只需要一只猫即可同时控制这两个点，若不是，则需要两只猫分别控制这两个点。
以此就可以判断出每一个猫边连通块内需要放置一到两个猫，即可计算出最小答案。
K - 开关灯
发现可以通过每个位置操作奇偶性的零一串得出答案零一串。发现在大部分时候两者都是一一对应的。不过仔细观察会发现当总长度对三取模后余二时，存在一种情况满足反转一系列位置后答案零一串不变的情况，在此情况下对总答案额外除以二即可。
2024.08.02 Day12 组队赛报告
提交情况（8 + 1）
赛题分析
A - 造花（简单版）
删除树上一个点，然后判断其相邻的两个点能否作为菊花中心，或者其为度数为二的点且另一相邻点可以作为菊花中心。
B - 造花（困难版）
由于不保证连通，考虑对每一个能够作为菊花中心的结点计算菊花大小和。每次删除一个点，就更新其所有相邻的点的信息。另外需要特判大小为二的菊花。
I - 数字加减
考虑扫描线，使用 set 维护所有可以达到的区间。可以发现区间端点位置为与时间相关的一次函数，对于相邻区间，使用额外的一个 set 维护对应端点对应一次函数交点。当时间超过此交点时则合并这两个区间。另外对于插入操作，删除区间内的所有整段区间，并调整与区间有交的区间边界即可。总面积也为与时间相关的一次函数，可以使用所有右端点之和减去所有左端点之和求出。
2024.08.06 Day13 组队赛报告
提交情况（5 + 1）
赛题分析
A - Maximum Subarray Sum
动态规划，题解使用了一种扫描线的表述，但与下面的状态本质无任何区别：
令 $f[i][tot][rest][0/1]$ 表示前 $i$ 个数已经划分好方案，其中已经使用了 $tot$ 次交换操作，并且前面有 $rest (rest \in [-m, +m])$ 个位置还需要后面的区间外的数与之交换，且上一个位置是否被选中，的方案数。我们考虑将长度长于 $k$ 的区间的最后几个数，和不属于区间的数归类为“散点”，可以发现对于前缀 $i$，散点的数量一定为 $i \bmod k$，因此在此状态设计下，只需要限制散点数量为 $k - 1$ 的状态不能再新添加散点，以此转移出的所有状态均为合法方案。状态转移时对于散点，$O(1)$ 讨论是否选中与是否与区间内数交换；对于区间，$O(m)$ 枚举区间内交换出去的数的数量，配合预处理即可快速计算区间对应答案。总时间复杂度 $O(n \times m^3)$。
扫描线的表述：可以将 $n$ 个点逐行从上至下从左至右放置在一个宽度为 $k$ 的矩形中，最后一行的元素数量为 $n \bmod k$。考虑从左上角开始，仅用向右和向下的方式走到 $n$ 对应的点，容易发现这一条路径（即轮廓线）代表了一种方案，向右走即为令此点为散点，向下走即为令上一行的后缀和下一行的前缀组成长度为 $k$ 的区间，这一构造思路与上述动态规划状态设计本质完全相同，状态设计和转移过程也几乎没有区别。
H - Database
模拟即可。
需要注意对于尚未保存的工作的处理方法。可以对每行保存一个标记记录这一行是否为新建行，和是否为已经删除的行，并在下一次保存或者放弃时更新所有状态。
由于字符串总长度可能较长，直接比较字符串会导致超出时间限制，换为哈希比较即可。
I - Fight Against the Monster
签到题。二分答案，直接计算通过此起始数量能够创建出的总机器数即可。
2024.08.08 Day14 组队赛报告
提交情况（6 + 1）
赛题分析
D - Haitang and Uma Musume
大模拟，难点在于读懂题意，模拟即可。
E - Haitang and Math
我们可以枚举 $S(m)$，容易发现它的取值不超过 $108$，我们可以对 $n - 108 \sim n $ 中的每个数分解质因数，可能的答案一定存在于这些数中。可以直接 $O(T \sqrt n)$ 配合小常数通过，也可以使用区间筛等算法通过。
I - Haitang and Ranking （补）
发现我们就是要求 $a_i < a_j$ 且 $b_i < b_j$ 且 $c_i > c_j$ 的数对是否存在。可以先取出一维 $a$，按照这一维排序并重新标号，然后建立线段树。对于一个线段树区间，我们考虑所有跨过中心点的数对，再建立一棵关于 $b$ 的线段树，对于其上的结点 $[l, r]$ 维护外层线段树区间内满足 $b_i \in [l, r]$ 的左区间的 $c_{max}$ 与右区间的 $c_{min}$，合并时即可检查是否存在满足要求的数对。这样一个树套树结构可以在线维护题目所求的内容。
但是实现上容易出现时间和空间均超出上界的情况。我们可以将内外层线段树分离，令外层线段树先离线处理所有询问，即每一个结点维护其区间内所有修改。然后依次处理每一个线段树结点，使用内层线段树对这一个结点上的修改单独进行处理，并处理出 $1 \sim m$ 询问时间对应的该区间是否合法状态，使用差分与前缀和即可将所有区间的答案求交，即为最终答案。这样的写法可以使两个线段树平行，均不需要使用动态开点，避免了过多的内存占用，也优化了代码常数。
K - Haitang and Ava_2024
签到题，模拟即可。
2024.08.09 Day15 组队赛报告
提交情况（9 + 0）
赛题分析
E - Hold'em Shark
大模拟。可以将代码分为如下部分：
- 手牌分值计算：发现最终的排序规则即为，若两个数出现次数不同，则出现次数较多的值靠前；若两个数出现次数相同，则数值较大的值靠前。再加上题目中提到的特殊顺子判断，即可快速完成手牌的牌型识别和排序。
- 七选五：枚举所有情况即可。
- 剩余两张随机卡牌：枚举所有情况进行判断即可。
H - 循环图
观察范围可以发现显然是一个邻接矩阵的快速幂。
考虑计算出相邻两层结点之间的转移方案数，配合同一层内的转移方案数然后快速幂即可求出某一层的每个结点的对应方案数。再在矩阵中新开一个元素记录总和，通过前缀和差分的方式，结合边界处的枚举即可完成答案求和。
I - 关于 agKc 实在不喜欢自动化于是啥都自己合成这件事
发现每个点只有一条入边和一条出边。而需要合成的物品没有意义作为其他物品的原材料。因此物品之间的依赖关系形成一棵树。进行树形 DP 即可。
J - 故障机器人想活下去
签到题。贪心，对于一个前缀一定删去若干最大的怪物，单调队列即可。
K - 蛋糕上的草莓是蛋糕的灵魂
签到题，对于 $x$ 不是 $y$ 的倍数的情况，取最小的 $n$ 满足 $2 \times n \times x$ 是 $y$ 的倍数即可。
2024.08.12 Day16 组队赛报告
提交情况（7 + 1）
赛题分析
A - cats 的快乐 CF 刷题
比较两个题目 $i$ 和 $j$ 先后顺序对答案带来的影响，发现若 $a_i \times b_j > a_j \times b_i$ 则 $i$ 比 $j$ 先更优。我们发现题目之间存在逻辑上的结合律，即我们可以将多个连续操作的题目合并，通过相加他们的 $a$ 与 $b$ 并额外记录一个常数贡献。
发现双端队列同一侧连续的递增优秀的几个题目将不会被另一侧的操作打断，否则可以通过调整使得答案。因此可以对每一个前缀与每一个后缀维护一个优先队列，记录一个递减优秀的题目队列。发现此时取一个分界线，将两侧的队列中的所有题目取出按照优秀程度降序排列，贪心从前往后取的操作序列一定为一个合法的从两端取值的操作序列。
提前维护出相邻两个前后缀之间的单调队列变化情况，将所有历史上出现过的题目进行排序。枚举分界点时动态维护所有前后缀存在的题目，在树状数组上维护 $\sum_{i < j} a_i \times b_j$ 即可。
F - cats 的最小生成树
可以使用 Kruscal，从小到大枚举每一条边，对于每一条边判断出在第几张图中它的两个端点并不连通。我们可以为每一张图维护一个并查集，由 Kruscal 正确性可发现一定是一个前缀满足图中连通，因此二分第一个不连通的图，在这张图中加入这条边即可。
H - cats 的数据结构
考虑若我们只有一些连接至 1 的结点，构造将如何进行。根节点的答案为 $(n, n)$，孩子结点按编号从小到大依次为 $(1, n - 1), (2, n - 2), \dots, (n - 1, 1)$。考虑在结点分为多层时应该如何处理，对于一个大小为 $s$ 的子树，可以由根结点分配连续 $s$ 个编号给子树。但子树中的结点还需要与子树根结点形成包含关系，可以令子树根拥有这些 $a$ 和这些 $b$ 中的最大值，然后将剩下的值重新组合分给下层结点。以此构造方法递归构造即可得到答案。
J - cats 的集合 1
由操作 5 可发现需要使用 0/1 Trie 维护序列。对于操作 4，可以使用标记解决。对于操作 2 和操作 3，发现我们可以在结点上打标记记录哪些位已经被钦定，以及被钦定为了多少。令后一个标记优先级高于前一个标记，进行维护即可。当下传标记发现某一位被强制钦定为某一数，而两侧子树都存在，则对两侧子树进行暴力合并即可，发现复杂度不会出现问题。
2024.08.13 Day17 组队赛报告
提交情况（8 + 1）
赛题分析
B - Break Sequence
对于某一个位置，考虑左侧哪些位置能够转移到这个位置。发现对于每一个值，可能存在最多 $m$ 个区间禁止了一些点向该点转移。从左往右枚举每一个点，在转移之前更新所有当前位置对应值的区间，取出所有没有被区间覆盖过的位置的方案总和更新当前点即可。
D - Luner XOR
考虑枚举所有可能的 $a$ 方案，对每个方案快速维护出对应序列中零与一的数量。考虑将原序列塞入线段树中维护，一次对 $a_i$ 的修改会将线段树第 $i$ 层所有右子结点进行子树零一翻转，这样的结点数量为 $2^i$。因此我们考虑使用 DFS 自后向前枚举每一个 $a_i$ 的取值。发现对于 $a_i$，搜索一共会在线段树这一层上操作 $2^{n - i}$ 次，因此总时间复杂度为 $2^n \times n$。由于这样的搜索顺序只会从深向浅访问到所有线段树结点，因此线段树标记不需要下传。至于线段树结点信息上传，可以按编号从大至小依次枚举所有层数比修改结点高的结点进行信息上传。这样的结点数量与枚举修改的结点数量相同，不增加时间复杂度。
F - Minesweeper
发现一个结点的父亲结点在序列中的位置为它左侧第一个深度比他小的点。由此发现由根节点至某一点的路径可以表示为这一个点对应的前缀的一个单调递增单调栈。考虑使用线段树维护这一单调栈。可以在每个结点维护单调栈的长度、最小值、最大值、对应位置权值和信息，合并两个单调栈时用右侧单调栈的最小值在左侧区间二分答案找到分界点，取分界点左侧的单调栈与之相连即可。直接实现这一算法复杂度在 $O((q_1 + q_2) \log^2 n)$。
发现修改操作数量较多，且修改操作实际不会影响树结构，即在线段树结点信息上传信息时似乎不需要使用线段树二分重新寻找分界点。发现我们可以对每个区间记录，其两个孩子结点对应区间合并后左子区间单调栈剩余的前缀长度。当我进行区间加修改，修改完边缘区间后向上传递信息时，可以令每个区间记录“被修改更新的结点在单调栈中的序号区间”，上传时父结点即可得知其对应单调栈中有多少结点受到修改影响。以此便可 $O(1)$ 完成信息上传更新。最终总时间复杂度为 $O(q_1 \log n + q_2 \log^2 n)$。
G - Sticky Pistons
根据样例手推发现，两个过程均只需要每个位置尽可能推或者尽可能拉就可以完成。
I - Interesting Numbers
将数划分为两半后，对左侧讨论上界、下界、中间三种情况，在右侧对应取值即可。由于数值较大，可以使用 128 位整数配合二分求解根号值。
2024.08.15 Day18 组队赛分析
提交情况（7 + 2）
赛题分析
A - Surrender to My Will
签到题。模拟即可。
B - std::pair
签到题，对输入的类型字符串进行拆分，建立树形包含结构，对于询问直接查询即可。
G - TNT Run
发现我们可以沿一条横线或者竖线分开路径上某两个相邻的点，使得路径的两个部分为分开的两个螺旋。我们可以枚举这一被切开的位置，然后对两侧进行判断。由于其形状为旋转向内的螺旋，因此边数在 $O(\sqrt n)$ 级别，暴力跳跃每一条边复杂度可以接受。暴力判断时注意断边仅需要枚举下标为最小值或最大值的位置即可，以此可以省去大量无用判断。
I - Riffle Shuffle
考虑只执行一步时序列的形态，发现其由两个数值连续子序列穿插而成。再考虑执行两步时的序列形态，发现其由最多四个数值连续子序列穿插而成。考虑在数值连续子序列数量上考虑合并策略。
发现对于一个局面，我们可以取出所有极长数值连续子序列，按照起始值排序后取奇数项分为 A 类，偶数项分为 B 类，发现这样的操作可以让数值连续子序列数量除以二。因为考虑每个奇数项序列最终被放置在了数列的左侧，而它后面的相邻偶数项序列被放置在了数列的右侧，这两个序列在这次操作后会被合并为一个极长数值连续序列，因此数量除以二成立。
J - Doremy's Starch Trees
对于每个点，判断它在 Y 上每一个相邻点子树是否合法。可以在 Y 图上随便取一个欧拉序，然后将这一点在 X 上相邻的点的欧拉序插入 set，然后对每个子树进行区间查询即可。若有至少两个子树不合法，则无解；若无子树不合法则对答案没有限制；否则根一定在这一不合法子树内。对每一个结点得出的合法区间求交，即可找出所有合法根的位置。
Day19 2024.08.16 组队赛分析
提交情况（8 + 1）
赛题分析
A - 树异或价值
发现可以将结点深度拆分，将原求和式化为每个点子树内任意两点异或和之和。发现每一个二进制位互相独立，因此只需要计算一位二进制位时的答案，取位数次幂即可得到最终答案。为了最大化任意两个点的异或和之和，发现当子树内零一的数量相差至多一时答案最大。因此题目化为求每个点子树内零一数量相差至多一的构造方案数。
考虑动态规划记录每个点的子树内构造方案数，转移时只需要统计子树大小为奇数的数量，乘上组合数取出其中一半为零或一的方案数即可。
B - 树上询问
考虑如何判断一条链是否满足条件，可以为每个点赋予一个随机数权值，然后为每个点记录从根节点至这个点路径上的结点权值异或和。对于一条链，只需要将链两端结点的前缀异或和与 LCA 权值异或，即可得到路径上每个点的权值异或和。这一信息可以用支持区间异或，单点查询的线段树完成。另外再记录每个编号对应的结点的权值，使用前缀和差分即可得到编号在一个区间内的所有结点的权值异或和。比较两者是否相同即可。
考虑在一个询问中如何找到链的两个端点。我们可以再使用一个线段树，维护每一个编号对应的结点在树上的深度。我们只需要区间查询深度最大值便可得到链的一个端点，询问深度最小值便可得到链最高的位置。再使用总区间长度减去得到的这条链的长度即可得到剩余链的长度，可以以此计算出另一端点的深度。我们再为每一个深度维护一个 set，插入这一层内所有的结点编号，查找在答案范围内的另一结点即可（应为恰好两个）。
D - 亡语
发现每一个二类型亡语会让血量翻倍，而一类型亡语的攻击不升，因此一共会触发的死亡次数较少，模拟即可。
E - 怪物猎人
不妨令 $x < y$，先让双方轮流以 $y$ 伤害攻击怪物，恰好击杀怪物者为真。考虑另一人是否可能为真。另一人击杀怪物的时间不可能先于当前时间，考虑下一时刻另一人是否有可能击杀怪物。我们可以将之前的每次操作更换为 $x$，会使另一人攻击的怪物血量范围左移。且发现每次减小量不超过 $y$，因此一个完全在 $k$ 右侧的血量范围不会突然减小至完全小于 $k$。因此只需要判断全部更换为 $x$ 后总伤害是否小于 $k$ 即可，因为在此情况下，总有一个时刻另一人的攻击血量范围会覆盖 $k$。
G - 小猫钓鱼
考虑若一张手牌双方都有，则任意一方若打出这一张牌，另一方能够立刻打出相同的一张牌以取走这两张牌，并回到先手出牌局面，对先手不利。因此双方均不应打出双方都有的牌。
其余牌组成了双方手上的“对子”，且双方数量相同。先手打出一张之后另外一方也会打出其中一张，然后先手可以打出上一次打出的数字以让对方的“对子”数量减一，然后先后手互换，直至某人不再存在“对子”，这一方失败。由于双方的“对子”数量相同，因此在存在“对子”的情况下均为先手胜，否则先手败。
J - 收集签名
考虑树形动态规划，令 $f_{i, j, 0/1}$ 表示以 $i$ 为根的子树内，$i$ 至父结点连边被 $j$ 条路径经过（$j$ 可正可负，表示两种不同的方向，显然不会同时存在两个方向的路径）且 $i$ 结点是否被直接行走访问过。合并时只需要树形背包即可。
Day20 2024.08.18 组队赛分析
提交情况（7 + 0）
赛题分析
A - LIS
考虑将最长上升子序列长度转化为划分为下降子序列数量的最小值，并将问题所求的权重取反，即可得到问题：取 $i$ 条链，经过的结点权值和最大为多少。使用费用流即可解决此问题。
I - 不基本子串结构
若一个串在另一个串中出现至少两次，则一定无合法答案。否则两个串一定存在前后缀相同的情况，枚举位置并字符串哈希判断是否相同即可。
K - NOI2024
考虑所有排名不超过自己的人的分数均设为与自己相同，则为了最大化总分高于自己的选手，可以将每一场排在自己之前的选手数量之和累加，即可得到最大的名次，判断是否在总分线内即可。
Comments | NOTHING