GDOI 2021 赛前个人练习及集训简要记录

口胡集锦。

往年省选泛做

愿意写代码的会单独分裂出文章。

2019

ZJOI

Done.

HNOI

D1T1

Done.

D1T2

Done.

D1T3

Done.

D2T1

高妙图论题。
明天就搬到提高组模拟里。

考虑一个暴力:从长度为 1/2 的回文串开始跑 DP,时间复杂度 O(m2)
总体基于二分图的优美结构,因为在二分图上任意走动并不改变路径长度的奇偶性。

对于同色连通块,如果其为二分图,则随便保留一棵生成树即可;否则保留一棵生成树后任意连一个自环以改变奇偶性。
对于连接不同色的边,一定为若干二分图的组合,类似地保留一棵生成树即可。
这样边数就降到了 O(n),时间复杂度 O(n2)

D2T2

Done.

D2T3

考虑最优解一定是划分成若干个区间,将 B 的区间内所有数改为 A 区间内的平均值,在单调的前提下区间长度尽量小。

证明来了。
这是典型的保序回归问题。

引理 1

如果强制要求 B 的所有数相同,那么这个数一定是 A 的平均数。

证明

问题即最小化 f(x)=ni=1(Aix)2。直接对其求导得 f(x)=2ni=1(Aix)=2[ni=1Ainx]

显然当 x=1nni=1Aif(x)0,且容易验证其为最小值。

引理 2

对于 1i<n,如果 Ai>Ai+1,那么最优解中一定满足 Bi=Bi+1

证明

若最优解中 Bi<Bi+1,令 ϵ>0 为一个实数,满足令 Bi=Bi+ϵ,Bi+1=Bi+1ϵ 后不影响大小关系。那么有 (BiAi)2+(Bi+1Ai+1)2(BiAi)2+(Bi+1Ai+1)2=2ϵ(AiAi+1)+2ϵ2<0

因此将 Bi,Bi+1 调整到 Bi=Bi+1 时更优。

做法

没有修改时用单调队列维护即可。带修改的话,考虑在数据结构上二分出修改点的前后分界线即可。

时间复杂度 O(nlog2n)

SNOI

D1T1

简单串题。
明天就搬到普及组模拟里。

考虑如何快速比较串的大小。
对于 si,sj (i<j),实际上只需要考虑 i,i+1 的 LCP 即可。
这显然相当平凡。直接求后缀有多少个位置满足其与后一个字符相等即可。

时间复杂度 O(nlogn)

D1T2

首先容易把 T 的范围缩减到 1012 级别。
根据经典结论,对于 E={(i,(i+P)modQ)0i<Q} 的图,可以划分为 gcd(P,Q) 个环,大小为 Qgcd(P,Q)
然后提前预处理一下每个环上的贡献,再枚举 ai 计算对应贡献。

D1T3

巧妙的优化建图题。
暴力 O(n2) 的建图费用流就不提了。
优化建图自然考虑分治一类的结构,但是绝对值并不好处理。
考虑经典套路,将权值排序之后利用相邻排名的权值之间的差累计出绝对值。
这样就把边数降到了 O(nlogn) 级别。

这题要写代码。
(支线任务:一些奇怪的费用流算法。)

D2T1

憨批麻将题。
随便矩乘一下,略。

D2T2

好像是 NB 阴间搜索,爬了。

考虑在空格移动的过程中,容易将这个空格的状态改为目标状态。但是不在空格移动路径上的木块就并没有归位。
因此搜索时主动去寻找周围没有归位的木块即可。

D2T3

显然点数越多越好,于是考虑枚举连通块直径的中点统计答案。
感觉上是个阴间长链剖分 DP,爬了。

(支线任务:长链剖分。)

十二省联考

D1T1

Done.

D1T2

阴间优化建图。
太平凡了就不口胡了。

D1T3

懂的都懂。

D2T1

分别讨论阵营和派系即可,对有限制的学校再另外 DP。

D2T2

Done.

D2T3

……

GXOI/GZOI

D1T1

拆位之后单调栈计算全 0/1 矩阵个数。

D1T2

Done.

D1T3

由于特技总是在固定的位置发生并被观测到,所以这部分的代价是固定的。并且特技发生的次数也是固定的……所以其实重点并不是最优化问题。

事实上只有两种可以达到最值的策略:交换次数最多和最少。具体哪个是最大值哪个是最小值取决于 a,b 的大小关系。
交换次数最多只需要全部交换即可,因为交点实际上就是逆序对。
交换次数最少则考虑将初始到最终状态的置换 p 循环分解,交换次数就是 nc(p),其中 c(p)p 的循环个数。

然后计算一下哪些点会被嘉宾观测到。随便算个交点然后转一下坐标,扫描线一下就好了。

D2T1

简单矩乘题。
明天就搬到普及组模拟里。

如果不存在 1×1 的块,那么显然就是斐波那契数列。
如果存在,考虑若第 i 列放了一个,那么在 1i2 列都可以放,并且这两块之间的列的方案是唯一确定的。
因此有 DP 式 fi=fi1+fi2+2i3j=0Fj

其中 Fj 是斐波那契数列。
矩阵快速幂即可。

D2T2

首先是 naive 的标算。
枚举二进制位将关键点分组,建图跑出点集到点集的最短路即可。

然后是少一个 log 的做法。
建图跑出每个点与哪个关键点最近,正反都要跑。然后枚举边计算贡献即可。
可以证明能取到最优解。
懒得胡了(

D2T3

Done.
经典套路题。

SDOI

D1T1

Done.

D1T2

考虑一个垃圾 O(nc2) DP。
f(i,x,y) 表示前 i 列,第 i 列的两个颜色分别为 x,y 的方案数。
是不是一点用都没有。

然后考虑优化掉一个 c
当第 i 列有被钦定的颜色时,只需要记另一个颜色即可。
对于没有被钦定的颜色的块,考虑一起转移。
预处理一个转移的系数即可。发现这部分状态数很少,只有 5 种本质不同的状态。

然后剩下的 4%,观察一下我们的 DP 在干什么。
你会发现这和你在 D1T1 里做的事一致,贺过来改几下就行了。
不过没脑子选手上线段树也是很资瓷的。

D1T3

对每个前缀维护 MST 上最左端和最右端的点的虚树,边权为原树上路径最大值。
合并时只需要考虑这些点和新的一列点的 MST。
xjb 乱搞,但我实在写不出来(
复杂度 O(n(m+q)logn)

D2T1

神仙构造!
明天就搬到提高组模拟里。

i 次操作时从图中选择一个度数最小的点 ai,将其及相邻的点删去,设这一次操作删掉了共 bi 个点。
t=argmaxbi,则选取第 t 次及以后删除的点为热闹的聚会,{ai} 为尴尬的聚会。

那么有 p=bt1。并且两个条件都是显然的。

D2T2

发现是阶梯博弈。xjb 拆个位 O(nmlogn) DP 一下。
不过可以优化到 O(m2logn) 乃至 O(mlogmlogn),咕了(

D2T3

考虑 T.M. 的另一种生成方式:从 0 开始,001,110
考虑反向模拟这个过程,然后以此对答案 xjb 记搜即可(

JSOI

T1

2-SAT。
明天就搬到提高组模拟里。

(i,t)0/1 表示 it 时刻是死是活。
那么「难兄难弟」可以表示为 (x,t)0(y,t+1)0(y,t+1)1(xt)1,「死神来了」可以表示为 (x,t)1(y,t+1)0(y,t+1)1(xt)0
同时还有任意 (i,t)0(i,t+1)0(i,t+1)1(i,t)1

不过这样点数过多,不太行。
t 离散化一下就完事了。
然后会发现它本身就是 DAG,不需要缩点。

然后对所有 (i,T+1)1,看它能否到达 (i,T+1)0,如果可以那么 i 就太悲催了……
否则看它能到达多少 (j,T+1)0

然后上 bitset,可惜空间不允许。所以分个块 S
时间复杂度 O(n(n+m)ω),空间复杂度 O(nSω)

隔壁 w33z 有一个相关的题来着。

T2

Done.

T3

根据 Significant Suffixes 的相关理论,一个串 u{argminvsuf(u)vwwΣ} 的大小是 O(logn) 级别的。
然后暴力维护集合即可(我试图跳过证明看这部分的做法,然后翻了无数篇题解都没有详细说咋维护……),具体方式和以上结论的证明相关。

然后跑出 Z 函数就可以求答案了。

BJOI

D1T1

思博题。
明天就搬到提高组模拟里。

ln exp 一发,然后变成经典分数规划,xjb 二分一下,AC 自动机上 DP 一下,完事。

D1T2

首先乱搞出递推式,然后解出通项,令 fn=Aαn+Bβnn 对应的填充方案数。
然后 rn=l(fnk)=1k!rn=lfk_n=1k!rn=lki=0(1)ki[ki]fin=1k!rn=lki=0(1)ki[ki](Aαn+Bβn)i=1k!rn=lki=0(1)ki[ki]ij=0(ij)(Aαn)j(Bβn)ij=1k!ki=0(1)ki[ki]ij=0(ij)AjBijrn=l(αjβij)n

枚举 i,j,扩域等比数列求个和即可。

D1T3

咕咕咕。

D2T1

Done.

D2T2

咕咕咕。

D2T3

咕咕咕。

膜你赛

2.27

T1

非完美口胡。

首先所有字符串的结尾一定只有两种字符,令它们分别为 a,b。若有第三种就显然无解。
a,b 为首尾的方案是对称的,先考虑 a 为首的情况。
假设有两个字符串 p1bs1a,p2as2b,那么结果应当形如 as1p1b,ap2s2b,但其中只有 s1,s2 的结果是确定的,p1,p2 内部的顺序并未确定。
于是同位置总有一部分是确定的,那么对着确定的部分逐一匹配,胡乱处理即可(
(并不会实现……)

T2

非完美口胡。

令给定的集合为 SaiiS 中出现的次数,siai 的前缀和。
考虑 35% 的暴力:排序后暴力选择 k 个位置钦定为 1n 链上的点,其余部分贪心地赋予父亲。
下称这 k 个位置为选择点,其余在树中的点为未选择点。

容易知道对于一个树中的点,有解当且仅当 si1i1。对于一个非选择点,有解当且仅当 si1i(因为在它之前必然有至少一个选择点)。
从而 si1=i1i 必然是选择点,于是可判断无解。
其余部分类似地贪心地作为选择点,然后在剩下的位置中贪心选择前 k 大的边权即可。

T3

非完美口胡。

不妨设 n=22k,x=2k
在测试数据中几乎是这样,不是的 xjb 调整一下就好了(雾

考虑系数模 2 的多项式 a,b,c,d (ab,cd),若有 a3b3=c3d3ab=cd,容易导出 ab=cd
由于 a+b=c+dab=cd,可知 a,b,c,d 均为 x2(a+b)x+ab 的解。但是由基本代数知识得其至多有两个解。
因此 {a,b}={c,d}

从而考虑对 1i<2k,拼接 i,i3 成为一个数。不过有一个问题就是 i3 可能超过范围,但是根据一些近世代数知识,只需要在模一个 k 次的既约多项式意义下作乘法即可,因为这会形成一个域。

3.6

T1

长剖经典题 & 原题。
略。

T2

n=9n,则 i29n10i1=i2n10i1=i2j1n10iji2j1n10ij

这个东西算一下贡献发现是一个差卷积,FFT 或者龟速乘 + 大模数 NTT(答案大概是 9l2 级别?)。
然后,然后,然后,出题人说随机情况下误差比较小,大胆毛估估一下保留前【数据删除】位就可以了……然后上一个 long double。

T3

如果把 piargmin1jiapibpj 连一条边,会得到一棵树。
然后会发现是个最小树形图。
字典序最小?逐位确定。

Related Issues not found

Please contact @Alpha1022 to initialize the comment