补题进度:4/7(10)
The end always near
A.Monotonic Matrix
题意
n∗m 的矩阵,每个数 0<=ai<=2, 问满足 ai,j<=ai+1,j AND ai,j<=ai,j+1 的矩阵数量
题解
假如只有01,考虑01分界线的位置(分界线上的格子只能填0,下面只能填1),答案即为:
Cmn+m
现在考虑012三个数字,考虑01和12分界线,
其实是(0,0)到(n,m)的两条不相交(可重合)路径数量
Lindström–Gessel–Viennot lemma
由于分界线的起点和终点不能 在同一行和同一列, 可以将01的分界线分别在xy方向都移动一格即可
B. Symmetric Matrix
题意
n∗n 的矩阵 矩阵每行的和必须为2 且是一个沿右对角线对称的矩阵 并且 ai,i=0 问合法矩阵数量 (0<=ai<=2)。
题解
待补
C.Fluorescent 2
留坑
D.Two Graphs
题解
赛时想了个从E2中选出E1条边,再和G1去匹配,很难写
正解:直接枚举G2的点n!种排列方式,暴力的和G1的中每个点的边的情况进行匹配,但存在一个问题: 一个图的遍历顺序不同,但是同构的,故要求出E1的所有同构
相当于G2中所有满足要求的都 ∗ 了一个 E1的所有同构, 排除即可
时间复杂度O(n!∗n2)
E.Removal
题意
长度为n的序列,每个数 <= k, 删除m个后,序列的种数(k<=10)
题解
法一:
法二:
定义:dpij:前i个删除j个的方案数
转移:dpi,j=dpi−1,j−1+dpi−1,j−以ai结尾相同的方案
设以a_i 结尾相同的方案:
ans[i]=dppre[i]−1,j−(i−pre[i])
其中 prei:位置i的 ai上次出现的位置。
Thick: 多个位置有相同的ai,每个位置都处理了它的前一个位置
pre[i]就是上一个a[i]出现位置,d是当前a[i]和前一个a[i]之间的距离。我们把他俩之间的全删掉才能保证串是重复的。j-d就是我们删掉他们之间所有所有字符后还剩下几次操作次数。
F.Sum of Maximum
题意
给一个序列 a, 问
a1∑x1=1a2∑x2=1…an∑xn=1max(x1,x2,….,xn)
mod(109+7)
题解
拉格朗日插值
待补
G. Steiner Tree
题意
留坑
H. Longest Path
留坑
I. Different Integers
题意
题解
待补
J. Different Integers
题解
赛时写了个复杂度不对的莫队,侥幸过了题
正解:树状数组
要是一个区间的话怎么做?
将数组长度n扩展到2n即可转化为一个区间
count(i,j)=[1,i]+[j,n]=>[j,n+i]
设pre[]: 表示出现不同的数的前缀和
answer=pre[r]−pre[l−1]+([1,l−1]和[l,r]都出现的数)
问题转化为:如何求([1,l−1]和[l,r]都出现的数)
设树状数组中的 Ci 为:第i个位置的数字是否在[1,i]出现过,这就需要维护一个nxt数组了表示每个位置的数出现的下一个位置
则 [1,l−1]和[l,r]都出现的数 =sum[r]−sum[l−1]
确认无误:无签到