A - Sleeping pairs

• 很明显，能删的要立刻删，它们会阻碍交换。
• 一共要删除 $n$ 列，这需要 $n$ 点体力。
• 由于删除时总要保证两列字符一致，故两列 X 的个数要相等。设两列 X 的个数原来相差 $b$ 个，则交换一行 XZ（或 ZX）会使得某一列减少一个 X，而另一列增加一个 X，差值减少 $2$，故这需要 $\dfrac{b}{2}$​ 点体力。
• 由样例 $1$ 可知，删除两行相邻的 XZ 和 ZX 需要 $1$ 点额外体力（删除所需的体力已经计算过了）。上一步完成后，ZX 和 XZ 一定都存在（否则两列 X 的个数不可能相同），因此总会有两行相邻的 XZ 和 ZX。设上一步结束后还剩下 $c$ 列，则这需要 $\dfrac{c}{2}$​ 点体力。

#include <bits/stdc++.h>

using namespace std;

int n;
int a, b, c;

string s;

int main()
{
    freopen("pairs.in", "r", stdin);
    freopen("pairs.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        if (s == "XZ")
        {
            b++;
            c++;
        }
        if (s == "ZX")
        {
            b--;
            c++;
        }
    }
    a = n + abs(b) / 2 + c / 2;
    printf("%d", a);
    return 0;
}

B - Have a check

模拟即可。样例已经涵盖了所有注意事项。

#include <bits/stdc++.h>

using namespace std;

string check(string answer, string output)
{
    if (answer == output)
    {
        return "Accepted.";
    }
    int line = 1, column = 1, al = answer.size(), ol = output.size();
    stringstream conv;
    string res;
    conv << "Wrong Answer: ";
    for (int i = 0; i < min(al, ol); i++)
    {
        if (answer[i] != output[i])
        {
            if (answer[i] == '\n')
            {
                conv << "Extra Character";
            }
            else if (output[i] == '\n')
            {
                conv << "Missing Character";
            }
            else
            {
                conv << "Wrong Answer";
            }
            conv << " on Line " << line << ", Column " << column << ".";
            getline(conv, res);
            return res;
        }
        if (answer[i] == '\n')
        {
            line++;
            column = 1;
        }
        else
        {
            column++;
        }
    }
    if (al > ol)
    {
        if (answer[ol] == '\n')
        {
            conv << "Missing Line on Line " << line + 1 << ".";
        }
        else
        {
            conv << "Missing Character on Line " << line << ", Column " << column << ".";
        }
    }
    else
    {
        if (output[al] == '\n')
        {
            conv << "Extra Line on Line " << line + 1 << ".";
        }
        else
        {
            conv << "Extra Character on Line " << line << ", Column " << column << ".";
        }
    }
    getline(conv, res);
    return res;
}

int main()
{
    freopen("check.in", "r", stdin);
    freopen("check.out", "w", stdout);
    string ansa, out;
    stringstream s0, s1, s2;
    bool sepa = false;
    char c = getchar();
    while (c != EOF)
    {
        s0 << (int)c << endl;
        if (c == 127)
        {
            sepa = true;
        }
        else if (sepa)
        {
            s2 << '*';
        }
        else
        {
            s1 << '*';
        }
        c = getchar();
    }
    s1 >> ansa;
    s2 >> out;
    int tmp = 0, cnt = 0;
    sepa = false;
    while (s0 >> tmp)
    {
        if (tmp == 127)
        {
            sepa = true;
            cnt = 0;
        }
        else
        {
            if (sepa)
            {
                out[cnt] = tmp;
            }
            else
            {
                ansa[cnt] = tmp;
            }
            cnt++;
        }
    }
    cout << check(ansa, out);
    return 0;
}

C - Moving like a spider

• 由于向上运动不花费体力，会合点的 $y$ 坐标可以无限大，因此只需要考虑会合点的 $x$ 坐标即可。
• 不难发现，每只蜘蛛最优移动路径只有两种：
  • 在当前 $y$ 坐标上改变 $x$ 坐标（设改变量为 $\Delta x$），然后向上运动，花费 $ry_0\Delta x$ 点体力（其中 $y_0$ 是初始的 $y$ 坐标）。
  • 向下运动到中心点 $O$，然后向上运动，花费 $dy_0$ 点体力。
• 由上可知，我们只需要关注 $\Delta x$ 和 $l=\dfrac{d}{r}$ 的大小关系，即可确定每只蜘蛛的最优移动路径。
• 因此，我们枚举会合点的 $x$ 坐标，然后差分（结合斜率）维护花费的总体力即可。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 12;

int K[N], D[N], R[N], A[N];

int move(int f, int s, int n)
{
    return (f + s + n) % n;
}

int dis(int f, int t, int n)
{
    int ans = abs(t - f);
    return min(ans, n - ans);
}

void build(int n, int d, int r, int l)
{
    for (int i = 0; i <= n - 1; i++)
    {
        if (l >= n / 2 && n % 2 == 1)
        {
            // i = 1, n = 7
            // pos: 0 1 2 3 4 5 6
            // dis: 1 0 1 2 3 3 2
            K[move(i, n / 2 + 1, n)] += -1 * A[i];
            K[move(i, n / 2 + 2, n)] += -1 * A[i];
            K[move(i, 1, n)] += 2 * A[i];
        }

        if (l >= n / 2 && n % 2 == 0)
        {
            // i = 1, n = 6
            // pos: 0 1 2 3 4 5
            // dis: 1 0 1 2 3 2
            K[move(i, n / 2 + 1, n)] += -2 * A[i];
            K[move(i, 1, n)] += 2 * A[i];
        }
        if (l < n / 2)
        {
            // i = 1, n = 8, l = 2
            // pos: 0 1 2 3 4 5 6 7
            // dis: 1 0 1 2 d d d 2
            R[move(i, l + 1, n)] += -l * A[i];
            K[move(i, l + 1, n)] += -1 * A[i];
            D[move(i, l + 1, n)] += 1 * A[i];
            R[move(i, -l, n)] += l * A[i] + A[i];
            K[move(i, -l, n)] += -1 * A[i];
            D[move(i, -l, n)] += -1 * A[i];
            K[move(i, 1, n)] += 2 * A[i];
        }
    }
    return;
}

signed main()
{
    freopen("spider.in", "r", stdin);
    freopen("spider.out", "w", stdout);
    int m, n, d, r;
    cin >> m >> n >> d >> r;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        A[x] += y;
    }
    int l = d / r;
    long long a0 = 0, d0 = 0, r0 = 0;
    for (int i = 0; i <= n - 1; i++)
    {
        if (dis(0, i, n) <= l)
        {
            a0 += dis(0, i, n) * r * A[i];
            r0 += dis(0, i, n) * A[i];
        }
        else
        {
            a0 += d * A[i];
            d0 += A[i];
        }
    }
    long long a1 = 0, d1 = 0, r1 = 0;
    for (int i = 0; i <= n - 1; i++)
    {
        if (dis(1, i, n) <= l)
        {
            a1 += dis(1, i, n) * r * A[i];
            r1 += dis(1, i, n) * A[i];
        }
        else
        {
            a1 += d * A[i];
            d1 += A[i];
        }
    }
    build(n, d, r, l);
    long long kk = r1 - r0 - R[1], dd = d1, rr = r1, aa = a1, ans = min(a0, a1);
    for (int i = 2; i <= n - 1; i++)
    {
        kk += K[i], dd += D[i], rr += R[i];
        rr += kk;
        aa = rr * r + dd * d;
        ans = min(ans, aa);
    }
    cout << ans << endl;
    return 0;
}

D - Faster than expected

第一部分

上述代码的最坏时间复杂度是 $O(nT \log n)$。

第二部分

为了证明中间的小猪不会出现左右往复移动而使时间复杂度达到 $O(n^2T)$ 的情况，我们考虑把场上所有的小猪从左向右平分成三分，分别记为 $A,B,C$。

根据题意，在 $A,B,C$ 中都至少有一只小猪还没下桥的情况下，$A$ 中的小猪总会向左移动，而 $C$ 中的小猪总会向左移动。$\dfrac{T}{2}$ 秒后，$A$ 中任意一只小猪和 $C$ 中任意一只小猪之间的距离将不小于 $T$，因此它们之间一定有一组全部下桥了。

由上可知，时间每过去 $\dfrac{T}{2}$ 秒，桥上小猪的数量都将至少减少 $\dfrac{1}{3}$，即剩下原来的 $\dfrac{2}{3}$ 或更少。因此，整个过程最多持续 $\dfrac{T}{2} \cdot \log _{\frac{3}{2}} n=O(T \log n)$ 秒。

阅读程序可知，它 while 循环内程序的时间复杂度为 $O(n)$，而 while 循环每执行一次相当于时间流逝一秒，因此 while 循环最多会执行 $O(T \log n)$ 次。

综上，上述代码的时间复杂度不高于 $O(nT \log n)$。

第三部分

只要让 $T$ 远大于 $n$（此时可以忽略 $n$ 对小猪位置的影响），且 $T,n$ 足够大，将 $n$ 只小猪都放在 $\dfrac{T}{3}$ 位置（时间每过去 $\dfrac{T}{3}$ 秒，桥上小猪的数量都将减少 $\dfrac{1}{2}$），即可使上述代码的时间复杂度退化到 $O(nT \log n)$。

例如：

• $n=10^6$。
• $T=3 \times 10^{18}$。
• $a_i=10^{18}+i$。