2024.3 训练记录

3.17（模拟赛）

100+45+30=175 rk12/54

A

考虑拆点跑二分图最大匹配，左侧连向右侧的一条边就相当于在原图中选择两个有边的点相邻，然后就可以算出答案了。

注意特判只有一个孤立点且其他部分能够完全匹配的情况，此时答案需要再 \(-1\)。时间复杂度 \(O(Tm\sqrt n)\)。

B

这种简单题咋就差一步没做出来呢？

发现所有工作最后的情况都可以规约到两种上，一种是完全不删，另一种是删到正好到工作时间结束，这样能把下一个也进行工作。容易归纳这样是最优的，剩下的金币直接从后往前删就行了。

这样就可以 dp 了，设 \(f_{i,j}\) 表示前 \(i\) 个工作，用了 \(j\) 个完整的区间到达下一个区间的起点的最小金币数量。\(g_{i,j}\) 表示到达下一个区间恰好进入休息时刻的最小金币数量。转移预处理下一个结束在休息时间的工作，枚举这个工作的两种状态分别进行转移。最后求答案的时候枚举每一个满足 \(i\) 不存在下一个结束进入休息时间的工作 \(f_{i,j}\) 和 \(g_{i,j}\) 来更新答案。时间复杂度 \(O(Tn^2)\)。

赛时除了正确的两个规约我还规约了第三类是全删掉，这样恰好就没法 dp 了，唐。

C

首先有一个显然的 \(O(n^2)\) dp。经过一些物理公式推导之后，对于 \(i\) 转移到 \(j\)(\(i>j\))。对于 \(u_j^2+2h_j\geq v_i^2+2h_i\) 时，第 \(i\) 个人以最大速度扔出去，用 \(f_i-v_i+\sqrt {v_i^2+2h_i-2h_j}\) 更新 \(f_j\)，否则第 \(j\) 个人用最大速度接住小球，用 \(f_i+u_j-\sqrt {u_j^2+2h_j-2h_i}\) 更新 \(f_j\)。

对于第二种转移，可以看做一个以 \(u_j^2+2h_j\) 为自变量的函数 \(g(x)=a-\sqrt {b+x}\)，分类条件对应定义域，这种通过平移得到的函数可以通过李超树维护，李超树每次插入线段并查询最值，时间复杂度 \(O(n\log^2 n)\)。

对于第一种转移，同样看做一个 \(g(x)=a+\sqrt {b+x}\) 的函数形式。但是此时限制条件和定义域变成了两个相对独立的维度。所以需要使用线段树套李超树或者 cdq 分治，时间复杂度 \(O(n\log^3 n)\)，常数小的 cdq 能过。

注意到定义域这个限制并没用，第一类转移所有插进来的查询的时候，只要满足限制条件，都是可以用来更新的。也就是所有查询的自变量都在以前插入进来的函数的定义域以内。所以李超树变成了全局插入。但是此时还和全局插入有一些区别，因为虽然查询点在定义域内，但是并不是全局都在定义域内。所以插入时会比较到一些无效节点。具体来说是对于一个点 \(x\)，所有编号 \(\geq x\) 的函数是有效的。对于这种情况，我们需要对于每个李超树节点，记录编号 \(>mid\) 的最优函数，如果没有再记录编号 \(\leq mid\) 的函数。手玩一下发现这样确实每个点都能取到最优答案。时间复杂度 \(O(n\log^2 n)\)。

3.18（题单）

AGC017C

智慧题。手玩一下，如果当前有 \(x\) 个球，\(x\) 节点上挂了 \(c_x\) 个球，那么就连一条从 \(x\rightarrow x-c_x\) 的边。如果从 \(n\) 到 \(1\) 联通就有解。一次修改相当于把一个线段长度 \(-1\)，一个线段长度 \(+1\)，所以答案就是没被覆盖的部分的长度。时间复杂度 \(O(n+q)\)。

qoj3276

乱搞题。有一个结论是对于随机序列，连续的正负相同的前缀和个数是 \(O(\sqrt n)\) 级别的。如果正负改变显然丢掉一半更优。所以可以暴力扫一下这 \(O(n\sqrt n)\) 个区间，将其中是前缀最大值的元素加入考虑，不是前缀最大值就说明有一个长度比他小且答案比他大。打表发现是前缀最大值的个数是 \(O(n)\) 的。跑二维数点就能过 \(70\) 分，再随便剪剪枝就能过 \(q=1\) 的那个包了。

qoj3047

这个经典套路竟然是第一次见到。建出第一棵树的点分树。对于点分树上每个节点，考虑他点分树上的子树，在第二棵树上建出这些点的虚树，虚树每个节点挂一个叶子表示在第一棵树上距离分治中心的距离。然后对虚树求出直径之后对每个点求答案即可。时间复杂度 \(O(n\log^2 n)\)。

另一种做法是考虑每个节点在两个点分树上的一对祖先，对于每个节点数量是 \(O(\log^2 n)\) 的。与他距离最近的节点一定是在其中一对祖先上统计贡献的。所以对每对祖先求出最小值和次小值，然后统计答案即可。时间复杂度 \(O(n\log^2 n)\)。为了卡空间需要先枚举第一棵树上的分治中心，把空间复杂度降到 \(O(n\log n)\)。

gym102268D

拟阵题。用拟阵相关知识证明按照收益从高到低对区间进行排序，然后贪心依次尝试插入就是最优的。

考虑判断能否插入。考虑 Hall 定理，记 \(sum_i\) 表示前 \(i\) 个点的点权和，\(pre_i\) 表示前 \(i\) 个区间选择的个数。那么对于任意 \(i<j\)，需要有 \(sum_{r_j}-sum_{l_i-1}\geq pre_j-pre_{i-1}\)，移项之后用两棵线段树维护即可。每次加入一个区间就是在 \(pre\) 数组上后缀加，需要维护区间最大最小值。时间复杂度 \(O(n\log n)\)。

3.19（USACO2024 Open Pt）

A

赛时只写了 \(10\) 分的暴力，这种情况下尽量让所有长度相同。剩下的不会，出了题解补。

T1 原来是签到，那我不是得分与难度完全成反比。

建出 01 trie，发现充要条件是不能有祖先关系。对于一个节点\(x\) 上的东西，有两种转移方式，一种是对于叶子结点 \(y\)，新建两个分支，原来的节点挪到一个上，现在这个点挪到一个上，贡献为 \(dep_y-dep_x+2\)。另一种转移是对于只有一个儿子的节点 \(y\)，放到他的另一个儿子位置，贡献为 \(dep_y-dep_x+1\)。用小根堆来维护合法的转移，启发式合并即可，时间复杂度 \(O(|S|\log^2 n)\)，常数很小，可以通过。

B

我怎么调了三个小时才调出来啊？

首先试图想了一些 \(\text{poly}\log\) 的做法，胡了一个 \(O(n\log^3 n)\) 的神秘做法 WA 但没有 TLE，然后发现是个假做法。

考虑分块。每 \(B\) 个一块，设 \(L_i,R_i\) 为这一块的左端点和右端点。对于每个块，尝试预处理出来每一个值经过这一块之后变成什么。发现如果朴素实现是 \(O(n^2)\) 的，所以需要发现一些性质。

设 \(mx_i=a_{L_i-1},mn_i=a_{R_i}\)，首先观察到除了最开始的 \(x\) 之外的情况 \(x\) 基本都是 \(\leq mx_i\) 的，又注意到如果 \(mx_i-mn_i+1<x<mn_i\)，这一块内的操作一定是加减交替出现的，所以这种情况就不需要预处理了，只需要记录一个前缀和数组即可。那么需要预处理的部分的个数就是 \(O(mx_i-mn_i)\) 级别的了。由于 \(a_i\) 单调不增，对于每个块这个东西的和是 \(O(n)\) 级别的。所以预处理部分的时间复杂度就是 \(O(\frac{n^2}{B})\) 的。

对于查询，先一直加或者减，直到下一个不再是加减，找到这个位置之后。散块暴力整块去查询，就可以了，时间复杂度是 \(O(q(B+\frac{n}{B}))\) 的。

但是这样会在 #6 #19 #22 三个点挂掉，事实上，进入块的 \(x\) 并不一定是 \(\leq mx_i\) 的，如果前面出现了一个位置 \(p\) 满足 \(a_p-\sum_{k=p+1}^{L_i-1} a_k>mx_i\)，那么来这个位置的就可以 \(>mx_i\)。我们将这种情况叫做特殊情况，其他叫做正常情况。那么对于一个块全都是特殊情况的话，这一个块所有数的加减是一样的。全是正常情况用上面的预处理信息查询。只有出现特殊情况向正常情况转变的话，我们就暴力处理，但是这种情况的出现概率很小，只有在块的交界处恰好出现了 \(a_i>2a_{i+1}\) 的情况才可能出现，并且最多出现 \(O(\log n)\) 次。最坏时间复杂度就是 \(O((n+q)\sqrt n\log n)\) 的。但是出题人并不知道块长，也就无法把所有特殊情况都卡在交界处。所以只需要随机扰动一下块的边界（其实不扰动出题人也不好卡），就是严格正确的 \(O((n+q)\sqrt n)\) 的复杂度了。

C

赛时设计了一个暴力的状压 dp，设 \(f_{i,s}\) 表示当前人在 \(i\) 个激活点，\(s\) 集合内的段内有机器人的最小答案，知道了 \(f\) 就可以知道机器人的位置。

转移枚举人下一步去哪，再枚举机器人转动几个单位之后激活一个新机器人，需要一些细节的计算。时间复杂度 \(O(2^Rn^2R)\)，期望得分 \(40\) 分。正解回头补。

哈哈，最难的题是 T2，这下真数据结构学傻了。考虑相对运动，假装机器人不会动，人和激活点都会有一个顺时针的基础速度，然后人再自己决定一个速度。然后设 \(dp_{s,i}\) 表示 \(s\) 集合内有了机器人，人在第 \(i\) 个机器人的位置上的最小答案。转移枚举下一个位置，然后二分找到第一个过来的激活点，时间复杂度 \(O(2^RR^2\log n)\)。

发现可以先不二分，\(dp\) 数组里先记录过来的时间（不需要等待的），容易发现这个越小等待后也越小，然后最后再二分找激活点即可，时间复杂度 \(O(2^RR(R+\log n))\)。

3.20（题单）

CodeChef XYHUMOQ

\(|S|\leq 32\)，考虑折半，对于前一半求出形如 \(101010\) 和 \(1010101\) 的有多少个，后一半求出形如 \(101010\) 和 \(0101010\) 的有多少个。打表发现最多有 \(1597\) 个。

然后记录下来之后要满足一个形如 \(a_1b_2+a_2b_1=m\) 的形式，对于每组 \(a_1,a_2\)，再枚举 \(b_2\)，\(b_2\) 只有 \(1597\) 种，然后求出 \(b_1\) 即可。时间复杂度不知道，可以过。

qoj5071

网格图是二分图，将所有左部点的颜色反转，合法矩形等价于全是 \(B\) 或者全是 \(W\) 的矩形。考虑每个矩形的左上角，建立一个二分图，左部图表示全选 \(B\)，右部图表示全选 \(W\)，将不能同时合法的点连一条边，用全局减去最小割就是答案，割掉表示就不让他做出贡献。

然后最小割求一下方案就行了，时间复杂度 \(O(Tnm\sqrt {nm})\)，可以通过。

CF48F

傻逼卡常卡精度题。

卡精度可以用一个 long long 存证书，一个 long double 存小数部分。

卡常要注意 sort(a+1,a+m+1,[&](node x,node y){return x.v<y.v;}); 的常数比 sort(a+1,a+m+1,cmp) 小一倍。

qoj3039

猜了个结论缩点之后 SCC 个数不会很多。所以缩点之后把所有 SCC 找出来，预处理出来两两之间可达性。每次询问枚举所有 SCC 判断是否在路径上。时间复杂度不知道，可以过。

正解不会，回头补。

ARC100F

正难则反，首先如果不考虑限制条件，那么答案就是 \(k^{n-m}(n-m+1)\)，考虑容斥掉不满足限制条件的序列带来的贡献。对于 \(a\) 序列进行分类讨论。

\(\text{Case 1:}\)

\(m\geq k\)，且 \(a\) 序列中存在满足限制的部分。

这种情况下需要容斥掉的数是 \(0\)。

\(\text{Case 2:}\)

\(m<k\)，且 \(a\) 序列中两两不同。

考虑一个神仙的转化，发现无论 \(a\) 序列长什么样都无所谓，所以我们需要统计的是所有不合法串中长度为 \(m\) 的满足条件个数，最后再除以 \(A_k^m\) 即可。

设 \(f_{i,j}\) 表示填了 \(i\) 个数，当前最长的两两不同的后缀长度为 \(j\) 的方案数，\(g_{i,j}\) 表示出现过长度为 \(m\) 的次数。转移分为两种，填一个没出现的数，\((k-j)f_{i,j}\rightarrow f_{i+1,j+1}\)；或者填一个已经出现过的数，\(f_{i,j}\rightarrow f_{i+1,p}(p\leq j)\)。\(g\) 的转移类似，同时如果 \(j\geq m\) 将 \(g\) 加上 \(f\) 即可。用简单的前缀和优化即可做到 \(O(nk)\)。

\(\text{Case 3:}\)

其他情况，即 \(a\) 中有相同元素。考虑枚举一个 \(a\) 序列的出现位置，那么条件转化为 \(a\) 序列两边不出现长度为 \(k\) 的互不相同的序列。所以可以对两边进行类似于 \(\text{Case 2}\) 的 dp，这时候只需要 dp 方案数了。注意到这里初值不再是 \(0\)，而是包含了 \(a\) 序列的一个前后缀。最后合并是卷积卷起来。时间复杂度 \(O(nk)\)。

3.22（模拟赛）

25+60+20=105 rk13/36

A

神秘题，被狠狠过河卒了。将未确定看做 \(2\)，然后逐位暴搜。如果交换的两位都是 \(2\)，那么初始 \(01\) 和 \(10\) 交换完是等价的。所以会变成两种状态 \(00\) 和 \(11\)。如果有一个是 \(2\)，那么交换完 \(2\) 的位置会发生变化。如果都不是 \(2\) 直接交换即可。

分析一下复杂度，每分两个分支会减少两个 \(2\)，所以复杂度是 \(O(2^{\frac{n}{2}}m)\) 的，但是要写递归不要写 vector 实现的迭代，会被卡常。

B

其实是简单题，但是冲了一场 A，没来得及写。

首先可以用线段树求出来每个线段左右端点正上方和正下方的第一条线段，然后发现每个线段能到他的线段就是找到他一直向上跳覆盖左右端点的线段，然后合并线段，直到有一个完全覆盖当前线段的线段。答案就是这个类似于梯形的图形中的线段数量。

考虑维护这个东西，先对于每个求出来那个完全覆盖当前合并后线段的位置，发现就是能到他的里面左边界最靠左的一个上面的一条线段，拓扑排序一遍预处理出来。然后可以通过倍增跳到那个位置，同时用差分处理出来贡献。对于处理贡献，每次贡献的是一个矩形内的线段，二维数点即可解决。然后用倍增预处理父亲节点和到父亲节点的权值，最后查询的时候倍增跳到覆盖他的线段即可。时间复杂度 \(O(n\log n)\)。

C

太困难了。

3.24（模拟赛）

100+55+10=165 rk8/34

A

容易观察到最后形式是 \((a_i-x)2^x\)，而 \(a_i-x\) 是偶数的情况都可以用更小的 \(a_i\) 和更大的 \(x\) 来表示。所以每个 \(a_i\) 能产生的贡献就是 \(\frac{a_i}{2}\) 个数，所以可以用 \(O(\sqrt n)\) 的复杂度求出第一问。

设每个 \(a_i\) 出现了 \(c_i\) 次，那么可以用 \(O(\log n)\) 的复杂度求出来 \(x\times 2^y\) 的排名，其中 \(x\) 是奇数。只需要枚举 \([y-\log n,y+\log n]\) 范围内的计算这一组有多少在他前面，剩下的要么全在要么全不在。然后就可以二分找到第一行满足 \(1\times 2^y\) 的排名在所求的数前面的，然后同理答案位置也只会在这周围 \(O(\log n)\) 行内，对于每一行二分就可以做到 \(O(q\log^3 n)\)，不知道能不能过。但是由于知道上一行的位置之后，下一行只需要检验 \(O(1)\) 个位置，所以复杂度为 \(O(\sqrt n+q\log^2 n)\)，可以通过。

B

其实想到了类似的思路，但是没有找到真正正确的方案就放弃了去想一些 cdq 状物去了。最后 50min 狂拼 6k 暴力。

先考虑 \(k=1\) 的部分，可以用重链剖分的 dfs 序，将每条重链的链顶标记。然后对于非标记节点 dfn 序即可。然后再 dfs 一遍，遍历到每个点的时候加入它所有标记的儿子。这样的话，对于二操作，操作的是一个区间和 \(O(1)\) 个单点，三操作是标记和非标记对应的两个区间，四操作是 \(O(\log n)\) 条重链和 \(O(\log n)\) 个单点。复杂度 \(O(n\log^2 n)\)。

对于 \(k\leq 10\) 的情况，类似的标记每条重链前 \(10\) 个节点。然后第二次 dfs 遍历到每个点加入所有子树内距离它为 \(10\) 的标记点。对于操作二，可以转化为 \(O(k)\) 个 \(S_{u,k}\) 表示 \(u\) 子树内到 \(u\) 距离为 \(k\) 的点集合。对于每个 \(S_{u,k}\)，标记点一定是一个区间，非标记点只有一个，复杂度单次 \(O(k\log n)\)。对于三操作，前 \(10\) 层的标记节点用 \(S_{u,k}\) 来处理，其它层的标记节点一定是一个区间，非标记节点一定也是一个区间，复杂度单次 \(O(k\log n)\)。对于四操作，跳重链，对于链顶的 \(10\) 个标记节点暴力处理，其他的正常重链剖分，复杂度 \(O(k\log^2 n)\)，总时间复杂度 \(O(qk\log^2 n)\)，常数很小，可以通过。

C

有点神秘的 dp 题。有结论：合法矩形的充要条件是除去全零的行列之后，一定可以分成四块，左上全 \(1\)，右下全 \(0\)，剩下两部分也合法。充分性显然，必要性就手玩一下，反正 OIer 不需要证明。

然后这样就可以进行一个二维的区间 dp，设 \(f_{l1,r1,l2,r2}\) 表示这个矩形的答案，然后枚举划分位置转移，时间复杂度 \(O(n^6)\)。

发现转移只需要从右下角 \(0\) 的阶梯位置转移，非阶梯位置一定是不优秀的，所以转移复杂度变成 \(O(n)\)，总时间复杂度 \(O(n^5)\)。

再观察一下，左下角矩形合法等价于下方两个矩形的并合法，右上角矩形合法等价于右边两个矩形的并合法，因为右下角全是 \(0\)。所以状态可以简化为所有右下角矩形，为 \(O(n^2)\) 个，总复杂度为 \(O(n^3)\)。

3.26（题单）

ARC105F

条件等价于导出子图是一个联通二分图。先不考虑联通的条件，如果只考虑二分图，那么可以枚举左部点，然后答案就是 \(2^{左部点与右部点连边数量}\)。对于每一个集合计算这个东西，记为 \(g_s\)，精细实现复杂度可做到 \(O(3^n)\)。

然后考虑处理联通，容斥，设 \(f_s\) 表示 \(s\) 集合内联通且是二分图的方案数，那么枚举编号最小的节点所在的集合 \(t\)，有 \(f_s=g_s-\sum f_tg_{s\oplus t}\)。总时间复杂度为 \(O(3^n)\)，可以通过。

qoj5070

先将网格图左部图的点颜色反转，那么就是不能用 \(2\times 2\) 同色联通块。考虑 bfs 一遍，推出一些可以推出来点的颜色，如果出现矛盾那么无解。

这时候可能没有全部染色完，但是不能继续染色了。如果出现这种情况，容易发现，因为每一个都可以是任意颜色，所以将一个点随机染色是不影响结果的。所以一旦出现这种情况，可以随机染色一个点，然后用现在情况去推出一些点的颜色。重复这个过程直到出现矛盾或者全部染色完毕。时间复杂度 \(O(Tnm)\)，可以通过。

gym102331H

差一点想出来，还是菜了。

首先显然是凸的，可以 wqs 二分并单调队列优化 dp 做到 \(O(nq\log n)\)，平凡的。因为有区间操作，还可以比较容易的想到一个做法，用线段树维护每个节点对应区间的 dp 值。设 \(dp_{0/1,0/1}\) 表示左边是否贴边界，右边是否贴边界的 dp 值。建树时 pushup 就是合并两个凸函数，用闵可夫斯基和实现，如果中间的两个区间靠在一起下标要 \(-1\)。查询的时候就闵可夫斯基和合并 \(O(\log n)\) 个区间的函数值，合并方式相同，这么做时间复杂度分析出来是 \(O(nq)\) 的，但是由于带着 \(4\) 倍大常数过不去，我独立思考也就想到了这些。

上面两个做法结合起来就是正解了。建出线段树，用闵可夫斯基和得到每个区间的凸函数，这部分的复杂度是 \(O(n\log n)\) 的。然后查询的时候，先进行 wqs 二分，二分一个斜率。然后去线段树对应的 \(O(\log n)\) 个区间上二分出来这个斜率会截到凸函数的哪个位置，然后只需要合并这些区间截出来的 dp 值而不是整个凸函数。注意还是需要维护两个表示是否贴右边界的 dp 值来合并下一个区间。时间复杂度 \(O(n\log n+q\log^3 n)\)，可以通过。