Featured image of post Cf747
codeforces

Cf747

Codeforces Round #747 (Div. 2)

A. Consecutive Sum Riddle

水题，一个为正一个为负即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;
typedef long long ll;
ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0', ch = getchar();}
    return x * f;
}
int main() {
    int t = read();
    while(t --) {
        ll n = read();
        ll l = - n + 1, r = n;
        if(l > r) swap(l, r);
        cout << l << " " << r << endl;

    }
    return 0;
}

B. Special Numbers

给一个 $n$, 用 $n^0,n^1,n^2,\dots$ 组合成数，可以用 $n = 2$ 的情况来观测别的情况

12345678
12345678
134910121327

第一行是标记，第二行是 $n = 2$ 的情况，第三行是 $n = 3$ 的情况，以第 $7$ 个数为例，它的二进制为 111, 当 $n = 2$ ,则第 7 个数由 $2^0,2^1,2^2$ 组成，当 $n = 3$ ,则第 7 个数由 $3^0,3^1,3^2$ 组成，所有对 $k$ 二进制拆分后，就可以得到答案了

 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

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0', ch = getchar();}
    return x * f;
}
ll mod = 1e9 + 7;

ll qp(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
    int t = read();
    while(t --) {
        ll n = read(), k = read();
        ll ans = 0;
        for(int i = 0; i <= 62; i ++) {
            if((k >> i) & 1)
                ans = (ans + qp(n, i)) % mod;
        }
        cout << ans << endl;
    }
    return 0;
}

C. Make Them Equal

如果所给的字符串就是满足条件的那么答案是 $0$，若目标字符串中最后面的与 $c$ 字符相等的下标是 $> \dfrac{n}{2}$ ，则只需要一次操作即可也就是输出这个下标，否则很明显在两次操作内必然能完成，只需要选两个互质的数即可，比如 n, 与 n - 1。

 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 <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0', ch = getchar();}
    return x * f;
}
const int M = 3e5 + 7;
char s[M];

int main() {
    int t = read();
    while (t--) {
        int n = read();
        char ch[2];
        scanf("%s%s", ch, s + 1);
        bool flag = true;
        int last = -1, big = 1;
        for (int i = 1; i <= n; i++) {
            if (s[i] != *ch)
                flag = false;
            else
                big = i;
        }
        if (flag) {
            printf("0\n");
        } else {
            if (s[n] == *ch) {
                printf("1\n");
                printf("%d\n", n);
            } else {
                if (big * 2 > n) {
                    printf("1\n");
                    printf("%d\n", big);
                } else {
                    printf("2\n");
                    printf("%d %d\n", n - 1, n);
                }
            }
        }
    }
    return 0;
}

D. The Number of Imposters

首先一个人有可能是 Imposters， 也有可能是 crewmate ，我们可以发现，如果一个说另一个人是 Imposters，则这两个人的身份必然是相反的，而如果一个说另一个人 Imposters，则这两个人的身份必然是相反的，并且这个关系是双向的，也就是说两个人之间是双向边。我们可以给在一个图中给每个人染色，如果染色冲突了就是无解，输出 -1，否则答案加上两种颜色中个数最多的那个。

 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
80
81
82
83
84
85
86
87
88

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0', ch = getchar();}
    return x * f;
}
const int M = 1e6 + 7, N = 2e5 + 7;

struct Node {
    int to, nxt, w;
} tr[M];

int head[N], idx, color[N], cnt;
char s[20];

void add(int u, int v, int w) {
    tr[idx] = {v, head[u], w};
    head[u] = idx ++;
}
int colornum[3];
bool dfs(int now) {
    for(int i = head[now]; ~i; i = tr[i].nxt) {
        int j = tr[i].to;
        if(!color[j]) {
            if(tr[i].w) {
                color[j] = 3 - color[now];
                colornum[color[j]] ++;
            }
            else {
                color[j] = color[now];
                colornum[color[j]] ++;
            }
            if(!dfs(j)) return false;
        } else {
            if(tr[i].w && color[j] != 3 - color[now]) return false;
            if(!tr[i].w && color[j] == 3 - color[now]) return false;
        }
    }
    return true;
}

int main() {
    int t = read();
    while(t --) {
        idx = 0;
        int n = read(), m = read();
        for(int i = 1; i <= n; i ++) {
            head[i] = -1;
            color[i] = 0;
        }
        for(int i = 1; i <= m; i ++) {
            int x = read(), y = read();
            scanf("%s", s);
            if(*s == 'i') {
                add(x, y, 1);
                add(y, x, 1);
            } else {
                add(x, y, 0);
                add(y, x, 0);
            }
        }
        // 1 imposter, 2 crewmate
        bool flag = true;
        int ans = 0;
        for(int i = 1; i <= n; i ++) {
            if(!color[i]) {
                colornum[1] = 1, colornum[2] = 0;
                color[i] = 1;
                if(!dfs(i)) {
                    flag = false;
                    break;
                }
                ans += max(colornum[1], colornum[2]);
            }
        }
        if(!flag) {
            printf("-1\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

E1. Rubik’s Cube Coloring (easy version)

第一个点是 $6$ 种颜色，它的子节点是 $4$ 种选择，而每个结点有两个子节点，所以答案是 $6\times 2^{2^2 + 2^3 + \dots 2^k}$，快速幂求解即可，注意 1 << k 种的 1 默认为 int，所以左移过多会溢出！

 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 <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0', ch = getchar();}
    return x * f;
}
const int M = 2e5 + 7;
const ll mod = 1e9 + 7;

ll qp(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
    ll k = read();
    if(k == 1) {
        cout << 6 << endl;
    } else {
        ll all = 0;
        for(ll i = 2; i <= k; i ++)
            all += (ll)1 << i;
        all %= mod - 1; // 对指数取模 mod - 1， 费马小定理，这边不去模也可以
        ll ans = qp(2, all) * 6 % mod;
        cout << ans << endl;
    }
    return 0;
}
Licensed under CC BY-NC-SA 4.0