口胡集锦。
往年省选泛做
愿意写代码的会单独分裂出文章。
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)=n∑i=1(Ai−x)2。直接对其求导得 f′(x)=−2n∑i=1(Ai−x)=−2[n∑i=1Ai−nx]
显然当 x=1nn∑i=1Ai 时 f′(x) 取 0,且容易验证其为最小值。
引理 2
对于 1≤i<n,如果 Ai>Ai+1,那么最优解中一定满足 Bi=Bi+1。
证明
若最优解中 Bi<Bi+1,令 ϵ>0 为一个实数,满足令 B′i=Bi+ϵ,B′i+1=Bi+1−ϵ 后不影响大小关系。那么有 (B′i−Ai)2+(B′i+1−Ai+1)2−(Bi−Ai)2+(Bi+1−Ai+1)2=−2ϵ(Ai−Ai+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)∣0≤i<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 循环分解,交换次数就是 n−c(p),其中 c(p) 为 p 的循环个数。
然后计算一下哪些点会被嘉宾观测到。随便算个交点然后转一下坐标,扫描线一下就好了。
D2T1
简单矩乘题。
明天就搬到普及组模拟里。
如果不存在 1×1 的块,那么显然就是斐波那契数列。
如果存在,考虑若第 i 列放了一个,那么在 1…i−2 列都可以放,并且这两块之间的列的方案是唯一确定的。
因此有 DP 式 fi=fi−1+fi−2+2i−3∑j=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=bt−1。并且两个条件都是显然的。
D2T2
发现是阶梯博弈。xjb 拆个位 O(nmlogn) DP 一下。
不过可以优化到 O(m2logn) 乃至 O(mlogmlogn),咕了(
D2T3
考虑 T.M. 的另一种生成方式:从 0 开始,0→01,1→10。
考虑反向模拟这个过程,然后以此对答案 xjb 记搜即可(
JSOI
T1
2-SAT。
明天就搬到提高组模拟里。
令 (i,t)0/1 表示 i 在 t 时刻是死是活。
那么「难兄难弟」可以表示为 (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 的 {argminv∈suf(u)vw∣w∈Σ∗} 的大小是 O(logn) 级别的。
然后暴力维护集合即可(我试图跳过证明看这部分的做法,然后翻了无数篇题解都没有详细说咋维护……),具体方式和以上结论的证明相关。
然后跑出 Z 函数就可以求答案了。
BJOI
D1T1
思博题。
明天就搬到提高组模拟里。
ln exp 一发,然后变成经典分数规划,xjb 二分一下,AC 自动机上 DP 一下,完事。
D1T2
首先乱搞出递推式,然后解出通项,令 fn=Aαn+Bβn 为 n 对应的填充方案数。
然后 r∑n=l(fnk)=1k!r∑n=lfk_n=1k!r∑n=lk∑i=0(−1)k−i[ki]fin=1k!r∑n=lk∑i=0(−1)k−i[ki](Aαn+Bβn)i=1k!r∑n=lk∑i=0(−1)k−i[ki]i∑j=0(ij)(Aαn)j(Bβn)i−j=1k!k∑i=0(−1)k−i[ki]i∑j=0(ij)AjBi−jr∑n=l(αjβi−j)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
非完美口胡。
令给定的集合为 S,ai 为 i 在 S 中出现的次数,si 为 ai 的前缀和。
考虑 35% 的暴力:排序后暴力选择 k 个位置钦定为 1…n 链上的点,其余部分贪心地赋予父亲。
下称这 k 个位置为选择点,其余在树中的点为未选择点。
容易知道对于一个树中的点,有解当且仅当 si−1≥i−1。对于一个非选择点,有解当且仅当 si−1≥i(因为在它之前必然有至少一个选择点)。
从而 si−1=i−1 的 i 必然是选择点,于是可判断无解。
其余部分类似地贪心地作为选择点,然后在剩下的位置中贪心选择前 k 大的边权即可。
T3
非完美口胡。
不妨设 n=22k,x=2k。
在测试数据中几乎是这样,不是的 xjb 调整一下就好了(雾
考虑系数模 2 的多项式 a,b,c,d (a≠b,c≠d),若有 a3−b3=c3−d3 且 a−b=c−d,容易导出 ab=cd。
由于 a+b=c+d 且 ab=cd,可知 a,b,c,d 均为 x2−(a+b)x+ab 的解。但是由基本代数知识得其至多有两个解。
因此 {a,b}={c,d}。
从而考虑对 1≤i<2k,拼接 i,i3 成为一个数。不过有一个问题就是 i3 可能超过范围,但是根据一些近世代数知识,只需要在模一个 k 次的既约多项式意义下作乘法即可,因为这会形成一个域。
3.6
T1
长剖经典题 & 原题。
略。
T2
令 n′=9n,则 ∑i≥2⌊9n10i−1⌋=∑i≥2⌊n′10i−1⌋=∑i≥2⌊∑j≥1n′10ij⌋≈∑i≥2∑j≥1⌊n′10ij⌋
这个东西算一下贡献发现是一个差卷积,FFT 或者龟速乘 + 大模数 NTT(答案大概是 9l2 级别?)。
然后,然后,然后,出题人说随机情况下误差比较小,大胆毛估估一下保留前【数据删除】位就可以了……然后上一个 long double。
T3
如果把 pi 和 argmin1≤j≤iapi⊕bpj 连一条边,会得到一棵树。
然后会发现是个最小树形图。
字典序最小?逐位确定。