A.Little Artem

题意：

给定一个 $n*m$ 的矩阵，可以在其中的每一格放 $B$ 或 $W$ 两种字母，如果一个格子四周有不同字母的格子就称这个点为好点，构造一种方案使得 $B$ 好点的数量多于 $W$ 好点的数量

题解：

令左上角为 $W$ 其余点为 $B$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i == 1 && j == 1)
                putchar('W');
            else
                putchar('B');
        }
        puts("");
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Kind Anton

题意：

数组 $a_n$ 由 ${−1,0,1}$ 中的元素构成，并且你可以将数组中的任意元素 $a_j$ 替换为 $a_j+a_i(j>i)$ ，该操作能进行任意次，询问数组 $a_n$ 能否通过变换变成数组 $b_n$

题解：

如果 $a_j<b_j$ ，那么必须存在 $a_i=1(i<j)$ ；如果 $a_j>b_j$ ，那么必须存在 $a_i=−1(i<j)$ 。记录两者第一次出现的位置即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], b[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] == 1 && !l)
            l = i;
        if (a[i] == -1 && !r)
            r = i;
    }
    bool flag = true;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
        if (b[i] > a[i] && (l >= i || !l))
            flag = false;
        if (b[i] < a[i] && (r >= i || !r))
            flag = false;
    }
    puts(flag ? "YES" : "NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Eugene and an array

题意：

统计数组 $a_n$ 中有几个连续子序列满足：该序列中不存在和为 $0$ 的连续子序列。

题解：

用 $sum[i]$ 记录每个值 $i$ 上一次出现的位置
若 $sum[a[i]]$ 在 $i$ 前面存在，那么这样的序列只能最后一次取到 $sum[a[i]]$ 的下标 $k$ 以后，数量为 $i - k$ 。
同时要与 $last$ ，比较取较大者，因为若 $last>k$ ,那么序列就可能存在 $last \sim sum[a[i-1]]$ 之和为0的情况

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[maxn];
map<ll, ll> mp;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    ll sum = 0, res = 0, last = 0;
    mp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i];
        if (mp[sum])
            last = max(last, mp[sum]);
        res += i - last;
        mp[sum] = i + 1;
    }
    printf("%lld\n", res);
    return 0;
}

D.Challenges in school №41

题意：

给定一个长度为 $n$ 且由字符 $L,R$ 构成的字符串，每次操作中，你都能选择任意对相邻的 $RL$ ，将其变为 $LR$ ，询问能否恰好用 $k$ 轮将字符串中的 $L$ 全部移动至左端， $R$ 全部移动至右端。能则输出每轮要交换的对数和对应的下标，否则输出 $-1$

题解：

首先要知道如果不限制轮数，那么无论任何字符串最终都能变成要求的，因此每次操作都贪心地将所有能够交换的位置互换，统计最少需要几轮才能完成交换（记为 $cnt$ ），并统计交换的总次数（记为 $sum$ ），如果 $k∈[cnt,sum]$ 那么就可以给出交换方案，因为我们能将某一轮中的操作拆开来，最多能够拆成 $sum$ 轮。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3005;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<int> vec[maxn];
char s[maxn];
int main()
{
    int n, k;
    scanf("%d%d%s", &n, &k, s + 1);
    int cnt = 0, sum = 0;
    while (1)
    {
        bool flag = false;
        cnt++;
        for (int i = 1; i < n; i++)
        {
            if (s[i] == 'R' && s[i + 1] == 'L')
            {
                flag = true;
                vec[cnt].push_back(i);
            }
        }
        for (auto i : vec[cnt])
            swap(s[i], s[i + 1]);
        sum += vec[cnt].size();
        if (!flag)
            break;
    }
    cnt--;
    if (k < cnt || k > sum)
    {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= cnt; i++)
    {
        while (!vec[i].empty() && k > cnt - i + 1)
        {
            printf("%d %d\n", 1, vec[i].back());
            vec[i].pop_back();
            k--;
        }
        if (!vec[i].empty())
        {
            printf("%d", vec[i].size());
            for (auto it : vec[i])
                printf(" %d", it);
            puts("");
            k--;
        }
    }
    return 0;
}

E.Road to 1600

题意：

构造一个 $n×n$ 的棋盘，每个格子上的数字是 $1,2,⋯,n^2$ ，分别控制两种棋子，国际象棋中的车和后。其中两种棋子的行动路径分别如下：
图片说明
两个棋子分别从 $1$ 出发，按照以下规则进行行走：

到达当前行动路径上权值最小且没有被访问过的格子，将其标记访问；
若当前行动路径上格子都被访问，那么花费1的代价到达一个权值最小且未被访问过的格子；
若所有格子已被访问，那么停止操作。

现在要求构造一种权值方案，使得车消耗的代价小于后所消耗的代价。

题解：

先从规模小的开始考虑，首先， $n \leq 2$ 的时候一定无解。因为格子之间总是可达的，无论怎么构造，车和后的代码都为0。
考虑 $n=3$ 的情况。如下构造可以使得车的代价为 $0$ ，后的代价为 $1$ 。

$\left[ \begin{matrix} 8 & 7 & 6 \\ 5 & 1 & 2 \\ 4 & 9 & 3 \\ \end{matrix} \right]$
那么 $n>3$ 的棋盘只需要将 $3*3$ 的棋盘放在左上角，其余让车和后一起走完即可， $n=4$ 和 $n=5$ 的构造如下:
图片说明

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int b[4][4] = {{0, 0, 0, 0}, {0, 8, 7, 6}, {0, 5, 1, 2}, {0, 4, 9, 3}};
int n, ans[505][505];
int main()
{
    scanf("%d", &n);
    if (n <= 2)
    {
        puts("-1");
        return 0;
    }
    if (n == 3)
    {
        for (int i = 1; i <= 3; i++)
        {
            for (int j = 1; j <= 3; j++)
                printf("%d ", b[i][j]);
            puts("");
        }
        return 0;
    }
    bool flag = ((n - 3) & 1);
    int cnt = 0;
    for (int i = n; i > 3; i--)
    {
        if (flag)
        {
            for (int j = 1; j <= i; ++j)
                ans[i][j] = ++cnt;
            for (int j = i - 1; j >= 1; --j)
                ans[j][i] = ++cnt;
        }
        else
        {
            for (int j = 1; j <= i - 1; ++j)
                ans[j][i] = ++cnt;
            for (int j = i; j >= 1; --j)
                ans[i][j] = ++cnt;
        }
        flag ^= 1;
    }
    swap(ans[1][4], ans[2][4]);
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            ans[i][j] = b[i][j] + cnt;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
            printf("%d ", ans[i][j]);
        puts("");
    }
    return 0;
}

F.Kate and imperfection

题意：

在集合 $S={1,2,⋯,n}$ 中，对于每个正整数 $1<k \leq n$ ，找出一个大小为 $k$ 的子集，使得该子集中两两间最大公因数的最大值最小，给出每个 $k$ 对应的最小值。

题解：

我们考虑如何构造两两间最大公因数的最大值最小的集合，首先肯定是把所有质数先丢进集合里，然后再把与已经在集合内的数的最大公因数 $=2$ 的数丢进去，然后是 $=3$ 的数……然后注意到，如果我们加入了一个合数，那么他的所有因子必定已经在集合内了，于是加入的这个数字能够产生的最大公因数就是他的最大因子，因此用埃筛维护这个贪心的过程，排序一遍输出即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3005;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> ans(n + 1, 1);
    for (int i = 2; i <= n; i++)
        for (int j = i + i; j <= n; j += i)
            ans[j] = i;
    sort(ans.begin(), ans.end());
    for (int i = 2; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}

Codeforces Round #632 (Div. 2)