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

A. Cut the Array

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<ll> s(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];

    for (int i = 1; i <= n - 2; ++i)
    {
        for (int j = i + 1; j <= n - 1; ++j)
        {
            ll s1 = s[i];
            ll s2 = s[j] - s[i];
            ll s3 = s[n] - s[j];

            s1 %= 3, s2 %= 3, s3 %= 3;

            if ((s1 == s2 && s2 == s3) || (s1 != s2 && s2 != s3 && s1 != s3))
            {
                cout << i << ' ' << j << endl;
                return;
            }
        }
    }

    cout << 0 << ' ' << 0 << endl;
}

B. Maximum Cost Permutation

算法：

    贪心。

思路：

    不难发现以下规律：

• 当一段区间左右端点为两个 \(0\) 时，那么这个区间的最大答案长度就为这个区间的长度。
• 当一段区间左右端点不为 \(0\) 并满足 \(p[i] != i\) 时，那么这个区间的最大答案长度就为这个区间的长度。
• 当一段区间左右端点为 \(0\) 和 \(p[i] != i\) 时，那么这个区间的最大答案长度就为这个区间的长度。
• 当区间内只有一个 \(0\) 并且缺少的 \(p[i] == i\) 时，那么这个 \(0\) 只能填 \(i\)，不会对答案造成影响。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> p[i];

    ll l = 1e9, r = -1e9;
    ll L = 1e9, R = -1e9;
    set<int> s1, s2;
    vector<int> st(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        if (!p[i])
        {
            l = min(l, 1ll * i);
            r = max(r, 1ll * i);
            s1.insert(i);
        }
        else
        {
            st[p[i]] = 1;

            if (p[i] != i)
            {
                L = min(L, 1ll * i);
                R = max(R, 1ll * i);
                s2.insert(i);
            }
        }
    }

    if (s1.size() == 1)
    {
        ll val = 1;
        while (val <= n && st[val])
            ++val;

        if (val == *s1.begin())
            s1.clear();
    }

    if (s1.empty() && s2.empty())
    {
        cout << 0 << endl;
        return;
    }

    if (s1.empty())
        cout << R - L + 1 << endl;
    else if (s2.empty())
        cout << r - l + 1 << endl;
    else
        cout << max(R, r) - min(L, l) + 1 << endl;
}

C. Non-Descending Arrays

算法：

    \(dp\)。

思路：

    定义 \(dp[i][0/1]\) 为第 \(i\) 个元素交换与否前缀升序的方案数。

    那么对于每个 \(i\) 就只有交换和不交换两种情况。

    状态转移：

• 当 \(a[i] >= a[i – 1]\) 并且 \(b[i] >= b[i – 1]\) 时对于 \(i\) 就可以通过以下状态转移而来：
  • 不交换 \(i – 1\) 并且不交换 \(i\)，既 \(dp[i][0] = (dp[i][0] + dp[i – 1][0]) \text{% MOD} \)
  • 交换 \(i – 1\) 并且 交换 \(i\)，既 \(dp[i][1] = (dp[i][1] + dp[i – 1][1]) \text{% MOD} \)
• 当 \(a[i] >= b[i – 1]\) 并且 \(b[i] >= a[i – 1]\) 时对于 \(i\) 就可以通过以下状态转移而来：
  • 不交换 \(i – 1\) 并且交换 \(i\)，既 \(dp[i][1] = (dp[i][1] + dp[i – 1][0]) \text{% MOD} \)
  • 交换 \(i – 1\) 并且 不交换 \(i\)，既 \(dp[i][0] = (dp[i][0] + dp[i – 1][1]) \text{% MOD} \)

关键代码：

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

    vector dp(n, array<ll, 2>());
    dp[0][0] = dp[0][1] = 1;
    for (int i = 1; i < n; ++i)
    {
        if (a[i] >= a[i - 1] && b[i] >= b[i - 1])
        {
            dp[i][0] = (dp[i][0] + dp[i - 1][0]) % MOD;
            dp[i][1] = (dp[i][1] + dp[i - 1][1]) % MOD;
        }

        if (a[i] >= b[i - 1] && b[i] >= a[i - 1])
        {
            dp[i][0] = (dp[i][0] + dp[i - 1][1]) % MOD;
            dp[i][1] = (dp[i][1] + dp[i - 1][0]) % MOD;
        }
    }

    cout << (dp[n - 1][0] + dp[n - 1][1]) % MOD << endl;
}

D. Price Tags

算法：

    枚举。

思路：

    当选择的数字 \(x\) 大于等于 \(max\)(数组中的最大值) 时，所有的值都会变为 \(ceil(x / a[i]) = 1\)。

    可以发现 \(x\) 最大取值取到 \(max\) 即可，更大就没有意义了。

    特判：当全部元素都为 \(1\) 时，\(x\) 怎么选商品价格都为 \(1\)，答案就为 \(n\)。

    由于 \(a[i]\) 的范围为 \(2e5\)，考虑枚举每个 \(x\) 即可。

    对于一个固定的 \(x\) ，可以枚举在当前 \(x\) 下商品的价格，对于每个价格 \(i\) 求得会有多少商品在打折后为 \(i\)。

    那么对于一个固定的 \(x\)，怎么快速得到新价格为 \(i\) 的商品个数？

    对于一个固定的 \(x\) 和某个价格 \(i\)，\(ceil(c / x) = i\) 等价于原价 \(c\) 落在这个整数区间：

\([(i – 1) * x + 1, i * x]\)

    所以新价格为 i 的商品数为：原价落在 \([(i – 1) * x + 1, i * x]\) 的件数

    这个可以通过前缀和 \(O(1)\) 求得。

关键代码：

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

    vector<ll> c(N, 0);
    ll maxx = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        ++c[x];
        maxx = max(maxx, 1ll * x);
    }

    if (maxx == 1)
    {
        cout << n << endl;
        return;
    }

    vector<ll> s(N, 0);
    for (int i = 1; i < N; ++i)
        s[i] = s[i - 1] + c[i];

    ll ans = LLONG_MIN;
    for (ll x = 2; x <= maxx; ++x)
    {
        ll val = (maxx + x - 1) / x;
        ll res = 0;

        for (ll i = 1; i <= val; ++i)
        {
            ll l = max(0ll, x * (i - 1) + 1);
            ll r = min(maxx, i * x);

            if (l > maxx)
                break;

            ll cnt = s[r] - s[l - 1];
            res += cnt * i;
            res -= max(0ll, cnt - c[i]) * y;
        }

        ans = max(ans, res);
    }

    cout << ans << endl;
}

E1. Looking at Towers (easy version)

    还没补。