Codeforces Round 949 (Div. 2) A~D

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;
}

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;
}

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++;elsebreak;}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;
}

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;
}