松鼠的小站


优质坚果提供地

Codeforces Round 712

  • 2021-04-23
  • 作者 sosusosu
  • ~10.27K 字
  1. 1. Codeforces Round #712 (Div. 2)(cf contest 1504)
    1. 1.1. A Déjà Vu
    2. 1.2. B Flip the Bits
    3. 1.3. C Balance the Bits
    4. 1.4. D 3-Coloring
    5. 1.5. E Travelling Salesman Problem
    6. 1.6. F Flip the Cards
    7. 1.7. 总结

Codeforces Round #712 (Div. 2)(cf contest 1504)

A Déjà Vu

题目大意：给字符串添加一个字母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
#include <bits/stdc++.h>
using namespace std;

int T, ans, n;

char s[300005];

int main(){
    cin >> T;
    while(T--){
        cin >> s + 1, n = strlen(s + 1), ans = -1;
        for(int i = 1; i <= n; i++) if(s[n - i + 1] != 'a'){
            ans = i;
            break;
        }
        if(ans == -1) puts("NO");
        else{
            puts("YES");
            for(int i = 1; i <= n; i++){
                if(i == ans) cout << 'a';
                cout << s[i];
            }
            puts("");
        }
    }
    return 0;
}

B Flip the Bits

题目大意：给一个01串，现有操作就是对于当前它的前缀，假如0和1的个数相等，就可以把0变1把1变0，最后要通过操作将A串变成B串。

解法：观察操作性质，发现任何一次操作都不影响别的点是否可以操作，所以从后往前扫，如果当前A串和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
#include <bits/stdc++.h>
using namespace std;

int T, ans, n, num[2][300005], fl;

char s[300005], t[300005];

int main(){
    cin >> T;
    while(T--){
        cin >> n >> s + 1 >> t + 1, ans = 1, fl = 1;
        for(int i = 1; i <= n; i++) num[0][i] = num[0][i - 1], num[1][i] = num[1][i - 1], num[s[i] == '1'][i]++;
        for(int i = n; i; i--){
            if((s[i] != t[i]) == (fl)){
                if(num[1][i] != num[0][i]){
                    ans = 0;
                }
                else fl = !fl;
            }
        }
        puts(ans ? "YES" : "NO");
    }
    return 0;
}

C Balance the Bits

题目大意：需要构造两个可以匹配的括号序列（包含左右括号，括号序列的匹配就是，哎呀去百度一下这里就不写了），首先每个括号序列需要满足给定的位置括号是一样的，剩下位置括号都是相反的（可以看样例，样例是很形象的）。

解法：实际上说是构造两个个序列，但是由于这两个序列的对应位置要么相同要么不同，所以是两个序列对应的（因为左括号反过来只有右括号一种情况）。之后考虑普通括号序列匹配的条件，我们有了num[右][i]>=num[左][i]且num[右][n]==num[左][n]，其中num[右][i]代表从左到第i个位置，右括号的数量，num[左][i]同理。之后再根据两个序列有一部分是一样的，一部分是截然相反的，那么对于第一个序列，num[右][一样][i]代表从左边到第i个位置，两个序列中都一样的右括号的数量，我们就有了：对于第一个序列num[右][一样][i]+num[右][不一样][i]>=num[左][一样][i]+num[左][不一样][i]，而因为所有不一样的元素都是反着的，所以对于第二个序列我们又有了num[右][一样][i]+num[左][不一样][i]>=num[左][一样][i]+num[右][不一样][i]，而在当i=n时，我们又有num[右][一样][i]+num[右][不一样][i]==num[左][一样][i]+num[左][不一样][i]且num[右][一样][i]+num[左][不一样][i]==num[左][一样][i]+num[右][不一样][i]。

故而根据上述的式子，我们可以选取一种贪心的策略，那就是尽量确保num[右][一样][i]>num[左][一样][i]且num[右][不一样][i]==num[左][不一样][i]，这样才能更好的满足上述的几个式子，所以我们在两个序列都相同的位置优先填左括号，左括号填完之后再填右括号，而对于两个序列不一样的位置 ，我们一左一右这样填，假如这样填到最后都没法满足条件，那么也就不存在别的情况可以满足了。

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

int T, ans, n, num[2], fl, w[2][2], cnt;

char s[300005], t[300005];

int main(){
    cin >> T;
    while(T--){
        cin >> n >> s + 1, fl = ans = 1, cnt = num[0] = num[1] = 0;
        memset(w, 0, sizeof(w));
        for(int i = 1; i <= n; i++) num[s[i] == '1']++;
        if(num[0] & 1){
            puts("NO");
            continue;
        }
        for(int i = 1; i <= n; i++) 
            if(s[i] == '1'){
                cnt++, t[i] = (cnt <= (num[1] / 2)) ? '(' : ')';
            }
            else{
                t[i] = fl ? '(' : ')', fl = !fl;
            }
        for(int i = 1; i <= n; i++){
            if(s[i] == '1'){
                w[1][t[i] == ')']++;
            }
            else{
                w[0][t[i] == ')']++;
            }
            if(w[1][0] + w[0][0] < w[1][1] + w[0][1] || w[1][0] + w[0][1] < w[1][1] + w[0][0]){
                ans = 0;
            }
            if(i == n){
                if(w[1][0] != w[1][1] || w[0][1] != w[0][0]) ans = 0;
            }
        }
        puts(ans ? "YES" : "NO");
        if(ans){
            for(int i = 1; i <= n; i++) cout << t[i]; cout << endl;
            for(int i = 1; i <= n; i++) if(s[i] == '0') t[i] = t[i] == '(' ? ')' : '(';
            for(int i = 1; i <= n; i++) cout << t[i]; cout << endl;
        }
    }
    return 0;
}

D 3-Coloring

题目大意：交互题，n*n的方格染色，一共有三种颜色，相邻的格子不能有同样的颜色，每次操作是首先程序给我们一个不能使用的颜色，我们来选择剩下的两种颜色之一，输出给哪个格子染这个颜色，最终要求把所有格子都合法的染完。

解法：简单的看一下n*n的格子图，我们可以把整张图可以将所有格子分为两类，分类方法就是斜线，显然斜着的一行格子之间不会有任何点相邻，而奇数斜线行格子之间的所有格子都不相邻，偶数行也同理。

1 0 1

0 1 0

1 0 1

就像这样将所有点分为两类。由于这两类之中，每一类任两个点都不相邻，所以我们可以使用以下策略：用颜色1来填第一类点，那么只要程序禁用颜色1，我们就用颜色2填第二类。必然会有一类先填完，而剩下如果是第一类，就用颜色1和颜色3来填，由于有两种颜色他没办法全部禁用，同理如果剩下的是第二类，我们就用颜色2和颜色3来填剩下的第二类格子。

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

int T, n, m, x, y, b, c1, c2, l1 = 1, l2 = 1;

int main(){
    cin >> n, T = n * n, c1 = 1, c2 = 2;
    while(T--){
        cin >> m;
        if(l1 <= n && l2 <= n){
            if(m != 1){
                x = l1, y = c1, c1 += 2, b = 1;
                if(c1 > n) l1++, c1 = 1 + !(l1 & 1);
            }
            else{
                x = l2, y = c2, c2 += 2, b = 2;
                if(c2 > n) l2++, c2 = 1 + (l2 & 1);
            }
        }
        else{
            if(m == 3){
                if(l1 <= n){
                    x = l1, y = c1, c1 += 2, b = 1;
                    if(c1 > n) l1++, c1 = 1 + !(l1 & 1);
                }
                else if(l2 <= n){
                    x = l2, y = c2, c2 += 2, b = 2;
                    if(c2 > n) l2++, c2 = 1 + (l2 & 1);
                }
            }
            else{
                if(l1 <= n){
                    x = l1, y = c1, c1 += 2;
                    if(c1 > n) l1++, c1 = 1 + !(l1 & 1);
                }
                else if(l2 <= n){
                    x = l2, y = c2, c2 += 2;
                    if(c2 > n) l2++, c2 = 1 + (l2 & 1);
                }
                b = 3;
            }
        }
        cout << b << ' ' << x << ' ' << y << endl, cout.flush();
    }
    return 0;
}

E Travelling Salesman Problem

题目大意：有n个点，任两个点i,j之间的通行花费是max(ci,aj-ai)，问从1点出发遍历所有点均一次最后回到1点的方案。

解法：观察题面，实际上就是完全图然后找一个长为n的最小环，每个点都被遍历一次，那么实际上他就和1作为起点关系不大了，因为它是一个环。那么朴素的枚举起点显然是过不了的，我们考虑这个加边的时候取通行花费的max(ci,aj-ai)，显然如果当前的点ai很大，那么它通向所有的点的花费都是ci，而每个点出发的花费最少就是ci，于是假如我们的起点是ai最大的点，那么可以通过对剩下的点的a数组进行排序做到每一条路径花费都是最少的。但是因为这是个环，那么现在问题出现在了怎么从最小的点回到最大的点上，如果直接回的话可能会很劣，所以我们可以转换思路，先使用最小的代价从a值最小的点走到a值最大的点，然后再从a最大的点走去其他点，而最终一点是会落在a最小的点上，这样是比刚才的方法更优的。

由于ci的存在，实际上对于一个点来说所有满足于aj<=ai+ci的点代价都是最优的，那么我们就从最小的点开始看他全部通过最小代价能走的最大的点是谁，之后从那个点开始继续向上找，直到找到a值最大的点（也就是查找max{aj+cj (j满足aj∈[0,ai+ci]) 然后令i=j，重复操作}）。假如当前ai+ci就是最大的，那就要产生额外花费了，就得去查找第一个大于ai+ci的aj，然后令i=j重复上述操作了。

这个做法的正确性是显然的，为了朴素的维护这样的一个做法可以使用权值线段树，然后就做出来了。不过好像这题是有On做法的，也有更加方便的写法，但是我个人比较笨，没有去往哪里想，估计也想不到，就这样在cf上用Onlogn水过去了hhhhhh。

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

struct po{
    long long l, r, w;
}t[200005 * 40];

long long ans, n, cnt = 1, rt, mx, a[300005], c[300005], b[300005], mn = 3000000001, st = 1;

void change(long long L, long long R, long long x, long long w, long long &k){
    if(!k) k = ++cnt;
    if(L == R){
        t[k].w = max(t[k].w, w);
        return;
    }
    long long mid = (L + R) >> 1;
    if(x <= mid) change(L, mid, x, w, t[k].l);
    else change(mid + 1, R, x, w, t[k].r);
    t[k].w = max(t[t[k].l].w, t[t[k].r].w);
}

long long que(long long L, long long R, long long l, long long r, long long k){
    if(!k) return 0;
    if(L == l && R == r) return t[k].w;
    long long mid = (L + R) >> 1;
    if(r <= mid) return que(L, mid, l, r, t[k].l);
    else if(l > mid) return que(mid + 1, R, l, r, t[k].r);
    else return max(que(L, mid, l, mid, t[k].l), que(mid + 1, R, mid + 1, r, t[k].r));
}

int main(){
    cin >> n;
    for(long long i = 1; i <= n; i++){
        cin >> a[i] >> c[i];
        b[i] = a[i], ans += c[i], mx = max(mx, a[i] + c[i]);
        if(mn >= a[i]) mn = a[i], st = i; 
        rt = 1, change(0LL, 3000000000LL, a[i], a[i] + c[i], rt);
    }
    sort(b + 1, b + 1 + n);
    long long now = a[st] + c[st], pro;
    while(1){
        pro = que(0LL, 3000000000LL, 0LL, now, 1);
        if(now == mx) break;
        if(pro == now){
            pro = upper_bound(b + 1, b + n + 1, now) - b;
            pro = b[pro], ans += pro - now;
        }
        now = max(now, pro);
    }
    cout << ans << endl;
    return 0;
}

F Flip the Cards

题目大意：n张卡片，一共是有1~2n，2n个数字印在卡片的正反两面上，操作是可以翻转某些卡片，最终要求所有正面的数字排完序之后，背面的数字是相反的大小顺序。

解法：假如某一张卡片上印的两个数字都大于n或者小于等于n，那这种情况显然不合法（证明还是比较好证的，设一下算一下就能看出矛盾了）。所以现在我们的每张卡片都是印着一个1n的和一个n+12n的数字。我们首先假装所有的1n都朝同一面，并且是按从1n有序排好的，那么对于这样的情况来说，假如第一张卡片翻转了，它就一定出现在当前序列的最后，因为它的另一面显然比n要大，而这一面显然比n+1要小，进而当我们翻转第二张时，它一定根据大小关系放在刚刚翻转的那张前边，以此类推。于是我们可以得到一个合法的序列（假如翻转的时候放不到指定的位置，那整个情况都是不合法的），接下来讨论最优解，实际上我们再观察最终排好的序列，会发现整个序列的可以分成几个段的，每一段之间都互不影响，也就是说如果我们有k张牌，k张牌里1n区间内的最大值-最小值是k且n+12n区间内的最大值减去最小值也是k，那么这个区间内的大小关系就只要在这个区间内自己处理就好。最后我们回到这个问题，最优解就是各个区间的最优解加到一起，而区间内的最优值就是假如刚才找出的情况中：要翻的卡片数多，我们就把所有不要翻转的翻一下；如果要翻的卡片数小我们就直接翻转这些卡片。最终我们扫一遍，扫到一个区间就给答案加上这个区间的最小值，就得到了答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include< bits/stdc++.h >
using namespace std;

int n, ans, x, y, a[400005], b[400005], c[400005], cnt, fl, pro[2];

int main(){
	scanf("%d", &n), fl = n + 1;
	for(int i = 1; i <= n; i++)
        scanf("%d%d", &x, &y), a[x] = y, a[y] = x, b[x] = b[y] = (x < y);
    x = y = 2 * n + 1, cnt = 1;
	for(int i = 1; i <= n; i++){
		if(a[i] > y || a[i] <= n) fl = -1;
		if(a[i] < x) x = a[i], c[i] = 0;
        else y = a[i], c[i] = 1;
		if(x == 2 * n - i + 1){
			while(cnt <= i) pro[c[cnt] ^ b[cnt]]++, cnt++;
			ans += min(pro[0], pro[1]), pro[0] = pro[1] = 0;
		}
	}
	printf("%d\n", min(fl, ans));
	return 0;
}

总结

后边还有div1的两道题，实在是做不动了就先放着了，只看div2方面的题目还是比较不错的，类型比较丰富，需要想的内容要比代码写的内容多得多。蛮不错的。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-04-23