A. Wonderful Sticks

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

using i64 = long long;

void solve() {
    int n;
    string s;

    cin >> n >> s;

    vector<int> f(n + 1);

    f[1] = 1;
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == '>') {
            f[i + 1] = 1;
        }
    }

    vector<int> pos;
    for (int i = 1; i <= n; i++) {
        if (f[i]) pos.push_back(i);
    }
    int m = pos.size();

    vector<int> a(n + 1);
    int st = n - m + 1;
    for (int i = 0; i < m; i++) {
        a[pos[i]] = st + i;
    }

    vector<int> ans;
    for (int i = n - m; i >= 1; i--) {
        ans.push_back(i);
    }

    int c = 0;
    for (int i = 1; i <= n; i++) {
        if (!f[i]) {
            a[i] = ans[c++];
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

B. Wonderful Gloves

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

using i64 = long long;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<i64> l(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> l[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }

    i64 res = 0;
    vector<i64> b(n + 1);
    for (int i = 1; i <= n; i++) {
        b[i] = min(l[i], r[i]);
        res += max(l[i], r[i]);
    }


    sort(b.begin() + 1, b.end(), greater<i64>());
    i64 sum = 0;
    for (int i = 1; i <= k - 1; i++) {
        sum += b[i];
    }

    i64 ans = res + sum;
    cout << ans + 1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

C. Wonderful City

观察可以发现，行操作和列操作是分开的，如果某一行有两个数字需要更改，那么必须在对应的两列中选一个去改

  • 行方向上的 DP
    令

  • dp0：到第 iii 行且 ri=0r_i=0ri​=0（不雇佣第 iii 行工人）的最小费用；

  • dp1：到第 iii 行且 ri=1r_i=1ri​=1（雇佣第 iii 行工人）的最小费用。

初始时

dp0=0,dp1=a1 dp0=0,\quad dp1 = a_1dp0=0,dp1=a1​

（第 1 行若雇佣，需花 a1a_1a1​；否则 0）。

然后对每个相邻行对 (i,i+1)(i,i+1)(i,i+1)：

  1. 枚举所有列 j=1…nj=1\ldots nj=1…n，计算原始高度差

    d=H[i][j]−H[i+1][j]. d = H[i][j] - H[i+1][j].d=H[i][j]−H[i+1][j].

  2. 根据 d∈{−1,0,1}d\in{-1,0,1}d∈{−1,0,1}，判定「哪几种 (ri,ri+1)(ri,r{i+1})(ri​,ri+1​) 会导致新高度相等」：

    • d=0d=0d=0：如果 ri=ri+1ri = r{i+1}ri​=ri+1​（要么都是 0，要么都是 1）会使 H′[i][j]=H′[i+1][j]H’[i][j]=H’[i+1][j]H′[i][j]=H′[i+1][j]；

    • d=1d=1d=1：如果 (ri,ri+1)=(0,1)(ri,r{i+1})=(0,1)(ri​,ri+1​)=(0,1) 会使差变成 1+0−1=01+0-1=01+0−1=0；

    • d=−1d=-1d=−1：如果 (ri,ri+1)=(1,0)(ri,r{i+1})=(1,0)(ri​,ri+1​)=(1,0) 会使差变成 −1+1−0=0-1+1-0=0−1+1−0=0。

  3. 把出现过的“禁止模式”用一个长 4 的布尔数组 tp[0..3] 标记，再只对允许的转移更新：

    cpp

    复制编辑

    // newdp0 = 不雇第 i+1 行；newdp1 = 雇第 i+1 行 newdp0 = min( dp0 if (r_i=0→r_{i+1}=0) 未被 d=0 禁止, dp1 if (r_i=1→r_{i+1}=0) 未被 d=-1 禁止 ); newdp1 = min( dp0 + a[i+1] if (0→1) 未被 d=1 禁止, dp1 + a[i+1] if (1→1) 未被 d=0 禁止 );

  4. 如果同时出现所有四种模式，说明这条相邻行边无论如何都不可能保持不等高，直接置 dp0=dp1=inf，提前剪掉。

走完 i=1i=1i=1 到 n ⁣− ⁣1n!-!1n−1，最终行方向最小费用取 min⁡(dp0,dp1)\min(dp0,dp1)min(dp0,dp1)，记作 XX。

对于列同理，记作YY，取和就是答案；

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

using i64 = long long;
constexpr i64 inf = 1e18 + 7;
void solve() {
    int n;
    cin >> n;

    vector h(n + 1, vector<i64>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> h[i][j];
        }
    }

    vector<i64> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    i64 dp0 = 0, dp1 = a[1];
    for (int i = 1; i < n; i++) {
        vector<int> tp(4);
        for (int j = 1; j <= n; j++) {
            i64 d = h[i][j] - h[i + 1][j];
            if (d == 0) {
                tp[0] = tp[3] = 1;
            } else if (d == 1) {
                tp[1] = 1;
            } else if (d == -1) {
                tp[2] = 1;
            }
        }

        if (tp[0] && tp[1] && tp[2] && tp[3]) {
            dp0 = dp1 = inf;
            break;
        }
        i64 ndp0 = inf, ndp1 = inf;
        if (!tp[0]) ndp0 = min(ndp0, dp0);
        if (!tp[2]) ndp0 = min(ndp0, dp1);
        if (!tp[1]) ndp1 = min(ndp1, dp0 + a[i + 1]);
        if (!tp[3]) ndp1 = min(ndp1, dp1 + a[i + 1]);

        dp0 = ndp0;
        dp1 = ndp1;
    }
    i64 xx = min(dp0, dp1);

    dp0 = 0, dp1 = b[1];
    for (int j = 1; j < n; j++) {
        vector<int> tp(4);
        for (int i = 1; i <= n; i++) {
            i64 d = h[i][j] - h[i][j + 1];
            if (d == 0) { 
                tp[0] = tp[3] = 1; 
            } else if (d == 1) { 
                tp[1] = 1; 
            } else if (d == -1) { 
                tp[2] = 1; 
            }
        }

        if (tp[0] && tp[1] && tp[2] && tp[3]) {
            dp0 = dp1 = inf;
            break;
        }
        i64 ndp0 = inf, ndp1 = inf;
        if (!tp[0]) ndp0 = min(ndp0, dp0);
        if (!tp[2]) ndp0 = min(ndp0, dp1);
        if (!tp[1]) ndp1 = min(ndp1, dp0 + b[j + 1]);
        if (!tp[3]) ndp1 = min(ndp1, dp1 + b[j + 1]);

        dp0 = ndp0;
        dp1 = ndp1;
    }
    i64 yy = min(dp0, dp1);

    if (xx >= inf / 2 || yy >= inf / 2) {
        cout << -1 << '\n';
    } else {
        cout << xx + yy << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

D. Wonderful Lightbulbs

疯狂观察， 疯狂在纸上乱花后发现：由于一开始只有一个点，你再怎么操作（不管操作多少次），一开始所在的点的那一条平行于Y轴的直线上都只能有奇数个点，而除了这条直线，其他平行于Y轴的直线都必然是偶数个点。

至此我们确定了X坐标

怎么确定Y坐标呢？

再次观察（神学），发现斜方向（与直线 y = -x平行方向），除了一开始所在点，其他直线都是偶数个，而一开始所在点是奇数个点，

这样我们确定了两个直线，取交点即可

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

using i64 = long long;
constexpr i64 inf = 1e18 + 7;
void solve() {
    int n;
    cin >> n;

    vector h(n + 1, vector<i64>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> h[i][j];
        }
    }

    vector<i64> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    i64 dp0 = 0, dp1 = a[1];
    for (int i = 1; i < n; i++) {
        vector<int> tp(4);
        for (int j = 1; j <= n; j++) {
            i64 d = h[i][j] - h[i + 1][j];
            if (d == 0) {
                tp[0] = tp[3] = 1;
            } else if (d == 1) {
                tp[1] = 1;
            } else if (d == -1) {
                tp[2] = 1;
            }
        }

        if (tp[0] && tp[1] && tp[2] && tp[3]) {
            dp0 = dp1 = inf;
            break;
        }
        i64 ndp0 = inf, ndp1 = inf;
        if (!tp[0]) ndp0 = min(ndp0, dp0);
        if (!tp[2]) ndp0 = min(ndp0, dp1);
        if (!tp[1]) ndp1 = min(ndp1, dp0 + a[i + 1]);
        if (!tp[3]) ndp1 = min(ndp1, dp1 + a[i + 1]);

        dp0 = ndp0;
        dp1 = ndp1;
    }
    i64 xx = min(dp0, dp1);

    dp0 = 0, dp1 = b[1];
    for (int j = 1; j < n; j++) {
        vector<int> tp(4);
        for (int i = 1; i <= n; i++) {
            i64 d = h[i][j] - h[i][j + 1];
            if (d == 0) { 
                tp[0] = tp[3] = 1; 
            } else if (d == 1) { 
                tp[1] = 1; 
            } else if (d == -1) { 
                tp[2] = 1; 
            }
        }

        if (tp[0] && tp[1] && tp[2] && tp[3]) {
            dp0 = dp1 = inf;
            break;
        }
        i64 ndp0 = inf, ndp1 = inf;
        if (!tp[0]) ndp0 = min(ndp0, dp0);
        if (!tp[2]) ndp0 = min(ndp0, dp1);
        if (!tp[1]) ndp1 = min(ndp1, dp0 + b[j + 1]);
        if (!tp[3]) ndp1 = min(ndp1, dp1 + b[j + 1]);

        dp0 = ndp0;
        dp1 = ndp1;
    }
    i64 yy = min(dp0, dp1);

    if (xx >= inf / 2 || yy >= inf / 2) {
        cout << -1 << '\n';
    } else {
        cout << xx + yy << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

E. Wonderful Teddy Bears

  1. 段落分解
    把原串看成一堆 “B…B” 之间夹着的若干 P 段：

    • 先把所有 B 的下标收集到 pos（在最前面加一个 −1 做哨兵），

    • 然后对相邻的两次 B，下标差减 1 就是中间连续的 P 的数目，存入数组 x。

    • 最后再在 x 末尾添加一个长度为 1 的哨兵段（方便后面操作统一处理）。

  2. 操作等价
    每次在位置 i 的窗口 [i,i+1,i+2] 里把黑熊都挪到左边，相当于：

    • 如果一个 P 段里有 ≥2 个 P，可以一次操作把其中的 2 个 P “跳过”一个 B，直接送到行尾（即把它们从 x[i] 中减去 2，同时计入答案的消耗 (M−1−i)）。

    • 如果一个 P 段里只有 1 个 P，则要和后面某个也还剩 P 的段配成一对：

      • 找到下一个非零段 p，把它们调整到同一“奇偶”距离上（保证能在一次操作中相互抵消），

      • 从 x[i] 减 1、给 x[k] 加 1，答案加 (k−i)/2。

  3. 批量与配对

    • 我们用一个 最大堆 持续挑有可能继续操作的段下标 i，

    • 还用一个 有序集合 快速定位下一个非零段 p。

    • 每次操作后，只要 x[i] 还能 ≥2 或 =1，就把它重新推回队列，保证所有可做的消除和配对都被执行到。

  4. 收尾处理
    当再也找不到能配对的 P，就剩下一些 孤立的 P，总数记作 rem。
    剩余的消除操作数，可证明是

    • 如果 rem 是偶数：rem2(rem2+1)\frac{rem}{2}\bigl(\frac{rem}{2}+1\bigr)2rem​(2rem​+1)

    • 如果 rem 是奇数：(rem2+1)2\bigl(\frac{rem}{2}+1\bigr)^2(2rem​+1)2
      把它加到答案上即可。

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
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = (s[i] == 'P');
    }

    vector<int> pos;
    pos.push_back(-1);

    for (int i = 0; i < n; i++) {
        if (!a[i]) {
            pos.push_back(i);
        }
    }

    int cnt = pos.size();

    vector<i64> x;
    for (int i = 0; i < cnt - 1; i++) {
        x.push_back(pos[i + 1] - pos[i] - 1);
    }

    x.push_back(1);
    int M = x.size();

    i64 ans = 0;
    priority_queue<int> pq;
    for (int i = 0; i < M - 1; i++) {
        pq.push(i);
    }

    set<int> fst;
    for (int i = 0; i < M; i++) {
        fst.insert(i);
    }

    while (!pq.empty()) {
        int i = pq.top();
        pq.pop();

        if (i < 0 || i + 1 > M) {
            continue;
        }

        if (x[i] >= 2) {
            i64 cur = x[i] / 2;
            ans += 1LL * cur * (M - 1 - i);
            x[i] %= 2;

            for (int d = -2; d <= 2; d++) {
                int p = i + d;
                if (p >= 0 && p + 1 < M) {
                    pq.push(p);
                }
            }

            continue;
        }

        if (x[i] == 0) {
            continue;
        }

        int p = i + 1;
        while (true) {
            if (p >= M) {
                break;
            }

            if (x[p] == 0) {
                fst.erase(p);
                auto it = fst.upper_bound(p);
                if (it == fst.end()) break;
                p = *it;
            } else {
                break;
            }
        }

        if (p >= M) continue;

        int k = p;
        if ((i + k) & 1) k--;
        if (i == k) continue;

        x[i]--;
        x[k]++;
        fst.insert(k);
        ans += (k - i) / 2;

        for (int d = -2; d <= 2; d++) {
            int u = i + d;
            if (u >= 0 && u + 1 < M) {
                pq.push(u);
            }

            int v = k + d;
            if (v >= 0 && v + 1 < M) {
                pq.push(v);
            }
        }
    }

    i64 rem{};
    for (int i = 0; i + 1 < M; i++) {
        rem += x[i];
    }

    if (rem & 1) {
        i64 t = rem / 2 + 1;
        ans += t * t;
    } else {
        ans += (rem / 2) * (rem / 2 + 1);
    }

    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}