2025夏季个人训练赛第三十三场

又是没有牛客打的一天～～

A. 矩阵转换#

一个大的矩形的变换一定可以由多个 2 * 2 的矩形拼出来，2 * 2 的矩形是最小的可以操作的单位，直接遍历一遍矩阵，贪心的变换 2 * 2 的矩阵，如果能成 B 就是 Yes，不能就是 No。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 510;
6
int a[N][N], b[N][N];
7

8
int main() {
9
    int T;
10
    scanf("%d", &T);
11
    while (T--) {
12
        int n, m;
13
        scanf("%d%d", &n, &m);
14
        for (int i = 1; i <= n; ++i) {
15
            for (int j = 1; j <= m; ++j) {
16
                scanf("%1d", &a[i][j]);
17
            }
18
        }
19
        bool f = true;
20
        for (int i = 1; i <= n; ++i) {
21
            for (int j = 1; j <= m; ++j) {
22
                scanf("%1d", &b[i][j]);
23
                if (a[i][j] != b[i][j])
24
                    if (i < n && j < m) {
25
                        a[i][j] ^= 1, a[i + 1][j] ^= 1, a[i][j + 1] ^= 1, a[i + 1][j + 1] ^= 1;
26
                    }
27
                    else {
28
                        f = false;
29
                    }
30
            }
31
        }
32
        if (f) printf("Yes\n");
33
        else printf("No\n");
34
    }
35
    return 0;
36
}

B. 胖虎的菜品#

我刚开始写了一个 $O\left(n \cdot n!\right)$ 的暴力，竟然自以为能过，被自己蠢哭了……

正解应该是状压dp，记录对于每一个 bitmask 最后一步走到 j 时的最短路径长度，枚举下一步的移动转移状态，答案是 2ⁿ - 1 对应的 bitmask 下所有状态的 min.

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

5
using namespace std;
6

7
const int N = 20;
8
double x[N], y[N];
9
double f[1 << 13][N];
10

11
int main() {
12
    int n;
13
    scanf("%d", &n);
14
    for (int i = 0; i < n; ++i) {
15
        scanf("%lf%lf", &x[i], &y[i]);
16
    }
17
    for (int i = 0; i < n; ++i) {
18
        for (int msk = 0; msk < (1 << n); ++msk) {
19
            f[msk][i] = 1e18;
20
        }
21
    }
22
    for (int i = 0; i < n; ++i) {
23
        f[1 << i][i] = sqrt(pow(x[i], 2) + pow(y[i], 2));
24
    }
25
    for (int i = 1; i < n; ++i) {
26
        for (int msk = 0; msk < (1 << n); ++msk) {
27
            for (int j = 0; j < n; ++j) {
28
                if (msk >> j & 1)
29
                    for (int k = 0; k < n; ++k) {
30
                        if (!(msk >> k & 1)) {
31
                            f[msk | (1 << k)][k] = min(f[msk | (1 << k)][k], f[msk][j] + sqrt(pow(x[j] - x[k], 2) + pow(y[j] - y[k], 2)));
32
                        }
33
                    }
34
            }
35
        }
36
    }
37
    double res = 1e18;
38
    for (int i = 0; i < n; ++i) {
39
        res = min(res, f[(1 << n) - 1][i]);
40
    }
41
    printf("%.2f\n", res);
42
    return 0;
43
}

C. 胖虎的攻沙 ^fixed#

~~疑似数据出问题了，我的代码删了点条件之后过洛谷上的(疑似)母题能过。~~

数据就是出问题了，而且已经被我修正了，虽然对拍的时候验证过我应该没问题，但是重判的时候就我一个过了……

目测大家都被卡精度了，看这张图，我依次输出了所有的 $a_{i, j}$ , $k_i$ , $\lfloor a_{i, j} k_i \rfloor + 1$ , $j \cdot p1_i - \left(s - j\right) \cdot p2_i$ 上面是我的输出，下面是原来 std 的输出，根据 python 的验证，确实是浮点数精度出了问题，而且我是对的。

刚开始没发现，写到最后回头一看，其实是一个分组背包问题，f_{i, j} 表示前 i 个沙城使用 m 个士兵的最大得分，对每个 i 对应的 s 个数从小到大排序，只需要考虑所有能刚好能拿到前 l 个的分时的士兵数，其他值取了只会浪费士兵，没有其他收益，时间复杂度是 $O\left(nsm\right)$ ，按说没问题。

疑似正确的代码 (目前新数据的 std，欢迎 hack)

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <cstring>
5
#include <cmath>
6

7
using namespace std;
8

9
const int N = 110, M = 20010;
10
int a[N][N], f[N][M], p1[N], p2[N];
11
double k[N];
12
vector<pair<int, int>> t[N];
13

14
int main() {
15
    int s, n, m;
16
    scanf("%d%d%d", &s, &n, &m);
17
    for (int i = 1; i <= s; ++i) {
18
        for (int j = 1; j <= n; ++j) {
19
            scanf("%d", &a[j][i]);
20
        }
21
    }
22
    memset(f, -0x3f, sizeof(f));
23
    for (int i = 1; i <= n; ++i) scanf("%lf", &k[i]);
24
    for (int i = 1; i <= n; ++i) scanf("%d", &p1[i]);
25
    for (int i = 1; i <= n; ++i) scanf("%d", &p2[i]);
26
    f[0][0] = 0;
27
    for (int i = 1; i <= n; ++i) {
28
        sort(a[i] + 1, a[i] + s + 1);
29
        for (int j = 1; j <= s; ++j) {
30
            int l = j + 1;
31
            while (l <= s && a[i][l] == a[i][j]) l++;
32
            j = l - 1;
33
            t[i].emplace_back((int)floor((double)a[i][j] * k[i] + 1e-8) + 1, j * p1[i] - (s - j) * p2[i]);
34
        }
35
    }
36
    for (int i = 1; i <= n; ++i) {
37
        for (int j = 0; j <= m; ++j) {
38
            f[i][j] = f[i - 1][j] - p2[i] * s; // 全不选
39
            for (auto [u, v] : t[i]) {
40
                if (j < u) break;
41
                f[i][j] = max(f[i][j], f[i - 1][j - u] + v);
42
            }
43
        }
44
    }
45
    int res = -0x3f3f3f3f;
46
    for (int i = 0; i <= m; ++i) res = max(res, f[n][i]);
47
    if (res >= 0) printf("%d\n", res);
48
    else printf("Run Away\n");
49
    return 0;
50
}

E. 不知道该叫啥 (noname)#

先看一下暴力 $O\left(nm\right)$ 的做法，记 f_{i, j} 第 i 个数选 j 的方案数, g_{i, j} 是 f_i 数组的前缀和。

1
for (int i = 1; i <= n; ++i) {
2
    for (int j = 1; j <= m; ++j) {
3
        if (i == 1) f[i][j] = 1;
4
        else f[i][j] = g[i - 1][m / j];
5
        g[i][j] = (g[i][j - 1] + f[i][j]) % MOD;
6
    }
7
}
8
printf("%d\n", g[n][m]);

关键点在于每一个 j 的前置状态是 $\lfloor\frac{m}{j}\rfloor$ 这就意味着所有 $\lfloor\frac{m}{j}\rfloor$ 相等的 j 的 f 都是一样的，考虑除法分块，对于每一个块只存一次答案就行，优化完时间复杂度为 $O\left(n\sqrt{m}\right)$ ，就可以过了。

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

5
using namespace std;
6
typedef long long LL;
7
const int N = 110, M = 100010;
8
const int MOD = 1000000007;
9

10
int f[N][M], g[N][M];
11
vector<tuple<int, int, int>> v;
12

13
int main() {
14
    int n, m;
15
    scanf("%d%d", &n, &m);
16
    for (int l = 1, r; l <= m; l = r + 1) {
17
        r = m / (m / l);
18
        v.emplace_back(l, r, m / l);
19
    }
20
    int k = v.size();
21
    for (int i = 1; i <= n; ++i) {
22
        for (int j = 1; j <= k; ++j) {
23
            auto &[l, r, t] = v[j - 1];
24
            if (i == 1) {
25
                f[i][j] = 1;
26
            }
27
            else {
28
                // 这里其实是可以用双指针的，需要用到的 L 一定是单调不增的，同时反向遍历 g[i - 1] 可以省掉这个 log
29
                int L = 0, R = k - 1;
30
                while (L < R) {
31
                    int mid = L + R + 1 >> 1;
32
                    if (get<0>(v[mid]) <= t) L = mid;
33
                    else R = mid - 1;
34
                }
35
                f[i][j] = (g[i - 1][L] + (LL)f[i - 1][L + 1] * (t - get<0>(v[L]) + 1)) % MOD;
36
            }
37
            g[i][j] = (g[i][j - 1] + (LL)f[i][j] * (r - l + 1)) % MOD;
38
        }
39
    }
40
    printf("%d\n", g[n][k]);
41
    return 0;
42
}

F. 双端队列 × LIS 问题 (dequexlis)#

翻译一下题意，其实就是问你从同一个点开始的单调上升子序列和单调下降子序列的长度和的最大值 - 1，正常用树状数组维护即可。

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

6
using namespace std;
7

8
const int N = 100010;
9
int a[N], tr[N], f[N], m;
10
vector<int> values;
11

12
void add(int x, int v) {
13
    for (; x <= m; x += x & -x) {
14
        tr[x] = max(tr[x], v);
15
    }
16
}
17

18
int query(int x) {
19
    int res = 0;
20
    for (; x; x -= x & -x) {
21
        res = max(res, tr[x]);
22
    }
23
    return res;
24
}
25

26
int main() {
27
    int n;
28
    scanf("%d", &n);
29
    for (int i = 1; i <= n; ++i) {
30
        scanf("%d", &a[i]);
31
        values.emplace_back(a[i]);
32
    }
33
    sort(values.begin(), values.end());
34
    auto t = unique(values.begin(), values.end());
35
    for (int i = 1; i <= n; ++i) {
36
        a[i] = lower_bound(values.begin(), t, a[i]) - values.begin() + 1;
37
    }
38
    m = values.size();
39
    for (int i = n; i; --i) {
40
        f[i] = query(a[i] - 1) + 1;
41
        add(a[i], f[i]);
42
    }
43
    fill(tr + 1, tr + m + 1, 0);
44
    int res = 0;
45
    for (int i = n; i; --i) {
46
        a[i] = m - a[i] + 1; // 我把他反过来就不用开线段树了，我真是个天才
47
        res = max(res, query(a[i] - 1) + f[i]);
48
        add(a[i], query(a[i] - 1) + 1);
49
    }
50
    printf("%d\n", res);
51
    return 0;
52
}

I. 树的统计#

题面/双倍经验

我发现我 22 年 10 月和 8 月各 A 了一次，所以我没双倍经验了……

裸的树剖 + 线段树板子，看我 30min 手搓一个。

我: 嗯？怎么 query_mx 比最大值还大。

我: 哎，我复制下来之后 tr_s 没改成 tr_mx！！

手: backspace M X control+option+N

手: command+C 提交button.click() command+V 提交button.click()

OJ: Accepted

我: ……

温馨提示：复制粘贴的时候记得仔细检查变量名！！

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 30010;
6

7
int head[N], ver[N * 2], ne[N * 2], tot;
8
int w[N], n;
9

10
int cnt[N], dep[N], son[N], fa[N];
11
int dfn[N], rnk[N], top[N], t;
12

13
int tr_s[N * 4], tr_mx[N * 4];
14

15
void add(int x, int y) {
16
    ver[++tot] = y;
17
    ne[tot] = head[x];
18
    head[x] = tot;
19
}
20

21
void dfs(int x) {
22
    cnt[x] = 1;
23
    for (int i = head[x]; i; i = ne[i]) {
24
        int y = ver[i];
25
        if (y == fa[x]) continue;
26
        fa[y] = x;
27
        dep[y] = dep[x] + 1;
28
        dfs(y);
29
        cnt[x] += cnt[y];
30
        if (cnt[y] > cnt[son[x]]) son[x] = y;
31
    }
32
}
33

34
void dfs(int x, int tp) {
35
    dfn[x] = ++t;
36
    rnk[t] = x;
37
    top[x] = tp;
38
    if (son[x]) dfs(son[x], tp);
39
    for (int i = head[x]; i; i = ne[i]) {
40
        int y = ver[i];
41
        if (y == fa[x] || y == son[x]) continue;
42
        dfs(y, y);
43
    }
44
}
45

46
void pushup(int u) {
47
    tr_s[u] = tr_s[u << 1] + tr_s[u << 1 | 1];
48
    tr_mx[u] = max(tr_mx[u << 1], tr_mx[u << 1 | 1]);
49
}
50

51
void build(int u, int l, int r) {
52
    if (l == r) tr_s[u] = tr_mx[u] = w[rnk[l]];
53
    else {
54
        int mid = l + r >> 1;
55
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
56
        pushup(u);
57
    }
58
}
59

60
void modify(int u, int l, int r, int p, int v) {
61
    if (l == r) tr_s[u] = tr_mx[u] = v;
62
    else {
63
        int mid = l + r >> 1;
64
        if (p <= mid) modify(u << 1, l, mid, p, v);
65
        else modify(u << 1 | 1, mid + 1, r, p, v);
66
        pushup(u);
67
    }
68
}
69

70
int query_s(int u, int l, int r, int ql, int qr) {
71
    if (ql <= l && r <= qr) return tr_s[u];
72
    else {
73
        int mid = l + r >> 1;
74
        int res = 0;
75
        if (ql <= mid) res = query_s(u << 1, l, mid, ql, qr);
76
        if (qr > mid) res += query_s(u << 1 | 1, mid + 1, r, ql, qr);
77
        return res;
78
    }
79
}
80

81
int query_mx(int u, int l, int r, int ql, int qr) {
82
    if (ql <= l && r <= qr) return tr_mx[u];
83
    else {
84
        int mid = l + r >> 1;
85
        int res = -0x3f3f3f3f;
86
        if (ql <= mid) res = query_mx(u << 1, l, mid, ql, qr);
87
        if (qr > mid) res = max(res, query_mx(u << 1 | 1, mid + 1, r, ql, qr));
88
        return res;
89
    }
90
}
91

92
int query_s(int x, int y) {
93
    int res = 0;
94
    while (top[x] != top[y]) {
95
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
96
        res += query_s(1, 1, n, dfn[top[x]], dfn[x]);
97
        x = fa[top[x]];
98
    }
99
    if (dfn[x] > dfn[y]) swap(x, y);
100
    res += query_s(1, 1, n, dfn[x], dfn[y]);
101
    return res;
102
}
103

104
int query_mx(int x, int y) {
105
    int res = -0x3f3f3f3f;
106
    while (top[x] != top[y]) {
107
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
108
        res = max(res, query_mx(1, 1, n, dfn[top[x]], dfn[x]));
109
        x = fa[top[x]];
110
    }
111
    if (dfn[x] > dfn[y]) swap(x, y);
112
    res = max(res, query_mx(1, 1, n, dfn[x], dfn[y]));
113
    return res;
114
}
115

116
int main() {
117
    scanf("%d", &n);
118
    for (int i = 1; i < n; ++i) {
119
        int x, y;
120
        scanf("%d%d", &x, &y);
121
        add(x, y), add(y, x);
122
    }
123
    for (int i = 1; i <= n; ++i) {
124
        scanf("%d", &w[i]);
125
    }
126
    dep[1] = 1;
127
    dfs(1);
128
    dfs(1, 1);
129
    build(1, 1, n);
130
    char s[20];
131
    int a, b, q;
132
    scanf("%d", &q);
133
    while (q--) {
134
        scanf("%s%d%d", s, &a, &b);
135
        if (s[0] == 'C') {
136
            modify(1, 1, n, dfn[a], b);
137
        }
138
        else if (s[1] == 'M') {
139
            printf("%d\n", query_mx(a, b));
140
        }
141
        else if (s[1] == 'S') {
142
            printf("%d\n", query_s(a, b));
143
        }
144
        else {
145
            cout << "qwq" << endl;
146
            return 123;
147
        }
148
    }
149
    return 0;
150
}

J. 棋盘制作II#

题面/双倍经验

我被他卡了好久，首先他这个可以转化一下，奇数行，奇数列 (都选偶数也一样) 都 xor 1 之后问的就是全 0 或者全 1 的最大矩形。

正方形好做，直接枚举右下角，然后二分一个边长就可以解决，然而这并没什么用……

根据题意，不难想到需要维护最长连续相同数字的长度，我被卡在了后面怎么处理，后来想了亿会儿，又睡了一觉回来突然茅塞顿开。其实之前做过类似的，但是没有和几何联系起来。比如，我维护了第 i 行前 j 个必须包含 j 的最长连续相同数字的长度 f_{i, j}，因为求的是一个矩形，不妨就把右端对齐，考虑其他的边界，首先，他要是个合法的矩形，硬性要求就是连续的 i 的值必须一样，对于每一个这样的值相等的小段单独抽出来考虑；现在想想区间最大值求和是怎么做的，这个就是怎么做的，枚举矩形的宽 w，用单调栈维护上面第一个比他小的和下面第一个比他小的，中间夹的长度就是最大的高度 h，把所有这样的 w * h 取 max 就是第一个答案，min(w, h)² 取 max 就是第二个答案。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 2010;
6
int a[N][N], f[N][N];
7
int st[N];
8

9
int main() {
10
    int n, m;
11
    scanf("%d%d", &n, &m);
12
    for (int i = 1; i <= n; ++i) {
13
        for (int j = 1; j <= m; ++j) {
14
            scanf("%d", &a[i][j]);
15
        }
16
    }
17
    for (int i = 1; i <= n; i += 2) {
18
        for (int j = 1; j <= m; ++j) {
19
            a[i][j] ^= 1;
20
        }
21
    }
22
    for (int i = 1; i <= n; ++i) {
23
        for (int j = 1; j <= m; j += 2) {
24
            a[i][j] ^= 1;
25
        }
26
    }
27
    for (int i = 1; i <= n; ++i) {
28
        int pre = -1;
29
        for (int j = 1; j <= m; ++j) {
30
            if (a[i][j] == pre) f[i][j] = f[i][j - 1] + 1;
31
            else f[i][j] = 1;
32
            pre = a[i][j];
33
        }
34
    }
35
    int s1 = 0, s2 = 0;
36
    for (int i = 1; i <= m; ++i) {
37
        int tp = 1;
38
        st[tp] = 0;
39
        f[0][i] = -1;
40
        for (int j = 1; j <= n; ++j) {
41
            if (tp != 1 && a[j][i] != a[st[tp]][i]) {
42
                while (tp > 1) {
43
                    int w = f[st[tp]][i], h = j - st[tp - 1] - 1;
44
                    s2 = max(s2, h * w);
45
                    s1 = max(s1, min(h, w) * min(h, w));
46
                    tp--;
47
                }
48
                f[j - 1][i] = -1, st[tp] = j - 1;
49
            }
50
            while (tp && f[j][i] <= f[st[tp]][i]) {
51
                int w = f[st[tp]][i], h = j - st[tp - 1] - 1;
52
                s2 = max(s2, h * w);
53
                s1 = max(s1, min(h, w) * min(h, w));
54
                tp--;
55
            }
56
            st[++tp] = j;
57
        }
58
        while (tp > 1) {
59
            int w = f[st[tp]][i], h = n - st[tp - 1];
60
            s2 = max(s2, h * w);
61
            s1 = max(s1, min(h, w) * min(h, w));
62
            tp--;
63
        }
64
    }
65
    printf("%d\n%d\n", s1, s2);
66
    return 0;
67
}

Star's Blog