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
标签:submission,contest,题解,Ladder,codeforces,https,A2OJ,com,考虑 From: https://www.cnblogs.com/TetrisCandy/p/17822576.html