说实话这绝对是我做过最垃圾的一套 ARC 了，没有之一。

D – Worst Case

这个题有点像我之前 Codeforces 做过的一个题，但是好像不是一样的，所以被卡了好久。

首先考虑几个特判，我们先设 \(A < B\)：

• \(A = B\)，这个答案就是 \(2(A – 1)\)，没什么好说的。
• \(A = B – 1\)，这个的话答案也是 \(2(A – 1)\)，没什么好说的。

之后考虑 \(A < B – 1\) 的情况了。首先他们的这个积最后是 \(A\times B\)。我们要数清楚有多少个 \((x, y), x \times y < A \times B\)。其实想到这里可以尝试找一个 \(C\) 使得 \(C^2 < AB\)。这个时候一般会存在 \(A < C < B\) 的情况。如果 \(C(C + 1) < AB\) 那么答案为 \(2C – 1\)，否则为 \(2C – 2\)。

发现其实 \(C(C + 1)\) 其实是一组解，所以我们先来思考为什么答案是 \(2C – 2\)。可以考虑构造 \((1, A + B – 1), (2, A + B), \dots, (A – 1, B + 1), (A + 1, 2C – A – 1), \dots, (C, C), \dots (2C, 1)\)。

// ARC094B.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll Q, n = 1e12, a, b;

int main()
{
    scanf("%lld", &Q);
    while (Q--)
    {
        scanf("%lld%lld", &a, &b);
        if (a > b)
            swap(a, b);
        ll ans = 0;
        if (a == b || a + 1 == b)
            ans += 2LL * a - 2;
        else
        {
            ll C = sqrt(1LL * a * b) - 1;
            while ((C + 1) * (C + 1) < 1LL * a * b)
                C++;
            if (C * (C + 1) >= 1LL * a * b)
                ans = 2LL * C - 2;
            else
                ans = 2LL * C - 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E – Tozan and Gezan

Tozan 可以直接随心所欲的走，而 Gezan 并不能进行有效的抑制。最后情况一定会是 \(0, 0, 0, 0, \dots, b_i, 0, \dots\)。所以最后 Candy 计数肯定会把所有的 \(a_i\) 计入，但是除了中间的 \(b_i\)。这个 \(b_i\) 取 \(a_i > b_i\) 时的最小值，因为只有这个情况会出现在最后状态下。

// ARC094C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

typedef pair<int, int> pii;

int n, ai[MAX_N], bi[MAX_N];
priority_queue<pii> pq1;
multiset<pii> pq2;

int main()
{
    scanf("%d", &n);
    long long ans = 0, acc = 1LL << 30;
    bool flag = true;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &ai[i], &bi[i]);
        flag &= (ai[i] == bi[i]), ans += ai[i];
        if (ai[i] > bi[i])
            acc = min(acc, 1LL * bi[i]);
    }
    if (flag)
        puts("0");
    else
        printf("%lld\n", ans - acc);
    return 0;
}

F – Normalization

就是这个题让整套题都很烂了（

想半天去看个题解，最后发现是个结论题，而且没有任何证明（四色定理式证明），我是佛了。

// ARC094D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200, mod = 998244353;

int n, dp[MAX_N][3][3][2], str[MAX_N];
char org[MAX_N];

int main()
{
    scanf("%s", org + 1), n = strlen(org + 1);
    int oddity = 0, tot[3] = {0, 0, 0};
    bool flag = true;
    for (int i = 1; i <= n; i++)
        str[i] = org[i] - 'a', oddity = (oddity + str[i]) % 3, tot[str[i]]++;
    for (int i = 1; i < n; i++)
        flag &= (str[i] != str[i + 1]);
    if (tot[0] == n || tot[1] == n || tot[2] == n)
        puts("1"), exit(0);
    if (n <= 3)
    {
        map<string, bool> mp;
        string org_str = org + 1;
        mp[org_str] = true;
        int delta = 0;
        do
        {
            delta = 0;
            for (auto x : mp)
                for (int i = 0; i < n - 1; i++)
                    if (x.first[i] != x.first[i + 1])
                    {
                        string nxt = x.first;
                        nxt[i] = nxt[i + 1] = ('a' ^ 'b' ^ 'c') ^ (x.first[i] ^ x.first[i + 1]);
                        if (mp[nxt] == false)
                            mp[nxt] = true, delta++;
                    }
        } while (delta);
        printf("%lld\n", 1LL * mp.size());
    }
    else
    {
        int ans = (flag == true);
        dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
        for (int i = 2; i <= n; i++)
            for (int sum = 0; sum < 3; sum++)
                for (int pre = 0; pre < 3; pre++)
                    for (int curt = 0; curt < 3; curt++)
                        if (pre == curt)
                            dp[i][(sum + curt) % 3][curt][1] = (0LL + dp[i][(sum + curt) % 3][curt][1] + dp[i - 1][sum][pre][0] + dp[i - 1][sum][pre][1]) % mod;
                        else
                        {
                            dp[i][(sum + curt) % 3][curt][0] = (0LL + dp[i][(sum + curt) % 3][curt][0] + dp[i - 1][sum][pre][0]) % mod;
                            dp[i][(sum + curt) % 3][curt][1] = (0LL + dp[i][(sum + curt) % 3][curt][1] + dp[i - 1][sum][pre][1]) % mod;
                        }
        for (int i = 0; i < 3; i++)
            ans = (0LL + ans + dp[n][oddity][i][1]) % mod;
        printf("%d\n", ans);
    }

    return 0;
}