链接：https://atcoder.jp/contests/abc443

A – Append s

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    string s;
    cin >> s;

    cout << s << 's' << endl;
}

B – Setsubun

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    ll n, k;
    cin >> n >> k;

    ll ans = 0, cnt = 0;
    while (cnt < k)
    {
        cnt += n;
        ++n;
        if (cnt < k)
            ++ans;
    }

    cout << ans << endl;
}

C – Chokutter Addiction

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    ll n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    a.push_back(t);

    bool ok = 1;
    ll ans = 0;
    ll next = 0;
    for (int i = 0; i <= n; ++i)
    {
        if (a[i] < next)
            continue;

        ans += a[i] - next;
        next = a[i] + 100;
    }

    cout << ans << endl;
}

D – Pawn Line

算法：

模拟。

思路：

设原数组坐标总和为 \(∑R_i\)，调整后的数组坐标总和为 \(∑A_i\)。

要使 \(|∑R_i – ∑A_i|\) 最小，既最大化 \(∑A_i\)（让每个 \(A_i\) 尽可能大）。

每个点 \(i\) 需要考虑与之相邻的两个点：

• 对于 \(i (i > 1)\)，其相较于 \(i – 1\)，需要满足其位置最终在 \(R[i – 1] + 1\) 之上（包含该点）；
• 对于 \(i (i < n)\)，其相较于 \(i + 1\)，需要满足其位置最终在 \(R[i + 1] + 1\) 之上（包含该点）；
• 那么最终 \(i\) 位置就在 \(min(R[i – 1] + 1, R[i + 1] + 1)\) 上；
• 正序求出相较于前面点的位置，逆序求出相较于后面点的位置。

关键代码：

下面给出两份代码。

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    ll s = accumulate(all(a), 0ll);

    for (int i = 1; i < n; ++i)
        a[i] = min(a[i], a[i - 1] + 1);
    for (int i = n - 2; i >= 0; --i)
        a[i] = min(a[i], a[i + 1] + 1);

    for (auto &x : a)
        s -= x;

    cout << s << endl;
}

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    vector<int> l(n), r(n);

    l[0] = a[0];
    for (int i = 1; i < n; ++i)
        l[i] = min(a[i], l[i - 1] + 1);

    r[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; --i)
        r[i] = min(a[i], r[i + 1] + 1);

    ll ans = 0;
    for (int i = 0; i < n; ++i)
        ans += a[i] - min(l[i], r[i]);

    cout << ans << endl;
}

E – Climbing Silver

算法：

\(dp\)。

思路：

结论：对于某一列，如果最下面的墙格可以到达，那么该列最上面的那一格也可以到达。

考虑 \(dp\)。

定义：

• \(dp[i][j]\) 表示 \((i, j)\) 是否可以到达；
• \(d[i]\) 表示第 \(i\) 列最下面的墙格的行号。

状态转移：

• 如果 \(g[i][j]\) 为空格，那么它可以通过它正下面的三个格子转移而来，既 \(dp[i][j] |= dp[i + 1][j – 1] | dp[i +- 1][j] | dp[i + 1][j + 1]\)；
• 如果 \(g[i][j]\) 为墙格，且是该列最下面的那个墙格，那么可以由它正下面的三个格子转移而来，状态转移公式同上；
• 如果 \(g[i][j]\) 为墙格，且不是该列最下面的那个墙格，只有该列最下面的墙格可以到达，其才可以到达，既 \(dp[i][j] |= dp[d[j]][j]\)。

关键代码：

void miyan()
{
    int n, c;
    cin >> n >> c;
    vector<string> g(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> g[i];

        g[i] = ' ' + g[i];
    }

    vector<int> d(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (g[i][j] == '#')
                d[j] = i;
        }
    }

    vector dp(n + 1, vector<int>(n + 2, 0));
    dp[n][c] = 1;
    for (int i = n - 1; i >= 1; --i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (g[i][j] == '.' || d[j] == i)
                dp[i][j] |= dp[i + 1][j - 1] | dp[i + 1][j] | dp[i + 1][j + 1];
            else if (g[i][j] == '#')
                dp[i][j] |= dp[d[j]][j];
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << dp[1][i];
    cout << endl;
}

F – Non-Increasing Number

还没补。