2020 湖南省大学生程序设计竞赛(HNCPC)题解

题目来源

A. 2020-substring

签到题。设dp[i]为[1~i]的串有多少个连续2020，如果s[i-3,i]是“2020”那么dp[i] = max(dp[i-1], dp[i-4), 否则dp[i] = dp[i-1]

B. 2020-vs-2018

观察可以发现只要看有多少个被o包围的联通快即可。3个联通快就是2018否则是2020

C. absolute-difference-equation

这题里面的差分取绝对值运算，其实相当于是异或运算。那么可以把每一次变换后的结果写出来观察一下 $a1,a2,a3,a4.....an$ $a1\ast a2,a2\ast a3,a3\ast a4.....$ $a1\ast a{2}^2\ast a3,a2\ast a{3}^2\ast a4...$ 这里$\ast$表示异或。那么最终化为一个数字的时候，$a_i$的贡献是$C_{n-1}^{i-1}$次异或。当它为奇数的时候才算有贡献。 因此我们判断每个位置的组合数的奇偶性，并且判断有多少个$?$是贡献奇数次，有多少个$?$贡献偶数次。如果没有贡献奇数次的$?$，最终结果无法改变，如果最终结果是0那么方案就是0，否则是$2^{偶数?的个数}$ 否则答案是$2^{偶数?+奇数?-1}$

D commutive-string-pair

当s1 + s2 = s2 + s1的时候，意味着他们拥有相同的最小循环节。用kmp求出最小循环节然后哈希判断一下即可。

E make-roundgod-very-happy

这题考虑每个位置i的a[i]作为最大值可以掌控的区间为[ L[i], R[i] ]，其中[ L[i],i-1 ]的每个值都小于等于a[i]，[i+1,R[i]]的每个值都小于a[i]。L[i], R[i]可以用单调栈得到 a[i]贡献的区间一定是右端点 >= i且 <= R[i], 左端点 <= i 且 >= L[i]的区间，且区间长度 len <= a[i]-m 画图来看一下： 如图，对于[i, t]这些右端点来说，[L[i], i]的所有点都可以作为它们的左端点，因此i对它们的贡献都是x，而从t开始，对t+1,t+2,…的贡献是x-1, x-2, x-3… 也就是对一段区间加上一个等差序列。这个操作可以通过二次差分来实现。 然后这题就结束了。最后把差分数组还原回来即可。

F mixed-radix-ntt

可以分治来求解这个问题。 要求的是$f(w^0),f(w^1),f(w^2)...f(w^{n-1})$ 让$f_1(x)=a_0+a_2{w}^2...a_{n-2}{w}^{n-2}$ $f_2(x)=a_{1}w+a_3{w}^3...a_{n-1}{w}^{n-1}$ 那么$f(w^i)=f_1(w^{2i})+w^i{f}_2(w^{2i})$ 而$f(w^{i+\frac{len}{2}})=f_1(w^{2i+len})+w^{i+\frac{len}{2}}{f}_2(w^{2i+len})$

因为题目给出条件$w^n=1(modp)$，所以在第一层显然有$w^{len}=1(modp)$ 所以$f(w^{i+\frac{len}{2}})=f_1(w^{2i+len})+w^{i+\frac{len}{2}}{f}_2(w^{2i+len})=f_1(w^{2i})+w^{i+\frac{len}{2}}{f}_2(w^{2i})$

用快速幂算出$w^{\frac{len}{2}}$即可同时求出$f(w^i)$和$f(w^{i+\frac{len}{2}})$

而区间减半后的长度 = len/2, w = w^2，相当于递归子问题中依然满足$w^{len}=1(modp)$的条件，因此子问题可以用同样的方式向下递归 递归的终点是$len为奇数的时候$，此时无法按上述方法进行分治，但是由题目条件可得len为奇数的时候只可能是3，所以这个时候直接暴力求解即可。 复杂度$O(nlogn)$ 实际上，也可以在第一层分成3等份，每一份长度就都是2的次幂了，此时可以使用蝴蝶变换进行非递归求解，常数更小一点。 代码（用叉姐的数据生成器得到的数据对拍通过）

#include<bits/stdc++.h> #define ll long long #define pb push_back #define lowbit(x) ((x)&(-(x))) #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define fors(i, a, b) for(int i = (a); i < (b); ++i) using namespace std; const int maxn = 2e5 + 50; int n, p, w; int mod; int qm(int a, int b){ int res = 1; while(b){ if(b&1) res = (ll)res*a%mod; a = (ll)a*a%mod; b >>= 1; }return res; } int a[maxn], b[maxn]; void ntt(int l, int r, int cw){ if(r-l+1 == 3){ int ww = 1; fors(i,0,3){ int x = 1; b[l+i] = 0; fors(j,0,3){ b[l+i] = ((ll)a[l+j]*x%mod + b[l+i])%mod; x = (ll)x*ww%mod; } ww = (ll)ww*cw%mod; } fors(i,0,3) a[l+i] = b[l+i]; return; } int len = r-l+1; int h = len/2; int mid = (l+r)>>1; fors(i,0,h) b[l+i] = a[l+2*i], b[mid+1+i] = a[l+2*i+1]; fors(i,l,r+1) a[i] = b[i]; ntt(l, mid, (ll)cw*cw%mod); ntt(mid+1, r, (ll)cw*cw%mod); int z = 1; int t = qm(cw, h); fors(i,l,mid+1){ b[i] = (a[i] + (ll)z*a[i+h]%mod)%mod; b[i+h] = (a[i] + (ll)z*t%mod*a[i+h]%mod)%mod; z = (ll)z*cw%mod; } fors(i,l,r+1) a[i] = b[i]; return; } int main() { while(scanf("%d%d%d", &n, &p, &w) != EOF){ mod = p; fors(i,0,n) b[i] = 0; fors(i,0,n) scanf("%d", &a[i]); ntt(0,n-1,w); fors(i,0,n){ printf("%d ", a[i]); }printf("\n"); } }

G odd-dmc-validation

不是我写的，略过

H 矩阵并

对每个内部的点用组合数求一下贡献，也不是我写的

I segment-colinear-triple

给三个平行于x轴的线段，问是否存在一条直线穿过三条线段 如果存在，一定可以通过平移和旋转使得直线经过两条线段的端点。那么枚举这两个点之后得到一条直线，看另一条线段和这个直线是否相交即可。

J spanning-tree-of-dynamic-weight-graph

假设答案对应的最小生成树已经知道，那么这颗生成树的总价值随着x的变换是 sum(a) + xsum(b)，那么当x取l或者取r的时候这颗生成树最小。设它取l最小的时候，如果x=l的情况下存在其他生成树的价值和 < sum(a) + lsum(b)，这与我们的假设"这颗最小生成树是[l,r]区间对应答案对应的最小生成树"产生矛盾，所以不会存在 其他生成树的价值和 < sum(a) + l*sum(b)。 因此只要在x=l和x=r两种情况分别求一次mst即可得到答案。

K threshold-graph-spanning-trees

这题直接根据原图构造基尔霍夫矩阵，然后求[(1,1), (n-1,n-1)]这个行列式的值： 第一行加上第2~n-1行，你会发现第一行全部变成了1 第2列、第3列、…第n-1列减去第一列，你会发现[(2,2), (n-1,n-1)]这个矩阵变成了上三角矩阵。 然后行列式的值就变成了对角线所有数字求乘积。对于a[i]为0的位置，(i,i)的数字=i点的度数，对于a[i]= 1的位置，因为第一列的$f[i][1]=-1$，所以(i,i)的数字=i点度数+1. 然后就没了，答案就是2~n-1的所有点，如果a[i]=1就乘上度数+1，否则乘上度数。

写完题解才感觉到这场叉姐真是挺仁慈了，也感觉到自己是真的菜……当时J、K直接就放弃治疗了，回过头才发现只是小清新的思维题。