Codeforces Round 949 (Div. 2) A~D

作者：IT小白 | 2024-08-19 22:22:40

踩

codeforces round 949 (div. 2)

A. Turtle and Piggy Are Playing a Game （思维）

题意：

给出一个整数 $x$ ，使得 $\le x \le r$ ，其中 $l, r$ 为给定值。同时保证 $\le r$ 。
执行以下操作，直到 $x$ 变为 $1$ ：

选择一个整数 $p$ ，使得 $\ge 2$ 和 $\mid x$ （即 $x$ 是 $p$ 的倍数）。
将 $x$ 设置为 $\frac{x}{p}$ ，得分将增加 $1$ 。

得分最初为 $0$ 。询问得分最大为多少。

分析：

$2$ 的增长速度是最慢的，并且题目有 $\times l \le r$ ，所以答案为 $log_2r$ 向下取整。

代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        int ans = __lg(r);
        cout << ans << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

B.Turtle and an Infinite Sequence （位运算）

题意：

给出一个无限长的序列 $a_0, a_1, a_2, \ldots$ 。对于每个非负整数 $i$ ，初始值为 $a_i = i$ 。
每一秒之后，序列中的每个元素都会同时发生变化。对于每个正整数 $i$ ， $a_i$ 将变为 $a_{i - 1} \mid a_i \mid a_{i + 1}$ 。 $a_0$ 将变为 $a_0 \mid a_1$ 。
给出 $m$ ，询问 $m$ 秒之后， $a_n$ 的值。

分析：

发现 $a_n$ 在 $m$ 秒之后的答案为 $[n - m, n + m]$ 这个区间里面所有数的异或和。我们直接枚举答案的二进制位 $i$ ，判断 $i$ 能否变成 $1$ 。只需找到第一个 $x$ ，满足 $\ge l, x \le r, x>>i$ & $1$ 即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    int t;
    cin >> t;
    while (t--) {
        LL n, m;
        cin >> n >> m;
        LL l = max(0LL, n - m);
        LL r = n + m;
        LL ans = 0;
        LL cnt = 0;
        while (l != r) {
            cnt++;
            l >>= 1;
            r >>= 1;
        }
        while (cnt--)
            r = (r << 1) ^ 1;
        cout << r << endl;
    }
    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

C.Turtle and an Incomplete Sequence （位运算）

题意：

给出一个正整数组成的序列 $a_1, a_2, \ldots, a_n$ 但是现在序列不完整了。可能存在任意数量的索引 $i$ ，使得 $a_i$ 变成 $- 1$ 。让新序列为 $a^{'}$ 。保证对于原始序列 $a$ ，要么 $a_i = \left\lfloor\frac{a_{i + 1}}{2}\right\rfloor$ 成立，要么 $a_{i + 1} = \left\lfloor\frac{a_i}{2}\right\rfloor$ 成立。

换句话说，你需要找到另一个由正整数组成的序列 $b_1, b_2, \ldots, b_n$ ，并且：

对于从 $1$ 到 $n$ 的每个整数 $i$ ，如果 $a'_i \ne -1$ ，则 $b_i = a'_i$ 。
对于从 $1$ 到 $n - 1$ 的每个整数 $i$ ， $b_i = \left\lfloor\frac{b_{i + 1}}{2}\right\rfloor$ 或 $b_{i + 1} = \left\lfloor\frac{b_i}{2}\right\rfloor$ 成立。
对于从 $1$ 到 $n$ 的每个整数 $i$ ， $\le b_i \le 10^9$ 。

如果没有满足上述所有条件的序列 $b_1, b_2, \ldots, b_n$ ，则需要输出 $- 1$ 。

分析：

我们考虑将操作统一，即满足 $b_i=b_{i-1}/2$ 或者满足 $b_i=b_{i-1} \times 2$ 或者 $b_i=b_{i-1} \times 2+1$ ，并将操作转换成在二进制上考虑是将前一个数右移一位还是在末尾填上 $0$ 或者 $1$ 。
我们接下来考虑从 $x$ 变成 $y$ 至少需要多少个操作，首先求出 $x$ , $y$ 的二进制最长公共前缀,然后将 $x$ 通过右移操作变成其最长公共前缀，然后再通过填 $1$ 或者填 $0$ 来变成 $y$ 。最后剩余的数通过反复乘 $2$ 或者除 $2$ 操作即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL N = 5e5 + 10;
const LL mod = 1e9 + 7;

LL gcd(LL a, LL b) {
    return b > 0 ? gcd(b, a % b) : a;
}

int a[N];

void solve() {
    int n;
    cin >> n;
    int bit[n + 5][32];
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> pos;
    int st = 0, en = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != -1) {
            if (!st)
                st = i;
            pos.push_back(i);
            for (int j = 0; j < 32; j++) {
                bit[i][j] = ((a[i] >> j) & 1);
            }
            en = i;
        }
    }
    int f = 0;
    for (int i = st - 1; i >= 1; i--) {
        if (f == 0) {
            a[i] = a[i + 1] * 2;
        } else {
            a[i] = a[i + 1] / 2;
        }
        f ^= 1;
    }
    f = 0;
    for (int i = en + 1; i <= n; i++) {
        if (i == 1) {
            a[i] = 2;
            continue;
        }
        if (f == 0) {
            a[i] = a[i - 1] * 2;
        } else {
            a[i] = a[i - 1] / 2;
        }
        f ^= 1;
    }
    int len = pos.size();
    for (int i = 0; i < len - 1; i++) {
        int l = a[pos[i]], r = a[pos[i + 1]];
        int tmp = l;
        int len1 = 0, len2 = 0;
        while (tmp) {
            tmp /= 2;
            len1++;
        }
        tmp = r;
        while (tmp) {
            tmp /= 2;
            len2++;
        }
        int tot = 0;
        for (int j = 0; j < min(len1, len2); j++) {
            if (bit[pos[i]][len1 - j - 1] == bit[pos[i + 1]][len2 - j - 1])
                tot++;
            else
                break;
        }
        int num = len1 + len2 - 2 * tot;
        if (pos[i + 1] - pos[i] < num || (pos[i + 1] - pos[i] - num) % 2 != 0) {
            cout << -1 << endl;
            return;
        }
        int num1 = len1 - tot;
        int num2 = len2 - tot;
        int po = pos[i] + 1;
        for (int j = 0; j < num1; j++) {
            a[po] = a[po - 1] / 2;
            po++;
        }
        for (int j = 0; j < num2; j++) {
            if (bit[pos[i + 1]][len2 - tot - j - 1] == 0) {
                a[po] = a[po - 1] * 2;
            } else {
                a[po] = a[po - 1] * 2 + 1;
            }
            po++;
        }
        int f = 1;
        for (po; po < pos[i + 1]; po++) {
            if (f == 1) {
                a[po] = a[po - 1] * 2;
            } else {
                a[po] = a[po - 1] / 2;
            }
            f ^= 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) {
        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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

D.Turtle and Multiplication （图论）

题意：

给一个整数 $n$ ，并要求构造一个由满足以下条件的整数组成的序列 $a_1, a_2, \ldots, a_n$ ：

对于所有 $\le i \le n$ ， $\le a_i \le 3 \cdot 10^5$ 。
对于所有 $\le i \le j \le n - 1$ ， $a_i \cdot a_{i + 1} \ne a_j \cdot a_{j + 1}$ 。

在所有这些序列中，找出具有最少个不同元素的序列。

分析：

如果我们都选质数，那么两对之间乘积不相同也就等价于两对质数不完全相同。那么将问题转化为在一个完全图上找欧拉路。如果我们只用奇数个质数，那么每个点度是偶数，有欧拉回路。如果用偶数个质数，就要删掉质数数量的一半减一条边，这样才会产生只有两个奇数度的点。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL N = 3e5 + 10;
const LL mod = 1e9 + 7;
int n, m, st[N], g[1510][1510];
vector<int> pri;
stack<int> stk;

void dfs(int u) {
    if (g[u][u])
        g[u][u] = 0, dfs(u);
    for (int i = 1; i <= m; i++)
        if (g[u][i])
            g[u][i] = g[i][u] = 0, dfs(i);
    stk.push(pri[u]);
}

int main() {
    for (int i = 2; i <= 300000; i++) {
        if (!st[i])
            pri.push_back(i);
        for (int j = i * 2; j <= 300000; j += i)
            st[j] = 1;
    }
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        if (n == 1) {
            cout << 1 << endl;
            continue;
        }
        m = 1;
        while (m * (m + 1) / 2 - (m % 2 ? 0 : m / 2 - 1) < n - 1)
            m++;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                g[i][j] = 1;
        if (m % 2 == 0)
            for (int i = 3; i <= m; i += 2)
                g[i][i + 1] = g[i + 1][i] = 0;
        dfs(1);
        while (stk.size() && n) {
            cout << stk.top() << " ";
            stk.pop();
            n--;
        }
        while (stk.size())
            stk.pop();
        cout << endl;
    }
    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
46
47
48
49
50
51
52
53
54
55

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/1003925