NOIP2019

Posted on Edited on In Word count in article: 737 Reading time ≈ 3 mins.
倒数第一次划水,还是要改改错的

Day1T1 格雷码

分析

这个找找规律模拟一下即可, 注意要开\(\text{ULL}\), 否则会挂掉

规律记不得了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>

using namespace std;

typedef unsigned long long ll;

ll N(1), M, K;

int main()
{
    cin >> M >> K;
    while (--M) N <<= 1;
    while (N)
    {
        if (K >= N) putchar('1'), K = N - K % N - 1;
        else putchar('0');
        N >>= 1;
    }
}

Day1T2 括号树

分析

用栈进行括号匹配, 如果能匹配上, 那么当前位置的答案就是他的父节点的答案加上这个节点有的贡献, 那么就十分的简单了

Code

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 5e5 + 10;
const ll mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

ll stk[maxn], f[maxn], top, cur, ans;
ll sta[maxn], sum[maxn], size[maxn];
ll head[maxn], _edge[maxn], _next[maxn];
char opt[maxn];

inline void Addedge(ll u, ll v)
{
    _next[++cur] = head[u];
    head[u] = cur;
    _edge[cur] = v;
}

void dfs(ll u, ll fa)
{
    ll left(0);
    if (sta[u]) {
        if (top) {
            left = stk[top];
            size[u] = size[f[left]] + 1;
            --top;
        }
    } else stk[++top] = u;
    sum[u] = sum[fa] + size[u];
    for (ll i = head[u]; i; i = _next[i]) {
        if (_edge[i] == fa) continue;
        dfs(_edge[i], u);
    }
    if (left) stk[++top] = left;
    else if (top) --top;
}

signed main()
{
    ll n = __read();
    scanf ("%s", opt + 1);
    for (ll i = 1; i <= n; ++i) sta[i] = (opt[i] == ')');
    for (ll i(2); i <= n; ++i) {
        f[i] = __read();
        Addedge(f[i], i);
    }
    dfs(1, 1);
    for (ll i = 1; i <= n; ++i) ans ^= (i * sum[i]);
    printf ("%lld\n", ans);
    system("pause");
}

Day1T3 树上的数

鸽~

Day2T1 Emiya 家今天的饭

分析

那么首先考虑容斥, 我们用所有方案减去不可行的方案

设计转移方程 : \(Dp[i][j][k]\)表示在第\(i\)种烹饪方式时选择第\(j\)种食材, 且这种食材比其他食材多用了\(k\)次

由于\(k\)有可能是负数, 所以我们给了一个\(n\)的偏移量

那么\(Dp[i][j][k]=Dp[i-1][j][k]+Dp[i-1][k-1]*a[i][j]+Dp[i-1][k+1]*(sum[i]-a[i][j])\)

所以不可行的方案就是\(k>n\)的方案数

减去即可

Code

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 110;
const int mod = 998244353;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int a[maxn][maxn * 20], sum[maxn][maxn * 20];
int f[maxn][maxn * 20][maxn << 1], ans(1);

signed main()
{
    int n = __read(), m = __read();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) sum[i][0] = (sum[i][0] + (a[i][j] = __read())) % mod;
        for (int j = 1; j <= m; ++j) sum[i][j] = (sum[i][0] - a[i][j] + mod) % mod;
        ans = 1ll * ans * (sum[i][0] + 1) % mod;
    }
    ans -= 1;
    for (int j = 1; j <= m; ++j) {
        f[0][j][n] = 1;
        for (int i = 1; i <= n; ++i)
            for (int k = n - i; k <= n + i; ++k)
                f[i][j][k] = (f[i - 1][j][k] + 1ll * f[i - 1][j][k - 1] * a[i][j] % mod + 1ll * sum[i][j] * f[i - 1][j][k + 1] % mod) % mod; 
        for (int i = 1; i <= n; ++i)
            ans = (ans - f[n][j][n + i] + mod) % mod;
    }
    printf ("%lld\n", ans);
    system("pause");
}

Day2T2 划分

别急, 先鸽鸽~