跃迁引擎启动

Codeforces Round 545 题解

发表于 更新于 分类于 阅读次数：

A Sushi for Two

给定一个序列，求最长的一个子串，满足 $00 \dots 011 \dots 1$。

预处理每个位置后的最长连续 $1$ 或 $2$，扫一遍即可。

B Circus

有 $n$ 个人，每个人可以表演 a 或 c 两种节目，将 $n$ 个人分成大小相同的两块，满足第一块能够表演 a 的人和第二块表演能够 c 的人数相同。

一共有四类，两种都无法表演，表演一种和两种都不能表演。

枚举第一块表演 a 的个数和第二块表演 c 的个数，解一个关于两种都行的方程即可。

注意各种边界条件。

C Skyscrapers

给定一个 $n \times m$ 的矩阵，独立询问每个位置所在行和列，用数字 $1$ 到 $x$ 去替换这一行一列的数字，使得原来的行内数字大小关系不变，列内数字大小关系不变。

对每一行和每一列分别离散化，询问就是行列比当前位置的数小的个数的最大值，以及对应大的最大值，最后加 $1$。

D Camp Schedule

给定 $01$ 串 $s$ 和 $t$，要求任意调换 $s$ 串内的顺序，使得新串包含最多的子串 $t$。

对 $t$ 串建 $KMP$ 的 $fail$ 指针，扫一遍贪心构造即可。

F Cooperative Game

有一个长度为 $t+c$ 的有向链，其中 $t+c$ 连向 $t+1$。

起点为 $1$，终点为 $t+1$，一开始有 $10$ 个人在起点。

每次可以移动一些点到其对应的下一个位置，返回哪些点在相同位置。

要求在 $3 \times (t+c)$ 次操作内将这些人移动到起点。

龟兔赛跑判环。

取两个点，每次一个点走 $1$ 步，一个点走 $2$ 步，设最后相遇在第 $x$ 步

$$
x-t \equiv 2x-t (mod \text{ } c)
$$

因此，$c|x$，然后起点和相遇点一同往后移动，显然第一次相遇在 $t$ 处。

代码

A

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 100000 + 5;

int n, a[maxn], suf[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = n; i >= 1; i--) {
        if (a[i] == 2) suf[i] = suf[i + 1] + 1;
        else suf[i] = 0;
    }
    int ans = 0, tot = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            tot++;
            ans = max(ans, min(tot, suf[i + 1]));
        } else tot = 0;
    }
    reverse(a + 1, a + 1 + n);
    for (int i = n; i >= 1; i--) {
        if (a[i] == 2) suf[i] = suf[i + 1] + 1;
        else suf[i] = 0;
    }
    tot = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            tot++;
            ans = max(ans, min(tot, suf[i + 1]));
        } else tot = 0;
    }
    cout << ans * 2 << endl;
    return 0;
}

B

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
  #define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
  #define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 100000 + 5;

int n; char c[maxn], a[maxn];

int c1, c2, c3, c4;
int check(int x, int y) {
    if (y - x + c4 < 0) return 0;
    if ((y - x + c4) % 2) return 0;
    
    int k = (y - x + c4) / 2;
    int a2 = x, a3 = c3 - y, a4 = k, a1 = n / 2 - a2 - a3 - a4;

    if (k > c4) return 0;
    if (a1 < 0 || a1 > c1) return 0;

    for (int i = 1; i <= n; i++) {
        if (c[i] == '0' && a[i] == '0') {
            if (a1) printf("%d ", i), a1--;
        }
        if (c[i] == '1' && a[i] == '0') {
            if (a2) printf("%d ", i), a2--;
        }
        if (c[i] == '0' && a[i] == '1') {
            if (a3) printf("%d ", i), a3--;
        }
        if (c[i] == '1' && a[i] == '1') {
            if (a4) printf("%d ", i), a4--;
        }
    }
    return 1;
}

int main() {
    scanf("%d%s%s", &n, c + 1, a + 1);
    for (int i = 1; i <= n; i++) {
        if (c[i] == '0' && a[i] == '0') c1++;
        if (c[i] == '1' && a[i] == '0') c2++;
        if (c[i] == '0' && a[i] == '1') c3++;
        if (c[i] == '1' && a[i] == '1') c4++;
    }
    for (int i = 0; i <= c2; i++) for (int j = 0; j <= c3; j++) if (check(i, j)) return 0;
    puts("-1");
    return 0;
}

C

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 1000 + 5;

int n, m, a[maxn][maxn], ans[maxn][maxn];
vector<int> row[maxn], col[maxn];

void init(vector<int>& v) {
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
}
int gid(int x, vector<int>& v) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        scanf("%d", &a[i][j]);
        row[i].push_back(a[i][j]);
        col[j].push_back(a[i][j]);
    }
    for (int i = 1; i <= n; i++) init(row[i]);
    for (int i = 1; i <= m; i++) init(col[i]);
    for (int i = 1; i <= n; i++, puts("")) for (int j = 1; j <= m; j++) {
        int x = gid(a[i][j], row[i]);
        int y = gid(a[i][j], col[j]);
        printf("%d ", 1 + max(x - 1, y - 1) + max((int)row[i].size() - x, (int)col[j].size() - y));
    }
    return 0;
}

D

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 500000 + 5;

char s[maxn], t[maxn], ans[maxn];
int nxt[maxn];

void getnxt() {
    int len = strlen(t), i = 0, j = -1; nxt[0] = -1;
    while (i < len) {
        if (j == -1 || t[i] == t[j]) i++, j++, nxt[i] = j;
        else j = nxt[j];
    }
}

int main() {
    scanf("%s%s", s, t);
    getnxt();
    int c[2] = {0, 0};
    for (int i = 0; s[i]; i++) c[s[i] - '0']++;
    int slen = strlen(s), tlen = strlen(t), i = 0, j = 0;
    while (i < slen && j < tlen) {
        if (j == -1) {
            if (c[t[0] - '0']) {
                ans[i] = t[0]; c[t[0] - '0']--;
            } else {
                ans[i] = (t[0] - '0' + 1) % 2 + '0';
                c[ans[i] - '0']--;
            }
            i++; j++;
        } else if (c[t[j] - '0']) {
            ans[i] = t[j]; c[t[j] - '0']--;
            i++; j++;
        } else j = nxt[j];
        if (j == tlen) j = nxt[j];
    }
    cout << ans << endl;
    return 0;
}

F

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 100000 + 5;

string query(vector<int> v) {
    cout << "next";
    for (int& x: v) cout << ' ' << x;
    cout << endl;
    string s; getline(cin, s);
    return s;
}

int main() {
    while (true) {
        query({0, 1});
        string s = query({1});
        if (s.find("01") != string::npos) break;
    }
    vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    while (true) {
        string s = query(v);
        if (s.find("0123456789") != string::npos) break;
    }
    cout << "done" << endl;
    return 0;
}