链接：https://codeforces.com/contest/2194

A. Lawn Mower

算法：

数学。

思路：

每隔 \(w – 1\) 个木板保留一个木板，那么共保留 \(\lfloor \frac{w}{n} \rfloor\) 个木板，拆除 \(n – \lfloor \frac{w}{n} \rfloor\) 个。

关键代码：

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

    cout << n - n / w << endl;
}

B. Offshores

算法：

贪心。

思路：

尝试对于每个 \(i\) 都作为最终银行，求其最总金额数，答案取最大即可。

当 \(i\) 作为最终银行时，最优策略是将剩余的银行直接加到 \(i\) 上，不进行任何中转。

证明：设 \(i\) 是最终银行，\(u, v\) 是非最终银行，\(u \to v\) 会减少一次向 \(i\) 的转移的次数，而 \(v\) 至多增加一次向 \(i\) 转移的次数，因此中转并不会使答案更大。

具体实现看代码。

关键代码：

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

    ll sum = 0;
    for (auto val : a)
        sum += val / x;

    ll ans = 0;
    for (auto val : a)
        ans = max(ans, (sum - val / x) * y + val);

    cout << ans << endl;
}

C. Secret message

算法：

枚举。

思路：

升序枚举 \(n\) 的因子 \(d\) 并将其作为信息度，定义 \(U_i\) 为所有纸带的第 \(i\) 个字符构成的集合，当信息度为 \(d\) 时，定义 \(U_{1}, U_{1 + d}, U_{1 + 2d}, ….. U_{1 + kd}\) 为同组，最终答案的第 \(i\) 个字符为 \(U_{i}\) 同组所有集合的交集中任意一个字符，因此，如果信息度 \(d\) 成立，需要对于每个 \(i\) 其同组交集都不为空集。

关键代码：

void miyan()
{
    ll n, k;
    cin >> n >> k;
    vector<string> s(k);
    for (auto &x : s)
        cin >> x;

    vector cnt(n, vector<int>(26, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < k; ++j)
            cnt[i][s[j][i] - 'a'] = 1;

    for (int d = 1; d <= n; ++d)
    {
        if (n % d)
            continue;

        string ans;
        bool ok = 1;
        for (int i = 0; i < d; ++i)
        {
            auto cur = cnt[i];

            for (int j = i + d; j < n; j += d)
            {
                for (int k = 0; k < 26; ++k)
                {
                    if (cur[k] == 0 || cnt[j][k] == 0)
                        cur[k] = 0;
                }
            }

            if (accumulate(all(cur), 0) == 0)
            {
                ok = 0;
                break;
            }

            for (int k = 0; k < 26; ++k)
            {
                if (cur[k])
                {
                    ans += k + 'a';
                    break;
                }
            }
        }

        if (ok)
        {
            for (int i = 0; i < n / d; ++i)
                cout << ans;
            cout << endl;

            return;
        }
    }
}

D. Table Cut

算法：

贪心，构造。

思路：

明显第一问答案为 \(\lfloor \frac{2}{cnt} \rfloor * \lceil \frac{2}{cnt} \rceil\)，其中 \(cnt\) 为表格中 \(1\) 的个数。

对于第二问答案可以尝试将表格分割为两部分，其中一部分个数恰好为 \(\lfloor \frac{2}{cnt} \rfloor\)，具体划分请看代码。

划分后，路径构造方法容易得到，具体方法看代码。

关键代码：

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

    ll cnt = 0;
    for (int i = 0; i < n; ++i)
        cnt += accumulate(all(a[i]), 0ll);

    cout << (cnt / 2) * ((cnt + 1) / 2) << endl;

    vector<pii> step;
    for (int i = m - 1; i >= 0; --i)
        step.push_back({0, i});
    for (int i = 1; i < n; ++i)
        step.push_back({i, 0});

    ll need = cnt / 2;
    vector st(n, vector<int>(m, 0));
    for (auto [x, y] : step)
    {
        int nx = x, ny = y;
        while (nx >= 0 && nx < n && ny >= 0 && ny < m)
        {
            if (a[nx][ny] == 1)
                --need;

            st[nx][ny] = 1;

            if (need == 0)
                break;

            ++nx, ++ny;
        }

        if (need == 0)
            break;
    }

    string ans;
    int start = 0;
    for (int i = 0; i < n; ++i)
    {
        if (start == m)
        {
            ans += 'D';
            continue;
        }

        for (int j = start; j < m; ++j)
        {
            if (st[i][j])
            {
                ans += 'D';
                start = j;
                break;
            }
            else
                ans += 'R';
        }

        if (ans.back() == 'R')
        {
            ans += 'D';
            start = m;
        }
    }

    for (int i = start; i < m; ++i)
        ans += 'R';

    cout << ans << endl;
}

E. The Turtle Strikes Back

还没补。