Codeforces Round 534 题解

发表于 | 分类于 |
字数统计: 923 字

我坑我自己

本次比赛中有亮点的题目：Div2 D(Div1 B)。

Div2 A

题目大意：给定一个数$n$，求出它的一种整数分拆，使得对于任何$i$有，且使得中不同的数种数尽量少。

所以全输出1就行了。就一种数。

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int main(){
    scanf("%d", &n);
    printf("%d\n", n);
    for(int i = 0; i < n - 1; ++i)
        printf("1 ");
    printf("1\n");
    return 0;
}

Div2 B

题目大意：给定只包含小写字母的字符串$s$，两个人对串做操作，一个人可以选择串中任意一个相邻的相同字母对删去，然后另一个人操作，如此反复，最后无法操作的人输。假设两人足够聪明，判断输赢情况。

类似于括号序列，用一个栈处理消除事件，最后根据总共消去的对数的奇偶性判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[100005];
int n, cnt = 0, top = 0;
char st[100005] = {0};
int main(){
    scanf("%s", s);
    n = strlen(s);
    for(int i = 0; i < n; ++i){
        if(top && st[top - 1] == s[i])
            top--, cnt++;
        else
            st[top++] = s[i];
    }
    printf("%s\n", cnt % 2 == 0 ? "No" : "Yes");
    return 0;
}

Div2 C(Div1 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[10005];
int main(){
    scanf("%s", s);
    int len = strlen(s);
    int modee = 0;
    for(int i = 0; i < len; i += 2){
        if(len - i == 1) break;
        if(s[i] == '0'){
            if(s[i + 1] == '0'){
                if(modee == 0) printf("1 1\n3 1\n");
                else printf("3 1\n1 1\n");
            }else{
                if(modee == 0) printf("1 1\n1 2\n"), modee = 1;
                else printf("1 4\n2 2\n"), modee = 0;
            }
        }else{
            if(s[i + 1] == '0'){
                if(modee == 0) printf("1 2\n1 1\n"), modee = 1;
                else printf("2 2\n1 4\n"), modee = 0;
            }else{
                if(modee == 0) printf("1 1\n1 3\n");
                else printf("3 1\n3 3\n");
            }
        }
    }
    if(len % 2 == 1) printf("3 3\n");
    return 0;
}

Div2 D(Div1 B)

题目大意：根据提问结果猜一个数$a$，每次提问给出2个数$x, y$，返回x（或y），表示$x \mod a \ge y \mod a$（或$x \mod a < y \mod a$）。至多提问60次。

很少见的一个交互题。
这道题基于一个倍增的想法：首先询问$(0, 1)$，如果答案在$(0, 1]$上那么就会返回x，否则再询问$(1, 2)$，如果答案在$(1, 2]$上就返回x，否则再询问$(2, 4)$…如此反复，根据归纳法，询问到$(n, 2n)$的时候，已经能够确认$a$不在$[1, n]$上了，因此如果返回值是x就可以判断$a$落在当前区间上。
依照此法找到$a$所在区间之后，按照上面的方法再对所在区间二分即可。
由于$\log n \approx 30$，因此询问在60次内可以完成。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[105];
int main(){
    for(; ; ){
        scanf("%s", s);
        if(s[0] == 'e') break;
        int l = 0, r = 1;
        for(; ; ){
            printf("? %d %d\n", l, r);
            fflush(stdout);
            scanf("%s", s);
            if(s[0] == 'x') break;
            l = r, r <<= 1;
        }
        while(r - 1 > l){
            int mid = (r + l) >> 1;
            printf("? %d %d\n", l, mid);
            fflush(stdout);
            scanf("%s", s);
            if(s[0] == 'x') r = mid;
            else l = mid;
        }
        printf("! %d\n", r);
        fflush(stdout);
    }
    return 0;
}

Div2 E(Div1 C)