2021CCPC威海【个人题解ADGJM】

A - Goodbye, Ziyin!（签到）

思路

首先判断是否存在度数大于3的点，如果存在的话，那么必然不可能构成二叉树。
否则则是度数不大于3的点可以作为二叉树的根。

代码

#include 

using namespace std;

const int N = 1000005;

int d[N];

int main() 
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i ++ )
    {
        int u, v;
        scanf("%d%d", &u, &v);
        d[u] ++, d[v] ++;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (d[i] > 3)
        {
            puts("0");
            return 0;
        }
        else if(d[i] == 3) cnt ++;
    
    printf("%d\n", n - cnt);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

D - Period（思维、KMP）

思路

由于将某个字符修改为#，必然会使得某一些长度不能成为周期，考虑#的位置。
如果#的位置$i$（从0开始）小于$\frac{n}{2}$时，如下图所示，那么周期的取值范围只可能从$n-i$到$n-1$，因为只有这样才能使得在比较的时候不涉及到#

而当#的位置$i$（从0开始）大于等于$\frac{n}{2}$时，如下图所示，周期的取值范围就可以是$i+1$到$n-1$，因为无论如何都不会涉及到#的比较

每个询问中，#的位置是固定的，那么也就是确定了周期的取值范围，但是如何判断某个周期值是否为真正的周期值呢？答案是KMP，想一想KMP的next[n]表示了什么，表示的就是这个串s[0…next[n]-1] = s[n-next[n] … n-1]，也就是最长的公共前后缀长度。于是利用KMP求出next数组，然后从next[n]开始往前跳，把公共前后缀的位置标记一下，求个后缀和就可以提供O(1)询问了。

代码

#include 
#include 
#include 

using namespace std;

const int N = 1000005;

int n, q;
char s[N];
int nt[N];
int f[N];

void getnext()
{
    nt[0] = -1;
    int i = 0, j = -1;
    while (i < n)
    {
        if (j == -1 || s[i] == s[j]) nt[++ i] = ++ j;
        else j = nt[j];
    }
}

int main()
{
    scanf("%s", s);
    n = strlen(s);
    getnext();

    int i = n;
    while (nt[i])
    {
        i = nt[i];
        f[n - i] ++;
    }

    for (int i = n - 1; i >= 0; i -- )
        f[i] += f[i + 1];

    scanf("%d", &q);
    for (int i = 1; i <= q; i ++ )
    {
        int x;
        scanf("%d", &x);
        x --;
        if (x < n / 2) printf("%d\n", f[n - x]);
        else printf("%d\n", f[x + 1]);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

G - Shinyruo and KFC（推柿子+样例优化）

思路

令$mx=ma{x}_i(a_i)$，那么如果$mx>m$，输出$m$个0.
否则从$k=mx$开始计算答案，由于每一种食物的分配方案是独立的，那么答案为：$C_k^{a_1}\ast ...\ast C_k^{a_n}$
由于$m$和$n$都比较大，考虑从$k-1$的答案转移向$k$的答案，把组合数拆开来之后可以看出乘上了
$\frac{k^n}{(k-a_1)\ast (k-a_2)\ast ...\ast (k-a_n)}$
如果直接暴力算还是$O(nmlogn)$的复杂度。
考虑优化，观察到$\sum a_i\le 10^5$，故不同的$a_i$数量级别为$O(\sqrt{n})$。
可以把相同的$a_i$一起算，这样复杂度就变为$O(n\sqrt{n}logn)$。

代码

#include
using namespace std;
const int mod = 998244353, N = 1e5 + 10;

int cnt[N];
int ksm(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }return ans;
}

int fact[N], inv[N];
int invNum[N];

void pre()
{
    fact[0] = 1;
    for(int i = 1; i < N; i ++) fact[i] = 1ll * i * fact[i - 1] % mod;
    inv[N - 1] = ksm(fact[N - 1], mod - 2);
    for(int i = N - 2; i >= 0; i --) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

int C(int n, int m)
{
    return 1LL * fact[n] * inv[m] % mod * inv[n - m] % mod;
}

int main()
{
    pre();
    int n, m;
    scanf("%d%d", &n, &m);
    int mx = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a;
        scanf("%d", &a);
        mx = max(a, mx);
        cnt[a] ++;
    }
    vector<int> A;
    for (int i = 0; i < N; i ++ )
        if (cnt[i]) A.push_back(i);
    for (int i = 1; i < N; i ++ )
        invNum[i] = ksm(i, mod - 2);

    if (mx > m)
    {
        for (int i = 1; i <= m; i ++ )
            puts("0");
        return 0;
    }

    for (int i = 1; i < mx; i ++ )  
        puts("0");
    
    int ans = 1;
    for (auto a : A)
        ans = 1LL * ans * ksm(C(mx, a), cnt[a]) % mod;
    printf("%d\n", ans);

    for (int k = mx + 1; k <= m; k ++ )
    {
        ans = 1LL * ans * ksm(k, n) % mod;
        for (auto a : A)
            ans = 1LL * ans * ksm(invNum[k - a], cnt[a]) % mod;
        printf("%d\n", ans);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

J - Circular Billiard Table（签到）

思路

画画图之后发现题意变为求出最小的正整数$y$使得$2\frac{a}{b}y\%360=0$，相当于是$y\frac{a}{b}=360k$。
化简一下变为$y=\frac{180b}{a}k$，最小化$y$相当于最小化$k$使得$\frac{180b}{a}k$为整数。
可以求得最小的整数$y$为$\frac{180b}{gcd(a,180\ast b)}$，答案为$y-1$。

代码

#include 

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b)
{
    return !b ? a : gcd(b, a % b);
}

int main()
{
    int _;
    cin >> _;
    while (_ --)
    {
        LL a, b;
        cin >> a >> b;
        b *= 180;
        LL g = gcd(a, b);
        b /= g;
        cout << b - 1 << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

M - 810975

思路

经典问题！
首先考虑这个问题，$n$场游戏中赢了$m$场，最多（注意是最多，和恰好不一样）连胜$k$场的方案数。转换一下，我们可以把赢的场次看作1，输的场次看作0，那么所有的输赢情况相当于把1填到每两个0中间（也可以不填），使得1的数量之和为$m$，且每两个0中间的1数量最多为k。由于0的个数为$n-m$个，那么有$n-m+1$个位置可以填数，所以问题转换为使得$x_1+x_2+...+x_{n-m+1}=m(0\le x_i\le k)$的方案数，记这个问题的解为$calc(n-m+1,m,k)$。
可以看到，原问题是恰好有$k$场连胜，而上述问题是最多有$k$场连胜（包含了$0k-1$场连胜的方案数），所以原问题的解就是$calc(n-m+1,m,k)-calc(n-m+1,m,k-1)$。
现在考虑$calc(n,m,k)$怎么求，再重申一下现在的问题：
求使得$x_1+x_2+...+x_n=m(0\le x\le k)$的方案数
首先如果$x\ge 1$且没有上界，则可以用隔板法求出方案数为$C_{m-1}^{n-1}$。隔板法就是求把$m$作为$m$个球，划分为$n$份，每一份至少有$n$个球，那么有$m-1$的空位，放$n-1$块隔板。
考虑如何把求$x\ge 0$且没有上界限的方案数，我们依然可以利用隔板法划分为$n$份，最后从每一份中拿出$1$个球即可，即最后拿出了$n$个球，那么一开始要补$n$个球，方案数为$C_{m-1+n}^{n-1}$。
最后考虑如何限制$x$的上界后算出最终的方案数，一个好想的思路是总方案数减去不满足条件的方案数。考虑钦定某个数一定大于$k$的方案数如何求，方法就是先让钦定的数为$k+1$，然后进行上述隔板法，方案数为$C_n^1{C}_{m-1+n-(k+1)}^{n-1}$，根据容斥原理，这些方案中会有重复，需要减掉钦定两个一定大于$k$的方案数，再加上钦定三个一定大于$k$的方案数…
于是最终方案数为${\sum }_{i=0}^n(-1{)}^i{C}_n^i{C}_{m-1+n-i\ast (k+1)}^{n-1}$

代码