Codeforces Round #779 (Div. 2)

A. Marin and Photoshoot

Sample input

9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101

Sample output

4
2
1
0
2
0
0
0
17

题意：

给出一个01串，要求任何一个连续的长度大于2的区间内1的个数大于等于0的个数，判断需要插入的最小字符个数

思路：

两个相邻的0之间最少有两个1，直接插入就行，下面看代码

#include
using namespace std;
const int N = 200010;
char s[200];
void solve(){
    int n,ans = 0;
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++){
        if(s[i] == '0'){
            if(s[i-1] == '0') ans += 2;
            else if(i > 2 && s[i-2] == '0') ans += 1;
        }
    }
    printf("%d\n",ans);
}
int main(){
    int _;
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

B. Marin and Anti-coprime Permutation

Sample input

7
1
2
3
4
5
6
1000

Sample ouput

0
1
0
4
0
36
665702330

题意：

思路：

一开始想的思路就是枚举这个gcd，从2到n，然后发现枚举到3的时候就已经填不满了，所以说答案只能在gcd = 2的情况下进行，因为gcd 需要 = 2，所以说n为奇数的话一定不行，n为偶数的话答案就是(n/2)!*(n/2)!，下面看代码：

#include
using namespace std;
const int N = 200010,mod = 998244353;
void solve(){
    int n;
    long long ans1 = 1,ans2 = 1;
    cin>>n;
    if(n & 1){
        puts("0");
        return;
    }
    for(int i=1;i<=n/2;i++) ans1 = ans1 * i * i % mod;
    printf("%lld\n",ans1);
}
int main(){
    int _;
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

C. Shinju and the Lost Permutation

Sample input

6
1
1
2
1 2
2
2 2
6
1 2 4 6 3 5
6
2 3 1 2 3 4
3
3 2 1

Sample output

YES
YES
NO
NO
YES
NO

题意：

思路：

当ci = 1的时候倒数第i个数就是最大值，那么会发现一个规律，就是在他循环左移的过程中，ci的值增加的话最多增加1，减少的话可以随便，所以说按照这个来判断就可，下面请看代码：

#include
using namespace std;
const int N = 200010;
int a[N];
void solve(){
    int n;
    scanf("%d",&n);
    int root = -1;
    bool flag = true;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i] == 1){
            if(root != -1){
                flag = false;
            }
            root = i;
        }

    }
    if(root == -1 || !flag){
        puts("NO");
        return;
    }
    int i = root + 1,u = i;
    if(i == n+1) i = 1,u = 1;
    while(1){
        if(i == 0) i = 1;
        int j = i - 1;
        if(j == 0) j = n;
        if(a[i] - a[j] >= 2){
            puts("NO");
            return;
        } 
        i ++;
        if(i == n+1) i = 1;
        if(i == u) break;
    }
    puts("YES");
}
int main(){
    int _;
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}
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

D1. 388535 (Easy Version)

Sample input

3
0 3
3 2 1 0
0 3
4 7 6 5
0 2
1 2 3

Sample output

0
4
3

题意：

思路：

从0到r+1的17位中每一位的0的个数一定不比1的个数小，所以说就是看每一位1的个数和n/2的关系就行，如果是大于等于n/2，那么x的这一位就是1，否则就为0，下面看代码：

#include
using namespace std;
const int N = 200010;
int a[N];
int cnt1[40],cnt2[40];
void solve(){
    int l,r;
    scanf("%d%d",&l,&r);
    for(int i=1;i<=r-l+1;i++){
        scanf("%d",&a[i]);
        for(int j=0;j<17;j++){
            if(a[i] >> j & 1){
                cnt2[j] ++;
            }
        }
    }
    int ans = 0;
    for(int i=0;i<17;i++){
        if(cnt2[i] + cnt2[i] > r+1) ans += 1 << i;
        cnt2[i] = 0;
    }
    printf("%d\n",ans);
}
int main(){
    int _;
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}
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