CFR-838(Div.2)解题报告

发表于 更新于 分类于

比赛传送门

A. Divide and Conquer

题意：给你一个数组，每次操作可以将一个数变为它除以二下取整，求将数组的和变为偶数的最小次数。

显然如果数组本来就是偶数，则为 00，否则一定是选一个数一直除到改变，而其他数不动（动了显然更劣）。于是对于每个数求改变奇偶的最小次数，模拟即可。

By jiangly

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 <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    int par = 0;
    int mn = 1E9;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        par ^= a[i] & 1;
        int x = a[i], t = 0;
        while (x % 2 == a[i] % 2) {
            x /= 2;
            t++;
        }
        mn = std::min(mn, t);
    }

    std::cout << (par ? mn : 0) << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

B. Make Array Good

题意：有一个数组，每次可以将一个数 xx 改为 [x,2x][x,2x] 内的任意整数，求在 nn 次以内将这个数组改为任意两个数均有倍数关系的方案。

由于在 [x,2x][x,2x] 内，容易想到让它们均变为二的幂（此时一定合法）。于是对于每个数改为比他大的最近的二的幂即可。可以使用 2⌊log⁡2(n)⌋+12^{\lfloor\log_2(n)\rfloor+1} 来快速得出。

By jiangly

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
#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    std::cout << n << "\n";
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        int p = 1 << (std::__lg(a[i]) + 1);
        std::cout << i + 1 << " " << p - a[i] << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

C. Binary Strings are Fun

给你一个 0101 串，对于每个前缀，计算生成合法串的方案数，输出它们的和（对 998244353998244353 取模）。生成一个合法串，需要在每相邻两位之间插入一个新位，使得任意一个奇数前缀的中位数为末尾的数字。

首先举例子找一找规律。假设待生成的串为 0_0_1_1_0_1_1_1，下划线是需要填的。我们依此考虑：只考虑前三位，中位数为 00，所以第一个空填 0101 都可以；考虑前五位，中位数为 11，所以第一个和第二个空都必须填 11；前七位，第四个空 01 都可以；前九位，则第三个和第四个空只能填 00。

依此类推，我们发现，如果某一个“限制位置”和下一个“限制位置”不同，那么中位数在这两位后发生改变，所以这两位之间的空位必须填后面的值，且前面这两位的数量差只能为 11。如果某一个限制位置和下一个限制位置相同，那么必须填与它们相反的值，因为如果与它们相同，则数量差超过 11，而后面一个不同的位置就会无法填。

所以，只有一个位置后面没有不同位置时，才可以真正的任意填，否则只有一种方案。此时答案就很显然了，即为 22 的（最后一段连续的长度 −1-1）次方。

By jiangly

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
void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    int last = 0;
    Z ans = 0, sum;

    for (auto c : s) {
        if (last != c) ans = 1;
        else ans *= 2;
        last = c;
        sum += ans;
    }

    std::cout << sum << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

D. GCD Queries

题意：交互题。有一个 0∼n−10\sim n-1 的排列，每次可以询问两位的 gcd⁡\gcd，在 2n2n 次操作内给出两个位置，使得它们中的一个位置为 00。

首先有一个非常重要的性质：∀y,gcd⁡(x,0)≥gcd⁡(y,0)\forall y,\gcd(x,0)\ge \gcd(y,0)。所以我们可以依此扫描每个位置，维护当前扫到的可能为 00 的两个位置 x,yx,y。

初始时 x=1,y=2x=1,y=2，从 33 开始，对于每个位置 ii，询问 gcd⁡(px,pi)\gcd(p_x,p_i) 和 gcd⁡(py,pi)\gcd(p_y,p_i)，如果两个答案相同，那么 pip_i 不可能是 00（因为 gcd⁡(0,x)=x\gcd(0,x)=x，而排列里 xx 互不相同）；如果两个答案不同，那么 x,yx,y 中较小的那个一定不是 00（因为前面的性质），而 pip_i 有可能是 00，将较小的那个改为 ii 即可。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
signed main() {
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        int now=2,x=1,y=2,xx,yy;
        while(now<n) {
            now++;
            cout<<"? "<<x<<" "<<now<<endl;
            cin>>xx;
            cout<<"? "<<y<<" "<<now<<endl;
            cin>>yy;
            if(xx>yy) y=now;
            else if(yy>xx) x=now;
        }
        cout<<"! "<<x<<" "<<y<<endl;
        cin>>n;
        assert(n==1);
    }
    return 0;
}