2025夏季个人训练赛第二十七场

今天没有牛客可以 vp 了，🐸说打一场个人训练吧，于是就有了这篇博客。

A. 折半枚举：四数之和为零 ^补#

当时被卡常卡空间，各种卡，卡绝望了……赛时 TLE 和 MLE 共计 12 发，补题的时候还有两发。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
const int N = 4010;
8
int v1[N * N], v2[N * N];
9
int a[4][N];
10
int len;
11

12
inline int read() {
13
    int x = 0, op = 1;
14
    char c = getchar();
15
    while (!isdigit(c)) {
16
        if (c == '-') op = -1;
17
        c = getchar();
18
    }
19
    while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
20
    return x * op;
21
}
22

23
int main() {
24
    int n = read();
25
    for (int i = 1; i <= n; ++i) {
26
        for (int j = 0; j < 4; ++j) {
27
            a[j][i] = read();
28
        }
29
    }
30
    for (int i = 1; i <= n; ++i) {
31
        for (int j = 1; j <= n; ++j) {
32
            v1[len] = a[0][i] + a[1][j];
33
            v2[len] = -a[2][i] - a[3][j];
34
            len++;
35
        }
36
    }
37
    sort(v1, v1 + len);
38
    sort(v2, v2 + len);
39
    long long res = 0;
40
    for (int i = 0, j = 0, ri, rj; i < len && j < len; ) { // 不用双指针就会喜提 TLE
41
        if (v1[i] == v2[j]) {
42
            ri = i + 1, rj = j + 1;
43
            while (ri < len && v1[ri] == v1[i]) ri++;
44
            while (rj < len && v2[rj] == v2[j]) rj++;
45
            res += (long long)(ri - i) * (rj - j);
46
            i = ri, j = rj;
47
        }
48
        else if (v1[i] < v2[j]) {
49
            int ri = i + 1;
50
            while (ri < len && v1[ri] == v1[i]) ri++;
51
            i = ri;
52
        }
53
        else {
54
            int rj = j + 1;
55
            while (rj < len && v2[rj] == v2[j]) rj++;
56
            j = rj;
57
        }
58
    }
59
    printf("%lld\n", res);
60
    return 0;
61
}

B. 会议#

朴实无华的换根 dp

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
const int N = 50010;
5
vector<int> ed[N];
6
long long f[N];
7
int cnt[N];
8
long long res;
9
int idx, n;
10

11
void dp(int x, int fa) {
12
    cnt[x] = 1;
13
    for (int y : ed[x]) {
14
        if (y == fa) continue;
15
        dp(y, x);
16
        f[x] += f[y] + cnt[y];
17
        cnt[x] += cnt[y];
18
    }
19
}
20

21
void chrt(int x, int fa) {
22
    for (int y : ed[x]) {
23
        if (y == fa) continue;
24
        long long bk = f[y];
25
        f[y] += (f[x] - f[y] - cnt[y]) + (n - cnt[y]);
26
        if (f[y] == res && y < idx || f[y] < res) {
27
            idx = y;
28
            res = f[y];
29
        }
30
        chrt(y, x);
31
        f[y] = bk;
32
    }
33
}
34

35
int main() {
36
    scanf("%d", &n);
37
    for (int i = 1; i < n; ++i) {
38
        int a, b;
39
        scanf("%d%d", &a, &b);
40
        ed[a].emplace_back(b);
41
        ed[b].emplace_back(a);
42
    }
43
    dp(1, 0);
44
    idx = 1, res = f[1];
45
    chrt(1, 0);
46
    printf("%d %lld\n", idx, res);
47
    return 0;
48
}

C. 变音量#

也是一道朴实无华的 dp 题，记录第 i 次能不能到 j，然后二维 dp 就可以。

1
#include <iostream>
2

3
using namespace std;
4
bool f[70][1010];
5

6
int main() {
7
    int n, s, m;
8
    scanf("%d%d%d", &n, &s, &m);
9
    f[0][s] = true;
10
    n--;
11
    for (int i = 1; i <= n; ++i) {
12
        int t;
13
        scanf("%d", &t);
14
        for (int j = 0; j <= m; ++j) {
15
            if (j >= t) f[i][j] |= f[i - 1][j - t];
16
            if (j + t <= m) f[i][j] |= f[i - 1][j + t];
17
        }
18
    }
19
    for (int j = m; j; --j) {
20
        if (f[n][j]) {
21
            printf("%d\n", j);
22
            return 0;
23
        }
24
    }
25
    printf("-1\n");
26
    return 0;
27
}

D. 三角棋盘上的N皇后#

直接爆搜就可以解决，我的爆搜 171 ms.

1
#include <iostream>
2

3
using namespace std;
4
const int N = 14;
5
int msk[N];
6
int mx, cur, t;
7
int n;
8

9
void dfs(int x, int msk1, int msk2) {
10
    if (x == 0) {
11
        if (cur > mx) {
12
            mx = cur;
13
            t = 1;
14
        }
15
        else if (cur == mx) t++;
16
        return;
17
    }
18
    int mask = msk1 | msk2;
19
    if (msk[x]) {
20
        if (msk[x] & mask) return;
21
        else dfs(x - 1, (msk1 | msk[x]) >> 1, (msk2 | msk[x]) & ((1 << x - 1) - 1));
22
    }
23
    else {
24
        for (int i = 0; i < x; ++i) {
25
            if (mask >> i & 1) continue;
26
            else {
27
                cur++;
28
                dfs(x - 1, (msk1 | (1 << i)) >> 1, (msk2 | (1 << i)) & ((1 << x - 1) - 1));
29
                cur--;
30
            }
31
        }
32
        dfs(x - 1, msk1 >> 1, msk2 & ((1 << x - 1) - 1));
33
    }
34
}
35

36
int main() {
37
    scanf("%d", &n);
38
    for (int i = 1; i <= n; ++i) {
39
        char s[N + 1];
40
        scanf("%s", s);
41
        for (int j = 0; s[j]; ++j) {
42
            msk[i] = (msk[i] << 1) | (s[j] == '*');
43
        }
44
    }
45
    dfs(n, 0, 0);
46
    printf("%d\n%d\n", mx, t);
47
    return 0;
48
}

E. 教主的游乐场#

最优的路径一定只往左走一次或者一直往右，从右往左更新一遍状态先处理直接往右的，再从左往右更新一遍先往左再往右的，可以用线段树维护，背板子的题写着就是😋。

我当时查询的循环写的 n 然后 OLE 了一次。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 100000;
7
int tr[N * 4];
8
int a[N];
9

10
void modify(int u, int l, int r, int p, int v) {
11
    if (l == r) tr[u] = min(tr[u], v);
12
    else {
13
        int mid = l + r >> 1;
14
        if (p <= mid) modify(u << 1, l, mid, p, v);
15
        else modify(u << 1 | 1, mid + 1, r, p, v);
16
        tr[u] = min(tr[u << 1], tr[u << 1 | 1]);
17
    }
18
}
19

20
int query(int u, int l, int r, int ql, int qr) {
21
    if (ql > qr) return 0x3f3f3f3f;
22
    if (ql <= l && r <= qr) return tr[u];
23
    else {
24
        int mid = l + r >> 1;
25
        int res = 0x3f3f3f3f;
26
        if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
27
        if (qr > mid) res = min(res, query(u << 1 | 1, mid + 1, r, ql, qr));
28
        return res;
29
    }
30
}
31

32
int main() {
33
    memset(tr, 0x3f, sizeof(tr));
34
    int n, m;
35
    scanf("%d%d", &n, &m);
36
    for (int i = 1; i <= n; ++i) {
37
        scanf("%d", &a[i]);
38
        if (i + a[i] > n) modify(1, 1, n, i, 1);
39
    }
40
    for (int i = n; i; --i) {
41
        modify(1, 1, n, i, min(query(1, 1, n, 1, i - 1), query(1, 1, n, i + 1, min(n, i + a[i]))) + 1);
42
    }
43
    for (int i = 1; i <= n; ++i) {
44
        modify(1, 1, n, i, min(query(1, 1, n, 1, i - 1), query(1, 1, n, i + 1, min(n, i + a[i]))) + 1);
45
    }
46
    for (int i = 1; i <= m; ++i) {
47
        int q;
48
        scanf("%d", &q);
49
        printf("%d ", query(1, 1, n, q, q));
50
    }
51
    printf("\n");
52
    return 0;
53
}

F. 任务 (task)#

用类似 dp 的思路贪心，按照 l 排序，维护一下目前所有线程的右端点，每次都找离第 i 个区间的左端点最近的右端点用，如果找不到就只能放弃一个，这个时候检查一下他的右端点是否比最大的小，如果是就把右端点最大的放弃掉把他加进去，否则直接把这个放弃掉。

1
#include <iostream>
2
#include <algorithm>
3
#include <set>
4

5
using namespace std;
6
const int N = 1000010;
7
pair<int, int> a[N];
8
multiset<int> s;
9

10
int main() {
11
    int n, k;
12
    scanf("%d%d", &n, &k);
13
    for (int i = 1; i <= n; ++i) {
14
        scanf("%d%d", &a[i].first, &a[i].second);
15
    }
16
    int res = 0;
17
    sort(a + 1, a + n + 1);
18
    for (int i = 1; i <= n; ++i) {
19
        auto p = s.upper_bound(a[i].first);
20
        if (p == s.begin()) {
21
            if (s.size() < k) s.insert(a[i].second), res++;
22
            else if (*s.rbegin() > a[i].second) s.erase(--s.end()), s.insert(a[i].second);
23
        }
24
        else {
25
            s.erase(--p), s.insert(a[i].second);
26
            res++;
27
        }
28
    }
29
    printf("%d\n", res);
30
    return 0;
31
}

G. 祈求者 (invoker)#

把状态用三进制压缩，然后直接一遍状压 dp 就解决了，最困难的地方在于三进制状态有 27 个，需要要注意打表的时候会不会抄错。

1
#include <iostream>
2
#include <map>
3
#include <vector>
4
#include <cstring>
5
using namespace std;
6

7
const int N = 100010;
8

9
map<char, vector<int>> mp = {
10
    {'Y', {0}},                         // QQQ
11
    {'V', {1, 3, 9}},                   // QQW
12
    {'G', {2, 6, 18}},                  // QQE
13
    {'C', {13}},                        // WWW
14
    {'X', {4, 10, 12}},                 // QWW
15
    {'Z', {14, 16, 22}},                // WWE
16
    {'T', {26}},                        // EEE
17
    {'F', {8, 20, 24}},                 // QEE
18
    {'D', {17, 23, 25}},                // WEE
19
    {'B', {5, 7, 11, 15, 19, 21}}       // QWE
20
};
21

22
int f[N][27];
23

24
int dis(int x, int y) {
25
    vector<int> s1 = {x / 9, x / 3 % 3, x % 3}, s2 = {y / 9, y / 3 % 3, y % 3};
26
    if (s1 == s2) return 1;
27
    else if (s1[1] == s2[0] && s1[2] == s2[1]) return 2;
28
    else if (s1[2] == s2[0]) return 3;
29
    else return 4;
30
}
31

32
int main() {
33
    ios::sync_with_stdio(0);
34
    cin.tie(0), cout.tie(0);
35
    string s;
36
    cin >> s;
37
    int n = s.length();
38
    memset(f, 0x3f, sizeof(f));
39
    for (int i = 1; i <= n; ++i) {
40
        auto v = mp[s[i - 1]];
41
        if (i == 1) {
42
            for (int j : v) f[i][j] = 4;
43
        }
44
        else {
45
            for (int j : v) {
46
                for (int k = 0; k < 27; ++k) {
47
                    f[i][j] = min(f[i][j], f[i - 1][k] + dis(k, j));
48
                }
49
            }
50
        }
51
    }
52
    int res = 0x3f3f3f3f;
53
    for (int i = 0; i < 27; ++i) {
54
        res = min(res, f[n][i]);
55
    }
56
    printf("%d\n", res);
57
    return 0;
58
}

I. 排列计数#

画一下样例很容易观察出来，这就是个二叉堆，对于每一个子树都保证根节点比子树的最小值小即可。于是就可以树形 dp 了。

刚在数位 dp 那里爆了一次 int，然后又在这儿爆 int 了……

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5
typedef long long LL;
6
const int N = 1000010;
7

8
LL power(LL n, LL p, LL mod) {
9
    LL res = 1, base = n;
10
    while (p) {
11
        if (p & 1) res = res * base % mod;
12
        base = base * base % mod;
13
        p >>= 1;
14
    }
15
    return res;
16
}
17

18
LL jc[N], f[N];
19
vector<int> ed[N];
20
int n, p;
21
int cnt[N];
22

23
LL c(int n, int m) {
24
    return jc[n] * power(jc[n - m], p - 2, p) % p * power(jc[m], p - 2, p) % p;
25
}
26

27
void dp(int x) {
28
    f[x] = 1;
29
    cnt[x] = 1;
30
    bool first = true;
31
    for (int y : ed[x]) {
32
        dp(y);
33
        cnt[x] += cnt[y];
34
        f[x] = (f[x] * f[y]) % p;
35
    }
36
    if (cnt[x] != 1) f[x] = (f[x] * c(cnt[x] - 1, cnt[ed[x][0]])) % p;
37
}
38

39
int main() {
40
    scanf("%d%d", &n, &p);
41
    jc[0] = 1;
42
    for (int i = 1; i <= n; ++i) {
43
        jc[i] = jc[i - 1] * i % p;
44
        if (i != 1) ed[i / 2].emplace_back(i);
45
    }
46
    dp(1);
47
    printf("%lld\n", f[1]);
48
    return 0;
49
}

K. 【数位DP】数字计数#

这个数位dp很恶心，需要一边统计方案数一边统计数字的出现次数，还需要排除前导零的情况，正好我数位dp不好，被硬控了一上午。好不容易 dp 调对了，又爆 int 了……

$f_{i, j, k}$ 表示从最高位开始数填到前 i 位时所有情况指定数字的个数， $j \in \{0, 1\}$ 表示是否顶到上界， $k \in {0, 1}$ 表示当前位置是不是前导零， $g_{i, j, k}$ 表示满足 j 和 k 约束的数的个数。

状态转移枚举当前位置填的数，0 的时候涉及到前导零的问题要单独算，其他的数一起算。

来欣赏一下一我横向滚动两屏半的超长状态转移方程🤮

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4

5
using namespace std;
6
const int N = 14;
7
long long a[N], len;
8
long long f[N][2][2], g[N][2][2]; // 顶上界 前导零
9

10
long long count(long long x, int k) {
11
    memset(g, 0, sizeof(g));
12
    if (x == -1) return 0;
13
    if (x == 0) return k == 0;
14
    len = 0;
15
    while (x) {
16
        a[++len] = x % 10;
17
        x /= 10;
18
    }
19
    reverse(a + 1, a + len + 1);
20
    g[0][1][1] = 1;
21
    for (int i = 1; i <= len; ++i) {
22
        g[i][0][0] = (g[i - 1][1][0] * (a[i] != 0) + g[i - 1][0][0]) + (g[i - 1][1][0] + g[i - 1][1][1]) * max(0LL, a[i] - 1) + (g[i - 1][0][0] + g[i - 1][0][1]) * 9;
23
        g[i][0][1] = g[i - 1][1][1] + g[i - 1][0][1];
24
        g[i][1][0] = 1;
25
        f[i][0][0] = (f[i - 1][1][0] * (a[i] != 0) + f[i - 1][0][0]) + g[i - 1][1][0] * (a[i] != 0 && k == 0) + g[i - 1][0][0] * (k == 0) + (f[i - 1][1][1] + f[i - 1][1][0]) * max(0LL, a[i] - 1) + (f[i - 1][0][0] + f[i - 1][0][1]) * 9 + (g[i - 1][1][0] + g[i - 1][1][1]) * (k != 0 && k < a[i]) + (g[i - 1][0][0] + g[i - 1][0][1]) * (k != 0);
26
        f[i][1][0] = f[i - 1][1][0] + (a[i] == k);
27
    }
28
    return f[len][0][0] + f[len][1][0] + (k == 0);
29
}
30

31
int main() {
32
    long long a, b;
33
    cin >> a >> b;
34
    for (int i = 0; i < 10; ++i) {
35
        cout << count(b, i) - count(a - 1, i) << ' ';
36
    }
37
    cout << endl;
38
    return 0;
39
}

Star's Blog

A. 折半枚举：四数之和为零 补#