Contestant'. Rank 1580. Rating +23(+173 -150).

A. New Palindrome

题意

给定一个回文串，输出是否可以将其重新排序，变成另一个回文串。

思路

只要回文串中有两种不同的字符，且这两个字符出现次数都大于 \(1\)，那么就可以。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    string s;
    cin >> s;
    int cnt = 0;
    for(int i=0;i<s.size();i++)
        if(s[i] != s[0]) cnt ++;
    cout << (cnt >= 2 ? "YES\n" : "NO\n");
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

什么手速题

B. Maximum Sum

题意

给定一个无重复元素的序列，定义操作为下列操作任选其一：

1. 删除序列中最小的 两 个数；

2. 删除序列中最大的 一 个数

输出一次操作后序列的和的最大值。

思路

枚举所有删除后的序列的和即可，至于求和，可以用前缀和。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> sum(n + 1);
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    sort(all(a));
    for(int i=0;i<n;i++) sum[i + 1] = sum[i] + a[i];
    int ans = 0;
    for(int l=0;l<=m;l++){
        int r = m - l;
        ans = max(ans, sum[n - r] - sum[2 * l]);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

为什么我想着用双指针啊哈哈哈，为什么有人和我想的一样然后觉得样例错了还去问啊哈哈哈

C. Contrast Value

题意

对于一个序列 \(a\)，定义其 "对比度" 为 \(|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|\)。

找出一个长度最小的 \(a\) 的子序列，使其和 \(a\) 的对比度一致，输出长度。

思路

显然，对于一段单调的区间，只有区间的头和尾对 "对比度" 有贡献，因此中间的数直接删掉即可。

或者换句话说，拐点的个数就是答案。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    int pre;
    cin >> pre;
    int now = -1, cnt = 0;
    for(int i=2;i<=n;i++){
        int cur;
        cin >> cur;
        if(cur == pre) continue;
        if(cur > pre && now == 0){
            cnt ++;
            now = 1;
        }else if(cur < pre && now == 1){
            cnt ++;
            now = 0;
        }
        if(now == -1){
            cnt ++;
            now = (cur > pre ? 1 : 0);
        }
        pre = cur;
    }
    cout << cnt + 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

怎么三道水题之后都是坐牢题啊！ImbalancedForces（迫真

D1. Red-Blue Operations (Easy Version)

题意

给定 \(n\) 个格子，给定每个格子内的数字，格子一开始都是红色的。

对于 \(k\) 次操作，定义第 \(i\) 次操作如下：

1. 选定一个格子

2. 按格子的颜色进行不同的操作：

   • 如果格子是红色的，那么将格子内的元素 \(+i\)，并将该格子变为蓝色；

   • 如果格子是蓝色的，那么将格子内的元素 \(-i\)，并将该格子变为红色

现在，对于 \(q\) 个独立询问，每个询问给定整数 \(k\)，输出恰好进行 \(k\) 次操作后，所有格子内元素的最小值 的最大值。

思路

简化问题 - 1

首先，如果 \(k\leq n\)，那么我们只需依次对没操作过的格子进行操作即可。

那么，很显然，我们对前 \(k\) 小的格子进行操作即可，且我们自然希望最小的能加上最大的数。

更具体地说，我们将格子对应的序列 \(a\) 升序排序，并将 \(k, k-1,\ldots,1\) 按顺序加到 \(a_i\) 中，最后遍历找出序列中的最小值即可。

简化问题 - 2

其次，我们来考虑 \(k > n\) 的时候，多余操作的如何处理。

对于一个红色的格子，我们可以对其进行两次操作，使其 \(+i\ -(i+1) = -1\)。

那么，我们不难发现，既然这样能让两次操作后对序列的影响最小，我们就可以把 "\(-1\)" 应用到当前最大的数上。

也就是说，我们可以先循环执行 \(-1\) 的操作，直到刚好剩余 \(n\) 个操作，最后按照 \(k \leq n\) 的方法做即可。

当然，上述思路只对 \(k - n\) 是偶数的情况有效，若它为奇数，那么我们有两个选择：

1. 多执行一次减操作

2. 少执行一次加操作

显然，后者能产生更大的最小值。

因此，总结为：先循环执行 \(-1\) 的操作，直到刚好剩余 \(n - (k - n)\mod 2\) 个操作，最后按照 \(k \leq n\) 的方法做即可。

优化复杂度 - 1

如果 \(k\) 不大，那么我们直接用 \(\mathtt{multiset}\) 模拟即可。

但这里的 \(k\) 是 \(1e9\) 级别的，这就迫使我们去找一个 \(O(1)\) 或 \(O(logn)\) 的解法。

后者可以通过二分实现，这边不做解释。

我们不妨模拟一下 \(-1\) 操作的过程：我们找出序列的最大值，拿掉这个数，并将其 \(-1\)，然后将这个新的数塞到序列中并排序序列。

那么，不难发现，除非这个最大值等于最小值，否则无论怎么减，操作后的数一定大于等于原来的最小值。

因此，想要让最小值减小，首先我们需要将整个序列全都减到和最小值相等为止。

这样，我们再依次将每个数 \(-1\)，\(n\) 次 \(-1\) 操作后，最小值就 \(-1\) 了。

总结

考虑到 \(-1\) 操作和 按顺序加的操作 是相互独立的，我们可以先执行 按顺序加的操作。

那么，对于每次询问，我们只需先遍历序列中的所有数，将 \(a_i\) 加上 \(k - i + 1\)（如果 \(k - n\) 是奇数，那么最后一个数不加），统计出总和以及最小值。那么按照优化的思路即可 \(O(1)\) 得到答案。

以上，即可通过 \(D1\)。

时间复杂度：\(O(nq)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(all(a));
    while(q --){
        int k;
        cin >> k;
        int left = k - n;
        int mn = inf, sum = 0;
        for(int i=0;i<n;i++) {
            int now = (i == n - 1 && left % 2 == 1) ? a[i] : a[i] + max(0ll, (k - i));
            mn = min(mn, now);
            sum += now;
        }
        if(left <= 0){
            cout << mn << ' ';
            continue;
        }
        left += left % 2;
        left >>= 1;
        cout << min(mn, (sum - left) / n) << ' ';
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

令人感慨，没看到 \(k\) 的范围，硬模拟 \(t\) 咯！

D2. Red-Blue Operations (Hard Version)

题意

同 \(D1\)，区别是 \(n, q\) 的数据范围更大了。

思路

前面的思路和 \(D1\) 一致。

优化复杂度 - 2

观察 \(D1\) 的代码，我们不难发现，只有统计总和以及最小值的步骤是 \(O(n)\) 的，因而我们考虑优化这个。

我们不妨构造一个 \(pre\) 数组，代表处理前 \(k\) 个数后，整个序列 的最小值。接下来我们来看看如何构造：

首先，对于 \(a_i\)，如果我们处理前 \(i\) 个数，那么，在处理之后，\(a_i\) 会 \(+1\)。

其次，对于上一次处理后的序列，本次处理等价于将前 \(i\) 个数都 \(+1\)。

那么，如果我们不考虑前 \(i\) 个数之外的其他数，前 \(i\) 个数的最小值具有递推性：\(x_i = \min(x_{i - 1} + 1, a_i + 1)\)。

考虑其他数，因为我们排过序，所以 \(a_{i + 1}\) 就是这些数中的最小值。

因此，\(pre_i = \min(x_i, a_{i + 1})\)。

\(ok\)，那么如果 \(k \leq n\)，我们就可以直接输出答案了。

如果 \(k > n\) 呢？

首先，我们不妨在递推的时候顺便统计一下序列 \(a\) 的总和 \(sum\)，那么最后的 \(sum'\) 就是 \(sum\) 加上 \(k, k - 1,\ldots, k - n + 1\) 的和。

显然，我们可以用等差数列求和公式直接计算。

之前，我们预处理得到的 \(pre_n\) 就是原序列依次加上 \(n, n-1, \ldots,1\) 中的最小值，而现在我们要加上的是 \(k, k - 1,\ldots, k - n + 1\)，显然对于每个元素，加上的数的差值都是 \(n - k\)，因此现在的最小值 \(mn = pre_n + (n - k)\)。

还没有结束，如果 \(k - n\) 为奇数，那么 \(sum'\) 要减去 \((n - k + 1)\)。并且，因为最大数 \(a_n\) 没有加上 \((n - k + 1)\)，所以最后 \(mn\) 还要和 \(a_n\) 取个最小值。

如上，即可线性得到答案。

时间复杂度：\(O(n + q)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1, inf);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(all(a));
    vector<int> pre(n + 1); //处理前k个后序列的最小值
    int pre_mn = inf, sum = 0; //前k-1个数的最小值（+1后有可能成为前k个数的最小值，需递推特判
    for(int i=0;i<n;i++){
        pre_mn = min(pre_mn + 1, a[i] + 1);
        pre[i + 1] = min(pre_mn, a[i + 1]);
        sum += a[i];
    }
    while(q --){
        int k;
        cin >> k;
        int left = k - n;
        if(left <= 0){
            cout << pre[k] << ' ';
            continue;
        }
        //从+k到+(k-n+1)
        int now_sum = sum + (k + left + 1) * n / 2;
        int mn = pre[n] + left; //+n到+1 -> +k到+(k-n+1)
        if(left % 2 == 1){
            now_sum -= (left + 1);
            mn = min(mn, a[n - 1]);
        }
        left += left % 2;
        left >>= 1;
        cout << min(mn, (now_sum - left) / n) << ' ';
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

有趣的题捏