💡

逆天记录 - 4

创建于 2023-10-09

Tags: 好题

CF1882E2 Two Permutations (Hard Version)

好题啊,E1 的构造已经让我想了好久了,E2 的第一步转化真的很妙!

需要最优化,首先考虑 dp,但是发现 dp 状态难以定义,所以需要对操作进行一些转化。

考虑在排列的开头加一个 00,标记整个排列的开头位置。当对位置 xx 进行一次操作时,等价于将位置 xx00 的位置进行交换。

操作完后,整个序列就是从 00 开始往后的数循环构成的排列,这样我们就完成了 O(1)O(1) 的交换操作,而且交换两个元素也比原题意的神笔操作正常一些。

由于 n,m2500n,m\le 2500,所以考虑枚举两个排列最后的形态(即 00 的位置),随后对于每一种最终状态。

对于一种对应的状态,对应点之间连边后,最少步数是去除所有一元环后,所有 00 不在的环的步数是环长 +1+100 所在的环的步数是环长 1-1。而如果要多一些步数去拟合另一个排列,可以操作 22 次。

将所有结束状态分为奇偶两类,对应的取 min\min 即可,构造方案是容易的。

感觉最为逆天的地方还是在于第一步加入一个 00 的转化,后面的做法还是较为套路的。

CF1879F Last Man Standing

这个题的意义在于让你突破思维定势,如果你被套路所局限,那么你终究只能度过一个相对失败的人生,,。

比较套路的想法是你对于每个 aa 进行上取整的整出分块,然后直接去扫描这 nAn\sqrt A 个分界点,时时维护最大值与次大值,但这种做法实现最优秀时复杂度也只能做到 O(nA)O(n\sqrt A),根本无法通过该题。

接下来尝试打破思维定势(其实这也是另一种套路吧),先去枚举 xx,随后枚举 ax\lceil\frac{a}{x}\rceil,这个枚举量是 O(AlogA)O(A\log A) 的,可以接受。

接下来,对于每个 ax\lceil\frac{a}{x}\rceil,可能成为最大值的只有可能对应区间内的 hh 最大的两个,但是这样就要求区间最大与次大,直接维护还是要带 log\log。如果我们把 larl\le a\le r 的条件弱化为 ala\ge l,然后对于 a>ra>r 的仍然当作现在枚举的 ax\lceil\frac{a}{x}\rceil 来算,发现并不影响结果,我们只需要在维护最大与次大时记录一个 idid,不要让最大与次大的 idid 相同即可。

这样,我们要求的问题转化为 ala\ge lhh 的最大与次大,这可以通过一个类似后缀 max\max 的操作来线性预处理。

至此,我们在 O(n+AlogA)O(n+A\log A) 的时间复杂度内解决了这个问题,突破了思维定势!

CF995F Cowmpany Cowmpensation

相比于前两题,就更像是一道套路的题目了,没有什么人类智慧难度。

考虑朴素的 dp,令 fu,if_{u,i} 为以 uu 为根子树内,uu 的点权 i\le i 的方案数。

考虑转移是什么,首先忽略 uu 填的值,那么就是将所有子树的 ff 进行点积,求出 gu,ig_{u,i} 表示 uu 子树内,所有儿子节点的点权都 i\le i 的方案数。

再考虑 uu 填什么,我们钦定每个 gu,ig_{u,i} 中,uu 的点权都选择 ii,这样不会算重,而 fu,i=jigu,jf_{u,i}=\sum_{j\le i} g_{u,j}

因此转移的本质是对一个点所有子节点的 dp 值进行点积,随后求一遍前缀和。

fu,if_{u,i} 看作一个函数(注意不是生成函数),即考虑 FuF_u,其中 Fu(x)=fu,xF_{u}(x)=f_{u,x}。容易发现每一次转移 FF 的度数会 +1+1,因此最终 FF 的度数 n\le n,因此只要记录 O(n)O(n)FuF_u 的值,就可以在计算答案的时候插值出 F1(d)F_{1}(d) 了。

ARC124E Pass to Next

考虑赋予 xi\prod x_i 实际意义,假设第 ii 个位置有 xix_i 个球,那么这个式子的意义就是每个位置选择一个球,选球的方案数。

先不考虑本质不同的方案,令 fi,0/1f_{i,0/1} 表示考虑了前 ii 个位置,最后一个位置是选择了自己原本的球 / 选择了上一个传过来的球的方案数。

此处,自己原本的球在往后传的过程中计算,上一个传过来的球在 i1ii-1\to i 的转移时计算。

那么容易列出转移方程:

[fi,0fi,1]×[x=0aixx=0aix(aix)x=0ai1x=0aix]=[fi+1,0fi+1,1]\begin{bmatrix}f_{i,0}&f_{i,1}\end{bmatrix}\times \begin{bmatrix} \sum_{x=0}^{a_i}x&\sum_{x=0}^{a_i}x(a_i-x)\\ \sum_{x=0}^{a_i}1&\sum_{x=0}^{a_i}x \end{bmatrix}=\begin{bmatrix}f_{i+1,0}&f_{i+1,1}\end{bmatrix}

此时还有两个问题:原问题是一个环 与 原问题 bb 相同的只算一次。

对于第一个问题,可以破环为链,然后枚举破环为链割开的点选了什么球来计算。

对于第二个问题,发现如果所有点都向后传了至少一个,那么每个都少传一个最终的 bb 是一样的,而如果有至少一个间隔没有往后传,那么一定没有另一个 bb 序列与之相同,因此只需要在 dp 时再记录一维 0/10/1 表示是否有一个间隔出现过没有往后传的情况即可。

AGC016F Games on DAG

首先发现两枚棋子其实是两个独立的游戏,我们对于每一个为起点放一枚棋子求出 SG 后,只需要 1,21,2 节点的 SG 值不同那么就是先手必胜。

如果一个点的 SG 值 =x=x,那么对于每个 y<xy< x 他必须向至少一个 SG 值 =y=y 的点连边,而不能像任何一个 SG =x=x 的点连边,对于 SG >x>x 的点,是否连边都行。

考虑从大到小分层确定每个点的 SG,令 f(S)f(S) 表示已经确定了 SS 点集的点相对 SG 值(因为我们是从大到小确定 SG 值的,所以并不能确定 SG 值具体是多少,但是最后一层 dp 到的点就可以看作 SG =0=0 的)的不同的连边方案。

转移时,枚举最后一层填 SG 最小 =x=x 的是哪个集合的点集,设为 ss,那么 t=Sst=S\setminus s 集合的点就是确定了的 SG >x>x 的点。

考虑转移的方案:

  • 对于每个 utu\in t 的点,都至少向 ss 中的点连一条边,方案是 2eus12^{\mid e_u\cap s\mid}-1
  • 对于每个 usu\in s 的点,都可以向 tt 中的点任意连边,方案是 2eut2^{\mid e_u\cap t\mid}

由于需要 1,21,2 的 SG 值不同,所以在转移时只需要保证 ss 中不能同时出现 1,21,2 即可。复杂度 O(3nn)O(3^n\cdot n)

AGC016E Poor Turkeys

发现如果想让一直火鸡最后生存下来,那么必然会牺牲一些火鸡,并且对于一只火鸡,如果他最后能生存下来,那么必须牺牲的火鸡是确定的。

对于每一只火鸡 aa,我们想让他最后生存下来,那么倒序考虑,时刻维护一个集合 S={a}S=\{a\} \cup 必须牺牲的火鸡集合。如果出现了一对 (x,y)(x,y),分如下情况考虑:

  • xS,ySx\in S,y\in S,那么两者在之后的操作中都是必须牺牲的或者就是 aa,但是这一次操作必须牺牲一个,所以直接导致 aa 不可能生存。
  • xS,y∉Sx\in S,y\not\in S,那么 xx 在之后操作中有用,这一次不能牺牲,所以 yy 只能牺牲,所以将 yy 加入 SS
  • x∉S,y∉Sx\not\in S,y\not\in S,那么这一次操作对于 SS 没有影响。

对于每一个火鸡 xx 求出 SxS_x 后,考虑如何判断两只火鸡 x,yx,y 能否同时生存,如果 x,yx,y 分别都有可能最终生存,结论是 SxSy=S_x\cap S_y=\emptyset。考虑证明:

  • 充分性:两者无交,所以每只火鸡最多只会影响到最终一只火鸡的状态,不会有重复,一定有解。
  • 必要性:考虑上述加入元素到 SS 中的过程,如果一对 (x,y)(x,y) 满足原来 xS,y∉Sx\in S,y\not\in S,导致 yy 加入了 SS,那么连一条从 yxy\to x 的有向边,死火鸡的过程其实等价于在这张 DAG 上不断删点,如果 SxSyS_x\cap S_y\not=\emptyset,那么最终一定会有至少一个点 uu 满足有 uvu\to vuwu\to w 两条边,且 vwv\not=w,那么两条边上都要让 uu 死一次,但是 uu 只能死一次,所以不合法,因此 SxSy=S_x\cap S_y=\emptyset

使用 bitset 维护每个 SxS_x,最后数数的时候暴力枚举即可,时间复杂度 O(nm+n3ω)O(nm+\frac{n^3}{\omega})

ARC117F Gateau

感觉没有铜牌难度啊。

首先考虑二分答案,暴力做法是破环成链,将每个限制转化为一段区间的和 \ge\le 某个值。考虑对前缀和做差分约束即可,时间复杂度 O(n2logA)O(n^2\log A)

考虑瓶颈在于每次都要使用 spfa 判断是否存在负环,我们希望能更快的判断负环。

观察到这张图其实就是上下两层,层间从下到上连边权为负的边,从上到下连边权为正的边,每个都都能往前连边权为 00 的边,第二层的头向第一层的尾边权为 00 的边,第一层的头向第二层的尾连边权为二分到的和的边。

负环的形态一定是如下三种之一:

  • 直接从一对上下的点走一个二元环。
  • 经过了从第一行头到第二行尾的边,此时一定是一个按照顺序上下交替的路径,起点和终点的方向没有限制。
  • 经过了从第二行头到第一行尾的边,此时一定是一个按照顺序上下交替的路径,并且头尾都是从上往下的路径。

对于第一种情况,可以直接判断,对于后面两种情况,可以 dp 求解最小值,判断其是否 <0<0,即可做到 O(n)O(n) 判断是否存在负环。

综上,时间复杂度被优化为 O(nlogA)O(n\log A)

P9746 「KDOI-06-S」合并序列

感觉是一道比较套路的题,但是我怎么没想出来。。。以下称 s[l,r]=i=lrais[l,r]=\oplus_{i=l}^r a_i

首先考虑区间 dp,令 fi,jf_{i,j} 表示区间 [i,j][i,j] 能否被操作成为一个数。发现转移一定是 [][][][\dots]\dots[\dots]\dots[\dots],其中三段 [][\dots] 都是能被操作为一个数的区间,且三段的异或和 =0=0,直接转移复杂度爆炸。

考虑减少枚举的位置,我们枚举第一个段的右端点,即第一个 [][\dots]]] 位置,假设该位置为 kk,那么第一段的异或和 =s[i,k]=s[i,k],我们要 check 是 (k,j](k,j] 能否找出两个合法的不交的区间,且第二个区间的右端点 =j=j,使得两个区间的异或和 =s[i,k]=s[i,k]

观察到一个性质,如果 [l,r][l,r] 内能找到两个不交的合法区间,第二个区间的右端点 =r=r,且两段区间的异或和 =s=s,那么对于 l<ll'< l[l,r][l',r] 一定也能找到。

所以考虑记 gi,wg_{i,w} 表示以 ii 为右端点,找到两段合法区间异或和 =k=k 的最右边的左端点,即一个 [][]\dots[\dots]\dots[\dots] 这样一个子结构的最右左端点位置。

那么在转移 ff 时只需要枚举 i,j,ki,j,k,然后判断 gj,s[i,k]g_{j,s[i,k]} 是否 >k>k 即可。此时 ff 的转移已经做到 O(n3)O(n^3) 了,但是我们仍然无法快速计算 gg

考虑再记录一个 hi,wh_{i,w} 代表寻找一个 ii 左边的区间,且这个区间异或和 =w=w 的最右边的左端点,即 [][\dots]\dots 这样一个结构,以 ii 为右端点,左边区间异或和 =w=w 的最右左端点。

那么在转移 gg 时,考虑枚举 [][]\dots[\dots]\dots[\dots] 种右边那个合法区间的左端点,即对于 gi,wg_{i,w},枚举 jj,那么 gi,whj,s[i,j]wg_{i,w}\leftarrow h_{j,s[i,j]\oplus w}

hh 是可以在求出 ff 后直接刷表更新的,综上所有 dp 数组的转移复杂度均为 O(n3)O(n^3)O(n2w)O(n^2w),注意一下转移顺序即可。

P6682 [BalticOI 2020 Day1] 染色

想了好久啊,感觉那个人类智慧的做法确实不好想。

朴素的想法是直接二分,每次先把位置移动到 11,然后往后移动 midmid 的距离,这样的询问次数是 2logn2\log n,无法通过,发现瓶颈在于每次想要二分一个值时都需要从 11 开始移动。

如果我们能够找到一种移动方法,使得每次无论二分到哪个值,都能够成功的走过这个距离,那么就能够做到 logn\log n 次询问了。

考虑极限情况,每次都往上二分,即 n2,3n4,7n8,\frac{n}{2},\frac{3n}{4},\frac{7n}{8},\dots 的情况。

接下来有一个非常人类智慧的做法,考虑倒序确定,假设最后会到达 11,那么倒序地左右交替跳,由于倒序情况下每次跳的长度都比上一次短,所以一定不会跳出界。

考虑如果有一次二分没有顶到上界,那么相当于整体的向左或向右平移,依旧并不会跳出界。因此我们可以直接跳来二分了,询问次数 logn\log n

CF1622F Quadratic Set

结论题也算逆天题嘛。。。可能这才是真的逆天吧!

首先考虑 nn 是偶数的情况,设 m=n2m=\frac{n}{2},那么有如下式子:

i=1ni!=i=12mi!=i=1m(2i1)!(2i)!=i=1m(2i1)22i=2mm!(i=1m(2i1)2)\prod_{i=1}^n i! =\prod_{i=1}^{2m} i! =\prod_{i=1}^m (2i-1)!(2i)! = \prod_{i=1}^m (2i-1)^2\cdot 2i=2^m\cdot m!\cdot(\prod_{i=1}^m (2i-1)^2)

  • 如果 mm 是奇数,那么删除一个 22,删除一个 mm 后,式子变成 2m1(i=1m(2i1)2)2^{m-1}\cdot(\prod_{i=1}^m (2i-1)^2),是完全平方数。
  • 如果 mm 是偶数,那么删除一个 mm 后,式子变成 2m(i=1m(2i1)2)2^m\cdot(\prod_{i=1}^m (2i-1)^2),是完全平方数。

因此对于 nn 为偶数是,答案 n2\ge n-2,而对于 nn 是奇数,再删掉一个 nn 可以变为 nn 是偶数的情况,因此答案 n3\ge n-3

接下来就比较套路了,对于每一个质因数随机一个 hash 值,做异或哈希,对于删除 0,1,20,1,2 个数是容易判的,删除三个数的直接构造即可。复杂度 O(nlogn)O(n\log n)

Powered by Hexo, theme by Facter