Asusetic
0%

2021.08.02模拟赛

发表于 分类于 Valine：
本文字数： 342 阅读时长 ≈ 1 分钟

一点浩然气，千里快哉风

2021.08.02模拟赛

T1 吊灯

奇异结论题

先分解因数，显然 有 nd\dfrac{n}{d} 个大小为 dd 的倍数的子树是必要条件，充分性可以考虑每次分出来一个大小为 dd 的连通块的时候都不影响其他的大小为 dd 的倍数的子树，就可以一直分下去直到分完

所以就可以开个桶记录下，不用建树，直接统计大小否则会被卡

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
#include <algorithm>
#include <array>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1200005;
int n;
vector<int> factor;
vector<int> ans;
int fa[N], siz[N], tmp[N], buc[N];
void change() {
    for (int i = 2; i <= n; i++) {
        fa[i] = (fa[i] + 19940105) % (i - 1) + 1;
    }
}
void pre() {
    for (int i = n; i; i--) {
        siz[i]++;
        siz[fa[i]] += siz[i];
    }
    for (int i = 1; i <= n; i++) {
        buc[siz[i]]++;
    }
}
int check(int x) {
    int cnt = 0;
    for (int i = 1; i * x <= n; i++) {
        cnt += buc[i * x];
    }
    return (cnt * x == n);
}
void solve() {
    ans.clear();
    memset(siz, 0, sizeof(siz));
    memset(buc, 0, sizeof(buc));
    pre();
    for (auto x : factor) {
        if (check(x) == 1) {
            ans.push_back(x);
        }
    }
}
void output(int k) {
    printf("Case #%d:\n", k);
    for (auto v : ans) {
        printf("%d\n", v);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factor.push_back(i);
            if (i * i != n) {
                factor.push_back(n / i);
            }
        }
    }
    sort(factor.begin(), factor.end());
    unique(factor.begin(), factor.end());
    for (int i = 2; i < n; i++) {
        scanf("%d,", &fa[i]);
    }
    scanf("%d", &fa[n]);
    for (int i = 1; i <= 10; i++) {
        solve();
        output(i);
        change();
    }
}

T2 小Z爱求和

考虑一个数是第 kk​ 小的就是有 k−1k-1​ 个小于等于它的，所以从大向小考虑，维护一个链表，记 posipos_i 为 ii 下标的排名，这样就能按大小顺序访问

每次前后找到 k−1k-1 个位置，然后算出答案后删掉个数字，复杂度 O(nlog⁡n)O(n\log n)

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
using ll     = long long;
const ll mod = 998244353;
const int N  = 1e6 + 10;
struct IO {
    static const int N = 1 << 20 | 1;
    char ibuf[N], *p, *q, c;
    char obuf[N], *o;
    bool s;
    int stk[50], t;
    IO() {
        p = q = ibuf, o = obuf;
    }
    char gc() {
        if (p == q)
            p = ibuf, q = ibuf + fread(ibuf, 1, sizeof ibuf, stdin);
        return p == q ? EOF : *p++;
    }
    template <typename T> IO &operator>>(T &x) {
        x = 0, s = false;
        do
            c = gc();
        while (!isdigit(c));
        s |= c == '-';
        do
            x = x * 10 + c - '0', c = gc();
        while (isdigit(c));
        if (s)
            x = -x;
        return *this;
    }
    void flush() {
        fwrite(obuf, 1, o - obuf, stdout);
        o = obuf;
    }
    void wc(char x) {
        *o++ = x;
        if (o - obuf >= N)
            flush();
    }
    IO &operator<<(char x) {
        wc(x);
        return *this;
    }
    template <typename T> IO &operator<<(T x) {
        if (x < 0)
            wc('-');
        t = 0;
        do
            stk[++t] = x % 10, x /= 10;
        while (x);
        while (t)
            wc(stk[t--] + '0');
        return *this;
    }
    ~IO() {
        flush();
    }
} io;
int n, k;
int a[N], pos[N];
int pre[N], nxt[N];
ll solve() {
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    for (int i = 1; i <= n; i++) {
        int x = pos[i];
        int l = x, r = x;
        int cnt = 1;
        while (cnt < k) {
            if (pre[l] != 0) {
                l = pre[l];
            } else {
                break;
            }
            cnt++;
        }
        while (cnt < k) {
            if (nxt[r] != n + 1) {
                r = nxt[r];
            } else {
                break;
            }
            cnt++;
        }
        if (cnt == k) {
            while (l <= x) {
                if (r == n + 1)
                    break;
                res +=
                    a[x] * 1ll * (nxt[r] - r) % mod * 1ll * (l - pre[l]) % mod;
                res %= mod;
                l = nxt[l];
                r = nxt[r];
            }
        }
        nxt[pre[x]] = nxt[x];
        pre[nxt[x]] = pre[x];
    }
    return res;
}
int main() {
    io >> n >> k;
    for (int i = 1; i <= n; i++) {
        io >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        pos[i] = i;
    }
    sort(pos + 1, pos + 1 + n, [&](const int &A, const int &B) -> bool {
        return a[A] < a[B];
    });
    ll sum = 0;
    sum += solve();
    sum %= mod;
    reverse(pos + 1, pos + 1 + n);
    sum += solve();
    sum %= mod;
    cout << sum << endl;
}
// Asusetic eru quionours.

T3 关押罪犯

状压DP

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
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 17;
int G[N][N];
int dp[1 << N];
int n, m, k;
int main() {
    cin >> n >> m >> k;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        G[x][y] = G[y][x] = 1;
    }
    for (int S = 1; S < (1 << n); S++) {
        int tot = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (G[i][j] && (S & (1 << (i - 1))) && (S & (1 << (j - 1)))) {
                    tot++;
                }
            }
        }
        if (tot <= k) {
            dp[S] = 1;
        } else {
            for (int T = S; T; T = (T - 1) & S) {
                dp[S] = min(dp[S], dp[T] + dp[S - T]);
            }
        }
    }
    cout << dp[(1 << n) - 1];
}
// Asusetic eru quionours.

T4 小P走迷宫

容斥一下即可

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 <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
using ll     = long long;
const int N  = 2005;
const ll mod = 1e9 + 7;
int n, m, dp[N][N];
char s[N][N];
int mp[N][N];
ll calc(int stx, int sty, int edx, int edy) {
    if (mp[stx][sty] == 1) {
        return 0;
    }
    memset(dp, 0, sizeof(dp));
    dp[stx][sty] = 1;
    for (int i = stx; i <= edx; i++) {
        for (int j = sty; j <= edy; j++) {
            if ((i != stx || j != sty) && !mp[i][j]) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
            }
        }
    }
    return dp[edx][edy];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            mp[i][j] = (c == '1');
        }
    }
    ll ans = ((calc(1, 2, n - 1, m) * calc(2, 1, n, m - 1) % mod) -
              (calc(1, 2, n, m - 1) * calc(2, 1, n - 1, m) % mod) + mod) %
             mod;
    cout << (ans + mod) % mod << endl;
    return 0;
}

-klbw3Qcqa9-awdpZcT3cSml-vx.jpg.medium.jpg