Codeforces Round #629(Div.3) 解题报告

发布于 2020-03-27  102 次阅读


A - Divisibility Problem
只需要求到 $\lceil{\frac{a}{b}}\rceil$ 向上取整然后计算一下就行。
答案就是 $\lceil{\frac{a+b-1}{b}}\rceil\times b-a$。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
void solve()
{
    int a, b;
    cin >> a >> b;
    printf(
}
int main()
{
    TIME_START = clock();
    int Test;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

B - K-th Beautiful String
假设从左到右第一个 b 在位置 $i$，那么第二个 b 的放法就有 $n-i$ 种。由此可以看出，我们首先要确定第一个 b 的位置，这一部分可以计算正整数前 $n$ 项和来确定（因为规律就是这个），然后 $\mathcal{O}(n)$ 枚举第二个 b 的位置即可。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 200050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
ll n, k;
ll s[N];
char ans[N];
void solve()
{
    cin >> n >> k;
    int pos = lower_bound(s + 2, s + n + 1, k) - s - 1;
    for (int i = 1; i <= n; ++i)
        ans[i] = 'a';
    ans[n - pos] = 'b';
    k -= s[pos];
    ans[n - k + 1] = 'b';
    ans[n + 1] = '\0';
    printf(
}
int main()
{
    for (int i = 2; i <= 200000; ++i)
        s[i] = s[i - 1] + i - 1;
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

C - Ternary XOR
这题就是大分类讨论......
我们假设 $a\ge b$，然后从前往后看：当 $a$ 和 $b$ 还未分出大小（即还没有遇到 $1$），那么就让 $a$ 和 $b$ 相等：即遇到 $0$ 就让这一位分配两个 $0$，遇到 $2$ 就分配两个 $1$。
然后就是遇到 $1$ 的情况，因为我们假设 $a>b$，那就给 $a$ 分配一个 $1$，给 $b$ 分配一个 $0$，这样就满足 $a\ge b$ 了。之后分配方案就是让 $a$ 分配小的，让 $b$ 分配大的即可（即遇 $2$ 给 $a$ 分配 $0$，给 $b$ 分配 $2$ 等）。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 200050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n;
char s[N], a[N], b[N];
void solve()
{
    cin >> n;
    scanf(
    int flag = 0;
    int i = 1;
    while((s[i]=='2'||s[i]=='0')&&i<=n)
    {
        if(s[i]=='2')
            a[i] = b[i] = '1';
        else
            a[i] = b[i] = '0';
        i++;
    }
    for (; i <= n;++i)
    {
        if(s[i]=='0')
        {
            a[i] = '0', b[i] = '0';
        }
        if(s[i]=='1')
        {
            if(flag==0)
            {
                a[i] = '0';
                b[i] = '1';
                flag = 1;
            }
            else
            {
                a[i] = '1';
                b[i] = '0';
            }
        }
        if(s[i]=='2')
        {
            if(i==1)
                a[i] = b[i] = '1';
            else
            {
                if(flag==1)
                {
                    a[i] = '2';
                    b[i] = '0';
                }
                else
                {
                    a[i] = '0';
                    b[i] = '2';
                    flag = 1;
                }
            }
        }
    }
    a[n + 1] = b[n + 1] = 0;
    printf(
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

D - Carousel
仍然是恶心的分类讨论（
如果环上每个数字都相同，显然我们只需要一种颜色即可。
如果 $n$ 是偶数，显然我们只需要 $1,2,1,2,...$ 交替染色即可。
如果 $n$ 是奇数，那么我们来看下环上存不存在相邻两数相等。不存在的话，显然我们需要 $3$ 种颜色。存在的话，我们让这两数全都染上颜色 $1$，这样就变成了偶数环的情况，交替染色即可。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 200050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n;
int a[N], ans[N];
int check()
{
    for (int i = 1; i < n; ++i)
    {
        if (a[i] == a[i + 1])
            return i;
    }
    return -1;
}
bool all_same()
{
    for (int i = 1; i < n; ++i)
        if (a[i] != a[i + 1])
            return false;
    return true;
}
void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    if (all_same())
    {
        puts("1");
        for (int i = 1; i <= n; ++i)
            printf("1 ");
        puts("");
        return;
    }
    if (n
    {
        puts("2");
        for (int i = 1; i <= n; ++i)
        {
            printf(
        }
        puts("");
    }
    else
    {
        if (a[1] == a[n])
        {
            puts("2");
            ans[1] = ans[n] = 1;
            for (int i = 2; i < n; ++i)
            {
                ans[i] = (i & 1) ? 1 : 2;
            }
        }
        else
        {
            int pos = check();
            if (pos == -1)
            {
                puts("3");
                for (int i = 1; i < n; ++i)
                    ans[i] = (i & 1) ? 1 : 2;
                ans[n] = 3;
            }
            else
            {
                puts("2");
                ans[pos] = ans[pos + 1] = 1;
                int now = 2;
                for (int i = pos + 2; i <= n; ++i)
                {
                    ans[i] = (now & 1) ? 1 : 2;
                    now++;
                }
                now = 2;
                for (int i = pos - 1; i > 0; --i)
                {
                    ans[i] = (now & 1) ? 1 : 2;
                    now++;
                }
            }
        }
        for (int i = 1; i <= n; ++i)
            printf(
        puts("");
    }
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

E - Tree Queries
当时真就是脑抽直接交了个暴力上去......
容易发现，如果一个点的父亲在路径上，那么这个点必然满足条件。所以我们只需要将这 $k$ 个点的父亲提取出来，然后按照深度从大到小排序，如果相邻两个父亲的 lca 不是深度较浅的那个父亲，那么说明这两个父亲必然不可能在同一条根节点为起点的路径上。这个题就做完了。
我当时怎么就写了一个暴力向上爬......

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 200050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
vector<int> e[N];
int mark[N], tot;
int n, m;
int p[N], a[N];
int fa[N][21];
int dep[N];
void LCA_pre_dfs(int u, int f, int d)
{
    dep[u] = d;
    fa[u][0] = f;
    for (auto v : e[u])
    {
        if (v != f)
            LCA_pre_dfs(v, u, d + 1);
    }
}
void LCA_pre()
{
    LCA_pre_dfs(1, 0, 1);
    for (int j = 1; j <= 19; j++)
        for (int i = 1; i <= n; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int LCA(int u, int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    int delta = dep[u] - dep[v];
    for (int i = 19; i >= 0; i--)
        if ((delta >> i) & 1)
            u = fa[u][i];
    for (int i = 19; i >= 0; i--)
        if (fa[u][i] ^ fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    if (u == v)
        return u;
    return fa[u][0];
}
bool cmp(const int &x, const int &y)
{
    return dep[x] > dep[y];
}
void work()
{
    sort(mark + 1, mark + tot + 1, cmp);
    for (int i = 1; i < tot; ++i)
    {
        int pp = LCA(mark[i], mark[i + 1]);
        if (pp != mark[i + 1])
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        scanf(
        e[x].push_back(y);
        e[y].push_back(x);
    }
    LCA_pre();
    while (m--)
    {
        int k;
        scanf(
        int cnt = 0;
        tot = 0;
        for (int i = 1; i <= k; ++i)
        {
            int x;
            scanf(
            if (x == 1)
                continue;
            mark[++tot] = fa[x][0];
        }
        work();
    }
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

F - Make k Equal
一道比较简单的数学题。
容易发现，最后那 $k$ 个数相等，一定是和原来这 $n$ 个数种的某一个数相同。所以我们从大到小枚举这个数就行。
设 $num$ 为当前枚举到的数，$cnt$ 表示这个数的出现次数，$sumcnt$ 为小于 $num$ 的个数，$s_i$ 是从小到大排序之后这 $n$ 个数的前缀和。
设 $sheng=k-cnt$ （没错就是剩余的“剩”），那么我们考虑怎么操作才可以得到 $sheng$ 个数。有三种情况：

  1. 小于 $num$ 的所有数先全部增加到 $num-1$，再从里面选择 $c_1$ 个数；大于 $num$ 的所有数先全部减小到 $num+1$，再从里面选择 $c_2$ 个数。显然，$c_1+c_2=sheng$;
  2. 只通过最小值+1的操作来得到，即让所有小于 $num$ 的数全部增加到 $num-1$，再从里面选择 $sheng$ 个数（需要满足 $sumcnt\ge sheng$）;
  3. 只通过最大值-1的操作来得到，即让所有大于 $num$ 的数全部减小到 $num+1$，再从里面选择 $sheng$ 个数（需要满足 $n-sumcnt-cnt\ge sheng$）。

设 $f_1$ 表示让所有小于 $num$ 的数全部增加到 $num-1$ 的花费，$f_2$ 表示让所有大于 $num$ 的数全部减小到 $num+1$ 的花费。显然，我们有：
$$f_1=(num-1)\times sumcnt-s_{sumcnt}$$
$$f_2=(s_n-s_{sumcnt+cnt})-(num+1)\times (n-sumcnt-cnt)$$
这样这个题就做完了，每次在三种情况中取最小值即可。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 200050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n, k;
ll a[N], ans = LLONG_MAX;
ll f[N], g[N], sum[N];
map<ll, int> mp;
int cnt = 1;
void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        scanf(
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        sum[i] = sum[i - 1] + a[i];
        mp[a[i]]++;
    }
    ll sumcnt = 0;
    for (auto i : mp)
    {
        ll num = i.first, cnt = i.second;
        if (cnt >= k)
        {
            puts("0");
            return;
        }
        ll sheng = k - cnt;
        ll f1 = (num - 1LL) * sumcnt - sum[sumcnt];
        ll f2 = (sum[n] - sum[sumcnt + cnt]) - (num + 1LL) * (n - sumcnt - cnt);
        if (sumcnt >= sheng)
            ans = min(ans, f1 + sheng);
        if (n - sumcnt - cnt >= sheng)
            ans = min(ans, f2 + sheng);
        ans = min(ans, sheng + f1 + f2);
        sumcnt += cnt;
    }
    cout << ans << endl;
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}