比赛链接：https://atcoder.jp/contests/agc037

A. Dividing a String

题目链接：https://atcoder.jp/contests/agc037/tasks/agc037_a

题目大意：将字符串分成若干个部分，满足相邻两个部分不相同。

我的做法

我一开始的想法是基于贪心，有相同的字符就让后一个变成长度为 $2$ 的字符串。

然后如果在 $n-1$ 就直接把 $n-1,n$ 合并了。

但是在写博客的时候发现我当时漏考虑了一种情况：$aaaaa$ ，这种情况我的想法会分出：$a|aa|aa$ 。

但最终结果还是一样的，为啥？因为对于最后以个串，假设分成了：$a|aa|a|aa…|aa|aa$ ，那么一定能变成：$aa|a|aa|a…|a|aa$ 。

但是为什么这是最优解呢？

我们不妨先想一个弱化版问题，如果 $abcd$ 中 $b=c$ ，那么必须有 $ab,bc,cd$ 中的其中一个满足（$ab$ 指 $ab$ 在一个部分，其余同理）

这样，我们可以把原问题看成 $n-1$ 个数字，然后有一堆要求 $[l,r]$ 中必须删除一个数字的要求，而这个问题的答案显然是删除剩下区间中 $r$ 最小的区间的 $r$ 位置。

显然任何一个合法解都满足上述要求，而上面求出了在这个要求下需要的最小合并数，如果这个能够是解，则就是最优解。

然后讨论易证上面的这个最小合并数能够构造出一个合法解，然后就做完了。

时间复杂度：$O(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
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
char st[N];
int n;
void get_char_array(char *s){
    static char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * strlen(ss));
}
int main(){
    get_char_array(st);
    n = strlen(st + 1);
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(i != n && st[i] == st[i + 1]){
            if(i == n - 1){
                cnt += 1;
                break;
            }
            else{
                cnt += 2;
                i += 2;
            }
        }
        else cnt++;
    }
    cout << cnt << "\n";
    return 0;
}

B. RGB Balls

题目链接：https://atcoder.jp/contests/agc037/tasks/agc037_b

题目大意：给 $3N$ 个球， 红蓝黄个数相同，要求你给 $N$ 个人分球，满足每个人每个颜色各一个球，最小化每个人拿到的球的下标最大值减最小值之和。

我的做法

我们可以这么想这个过程（用 $A,B,C$ 代表三个颜色）。

我们现在有一堆 $AB,A,AC…$ 然后进来一个新的颜色，我们希望去拿它匹配。

就比如说进来一个 $A$ 吧，那么，如果有现成的 $BC/CB$ 一定会去匹配，因为答案可以写成：$\sum\limits_{e_i-s_i}$ （$e_i$ 表示结束时间，$s_i$ 表示开始时间）。

证明就是交换，无论这个 $A$ 去和其他什么乱七八糟的东西匹配，最后和 $BC/CB$ 匹配的 $A’$ 交换，都会使答案下降。

同理，如果没有 $BC/CB$ ，但是有 $B/C$ ，也会去匹配，而不是单开一个，证明也是交换。

因此做法就出来了，当前剩下的对是固定的，而且和前缀每个颜色的个数有关，例如 $A>B>C$ ，那么就有 $A-B$ 个 $A$ ，$B-C$ 个 $AB/BA$ 。

根据这个 $dp$ 计数就行了。

时间复杂度：$O(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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 1e5 + 5;
const int B = 5;
void get_char_array(char *s){
    static char ss[N * 3];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * strlen(ss));
}
int n, now;
char st[N * 3];
int cnt[B], id[B], be[B];
char num[300];
int main(){
    num['R'] = 0;
    num['G'] = 1;
    num['B'] = 2;
    cin >> n;
    get_char_array(st);
    LL ans = 1ll;
    for(int i = 0; i <= 2; i++) id[i] = i;
    for(int i = 1; i <= n * 3; i++){
        now = num[st[i]];
        sort(id, id + 3, [](int x, int y){
            if(cnt[x] == cnt[y]) return (x == now) > (y == now);
            return cnt[x] > cnt[y];
        });
        for(int j = 0; j <= 2; j++) be[id[j]] = j;
        if(be[now] == 0);
        else ans = ans * (cnt[id[be[now] - 1]] - cnt[now]) % mod;
        cnt[now]++;
    }
    for(int i = 1; i <= n; i++) ans = ans * i % mod;
    cout << ans << "\n";
    return 0;
}

不过这个做法在 $4$ 个及以上的颜色就爆了，只能 $3$ 个。

原因是：$ABACC$ ，在有了 $AB,A$ 后，由于 $ABC$ 不是成品，所以 $CC$ 可以以任意顺序匹配现有的串，导致性质失效，所以无法再用上述的方法计数。

C. Numbers on a Circle

题目链接：https://atcoder.jp/contests/agc037/tasks/agc037_c

题目大意：所有数字在环上，可以进行一个操作，选择一个数字，令其加上相邻两个数字之和，所有数字为正数，问能不能使所有数字由 $a\to b$ 。

我的做法

注意到一个事情，由于所有数字都是正数，那么 $b$ 中的局部极大值都一定是这个局部最后操作的，或者说以他为中心的相邻三个数字中最后一个操作的，因此我们可以直接尝试从 $b$ 还原到 $a$ 。

注意到等价于用局部最大值去模相邻两个数字之和，每次取模一定会少一半，因此次数上界为 $O(n\log{V})$ 。

注意到最大值一定是局部极大值，直接用堆就行了。

时间复杂度：$O(n\log{V}\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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PLI;
const int N = 2e5 + 5;
priority_queue<PLI> p;
int a[N], b[N];
int n;
int preid(int x){return x == 1 ? n : x - 1;}
int nexid(int x){return x == n ? 1 : x + 1;}
LL solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        p.push({b[i], i});
        if(b[i] < a[i]) return -1ll;
    }
    LL cnt = 0ll;
    while(!p.empty()){
        auto [d, id] = p.top();
        p.pop();
        int pid = preid(id);
        int nid = nexid(id);
        LL val = b[pid] + b[nid];
        LL T = min( (b[id] - a[id]) / val, (b[id] - max(b[pid], b[nid])) / val + 1);
        cnt += T;
        b[id] -= T * val;
        if(b[id] > a[id] && b[id] >= max(b[pid], b[nid])) return -1ll;
        if(b[id] > a[id]) p.push({b[id], id});
    }
    return cnt;
}
int main(){
    cout << solve() << "\n";
    return 0;
}

D. Sorting a Grid

题目链接：https://atcoder.jp/contests/agc037/tasks/agc037_d

题目大意：给一个矩形，矩形中的数字都是 $[1,nm]$ 且不同，然后有三次操作，第一次对所有行重排，第二次对所有列重排，第三次对所有行重排，给一种方案使得最后矩形变成 $1,2,3,….$ 的矩形。

我的做法

很有意思的一道题目，注意到问题可以等价于在第一步行排列的时候，让每一行的数字在每一列都有一个，即把最终矩阵中每一行的数字给同一个颜色，不同行不同颜色，然后希望在行排列后，每一列中的颜色都是不一样的。

这个时候有一个二分图匹配的感觉，很可惜的是，建不出能过的图。

那么怎么做呢？注意到在列数只有两个的时候，等价于将每一行的两个颜色连边然后找环，这启示我们是与图相关的算法。那还能不是二分图匹配？

又注意到，如果一定有解的话，我们可以归纳，即先摆出一列，剩下的部分就是一个子问题，因此问题是怎么摆出一列。

注意到这个时候用二分图匹配就可以，至于为什么二分图匹配一定有解，可以使用 Hall 定理证明。

时间复杂度：$O(n^4)$ 。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
const int NN = 1e4 + 5;
int n, m;
vector<int> cnt[N][N];
int getid(int x){return (x - 1) / m + 1;}
namespace Graph{
    int mat[N];
    bool e[N][N], v[N];
    void ins(int x, int y){e[x][y] = 1;}
    bool findmatch(int x){
        v[x] = 1;
        for(int i = 1; i <= n; i++){
            if(!e[x][i]) continue;
            if(!mat[i] || (!v[mat[i]] && findmatch(mat[i]))){
                mat[i] = x;
                return 1;
            }
        }
        return 0;
    }
    void solve(){
        for(int i = 1; i <= n; i++){
            memset(v, 0, sizeof(v));
            assert(findmatch(i));
        }
    }
    void init(){
        memset(e, 0, sizeof(e));
        memset(mat, 0, sizeof(mat));
    }
}
using Graph::ins;
using Graph::init;
using Graph::solve;
using Graph::mat;
int ans1[N][N], ans2[N][N];
int id[N];
int tmp;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int x;
            cin >> x;
            cnt[i][getid(x)].push_back(x);
        }
    }
    for(int t = 1; t <= m; t++){
        Graph::init();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(!cnt[i][j].empty()) ins(j, i);
            }
        }
        Graph::solve();
        for(int i = 1; i <= n; i++){
            int col = mat[i];
            ans1[i][t] = cnt[i][col].back();
            cnt[i][col].pop_back();
        }
    }
    for(int i = 1; i <= n; i++) id[i] = i;
    for(int j = 1; j <= m; j++){
        tmp = j;
        sort(id + 1, id + n + 1, [](int x, int y){return getid(ans1[x][tmp]) < getid(ans1[y][tmp]);});
        for(int i = 1; i <= n; i++) ans2[i][j] = ans1[id[i]][j];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) cout << ans1[i][j] << " ";
        cout << "\n";
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) cout << ans2[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

就算用网络流时间复杂度也是：$O(n^3\sqrt{n})$ 的，但是如果用 Vizing 定理可以做到 $O(n^3)$ ，做法写在了 Vizing 定理学习笔记中了。

E

题目链接：https://atcoder.jp/contests/agc037/tasks/agc037_e

题目大意：你可以对字符串进行以下操作 $K$ 次：

$S$ 翻转得到 $S’$ ，在 $SS’$ 中找到长度为 $n$ 的字符串替代 $S$ 。

问最后得到的最小字典序的字符串。

做法

这是题？

显然一个事情，设 $maxlen=SS’$ 中最长的连续最小字符。

那么显然最后得到的字符串的前缀一定 $\le maxlen*2^{K-1}$ ，而且等号成立当且仅当每一步中都选择最长的连续最小字符段为后缀（最后一次为前缀）.

可以注意到，除了第一次有多种选择，后面都只有唯一选择。

因此直接暴力就行了，时间复杂度：$O(n^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
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
char st[N];
void get_char_array(char *s){
    static char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * strlen(ss));
}
char ans[N], now[N], tmp[N];
int n, K;
char query(int pos){
    return pos > n ? st[n + n - pos + 1] : st[pos];
}
void rev(char *s){
    for(int i = 1; i + i <= n; i++) swap(s[i], s[n - i + 1]);
}
bool cmp(char *s1, char *s2){ // s1 < s2
    for(int i = 1; i <= n; i++){
        if(s1[i] != s2[i]) return s1[i] < s2[i];
    }
    return 0;
}
void updata(){
    if(cmp(now, ans)) swap(ans, now);
}
int main(){
    cin >> n >> K;
    get_char_array(st);
    char minchar = 'z';
    for(int i = 1; i <= n; i++) minchar = min(minchar, st[i]);
    int maxlen = 1;
    for(int l = 1; l <= n; l++){
        if(st[l] != minchar) continue;
        int r = l;
        while(r < n && st[r + 1] == minchar) r++;
        if(r == n) maxlen = max((r - l + 1) * 2, maxlen);
        else maxlen = max(maxlen, r - l + 1);
    }
    for(int i = 1; i <= n; i++) ans[i] = st[i];
    for(int l = 1; l <= n; l++){
        if(st[l] != minchar) continue;
        int r = l;
        while(r < n && st[r + 1] == minchar) r++;
        if((r != n && (r - l + 1) == maxlen) || (r == n && (r - l + 1) * 2 == maxlen)){
            int endpos = n + (n - l + 1);
            for(int t = 0; t < n; t++) tmp[n - t] = query(endpos - t);
            int startpos = 1;
            if(K >= 14 || maxlen * (1 << (K - 1)) >= n) startpos = n + 1;
            else startpos += maxlen * (1 << (K - 1)) - maxlen;
            for(int t = 0; t < n; t++){
                if(t + startpos <= n) now[t + 1] = tmp[t + startpos];
                else now[t + 1] = minchar;
            }
            rev(now);
            updata();
        }
    }
    cout << ans + 1 << "\n";
    return 0;
}

幽默题目。