Codeforces Round 949 (Div. 2) A~D

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

题意：

给出一个整数

x

x

x ，使得

l

≤

x

≤

r

l \le x \le r

l≤x≤r ，其中

l

,

r

l, r

l,r 为给定值。同时保证

2

l

≤

r

2l \le r

2l≤r 。
执行以下操作，直到

x

x

x 变为

1

1

1 ：

• 选择一个整数 $p$
• 将 $x$

得分最初为

0

0

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

分析：

2

2

2的增长速度是最慢的，并且题目有

2

×

l

≤

r

2 imes l \le r

2×l≤r，所以答案为

l

o

g

2

r

log_2r

log2​r向下取整。

代码：

#include 

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

,

…

a_0, a_1, a_2, \ldots

a0​,a1​,a2​,… 。对于每个非负整数

i

i

i ，初始值为

a

i

=

i

a_i = i

ai​=i 。
每一秒之后，序列中的每个元素都会同时发生变化。对于每个正整数

i

i

i ，

a

i

a_i

ai​ 将变为

a

i

−

1

∣

a

i

∣

a

i

+

1

a_{i – 1} \mid a_i \mid a_{i + 1}

ai−1​∣ai​∣ai+1​ 。

a

0

a_0

a0​ 将变为

a

0

∣

a

1

a_0 \mid a_1

a0​∣a1​。
给出

m

m

m，询问

m

m

m秒之后，

a

n

a_n

an​的值。

分析：

发现

a

n

a_n

an​在

m

m

m秒之后的答案为

[

n

−

m

,

n

+

m

]

[n-m,n+m]

[n−m,n+m]这个区间里面所有数的异或和。我们直接枚举答案的二进制位

i

i

i，判断

i

i

i能否变成

1

1

1。只需找到第一个

x

x

x，满足

x

≥

l

,

x

≤

r

,

x

>

>

i

x \ge l, x \le r, x>>i

x≥l,x≤r,x>>i &

1

1

1即可。

代码：

#include 

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

,

…

,

a

n

a_1, a_2, \ldots, a_n

a1​,a2​,…,an​但是现在序列不完整了。可能存在任意数量的索引

i

i

i ，使得

a

i

a_i

ai​ 变成

−

1

-1

−1 。让新序列为

a

′

a’

a′。保证对于原始序列

a

a

a ，要么

a

i

=

⌊

a

i

+

1

2

⌋

a_i = \left\lfloor\frac{a_{i + 1}}{2}\right\rfloor

ai​=⌊2ai+1​​⌋ 成立，要么

a

i

+

1

=

⌊

a

i

2

⌋

a_{i + 1} = \left\lfloor\frac{a_i}{2}\right\rfloor

ai+1​=⌊2ai​​⌋ 成立。

换句话说，你需要找到另一个由正整数组成的序列

b

1

,

b

2

,

…

,

b

n

b_1, b_2, \ldots, b_n

b1​,b2​,…,bn​ ，并且：

• 对于从 $1$
• 对于从 $1$
• 对于从 $1$

如果没有满足上述所有条件的序列

b

1

,

b

2

,

…

,

b

n

b_1, b_2, \ldots, b_n

b1​,b2​,…,bn​ ，则需要输出

−

1

-1

−1 。

分析：

我们考虑将操作统一，即满足

b

i

=

b

i

−

1

/

2

b_i=b_{i-1}/2

bi​=bi−1​/2 或者满足

b

i

=

b

i

−

1

×

2

b_i=b_{i-1} imes 2

bi​=bi−1​×2 或者

b

i

=

b

i

−

1

×

2

+

1

b_i=b_{i-1} imes 2+1

bi​=bi−1​×2+1，并将操作转换成在二进制上考虑是将前一个数右移一位还是在末尾填上

0

0

0或者

1

1

1。
我们接下来考虑从

x

x

x变成

y

y

y至少需要多少个操作，首先求出

x

x

x,

y

y

y 的二进制最长公共前缀,然后将

x

x

x通过右移操作变成其最长公共前缀，然后再通过填

1

1

1或者填

0

0

0来变成

y

y

y。最后剩余的数通过反复乘

2

2

2或者除

2

2

2操作即可。

代码：

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

D.Turtle and Multiplication （图论）

题意：

给一个整数

n

n

n ，并要求构造一个由满足以下条件的整数组成的序列

a

1

,

a

2

,

…

,

a

n

a_1, a_2, \ldots, a_n

a1​,a2​,…,an​ ：

• 对于所有 $1\le i\le n$
• 对于所有 $1\le i\le j\le n-1$

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

分析：

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

代码：

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

赛后交流

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

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