NOIP2021 题解

    NOIP2021 题解

    T1. 报数

    LOJ 3564

    Solution

    可以先把十进制表示下数位含有 77 的所有数都求出来,然后去枚举这些数的倍数,将其标记。

    如果当前枚举到的数被标记过了则就不需要再枚举倍数了(因为枚举的倍数肯定也被标记过了)。

    标记出所有需要跳过的数后,从后往前预处理一遍答案即可。

    类似埃筛,时间复杂度 O(nlog⁡log⁡n)\mathcal{O}(n \log \log n)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int SIZE = 1e7 + 500;
    
    bool ori[SIZE + 10];
    bool f[SIZE + 10];
    
    int go[SIZE + 10]; 
    
    void prework(int N) {
        for (int i = 1; i <= N; i ++)
            ori[i] = ori[i / 10] | (i % 10 == 7);
    
        for (int i = 1; i <= N; i ++) {
            if (!ori[i]) continue;
            if (f[i]) continue;
            for (int j = i; j <= N; j += i) f[j] = 1;
        }
    
        for (int i = N; i >= 1; i --)
            if (f[i])
                go[i] = go[i + 1];
            else
                go[i] = i;
    }
    
    void work() {
        int x = read();
    
        if (f[x])
            puts("-1");
        else
            printf("%d\n", go[x + 1]);
    }
    
    int main() {
        prework(SIZE);
    
        int T = read();
    
        while (T --)
            work();
    
        return 0;
    }
    
    // I hope changle_cyx can pray for me.

    T2. 数列

    LOJ 3565

    Solution

    注意到直接在序列后加入一个数会比较难维护,可以考虑从小到大向序列中加数。

    设 f(i,j,h,S)f(i, j, h, S) 表示:已经选了 jj 个数,选出的数的值域为 [0,i][0, i],二进制表示中的 [0,i][0, i] 位中有 hh 个 11,[i+1,∗][i + 1, *] 中的二进制表示为 SS 时的方案数。

    可以考虑枚举选了多少个 ii。假设选了 xx 个 ii,那么就有转移:

    f(i,j,h+(S+x) mod 2,⌊S+x2⌋)←+f(i−1,j−x,h,S)⋅vix⋅(jx)f(i, j, h + (S + x) \bmod 2, \left\lfloor\frac{S + x}{2}\right\rfloor) \gets_+ f(i - 1, j - x, h, S) \cdot v_i^x \cdot \dbinom{j}{x}

    最后答案即为:∑h+count(S)≤kf(m,n,h,S)\sum\limits_{h + \text{count}(S) \leq k} f(m, n, h, S)。

    其中 count(S)\text{count}(S) 表示 SS 二进制表示下 11 的个数。

    时间复杂度 O(n4m)\mathcal{O}(n^4m)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    int power(int a, int b, int p) {
        int ans = 1;
        for (; b; b >>= 1) {
            if (b & 1) ans = 1ll * ans * a % p;
            a = 1ll * a * a % p;
        }
        return ans;
    }
    
    const int N = 35, M = 110; 
    const int mod = 998244353;
    
    void add(int &x, const int &y) {
        x += y;
        if (x >= mod) x -= mod;
    }
    
    int n, m, k;
    int val[M];
    
    int fact[N], inv[N];
    int C(int n, int m) {
        return 1ll * inv[n - m] * inv[m] % mod * fact[n] % mod;
    }
    
    int f[M][N][N][N];
    
    int cnt[N];
    
    int main() {
        n = read(), m = read(), k = read();
    
        for (int i = 0; i <= m; i ++)
            val[i] = read();
    
        fact[0] = 1;
        for (int i = 1; i <= n; i ++) fact[i] = 1ll * fact[i - 1] * i % mod;
        inv[n] = power(fact[n], mod - 2, mod);
        for (int i = n - 1; i >= 0; i --) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    
        for (int x = 0, cur = 1; x <= n; x ++, cur = 1ll * cur * val[0] % mod)
            f[0][x][x % 2][x / 2] = cur;
    
        for (int i = 1; i <= m; i ++) {
            for (int x = 0, cur = 1; x <= n; x ++, cur = 1ll * cur * val[i] % mod) {
                for (int j = x; j <= n; j ++) {
                    for (int h = 0; h <= n; h ++) {
                        for (int S = 0; S <= n; S ++) {
                            if (!f[i - 1][j - x][h][S]) continue;
                            int d = 1ll * f[i - 1][j - x][h][S] * C(j, x) % mod * cur % mod;
                            add(f[i][j][h + (S + x) % 2][(S + x) / 2], d);
                        }
                    }
                }
            }
        }
    
        for (int S = 1; S <= n; S ++)
            cnt[S] = cnt[S ^ (S & -S)] + 1;
    
        int ans = 0;
        for (int h = 0; h <= n; h ++)
            for (int S = 0; S <= n; S ++)
                if (h + cnt[S] <= k) add(ans, f[m][n][h][S]);
    
        printf("%d\n", ans);
    
        return 0;
    }

    T3. 方差

    LOJ 3566

    Solution

    简单处理可以把方差的 n2n^2 倍化为:

    n(∑i=1nai2)−(∑i=1nai)2n\left(\sum\limits_{i = 1}^n a_i^2\right) - \left(\sum\limits_{i = 1}^n a_i\right)^2

    那么,只需要知道一个序列的数值和与数值平方和,就可以计算出该序列的方差了。

    记差分数组 bi=ai−ai−1b_i = a_i - a_{i - 1},那么一次对 ii 的操作就相当于交换 bi,bi+1b_i, b_{i + 1}。

    由于邻项交换,并且可以进行任意多次操作。
    那么所有操作结束后的新差分数组 {b′}\{b'\} 可以是原差分数组 {b}\{b\} 的任意一个排列。

    一个结论:最优解的差分数组一定是先递减、后递增的(也就是单谷的)。

    根据这个性质,我们就可以先将所有的 n−1n - 1 个差分值从小到大排序,然后从小到大加入差分值。由于方差关系的是数据之间的相对大小,我们不妨钦定一个基准点,它的值为 00。

    设 sumi\text{sum}_i 表示前 ii 小的差分值之和是多少。

    设 f(i,S)f(i, S) 表示:考虑到前 ii 个差分值,当前的数值和为 SS 时,数值平方和最小是多少。

    若向当前序列的左端加数,则有转移:

    f(i,S+bi⋅i)←minf(i−1,S)+2⋅S⋅bi+i⋅bi2f(i, S + b_i \cdot i) \gets_\text{min} f(i - 1, S) + 2 \cdot S \cdot b_i + i \cdot b_i^2

    若向当前序列的右端加数,则有转移:

    f(i,S+sumi)←min⁡f(i−1,S)+sumi2f(i, S + \text{sum}_i) \gets_{\min} f(i - 1, S) + \text{sum}_i^2

    最后的答案即为 min⁡{n⋅f(n−1,S)−S2}\min\{n \cdot f(n - 1, S) - S^2\}。

    设值域为 mm,直接做显然是 O(n2m)\mathcal{O}(n^2m) 的。

    但是注意到整个序列 {a}\{a\} 中不同的数总共就只有 min⁡(n,m)\min(n, m) 个,也就是说差分数组中不为 00 的有效差分值不超过 min⁡(n,m)\min(n, m) 个,于是就可以优化到 O(min⁡(n,m)⋅nm)\mathcal{O}(\min(n, m) \cdot nm)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 10010, SZ = 500100;
    const int inf = 0x3f3f3f3f;
    
    int n, m, L, res;
    int a[N], b[N];
    
    int sum[N];
    
    int p, q;
    int f[2][SZ];
    
    int main() {
        n = read();
    
        for (int i = 1; i <= n; i ++)
            a[i] = read(), m = max(m, a[i]);
    
        L = n * m;
    
        for (int i = 1; i < n; i ++) {
            b[i] = a[i + 1] - a[i];
            if (!b[i]) res ++;
        }
    
        sort(b + 1, b + n);
    
        for (int i = 1; i < n; i ++)
            sum[i] = sum[i - 1] + b[i];
    
        p = 0, q = 1;
    
        f[p][0] = 0;
        for (int S = 1; S <= L; S ++) f[p][S] = inf;
    
        for (int i = res + 1; i < n; i ++) {
            p ^= 1, q ^= 1;
    
            for (int S = 0; S <= L; S ++) f[p][S] = inf;
            for (int S = 0; S <= L; S ++) {
                f[p][S + sum[i]] = min(f[p][S + sum[i]], f[q][S] + sum[i] * sum[i]);
                f[p][S + b[i] * i] = min(f[p][S + b[i] * i], f[q][S] + 2 * S * b[i] + i * b[i] * b[i]);
            }
        }
    
        long long ans = 1e18;
        for (int S = 0; S <= L; S ++)
            ans = min(ans, 1ll * n * f[p][S] - 1ll * S * S);
    
        printf("%lld\n", ans);
    
        return 0;
    }

    T4. 棋局

    LOJ 3567

    Solution

    (待填 …)