牛客周赛38

A 小红的正整数自增

小红拿到了一个正整数，她每次操作可以使得这个正整数加 1。
小红想知道，使得该数的末尾为 0 至少需要操作多少次？

void solve() {
    string s;cin >> s;
    int x = s.back() - '0';
    if (!x) {
        cout << "0\n";return;
    }
    cout << 10 - x << '\n';
}

B 小红的抛弃后缀

小红得到一个正整数，她打算删去一个数字并丢弃，以便剩下的部分是 9 的倍数。小红想知道有多少种不同的操作方案？

#define int long long
void solve() {
    string s;cin >> s;s = " " + s;
    vector<int> pre(s.size() + 1);
    for (int i = 1;i < s.size();i++) {
        pre[i] = pre[i - 1] + s[i] - '0';
    }
    int ans = 0;
    for (int i = 1;i < s.size();i++) {
        if (pre[i] % 9 == 0) {
            ans++;
        }
    }
    cout << ans << '\n';
}

C 小红的字符串构造

小红想让你创建一个长度为 n 的字符串，只包含小写字母，里面正好有 k 个长度大于 1 的回文子串。你能帮帮她吗？

D 小红的平滑值插值

现在小红手头有个数组，她想调整其中数值的顺序来使得最终数组的平均值正好是 k。你能帮忙计算出最少需要操作几次吗？

#define int long long
void solve() {
    int n, k;cin >> n >> k;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int mx = 0;
    for (int i = 2;i <= n;i++) {
        mx = max(mx, abs(a[i] - a[i - 1]));
    }
    if (mx == k) {
        cout << "0\n";return;
    }
    if (mx < k) {
        cout << "1\n";return;
    }
    int ans = 0;
    for (int i = 2;i <= n;i++) {
        if (abs(a[i] - a[i - 1]) > k) {
            ans += (abs(a[i] - a[i - 1]) - 1) / k;
        }
    }
    cout << ans << '\n';
}

E 小苯的等比数列

小苯很喜欢等比数列。有一天他得到了一个长为 n 的数组 a，他想从里面选一些数字使得被选中的数字构成一个等比数列，请问他最多可以选择多少个数字呢？
注意：小苯选择的等比数列公比需要是正整数。

等比数列公比不可能会很大，这里只需要列到 10 就可以过了。

#define int long long
void solve() {
    int n;cin >> n;map<int, int>mp;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;mp[x]++;
    }
    int ans = 0;
    for (auto [x, y] : mp) {
        ans = max(ans, y);
    }
    
    for (auto [x, y] : mp) {
        int res = 0;
        for (int i = 2;i * x<=2e5;i++) {
            int k = x;
            res = 0;
            while (mp.count(k)) {
                res++;k *= i;
            }
            ans = max(ans, res);
        }
    }
    cout << ans << '\n';
}

F 小苯的回文询问

小苯有一个长度为 $n$ 的数组 $a$，他定义一个数组是好数组，当且仅当该数组是一个回文数组，且长度严格大于 2。

他现在进行了 $q$ 次询问，每次询问都给出一段区间 $[l,r]$，他想知道数组 $a$ 在这一段区间中是否存在一个子序列是一个好数组，请你帮帮他吧。

Solution

这题只要满足有 3 个字符，第一个字符和第三个字符相等，则一定满足要求。

可以通过预处理。jd 数组来记录上一个最近满足回文字符串要求的下标，mp 来映射数组的下标，每次遇到满足要求的情况，取最大下标即可。

void solve() {
    int n, q;cin >> n >> q;
    map<int, int> mp;
    vector<int>a(n + 1), jd(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];jd[i] = jd[i - 1];
        if (mp.count(a[i])) {
            if (mp[a[i]] < i - 1)jd[i] = max(jd[i], mp[a[i]]);
        }
        if (i >= 3 && a[i] == a[i - 2])jd[i] = max(jd[i], i - 2);
        mp[a[i]] = i;
    }
    while (q--) {
        int l, r;cin >> l >> r;
        if (r > 2 && jd[r] >= l)cout << "YES\n";
        else cout << "NO\n";
    }
}

G 小红的区间删除

小红有一个长度为 n 的数组 a，他想从 a 中删除一段区间，但又要使得剩余的部分拼起来组成的新数组满足：逆序对个数不少于 k。

她想知道有多少种删除方案，请你帮帮她吧。
注：空数组逆序对数量为 0。

Solution

树状数组+滑动窗口/逆序对

P1908 逆序对

代码

为什么没开全局 ll 就会 tle?

两个树状数组，一个记录前缀，一个记录后缀。

牛客周赛38直播讲解回放

计算逆序对可以从后往前遍历，每次看有多少个数字的下标比该数字小的，每次累加，就是逆序对的个数

for (int i = n;i >= 1;i--) {
	change(tr2, a[i], 1);
	sum += query(tr2, a[i] - 1);
}

也可从前往后遍历：每次看有多少下标比该数字大即可。

for (int i = 1;i <= n;i++) {
	change(tr1, a[i], 1);
	sum += query(tr2, max(a)) - query(tr2, a[i]);
}

从下标前往后删除数，减去相应的逆序对数，若仍然满足逆序对数 $\ge k$ 则算是($j-i+1$ 种)方案，否则 $j$ 向右添加，并添加相应逆序对数，若满足也算是方案，

#define int long long
int a[200010];
int n, k, tr1[1000010], tr2[1000010];
int lowbit(int x) {
    return x & -x;
}
void change(int tr[], int x, int k) {
    while (x <= 1e6)tr[x] += k, x += lowbit(x);
}
int query(int tr[], int x) {
    int ans = 0;
    while (x)ans += tr[x], x -= lowbit(x);
    return ans;
}
void solve() {
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    int sum = 0;
    for (int i = n;i >= 1;i--) {
        change(tr2, a[i], 1);
        sum += query(tr2, a[i] - 1);//算出的结果就是逆序对的总对数
    }
    int ans = (sum >= k);
    for (int i = 1, j = 1;i <= n;i++) {
        change(tr2, a[i], -1);
        sum -= query(tr2, a[i] - 1);
        sum -= query(tr1, 1e6) - query(tr1, a[i]);
        while (j <= i && sum < k) {
            change(tr1, a[j], 1);
            sum += query(tr2, a[j] - 1);
            sum += query(tr1, 1e6) - query(tr1, a[j]);
            j++;
        }
        ans += (i - j + 1);
    }
    cout << ans << '\n';
}