国庆集训DAY 1

今天的题目很有意思

水题但是看不出来。

难题又难到不会。

这边说前两题

破门而入(broken)

分析一下题目,其实这只输入两个数的,一般都是有规律的,因为数据范围比较大就有这个考虑。(就是考试我也没看出来)

分析多一个点的情况下,会不会多一个环,就可以弄出递推式。


1
2
3
4
5
for(int j=1;j<=k;j++)f[1][j] = 1;
    for(int i=2;i<=n;i++)f[i][1] = f[i-1][1]*(i-1)%N;
    for(int i=2;i<=n;i++)
        for(int j=2;j<=k;j++)
            f[i][j] = (f[i-1][j]*(i-1)+f[i-1][j-1])%N;

 

翻转游戏(turn)

我的考试时思路很简单,就是暴力(翻转,哈希)。

谁知道到这玩意也能有规律。

先求出所有的变法个数(只翻转一个的不算,但是只翻转一个的也就一种答案情况)

然后减去所有字母的(个数*个数减一)/2,就是减去所有翻转后无用的情况。

再然后

……

就没有然后了。


1
2
3
    ans = (n-1)*n/2+1;
    for(int i=97;i<=122;i++)
        ans -= a[i]*(a[i]-1)/2;

 

发表评论

邮箱地址不会被公开。 必填项已用*标注