A.Candies and Two Sisters

题意：

给你 $n$ 个糖果分成 $a,b$ 两份，要求 $a>b>0$ ，询问有多少种分法

题解：

$b \in [1,\frac{n-1}{2}]$ ，方案数就是 $\frac{n-1}{2}$ 种

#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;
    scanf("%d", &n);
    printf("%d\n", (n - 1) / 2);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Construct the String

题意：

给定 $n,a,b$ ，表示构造一段长度为 $n$ 的字符串使得任意一段长度为 $a$ 的子串中都包含 $b$ 个不同的字符 $1≤a≤n≤2000,1≤b≤min(26,a)$

题解：

因为 $1≤b≤min(26,a)$ ，所以可以构造长度为 $b$ 的不同字符串一直循环直到长度为 $n$ 即可

#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, a, b;
    scanf("%d%d%d", &n, &a, &b);
    string s = "";
    for (int i = 0; i < b; i++)
        s += char('a' + i);
    while (n)
    {
        int t = min(n, b);
        for (int i = 0; i < t; i++)
            putchar(s[i]);
        n -= t;
    }
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Two Teams Composing

题意：

从 $a_n$ 中选出一部分数字分别放入两组，要求第一组数字各不相同，第二组数字全部相同，并且两个组包含的个数相同，询问最大的每组个数

题解：

分别统计 $a_n$ 中的不同数值的个数 $cnta$ 和众数的数值 $cntb$ ，最终答案为 $max(min(cnta-1,cntb),min(cnta,cntb-1))$ ，因为 $cnta$ 和 $cntb$ 中肯定包含了同一个数，将它放到数量少的那组即可

#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;
    scanf("%d", &n);
    set<int> s;
    map<int, int> mp;
    int cnta = 0, cntb = 0;
    for (int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        s.insert(x);
        mp[x]++;
        cntb = max(cntb, mp[x]);
    }
    cnta = s.size();
    printf("%d\n", max(min(cnta - 1, cntb), min(cnta, cntb - 1)));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Anti-Sudoku

题意：

给定一个填好的 $9∗9$ 数独表，至多改动其中的 $9$ 个数字，使其满足一下条件：

每一行至少存在一个数字出现两次或以上
每一列至少存在一个数字出现两次或以上
每一个宫中至少存在一个数字出现两次或以上

题解：

考虑到九宫格的性质： $1 \sim 9$ 每个数字在每一行、每一列和每一宫中都只出现一次。那么只要将 $1 \sim 9$ 中的一个数字替换成另一种即可

#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()
{
    string s;
    for (int i = 0; i < 9; i++)
    {
        cin >> s;
        for (int j = 0; j < 9; j++)
            if (s[j] == '1')
                s[j] = '2';
        cout << s << "\n";
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Three Blocks Palindrome

题意：

给定数字序列 $a_n$ ，要求找到一段最长的回文子序列使其满足 $[\underbrace{a,a,...,a}_x,\underbrace{b,b,...,b}_y,\underbrace{a,a,...,a}_x]$ ,其中 $x,y \geq 0,n \leq 2*10^5,a_i \leq 200$

题解：

用前缀和 $sum[i][j]$ 统计出 $a_1 \sim a_i$ 中 $j$ 的个数，利用双指针 $l、r$ 对于每个数字分别从两端向中间滑动，对于中间的序列最大值就是枚举每个数字， $l、r$ 两端前缀和相减即可，取最大值就是答案，具体可以参考代码

#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;
vector<int> pos[205];
int sum[maxn][205];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= 200; i++)
        pos[i].clear();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 200; j++)
            sum[i][j] = 0;
    int v = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        v = max(v, x);
        pos[x].push_back(i);
        for (int j = 1; j <= v; j++)
            sum[i][j] = sum[i - 1][j];
        sum[i][x]++;
    }
    int mx = 0;
    for (int i = 1; i <= v; i++)
    {
        int l = 0, r = pos[i].size() - 1;
        mx = max(mx, r + 1);
        while (l < r)
        {
            int c = 0;
            for (int j = 1; j <= v; j++)
                c = max(c, sum[pos[i][r] - 1][j] - sum[pos[i][l]][j]);
            mx = max(c + 2 * l + 2, mx);
            l++, r--;
        }
    }
    printf("%d\n", mx);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

F.Robots on a Grid

题意：

给定一个 $n*m$ 的图，给定每个格子的颜色为黑还是白（ $c_{i,j}=0$ 为黑, $c_{i,j}=1$ 为白）每个格子上面有标有一个方向 $UDLR$ (上下左右)，保证给定的方向不会指引机器人越过边界。询问最多能放多少个机器人和最多能在黑格上放多少个机器人。机器人能同时存在的条件是机器人在沿着格子指引的方向同时移动，不会在任意时刻撞在一起

题解：

考虑到所有格子的出度都是 $1$ ,所以最终就构成了几个基环内向树。而询问最多能放多少个机器人就是求各个基环内向树的环数之和，因为最终环外的节点最终都会转移到环内，所以只要在环内的每个点上放一个机器人即可。
而考虑最多能在黑格上放多少个机器人，最好情况就是环上的每一个节点都是黑格，那么最终答案就等于最多能放多少个机器人，但是显然不太可能环上的都为黑格，那么我们可以考虑将环外的黑格转移到环内，从而代替这个环内白格的节点。可以通过求出基环树定一个起始点，从这个节点反向遍历整棵基环树，对于每个遍历到的点记录它到起始点的距离，如果距离对环数取模没有出现过且这个节点为黑格则可以，可以用染色法实现。
这里就用一种简单的方法而不是直接建基环树了，直接将每个节点都走足够长的路径，保证每个节点都出现在环中，直接计算环数和最终能到环内的黑格数量，具体看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, m, jmp[2][maxn];
char c[maxn], s[maxn];
bool vis[maxn];
void solve()
{
    cin >> n >> m;
    n *= m;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    for (int i = 0; i < n; i++)
        cin >> s[i];
    for (int i = 0; i < n; i++)
        if (s[i] == 'U')
            jmp[0][i] = i - m;
        else if (s[i] == 'R')
            jmp[0][i] = i + 1;
        else if (s[i] == 'D')
            jmp[0][i] = i + m;
        else
            jmp[0][i] = i - 1;
    for (int j = 0; j < 22; j++)
        for (int i = 0; i < n; i++)
            jmp[(j + 1) & 1][i] = jmp[j & 1][jmp[j & 1][i]];
    fill(vis, vis + n, 0);
    for (int i = 0; i < n; i++)
        vis[jmp[0][i]] = 1;
    printf("%d ", accumulate(vis, vis + n, 0));
    fill(vis, vis + n, 0);
    for (int i = 0; i < n; i++)
        if (c[i] == '0')
            vis[jmp[0][i]] = 1;
    printf("%d\n", accumulate(vis, vis + n, 0));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

Codeforces Round #634 (Div. 3)