bnu-faraway/牛客网暑期ACM多校训练营(第一场)

Info

Date:2018.06.02

Link

Solutions

A Monotonic Matrix

solved by sk


sk’s solution

赛中强行打表找规律的,猜出一个对称的公式\(\frac{\tbinom{n+m+1}{n} \tbinom{n+m+1}{m}}{n+m+1}\)

正确思路是考虑01和12的分界线,即求有多少对可重合但不相交的从(n,0)到(0,m)的路径。将其中一个平移,从(n-1,-1)到(-1,m-1),即变成了严格不相交。

这里套用Lindström–Gessel–Viennot lemma

双倍经验CodeForces 348D Turtles

其实就是徐州那个题啊

B Symmetric Matrix

upsolved by ghc


ghc’s solution

占坑待更

C Fluorescent 2

upsolved by gjy


gjy’s solution

考虑随机变量\(X_i,X_j,X_k\)对答案的贡献,即转化为求\(i,j,k\)对应三个方程成立的概率,通过高斯消元求秩计算概率即可。

D Two Graphs

solved by sk


sk’s solution

枚举排列,算出满足条件方案数,除以自同构方案数。

E Removal

upsolved by gjy


gjy’s solution

f[i][j]表示使用到i,删除j个的方案数。 考虑放入字符a,在其下一次出现位置放入,保证子序列方案不少不重。

F Sum of Maximum

solved by sk,gjy


sk,gjy’s solution

考虑每种答案的贡献,简化为一个含幂和的式子,用求幂和模板解决。

G Steiner Tree

solved by


’s solution

H Longest Path

upsolved by gjy


gjy’s solution

考虑点分治,对于当前重心的每个儿子求得二元组\((c,dis)\),按第一维排序正反做一次凸壳,更新每个点的答案。

I Substring

upsolved by sk


sk’s solution

注意到字符集大小只有三,对原串枚举所有6种映射,转化为求6个字符串不同子串个数,比如ab,ac,ba,bc,ca,cb,可以发现同一种结构的子串会被统计6次,除了只有同一种字符构成的子串比如aaa,bbb,ccc,只重复了3次。

所以答案为 (不同子串数量+3*单一字符的串)/6

求多个字符串不同子串个数可以用广义后缀自动机,操作是在插入每个串前让last=1,这里还需要再研究一下。

J Different Integers

solved by sk


sk’s solution

求区间[1,l]和[r,n]的不同数的个数,首先将原序列延长一倍就变成了一个区间,然后记last[i]表示之前距离i最近且和a[i]相等的位置,就转化为了求区间有多少个last[i]小于l,主席树或离线树状数组。

Replay

ghc

gjy

盲目跟榜,没有有选择地开题,训练不饱和,做题状态很差。

sk