Codeforces Round #861 (Div. 2)

Date: 03/29/2023

Link: Dashboard - Codeforces Round 861 (Div. 2) - Codeforces

A|Lucky Numbers

Brief: 从 \(l\) 到 \(r\) 的整数中找到任意一个最幸运的数。幸运度定义为一个数中最大数字和最小数字的差值。

Data: \(T\leq 1e4\), \(l,r\leq1e6\).

Solution: 【简单思维题】【构造】

暴力即可。最多 \(100\) 次可以找到幸运度为 \(9\) 的数。

题解给出当 \(r-l\geq 100\), 可以直接找后两位是 \(90\) 的数。

Review: -

State: AC.

B| Playing in a Casino

Brief: \(n\) 张牌，每张上 \(m\) 个数字。每人一张，每两人对决，胜者获得 \(\sum|a_i-b_i|\) 分（牌上对应数字相减）。问总共有多少分。

Data: \(n\cdot m\leq 3e5\).

Solution: 【排序】【前缀和】

可以发现对于每张牌上的 \(m\) 个数字是互不干扰的，因此只需考虑每张牌上对应的数即可。发现每个数对答案的贡献为他减去比他小的数的和，排序后前缀和计算即可。

Review: -

State: AC.

C| Unlucky Numbers

Brief: 题意同 \(A\), 但找幸运度最小的。

Data: \(T\leq 6e2\), \(l,r\leq1e18\).

Solution: 【构造】

显然没法暴力，注意并非有相等的数字幸运度就为 \(0\)，因为并不一定的最大最小数字的差。

可能涉及数位dp的思想，所以先咕（

让我先滚去学一下数位dp

Review: -

State: TLE => ?

D| Petya, Petya, Petr, and Palindromes

Brief: 给出一个整数序列，对于所有长度为奇数 \(k\) 的子串，最少修改几个数使其成为回文，求和。

Data: \(n\leq 2e5, a_i\leq2e5\).

Solution: 【回文】【计数】

对于每一个数，考虑它会和谁比较。我们可以计算出对于 \(a_i\) 的区间 \([l, r]\)，\(a_i\) 会和其中所有位置和 \(i\) 奇偶性相同位置的数比较。\(l\) 为对称中心在 \(i+1\) 时的对应点，\(r\) 为 \(a_i\) 在 \(k\) 区间最左端的对应点。另外，还有 \(l\) 和 \(r\) 的限制是长度为 \(k\) 的区间不超出数组两端。

反面考虑统计不用修改的数量，即比较结果是相同的数量。答案即是总比较数量 \((n - k + 1)\cdot(k - 1) / 2\) 减去比较结果是相同的数量。

因此只需要对于每个 \(i\), 找到对应的 \([l,r]\), 对于这个区间维护数组 bt[a][odd/even], 第一维是值域，第二维表明是奇数还是偶数位置的桶。每次答案减去即可。由于 \(l\) 和 \(r\) 每次的变动不超过 \(1\), 所以可以很快维护。

Review: 感觉当时是题都没读清楚，以为马拉车…赛后终于理清思路。

State: - => AC.

Code:

#include Justanaaaaame
#include <iostream>
using namespace std;
#define MAXN 200010

int n, k;
int a[MAXN];
long long ans;
int bt[MAXN][2];


int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> k;
    ans = (n - k + 1LL) * (k - 1LL) / 2LL;
    for (int i = 1 ; i <= n ; ++i)
        cin >> a[i];
    int curl = 0, curr = 0;
    for (int i = 1 ; i < n - (k - 1) / 2 ; ++i)
    {
        int lc = max(i + 1, (k + 1) / 2);
        int l = lc * 2 - i;
        int rc = min(i + (k - 1) / 2, n - (k - 1) / 2);
        int r = rc * 2 - i;
        // cerr << i << ":l(" << l << "), r(" << r << ")\n";
        while (curl > l)
        {
            --curl;
            ++bt[a[curl]][curl & 1];
        }
        while (curl < l)
        {
            --bt[a[curl]][curl & 1];
            ++curl;
        }
        while (curr < r)
        {
            ++curr;
            ++bt[a[curr]][curr & 1];
        }
        while (curr > r)
        {
            --bt[a[curr]][curr & 1];
            --curr;
        }
        ans -= bt[a[i]][i & 1];
    }
    cout << ans << endl;

    return 0;
}