AtCoder Regular Contest 091 – 解题报告

这场代码都好短啊。

C – Flip,Flip, and Flip……

傻逼题，随便搞就行了。

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

using namespace std;

typedef long long ll;

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    if (n > m)
        swap(n, m);
    if (n == 1)
    {
        if (m == 1)
            puts("1");
        else
            printf("%d\n", max(0, m - 2));
        return 0;
    }
    printf("%lld\n", max(0LL, 1LL * (n - 2) * (m - 2)));
    return 0;
}

D – Remainder Reminder

这个题也比较傻逼，枚举 \(b\) 然后算 \(a\) 的个数即可。

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

using namespace std;

int n, k;

int main()
{
    scanf("%d%d", &n, &k);
    long long ans = 0;
    for (int b = max(k + 1, 1); b <= n; b++)
    {
        int rem = (n + 1) % b, loop_num = (n + 1) / b;
        int bpart = b - k;
        long long pans = 1LL * loop_num * bpart + max(0, rem - k) - (k == 0);
        ans += pans;
    }
    printf("%lld\n", ans);
    return 0;
}

E – LISDL

这个题比较有意思。

考虑构造一个长度为 \(AB\) 的序列，那么满足条件的序列可以被构造成：

\[ (B – 1)A + 1, (B – 1)A + 2, \dots, BA, (B – 2)A + 1, (B – 2)A + 2, \dots \]

我们发现这个序列发挥性质的部分只在于全局的 \(B\) 个下降点和至少一段 \(A\) 的上升段。所以我们可以抛弃一部分无用信息，然后重新标号成排列即可。

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

using namespace std;

int n, a, b;

int main()
{
    scanf("%d%d%d", &n, &a, &b);
    if (a + b - 1 > n || 1LL * a * b < n)
        puts("-1"), exit(0);
    while (n > 0)
    {
        int rd = min(a, n - b + 1);
        for (int i = n - rd + 1; i <= n; i++)
            printf("%d ", i);
        n -= rd, b--;
    }
    puts("");
    return 0;
}

F – Strange Nim

神仙博弈论。

每堆石子都是独立的，所以我们分开求 SG 函数值然后异或起来即可。注意到：

\[ SG(X, K) = \begin{cases} \frac{X}{K}, X \bmod K \equiv 0 \\ SG(X – \lfloor \frac{X}{K} \rfloor + 1), \text{otherwise} \end{cases} \]

然后就 OK 了。

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

using namespace std;

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1, x, k; i <= n; i++)
    {
        scanf("%d%d", &x, &k);
        while (x % k != 0)
            x -= ((x % k - 1) / (x / k + 1) + 1) * (x / k + 1);
        ans ^= x / k;
    }
    puts(!ans ? "Aoki" : "Takahashi");
    return 0;
}