Codeforces Round #806 Div.4 解题记录

回归 OI 了！打算用这套题来练手，来找一找感觉，然后开始学习。

这是一场 Div.4，难度较低。

A. YES or YES?

利用常量数组可以简单地实现。以此判断三个字母，代码如下：

#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

int main(void)
{
    const string a = "YES", b = "yes";
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        bool flag = true;
        cin >> s;
        for (int i = 0; i < 3; ++i)
            if (s[i] != a[i] && s[i] != b[i])
                flag = false;
        if (flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

B. ICPC Balloons

Portal.

利用一个数组记录这个字母之前是否出现过即可，代码如下：

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int main(void)
{
    int T, n;
    string s;
    bool flag[30];
    cin >> T;
    while (T--)
    {
        cin >> n >> s;
        int ans = 0;
        memset(flag, 0, sizeof(flag));
        for (int i = 0; i < n; ++i)
        {
            if (!flag[s[i] - 'A']) ++ans, flag[s[i] - 'A'] = true;
            ++ans;
        }
        cout << ans << '\n';
    }
    return 0;
}

C. Cypher

Portal.

按顺序模拟即可，代码如下：

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int main(void)
{
    int T, n, b, a[105]; cin >> T;
    string s;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i)
        {
            cin >> b >> s;
            for (int j = 0; j < b; ++j)
            {
                a[i] += (s[j] == 'D') ? (1) : (-1);
                if (a[i] == 10) a[i] = 0;
                if (a[i] == -1) a[i] = 9;
            }
            cout << a[i] << ' ';
        }
        putchar('\n');
    }
    return 0;
}

D. Double Strings

Portal.

注意到字符串的长度很短，直接枚举前缀同时计算后缀，再利用集合（~~当然可以写字符串哈希~~）判断是否存在即可。代码如下：

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

string s[100005];
unordered_set <string> us;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t, n;
    cin >> t;
    while (t--)
    {
        us.clear();
        cin >> n;
        for (int i = 1; i <= n; ++i) 
            cin >> s[i], us.insert(s[i]);
        for (int i = 1; i <= n; ++i)
        {
            bool flag = false;
            string a = "", b = s[i];
            for (int j = 0; j < s[i].length() - 1; ++j)
            {
                a += s[i][j], b.erase(b.begin());
                if (us.find(a) != us.end() && us.find(b) != us.end())
                {
                    flag = true;
                    break;
                }
            }
            putchar(flag ? '1' : '0');
        }
        putchar('\n');
    }
    return 0;
}

E. Mirror Grid

Portal.

经典题。找规律找到旋转后的坐标，模拟即可。

#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

bool a[105][105];

int main(void)
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        string s;
        for (int i = 0; i < n; ++i)
        {
            cin >> s;
            for (int j = 0; j < n; ++j)
                a[i][j] = s[j] - '0';
        }
        int ans = 0;
        for (int i = 0; i < n / 2 + 1; ++i)
            for (int j = 0; j < n / 2 + 1; ++j)
            {
                int s = a[i][j] + a[j][n - i - 1] + a[n - i - 1][n - j - 1] + a[n - j - 1][i];
                if (s <= 2)
                {
                    a[i][j] = a[j][n - i - 1] = a[n - i - 1][n - j - 1] = a[n - j - 1][i] = 0;
                    ans += s;
                }
                else 
                {
                    a[i][j] = a[j][n - i - 1] = a[n - i - 1][n - j - 1] = a[n - j - 1][i] = 1;
                    ans += 4 - s;
                }
            }
        printf("%d\n", ans);
    }   
    return 0;
}

F. Yet Another Problem About Pairs Satisfying an Inequality

Portal.

对不等式进行拆解，得到 $a_i<i$ ， $a_j<j$ 和 $i < a_j$ 三个不等式。考虑暴力算法，枚举 $i,j$ 可以轻松得到答案。

对此进行优化。 $i < a_j$ 变形为 $a_j\ge i+1$ （因为都是整数），满足这个条件的数的个数具有单调性，可以用一个 sum 数组记录，维护后缀和即可。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
using i64 = long long;

int n, t;
int a[200005];
i64 sum[200005];

int main(void)
{
    scanf("%d", &t);
    while (t--)
    {
        memset(sum, 0, sizeof(sum));
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", a + i);
            if (a[i] < i) ++sum[a[i]]; // 满足基本条件，将这个 sum +1
        }
        for (int i = n; i >= 1; --i) // 计算后缀和
            sum[i] += sum[i + 1];
        i64 ans = 0;
        for (int i = 1; i <= n; ++i)
            if (a[i] < i) ans += sum[i + 1]; // a[j] >= i+1
        printf("%lld\n", ans);
    }
    return 0;
}

G. Good Key, Bad Key

Portal.

用 Bad Key 减半这种事情越在后面发生越好。因为 $\left\lfloor \cfrac{A_i}{2}\right\rfloor + \left\lfloor \cfrac{A_{i+1}}{2}\right\rfloor - k \le \left\lfloor A_i\right\rfloor + \left\lfloor \cfrac{A_{i+1}}{2}\right\rfloor - k$ 恒成立。

交替使用 Good Key, Bad Key 没有意义。理由基本同上，在 Bad Key 后面出现一个 Good Key 不如将这个 Good Key 移到 Bad Key 前。花费的钱都是 $k$ ，而先用 Good Key 却能避免第一个箱子中钱减半的惨案。

而且用了 $30$ 个 Bad Key 之后就无意义了。因为 $2^{30} > 10^9$ 。

#include <iostream>
#include <cstdio>

using namespace std;
using i64 = long long;

const i64 MAX = 1000000005;

int read(void)
{
    int x = 0, c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return x;
}

int n, k;
int a[100005];

int main(void)
{
    int t = read();
    while (t--)
    {
        n = read(), k = read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        i64 ans = 0, res = 0;
        for (int i = 0; i <= n; ++i)
        {
            if (i >= 1) res += a[i] - k;
            i64 ret = 1, cur = 0;
            for (int j = i + 1, R = min(n, i + 31); j <= R; ++j) // 为防止出错，开了 31
                cur += a[j] / (ret *= 2);
            ans = max(ans, res + cur);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

总结

主要是考察了一些编程基本功，练一下手还是不错的。