A.Divisibility Problem

题意：

给两个数 $a,b$ ，每次操作可以使 $a=a+1$ ，问最少几次操作后 $a$ 是 $b$ 的倍数。

题解：

$ans = \begin{cases}{0,a\%b=0}\\{b-a,a \leq b}\\{b-a\%b,a>b} \end{cases}$

#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 a, b;
    scanf("%d%d", &a, &b);
    if (a % b == 0)
    {
        puts("0");
        return;
    }
    if (a <= b)
        printf("%d\n", b - a);
    else
        printf("%d\n", b - a % b);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.K-th Beautiful String

题意：

长度为 $n$ 的字符串包含 $n−2$ 个 $a$ 和 $2$ 个 $b$ ，求按照字典序排列的第 $k$ 个。

题解：

观察样例，左边的 $b$ 的位置出现次数倒数第二位有 $1$ 个，倒数第三位有 $2$ 个，倒数第四位有 $3$ 个，确定后再确定右边的 $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, k;
    scanf("%d%d", &n, &k);
    int l = 1;
    while (k > l)
        k -= l, l++;
    l++;
    int r = k;
    for (int i = n; i >= 1; i--)
    {
        if (i == l || i == r)
            putchar('b');
        else
            putchar('a');
    }
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Ternary XOR（构造）

题意：

规定三进制下的运算 $c=a⊙b为c_i=(a_i+b_i)\%3$ ，现给定长度为 $n$ 的 $c$ ，要求构造 $a,b$ ，并使得 $max(a,b)$ 尽可能小。

题解：

先讲最前面的 $0$ 和 $2$ 平分，遇到的第一个 $1$ 给 $a$ ，之后所有的值全给 $b$ ，此时的 $a$ 就是最小的 $max(a,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;
    scanf("%d", &n);
    string a, b, c;
    cin >> c;
    bool flag = true;
    for (auto i : c)
    {
        if (flag)
        {
            if (i == '0')
                a += '0', b += '0';
            if (i == '1')
                a += '1', b += '0', flag = false;
            if (i == '2')
                a += '1', b += '1';
        }
        else
        {
            a += '0';
            b += i;
        }
    }
    cout << a << endl << b << endl;
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Carousel（构造）

题意：

$n$ 个动物围成一个环，现在要给动物上色，要求不能给相邻的不同动物上同一种颜色，问最少几种颜色可以满足条件。

题解：

观察样例，其实可以得出结论的

全同色，1种
不存在相邻的相同动物且为奇数，3种。（前面1，2间隔最后一个3）

其余情况两种。偶数（12121212）奇数（找组相邻相同的把12反向）

#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;
int a[maxn];
void solve()
{
 int n;
 scanf("%d", &n);
 for (int i = 1; i <= n; i++)
     scanf("%d", &a[i]);
 a[0] = a[n];
 int f1 = 0, f2 = 0;
 for (int i = 1; i <= n; i++)
 {
     if (a[i] != a[i - 1])
         f1 = 1;
     else
         f2 = i;
 }
 if (!f1)
 {
     puts("1");
     for (int i = 1; i <= n; i++)
         printf("%d ", 1);
     puts("");
     return;
 }
 if (!f2 && (n & 1))
 {
     puts("3");
     for (int i = 1; i < n; i++)
         printf("%d ", (i & 1) ? 1 : 2);
     puts("3");
 }
 else
 {
     puts("2");
     if (n & 1)
     {
         for (int i = 1; i < f2; i++)
             printf("%d ", (i & 1) ? 1 : 2);
         for (int i = f2; i <= n; i++)
             printf("%d ", (i & 1) ? 2 : 1);
         puts("");
     }
     else
     {
         for (int i = 1; i <= n; i++)
             printf("%d ", (i & 1) ? 1 : 2);
         puts("");
     }
 }
}
int main()
{
 int t;
 for (scanf("%d", &t); t >= 1; t--)
     solve();
}

E.Tree Queries（LCA）

题意：

给定一棵 $n$ 个节点且以节点 $1$ 为根的有根树。对于 $m$ 个询问，每个询问给 $k$ 个点，问是否存在从 $1$ 出发的一条链使得这 $k$ 个点都在链上，或者距这条链上一点的距离为 $1$

题解：

在 $k$ 个点里找深度最大的点为该链终点。判断一下其他的点是否满足条件。只要判断 $lca$ (当前结点,最深结点) = 当前结点或者 $lca$ (当前结点,最深结点)=当前结点的父亲。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int n, q, f[25][maxn], h[maxn];
vector<int> G[maxn];
void dfs(int x)
{
    for (int i = 0; i < G[x].size(); i++)
    {
        int v = G[x][i];
        if (v == f[0][x])
            continue;
        f[0][v] = x;
        h[v] = h[x] + 1;
        dfs(v);
    }
}
void lca_init()
{
    dfs(1);
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = f[i - 1][f[i - 1][j]];
}
int lca(int x, int y)
{
    if (h[x] < h[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
        if ((h[x] - h[y]) >> i)
            x = f[i][x];
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
    {
        if (f[i][x] != f[i][y])
        {
            x = f[i][x];
            y = f[i][y];
        }
    }
    return f[0][x];
}
void solve()
{
    int k;
    scanf("%d", &k);
    vector<int> node;
    int mxdep = -1, mxnode = -1;
    for (int i = 0, x; i < k; i++)
    {
        scanf("%d", &x);
        node.push_back(x);
        if (h[x] > mxdep)
        {
            mxdep = h[x];
            mxnode = x;
        }
    }
    for (auto u : node)
    {
        int LCA = lca(u, mxnode);
        if (LCA != u && LCA != f[0][u])
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}
int main()
{
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    lca_init();
    while (m--)
        solve();
    return 0;
}

F.Make k Equal

题意：

给定由 $n$ 个数的数组 $a$ ，每次操作可以将任意一个最大值 $-1$ 或任意一个最小值 $+1$ 。问操作几次使得至少存在 $k$ 个相等的数字。

题解：

我们假设 $k$ 个相等的数字都是 $i$ ，只有先将所有小于 $i$ 的数字变为 $i−1$ 或者所有大于 $i$ 的数字变为 $i+1$ 才能够操作成 $i$ 。所以我们只要把a排序后维护一个前缀和和一个后缀和。计算出前缀变成 $i−1$ 和后缀变成 $i+1$ 的次数就可以简单的计算出答案。扫描一遍取最小值即可。

#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 ll INFL = 0x3f3f3f3f3f3f3f3fll;
const int mod = 998244353;
ll a[maxn];
set<ll> s;
map<ll, ll> mp;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    ll suml = 0, sumr = 0, cntl = 0, cntr = n;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        sumr += a[i];
        s.insert(a[i]);
        mp[a[i]]++;
    }
    ll res = INFL;
    for (auto i : s)
    {
        if (mp[i] >= k)
        {
            puts("0");
            return 0;
        }
        sumr -= mp[i] * i;
        cntr -= mp[i];
        ll cnt = k - mp[i];
        ll l = cntl * (i - 1) - suml;
        ll r = sumr - cntr * (i + 1);
        if (cntl >= cnt)
            res = min(res, l + cnt);
        if (cntr >= cnt)
            res = min(res, r + cnt);
        res = min(res, l + r + cnt);
        suml += mp[i] * i;
        cntl += mp[i];
    }
    printf("%lld\n", res);
    return 0;
}

Codeforces Round #629 (Div. 3)