Processing math: 100%

牛客多校第一场

补题进度:4/7(10)
The end always near


A.Monotonic Matrix

题意

nm 的矩阵,每个数 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

题意

nn 的矩阵 矩阵每行的和必须为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=dpi1,j1+dpi1,jai

设以a_i 结尾相同的方案:
ans[i]=dppre[i]1,j(ipre[i])
其中 prei:位置i的 ai上次出现的位置。

Thick: 多个位置有相同的ai,每个位置都处理了它的前一个位置

pre[i]就是上一个a[i]出现位置,d是当前a[i]和前一个a[i]之间的距离。我们把他俩之间的全删掉才能保证串是重复的。j-d就是我们删掉他们之间所有所有字符后还剩下几次操作次数。


F.Sum of Maximum

题意

给一个序列 a, 问
a1x1=1a2x2=1anxn=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[l1]+([1,l1][l,r])
问题转化为:如何求([1,l1][l,r]都出现的数)

设树状数组中的 Ci 为:第i个位置的数字是否在[1,i]出现过,这就需要维护一个nxt数组了表示每个位置的数出现的下一个位置

[1,l1][l,r]都出现的数 =sum[r]sum[l1]

确认无误:无签到