A2OJ Ladder 21 简要题解

https://earthshakira.github.io/a2oj-clientside/server/Ladder21.html

只记录 Difficulty level >= 8 的。有很多题是口胡的。写了的会标注提交记录。还有些很久以前写过的题就懒得搬提交记录了。

71. CF444E DZY loves planting

我们二分答案，然后可以这样转化：把权 \(\ge d\) 的边全部切掉，需要然后需要使得 \(i,p_i\) 不在同一连通块。如果所有连通块大小都 \(\le n/2\) 那么显然可行；否则考虑最大连通块，如果其余连通块的 \(\sum x\) 要比这个连通块的 size 小那么肯定不行，否则一定可行。

https://codeforces.com/contest/444/submission/232029798

72. CF536D Tavas in Kansas

首先注意到和图的关系不大，我们分别求出每个点到 \(s,t\) 的最短路，排序后就可以直接 DP 了。\(f(i,j)\) 表示 S 已经选了距离它前 \(i\) 近的，T 已经选了距离它前 \(j\) 近的，S 先手。\(g\) 同理。考虑转移。\(f(i,j)=\max -g(k,j)+p(k+1,i)\)，其中 \(p(l,r)\) 表示 \([l,r]\) 中距离 T \(> j\) 的点权和。于是我们在固定 \(j\) 时，可以轻松借助单调栈求出所有 \(f(i,j)\)，求 \(g\) 同理。复杂度 \(O(n^2)\)。

73. CF605E Intergalaxy Trip

考虑对于 \(i\)，设其临边的点按 \(f\) 排序为 \(a_1,\dots,a_m\)，则有 \(f_i=\sum_j (1+f_{a_j})e_{i,a_j}\prod_{k<j}(1-e_{i,a_k})\)，其中 \(a_m=i\)。把 \(f_i\) 项的系数移到左边，就是一个式子了。考虑如果我们每次能保证用 \(f_i\) 最小的点去更新其它点，那么 \(f_i\) 这个式子只会往后面填上一项，并且更改 \(f_i\) 项的系数。于是我们每次找到 \(f_i\) 最小的点，显然它不会再被更新了，用来更新别的点即可。

https://codeforces.com/contest/605/submission/232024752

74. CF407D Largest Submatrix 3

考虑先钦定上边界，然后下边界往下扫，维护每列的 \(l_i,r_i\) 表示若要包含这列，那么必须满足 \(L\ge l_i\)，\(R\le r_i\)，然后就可以对右边界扫的时候维护一个单调队列。暴力更新 \(l_i,r_i\) 逃不掉求前驱后继的 \(\log\)。考虑上边界从下往上扫，然后每次考虑上边界往上挪后对每行的所有列的 \(l_i,r_i\) 的贡献，发现可以做到 \(O(n^3)\)。

https://codeforces.com/contest/407/submission/232016115

75. CF455D Serega and Fun

可以考虑分块。每个块用一个双端队列维护块内的值，然后每个块再维护一个桶。

但是这题可以 polylog。考虑维护一个维护原序列的 treap，和一个对于每个值都维护这个值的这些点的 treap，构成一个平衡树森林。然后我们每次问询，需要在 \(k\) 代表的平衡树上分裂出一段区间，满足这段区间在原序列上位于 \([l,r]\)。查在原序列的位置可以直接在第一个 treap 上查。

76. CF484E Sign on Fence

一种整体二分的方法：考虑离散化后整体二分，然后每一个分治层相当于维护一个 01 序列，从左往右不断把一些位置的 0 变成 1，求区间最长连续段。这是双 log 的。

EI 的单 log 做法：考虑把 \([ l,r]\) 的最大值 \(f_{l,r}\) 形成的表格画在坐标系上。于是这个表格应该是一个由若干个矩形拼成的45°的直角三角形，然后每次查询一个斜线段上的最大值。考虑把坐标轴变换，让问询变成水平的线段，那么现在修改就变成了一堆左右边平行于y轴的平行四边形。考虑把平行四边形切成两个三角形+一个矩形，或两个三角形+一个上下边平行于x轴的平行四边形。矩形直接做，平行四边形再把它变换成矩形后直接做，三角形考虑分别统计问询线段经过直角边，经过斜边和被包含的情况。单 log。

77. CF321E Ciel and Gondolas

首先考虑暴力 DP。\(f(i,j)\) 表示前 \(i\) 个分成 \(j\) 段。首先我们可以仔细分析拥有决策单调性，所以通过整体二分复杂度降为 \(O(nk\log n)\)。但是实际上由于这是二维 DP，决策关于 \(i,j\) 都是递增的，所以可以 \(O(n^2)\) 做。

还有，答案关于 \(k\) 是凸的，所以也可以 wqs 二分，结合决策单调性的整体二分可以做到 \(O(n\log^2 n)\)。

78. CF568D Sign Posts

考虑一些性质：对于一个点，如果它被 \(k+1\) 条直线经过，那么它必选；任意 \(k+1\) 条直线形成的交点中，必有一个点被选。利用这个性质，进行转移。并且在转移的时候，对于选出的 \(k+1\) 条直线的形成的交点中，选出被经过次数最多的优先去转移。并且进行一个微小的记忆化，对目前剩余的直线以及目前的 \(k\) 进行哈希然后记忆化。在有解的时候跑的飞快。

ps. 这题 CF 上数据十分水… 把其中的一些数据的前 \(30\) 条直线拉出来，能卡掉洛谷题解区的所有解。

https://codeforces.com/contest/568/submission/232054523

79. CF285E Positions in Permutation

考虑二项式反演，然后把排列变成二分图匹配的形式。现在我们需要钦定一些点满足第 \(i\) 层的点匹配第 \(i-1\) 层的点。可以直接 DP：\(f(i,j,0/1,0/1)\) 表示前 \(i\) 层配了 \(j\) 个且第 \(i\) 层的左右部分别有没有配。然后再二项式反演即可。

https://codeforces.com/contest/285/submission/231948437

80. CF547E Mike and Friends

一个不好的方法是建出广义后缀树后直接线段树合并。更好的做法：建 AC 自动机，离线后把问询拆成对于 \(s_1,\dots,s_r\)，\(s_x\) 出现了多少次。考虑对 \(r\) 扫描线，每次把 trie 路径上的点 +1，然后问询就是 fail 树上子树和。

81. CF461D Appleman and Complicated Task

首先我们可以发现这个现实很严。更进一步地，只要确定了第一行，那么剩下的都能全部确定。考虑用第一行来表示剩下的格子上的数。设第一行的格子的值为 \(x_1,\dots,x_n\)，那么我们可以发现某一个格子一定是一段同奇偶的连续 \(x_i\) 的异或和。于是我们设 \(x\) 的前缀异或为 \(s\)，那么限制就可以描述成 \(s_i\oplus s_j=0\) 或 \(s_i\oplus s_j=1\)。用并查集即可。

https://codeforces.com/contest/461/submission/231912114

82. Stairs and Lines

怎么看都可以直接轮廓线吧…复杂度看上去是 \(O(2^nn w)\)，但是感觉常数挺小的啊。

如果 \(w\) 更大一些呢？处理出上一列轮廓线为 \(s\) 到下一列轮廓线为 \(t\) 的转移系数，然后矩阵快速幂。

83. CF494C Helping People

首先离散化后，相当于长 \(O(q)\) 的序列，然后有 \(q\) 次操作。由于操作区间不交，所以可以搞出 \(O(q)\) 个区间使得每个区间都包含或者等于一个操作区间。\(f(x,y)\) 表示对于区间 \(x\)，最大值恰好为原先区间最大值 \(+y\) 的概率。转移是容易的。

84. CF494D Birthday

把平方拆开后暴力各种分类讨论。/tuu

85. CF477D Dreamoon and Binary

考虑 DP：\(f(r,l)\) 表示截至到 \(r\)，最后一个分割的串为 \(S[l,r]\)，最小分段数。然后我们在 \(r\) 处尝试更新所有以 \(r+1\) 为起点的 \(f(x,r+1)\)。具体而言，\(f(x,r+1)\) 可以由 \(S[l,r]\le S[r+1,x]\) 进行转移，于是我们可以用单调栈加速转移。比较两个数可以用 trie 进行预处理。求答案暴力比较所有的 \(S[i,n]+f(n,i)\) 即可。

86. CF487D Conveyor Belts

考虑对于线段树上每个区间 \([l,r]\)，处理出数组 \(v\)，其中 \(v_j\) 表示如果从 \((l,j)\) 出发，那么最终会跑到什么地方。容易发现这是可以简单合并与修改的。复杂度 \(O((n+q)m+(Cm+q)\log n)\)。

https://codeforces.com/contest/487/submission/231889491

87. CF505E Mr. Kitayuta vs. Bamboos

二分答案 \(d\)，然后倒过来做。倒过来相当于一开始每个都是 \(x_i=d\)，然后第 \(t\) 轮需要保证 \(x_i\ge t\times a_i\)，然后选 \(k\) 次加 \(p\)，并希望最终能 \(x_i\ge h_i+m\times a_i\)。于是我们贪心，维护每个元素存储 \(x_i\) 最紧急的要求是，在往后的 \(r_i\) 轮之内需要加 \(w_i\) 次 \(p\)。这些条件最终都会被满足，于是我们肯定是优先选择 \(r_i\) 最小的进行加。

88. CF601E A Museum Robbery

动态背包。看上去没有什么更好的解法，只能硬线段树分治。复杂度 \(O(nk\log n)\)。

89. CF512D Fox and Travelling

这题的操作方式相当于剥一度点，于是能剥的点一定形成一个森林。于是我们对森林做树形 DP，\(f(i,j)\) 表示 \(i\) 子树剥掉 \(j\) 个点的方案数，合并类似于 EGF 卷积。环上挂着的相当于有根树，非环上的相当于无根树。无根树要钦定一个最后一个选的点作为根。最后要除掉选根的贡献。所以总复杂度 \(O(n^3)\)。

90. CF258D Little Elephant and Broken String

考虑这样的 DP：\(f(i,x,y)\) 表示对于两个数 \(p<q\)，它们一开始位置在 \(x,y\)，那么在经过了 \([i,m]\) 的这些操作后，最后 \(p,q\) 形成逆序对的概率。那么转移就很方便，从 \(i+1\) 到 \(i\) 只会更改 \(O(n)\) 个位置的值。所以总复杂度 \(O(n(n+m))\)。由于和 AGC30F 是几乎一样的，就放 AGC30F 的代码了，因为 AGC30F 有取模，我喜欢取模不喜欢小数。

https://atcoder.jp/contests/agc030/submissions/47373650

91. CF547D Mike and Fish

考虑转化为图论模型。把每行每列看作点，每一个整点看作一条边，把染色看作定向。由于是二分图，所以可以对于每行，入边为蓝；对于每列，出边为蓝。由于最多差一，于是意味着偶数时必须相等，可以想到欧拉回路。允许差一的限制表示每个奇点可以再连一条人为加的边出去。由于奇点数一定为偶数，所以一定可以连成一个欧拉图。然后跑欧拉回路，给边定向，即可。

92. CF484C Strange Sorting

这个 d-sorting 没有什么性质，考虑直接做。考虑令对区间 \([1,k]\) 的置换为 \(P_1\)，那么我们现在希望求得对 \([2,k+1]\) 的置换 \(P_2\)。即原本 \(x\to y\) 要变成 \(x+1\to y+1\)。可以理解为 \(x\to x-1\to y-1\to y\)，于是 \(P_2=(2,\dots,n,1)\circ P_1 \circ (n,1\dots,n-1)\)。令 \(Q=P_1\circ (n,1,\dots,n-1)\)，则全部结合起来可以得到最终总的置换 \(P\) 为 \(Q^{n-k+1}\circ (n,1\dots,n-1)^{n-k+1}\)。然后就做完了。

https://codeforces.com/contest/484/submission/231938693

93. CF555E Case of Computer Network

考虑边双联通分量一定可以定向为一个强连通分量。于是我们边双缩点后，就转化为了一棵树，然后需要进行定向使得 \(s_i\) 可以到达 \(t_i\)。这个是 Trivial 的，树上差分即可。

94. CF521D Shop

首先对于每个数，一定是先赋值，再加。赋值一定只需要保留最大的，于是就可以转化为加。加一定是优先加最大的，所以对于每个数的加，把它从大到小排序后，一定是从前往后去选，于是就可以转化为乘法。然后就全是乘法了，就做完了。输出方案的时候需要注意一下细节。

95. CF559E Gerald and Path

考虑一个性质：我们把所有没有实际贡献的线段删掉后，每个区间最多被两个线段覆盖，否则一定可以进行调整。然后考虑离散化后进行一种 DP：\(f_{i}(j,k)\) 表示第 \(i\) 段被 \(j,k\) 覆盖（\(j<k\)，若只被覆盖一次那么 \(k=0\)，没有被覆盖则 \(j=k=0\)），前 \(i\) 段中被覆盖的最大长度和。我们发现每次转移实际上从 \(f_{i-1}\) 转移过来只会修改 \(O(n)\) 个位置的值，并且除 \((0,0)\) 外全局加 \(x\)。后面那个我们稍微修改一下状态，变为没被覆盖的最短长度和，就只需要在 \((0,0)\) 处加 \(x\) 了。总复杂度 \(O(n^2)\)。

https://codeforces.com/contest/559/submission/231741031

96. CF536E Tavas on the Path

树剖板板题。考虑离线，按 \(l\) 排序。然后我们就是单点修改，然后树剖维护题目中说的这个东西即可。可能代码会比较复杂一些。

97. CF288E Polo the penguin and lucky numbers

考虑把每个数的贡献拆在其 LCP 处算。按高位往低位 DP。对于 LCP 的贡献，DP 时记录平方和即可；LCP 后面一定是 7444... 和 4777...，统计个数以及 LCP 之和即可。

https://codeforces.com/contest/288/submission/230933609

98. CF364D Ghd

考虑每次选一个数，有 \(1/2\) 的概率这个数在答案集合中。然后假设已经钦定了包含数 \(x\)，我们令 \(b_i=\gcd(a_i,x)\)，那么我们就需要对于每个 \(d\mid x\) 求 \(d\mid b_i\) 的个数。写一个 dfs 做迪利克雷前缀和即可。复杂度 \(O(T(n\log n+d_nw_n\log n))\)，其中 \(T\) 取 \(10\) 即可。但是感觉后面那个用暴力求不会差太多。

https://codeforces.com/contest/364/submission/231584365

100. CF590E Birthday

本质上题目是让我们在子串偏序关系中选出一个最长反链。于是我们建 AC 自动机，然后对于每个 trie 上节点找到 fail 树上第一个有串的祖先，连边后再 floyd 求传递闭包即可得到偏序关系。然后就是最长反链了。

https://codeforces.com/contest/590/submission/227682207