Codeforces Educational Round 84 题解

· · 个人记录

UPD：对部分 \LaTeX 公式的误用进行了修正。

CF1327A Sum of Odd Integers

我才不会告诉你们这道题我错了3次才AC

首先我们要明白一个事实：奇数个奇数的和是奇数，偶数个奇数的和是偶数。如果我们要把 n 拆成 k 个奇数（先不考虑拆成不同的奇数），n 与 k 的奇偶性必须相同。

于是我们得到：

条件1：n \equiv k \pmod 2

接下来我们考虑拆成 k 个不同的奇数需要满足什么条件。

其实只要满足 n 大于等于前 k 个奇数的总和就可以了。（因为我们总可以把最大的奇数不断增加直至总和为 n）

举个栗子：n=21,k=4 时，首先前4个奇数分别是 1,3,5,7。因为 21>1+3+5+7，所以我们可以把 7 增加至 12，这样就满足条件了。

而前 k 个奇数的和是 k^2，于是我们得到：

条件2：n \ge k^2

综上，AC代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    //ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)
    {
        int n,k;
        cin >> n >> k;
        if(n % 2 == k % 2 && n >= k * k)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

CF1327B Princesses and Princes

刚开始确实没有想到这道题模拟就可以了。

我们首先按照国王的规则包办婚姻，然后看看有没有剩男剩女未能配对的王子和公主，把它们配对就OK了。如果所有公主都嫁出去了，答案就是OPTIMAL。

但是这样有一个问题：题目里说了这样一句话（还特别加粗）

Note that this kingdom should not be present in the daughter's list.

后来我想了想发现这是废话！！！如果有未能配对的王子和公主，那么这个王子一定不是公主喜欢的人。

反证法：假如这个王子出现在了公主喜欢的人的列表中，且这个公主没有嫁出去，这个王子也没有娶任何一个公主，那么这个公主和王子就一定可以配对，矛盾。

所以题目这句话有点坑

最后我们的代码就很简洁了：

#include<bits/stdc++.h>
#define endl '\n'//一般输出规模超过10^5最好用'\n'换行
using namespace std;
const int maxn = 100010;
bool used[maxn], choosed[maxn];
//分别为王子和公主

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        fill(used + 1, used + n + 1, false);
        fill(choosed + 1, choosed + n + 1, false);
        for(int i = 1; i <= n; i++)
        {
            int k;
            cin >> k;
            bool flag = false;
            for(int j = 1; j <= k; j++)
            {
                int x;
                cin >> x;
                if(!flag && !used[x])
                {
                    used[x] = true;
                    choosed[i] = true;
                    flag = true;
                }
            }
        }
        bool flag = false;
        for(int i = 1; i <= n; i++)
            if(!used[i])
            {
                for(int j = 1; j <= n; j++)
                    if(!choosed[j])
                    {
                        cout << "IMPROVE" << endl << j << ' ' << i << endl;
                        flag = true;
                        break;
                    }
                if(flag)
                    break;
            }
        if(!flag)
            cout << "OPTIMAL" << endl;
    }
    return 0;
}

时间复杂度是 O(n)。

因为只要有一个没配对的王子，就必然有一个没配对的公主。

吐槽下题意翻译，叫王子和公主多好

CF1327C Game with Chips

这里我要感谢下比赛时候的弹窗：

We don't have to minimize the number of operations in problem C.

所以其实这道题的 k,sx,sy,fx,fy 都用不到！（惊不惊喜意不意外）

由于最大移动次数限制是 2nm，所以我们可以把整个棋盘全部走一遍。

我的做法是这样的：
首先先从右上角出发，不断向下，走到底再向左走一步，不断向上，走到顶再向左走一步，不断向下……一直走到左下角/左上角。
然后从左下角/左上角出发，与刚才的做法类似，一直走到最右端。
（读者可根据代码理解）

把整个棋盘全部走一遍之后，所有的chip一定能够经过目标。

这是因为我们的操作实际上相当于把所有的chip都利用墙壁堆到了左上角或左下角，然后再带着所有的chip遍历棋盘。

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, tmp
    cin >> n >> m >> tmp;
    for(int i = 1; i <= 4 * k; i++)
        cin >> tmp;
    //大大简化了空间复杂度
    string ans = "";
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j < n; j++)
            if((m - i) % 2 == 0)
                ans += 'D';
            else
                ans += 'U';
        if(i != m)
            ans += 'L';
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j < n; j++)
            if(i % 2 == 0)
                ans += 'D';
            else
                ans += 'U';
        if(i != m)
            ans += 'R';
    }
    cout << ans.size() << endl << ans << endl;
    return 0;
}

时间复杂度 O(n \times m)，空间复杂度 O(1)。

CF1327E Count The Blocks

这题其实就是个乘法原理的计算。

不难想到，一个block要么出现在两边，要么出现在中间，分别计算答案即可。

令 ans_i 表示长为 i 的block的个数。

首先 ans_n = 10；（也就是 000\dots0,\ 111\dots1,\ 222\dots2 一直到 \ 999\dots9）

然后，如果一个长为 i(i<n) 的block出现在两边，方案总数是 10 \times 9 \times 10^{n-i-1} \times 2。
解释：10（block本身有10种可能）\times 9（block旁边的数不能与block本身的取值相同）\times 10^{n-i-1}（剩下的数没有限制） \times 2（有两边）。

如果这个block出现在中间，方案总数是 10 \times 9^2 \times 10^{n-i-2} \times (n-i-1)。
解释：10（block本身有10种可能）\times 9^2（block两边的数不能与block本身的取值相同）\times 10^{n-i-2}（剩下的数没有限制） \times (n-i-1)（中间有 n-i-1 个block可以放置的位置）。

但是注意：当 i=n-1 时，这个block不可能出现在中间，所以我们要特判一下。
由于要大量用到 10 的幂，所以我们可以预处理一下降低时间复杂度。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long n;
const int maxn = 200010;
long long pow10[maxn], ans[maxn];
int main()
{
    cin >> n;

    pow10[0] = 1;
    for(int i = 1; i <= n; i++)
        pow10[i] = pow10[i - 1] * 10 % mod;

    ans[n] = 10;
    ans[n - 1] = ans[n] * 2 * 9;
    for(int i = n - 2; i > 0; i--)
    {
        ans[i] = (ans[i] + 10 * 9 * pow10[n - i - 1] % mod * 2) % mod;
        ans[i] = (ans[i] + 10 * 9 * 9 * pow10[n - i - 2] % mod * (n - i - 1) % mod) % mod;
    }

    for(int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    cout << endl;

    return 0;
}

时间复杂度 O(n)。