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

发表于 分类于

B. BAN BAN

题意：给你一个 nn，生成一个字符串为 BAN 重复 nn 遍。每次操作可以选择两个位置进行交换，问至少多少次交换后可以使该串不存在 BAN 的子序列。输出方案。

显然对于每个 BAN 都至少要动一下，而每次交换可以动两位，所以答案的下界是 ⌈n2⌉\lceil\frac{n}{2}\rceil。这个下界是可以达到的，我们只需要交换最左边的 B 和最右边的 N，再交换第二段的 B 和倒数第二段的 N，以此类推，结果形如 NANNAN...BABBAB，显然满足条件。

By Um_nik

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int n;
    scanf("%d", &n);
    int m = (n + 1) / 2;
    printf("%d\n", m);
    for (int i = 0; i < m; i++) {
        printf("%d %d\n", 3 * i + 1, 3 * (n - i));
    }
}

int main()
{
    startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--) solve();

    return 0;
}

C. Swap Game

题意：有一个数组 aa，Alice 和 Bob 轮流操作（Alice 先手）。每次操作可以选择一个位置 i∈[2,n]i\in[2,n]，将 a1a_1 减去 11 后交换 a1a_1 和 aia_i。操作前遇到 a1=0a_1=0 的局面的人输。

由于是减法运算，可以从最小值入手考虑。如果 a1a_1 即为最小值，则 Alice 只能将它减一后换出去，此时 Bob 可以再将它换进来。于是每轮操作 a1a_1 都会减少 11，而其他数中选一个减少 11。由于 a1a_1 为最小值，必然先变成 00，所以 Bob 可以胜出。如果 a1a_1 不为最小值，则 Alice 可以将最小值换进来，此时 Bob 面临的局面同上，Alice 必胜。

By turmax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>

using namespace std;
#define int long long
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int a[n];for(int i=0;i<n;++i) cin>>a[i];
        puts((a[0]==(*min_element(a,a+n))) ? "Bob" : "Alice");
    }
    return 0;
}

D. Yet Another Problem

题意：给你一个数组 aa，每次询问给出一个 l,rl,r，询问将这部分子段全部变成 00 的最小操作次数。每次操作可以选择一个 l′,r′(l≤l′≤r′≤r,(l′−r′+1) is odd)l',r'(l\le l'\le r'\le r,(l'-r'+1)\text{ is odd})，使用这段区间的异或和来替换其中每个数。