2019年湖南省⼤学⽣计算机程序设计竞赛（HNCPC2019）简要
题解
2019年湖南省⼤学⽣计算机程序设计竞赛 (HNCPC2019) 简要题解
update10.01 突然发现叉把这场的题传到上了，现在⼤家可以有地⽅提交了呢。
不知道该⼲什么所以就来⽔⼀篇题解
题解全是根据印象⼝胡的，代码是不可能重新写的，这辈⼦不可能重新写的。
A
description
有⼀个n×m的全0矩阵，选择⼀个⼦矩阵全部修改成1，现在给出修改后的矩阵，问是否存在合法修改⽅案。
1≤n,m≤10.
solution
到最左上的1和最右下的1，判断是否中间全是1，剩下的全是0就好了。
需要特判没有1的case。
B
description
给出n,k，求min((n
k),1018)。
0≤k≤n≤109.
solution
gzy写的，他⼀遍过了，反正gzynb就对了。
先令k≤⌊n
2⌋，然后再O(k)计算组合数，即每次乘⼀个数再除⼀个数，可以⽤long double或__int128判断是否超过1018，⼀旦爆了就直接输出
1018。
C
description
给出⼀个长度为n的字符集⼤⼩为m的串，对于∀i∈[1,m]，求往字符串后⾯新增⼀个字符i后增加了多少本质不同的⼦串。
1≤n,m≤106.
solution
实现中可以使⽤后缀⾃动机（只要从⾃动机上原串对应的那个点出发⼀直跳fail就⾏了）或者exkmp（线性求原串与所有前缀的lcs）。D
description
求有多少长度为n的序列{a i}满⾜：
a i∈[0,9].
⽅案数对109+7取模。
1≤n,m≤50.
solution
限制即为要求区间内存在⾄少两个3的质因⼦，在这⾥可以认为0包含∞个3质因⼦。
记dp i,j,k表⽰前i个位置，最近的两个3质因⼦在j,k的⽅案数，转移是先判掉不合法（对每个限制的右端点维护对应最⼤左端点），然后在考虑第i+1位上是填{0,9}还是{3,6}还是{1,2,4,5,7,8}。
E
description
给⼀个数字串S，要求将S划分成若⼲互不相同的[0,99]内的整数，不能含有前导零，求⽅案数。
1≤|S|≤50.
solution
直接搜。
考虑⼀位数（包括0）只有10个，那么确定了⼀位数的位置后剩下的划分也就随之确定了，假设数字i出现了a i次，那么搜索的总状态数不超
过∏9i=0(a i+1)≤(∑9i=0(a i+1)
10)10=610。
F
description
⼀个⼈初始在(0,0)，可以⾛不超过n步，每⼀步可以向右⾛不超过a步，或者向上⾛不超过b步，或者向左⾛不超过c步，或者向下⾛不超过d 步，求这个⼈可到达的位置数mod109+7。
李晨霍思燕1≤n,a,b,c,d≤109.
solution
等差数列求和直接算就好了。
G
description
有⼀个n×m的矩阵{C ij}，需要构造⼀个m阶排列σ，使得矩阵的所有列向量根据σ重新排列后满⾜⾏向量字典序单调不降。要求输出满⾜条件的字典序最⼩的
1≤n,m≤2000.
天蝎座 12星座solution
郑爽的孩子考虑n=2，那么每⼀列的两个数的⼤⼩关系只有以下三种：C1j>C2j或C1j=C2j或C1j<C2j。由于需要满⾜第⼆⾏的字典序⼤于等于第⼀⾏，那么所有C1j>C2j的j都需要排在⾄少⼀个C1k<C2k的k后⾯。
这个限制可以抽象成：给出{1,2,...,m}的两个⼦集A,B，满⾜A∩B=∅，要求在最终的排列σ中，B中每个
元素都⾄少排在⼀个A中元素的后⾯。
n>2的情况就是给出了多组A,B。
令每个点的⼊度为包含这个点的B集合数量，每次选择⼀个⼊度为零且编号最⼩的点（保证字典序最⼩）放在当前排列末尾，如果这个元素在某些A集合内是第⼀次出现，那么就把这个A对应的B中所有元素的⼊度减1。
总时间复杂度O(nm+m log m)。
H
description
⼀张n+m个点的图，初始在1号点，每次在i号点的时候有P i,j的概率⾛到j号点，保证∀i∈[n+1,n+m],P i,j=[i=j]。可以发现经过⽆限次⾏⾛后停留在前n号点上的概率是0，求停留在后m号点每个点的概率mod109+7。
1≤n+m≤500.
solution
犹如的近义词设f i表⽰经过i点的期望次数，于是
f1=
n
∑
j=1f j P j,1+1f i=
n
∑
j=1f j P j,i(i>1)
⾼斯消元解出f i 后随便算⼀下就好了。
I
description
李英爱女儿
给⼀棵树，边有边权，求有多少条路径满⾜边权和是2019的倍数。
1≤n≤20000.
solution满分作文600字
点分即可。
J
description
给出n个m元组(a1,a2,...,a m)，记count(x)表⽰有多少个m元组满⾜∀j∈[1,m],popcount(a j∧x)为奇数。求∑2k−1
x=0
count(x)3x mod109+7。1≤n≤104,1≤m≤10,1≤k≤30,0≤a i<2k .
solution
对于每个n元组单独求答案然后相加即为答案。
把m元组写成⼀个k×m的01矩阵，相当于选出⼀些⾏向量做异或运算，要求结果为2m−1。直接按⼆进制位dp，记f i,j表⽰处理完前i位，当前⼆进制状态为j(j∈[0,2m))的⽅案数。
总复杂度是O(nk2m)，⼤概能过的样⼦。
K
description
维护n个链表以及m次操作，每次操作为将⼀个链表剪切到另外⼀个的后边并将其翻转。1≤n,m≤105.
solution
直接启发式合并即可。
不过要我写可能就直接上treap了。
Processing math: 100%
发布评论