Codeforces Round 932 (Div. 2)

A. Entertainment in MAC

题意

有一个字符串$s$和偶数$n$， 你可以对这个字符串进行$n$次操作（不能多不能少）

• 操作一：将$s$的反向字符串拼接到s的后面，比如对字符串abc进行操作会变成 abccba
• 操作二：将当前的字符串反转

问进行完这n次操作后，最终的字符串的字典序最小的可能是什么样子的。

思路

可以发现，如果这个字符串翻转后更大（比如abc ，进行翻转后是cba 比原先更大了）,那么我们就可以进行n次翻转，这样最终的字符串就是原先的字符串，也就实现最小了。

如果这个字符串s在反转后更小了，那么我们就必须执行奇数次翻转，才能保证这个s最终是较小的。但题目中说n是偶数，所以就意味着我们必须进行至少一次拼接操作， 那么显而易见，拼接操作进行的越少越好， 因此需要翻转$n-1$次，然后拼接一次。 （比如bca， 如果进行偶数次翻转，那么最终的字符串前三个字符是bca ，而进行奇数次翻转时最终的字符串的前三个字符是acb 一定更小）

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    string rs = str;
    reverse(rs.begin(),rs.end());
    if(rs < str){
        cout<<(rs + str)<<'\n';
    }else cout<<str<<'\n';
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B. Informatics in MAC

题意

给出一个长度为n的数组a， 有$a_1, a_2,...,a_n$ （$1\le a_i \le n$) , 请你给这个数组分为至少两组（每组之间的数都是连续的，所以相当于插入至少一个隔板来分组）， 并且让每组的$mex$都是相同的。 如果不能分出至少两组，那么就输出 -1 。

一个数组的$mex$表示为 这个数组中没有出现过的最小的自然数 。如$mex(\{0,1,3,2\}) = 4 , mex(\{3,1,0,1 \}) = 2$ 。

思路

我们可以先找到整个数组的$mex$ ，我们称为$mx$， 这样一定可以分出一个子数组，使得他的$mex$ 为$mx$ , 所以我们就看能否分出两组即可。我们从左到右开始收集数组中的元素， 如果收集到了全部的$[0,mx-1]$ 这$mx$个数，由于我们已经知道整个数组中不含有$mx$,所以这个子数组的$mex$一定是$mx$，接下来我们再按此法不断收集，每当有完整的$[0,mx-1]$就分一组，最后看一下能否分出至少两组即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+5);
    rep(i,1,n) cin>>a[i];
    vector<int> cnt(n+5);
    rep(i,1,n) cnt[a[i]] ++;
    int mn = INF;
    if(cnt[0] == 0){
        cout<<n<<'\n'; rep(i,1,n) cout<<i<<' '<<i<<'\n';
        return ; 
    }
    int mex = 0;
    for(int i =0;i<=n;i++){
        if(cnt[i] == 0){
            mex = i; break;
        } 
    }
    int l = 1;
    vector<PII> ans;
    set<int> st;
    for(int i = 1;i<=n;i++){
        if(a[i]<mex) st.insert(a[i]);
        if(st.size() == mex) {
            ans.push_back({l,i});
            st.clear();l = i+1;
        }
    }
    if(ans.size() == 1) {cout<<-1<<'\n';return ;}
    ans.back().second = n;
    cout<<ans.size()<<endl;
    for(auto p : ans){
        cout<<p.first<<" "<<p.second<<'\n';
    }
    return ;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C. Messenger in MAC

题意

给出一个数组$a$和数组$b$， 我们可以从中取出一些数，这些数的总花费为如下公式：

$$\Large \sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|$$

现在问保证这个花费不大于l的情况下， 最多能选出**多少个数** 。$1\le n^2 \le 4*10^6$

思路

不难发现，如果已经确定我们选择的数之后，那么第一项undefinedLarge \sum_{i=1}^{k} a_{p_i}$就是一个定值，而第二项$\Large \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|$的最小值即为$MAX(b_{p_1},…,b_{p_k}) - MIN(b_{p_1},…,b_{p_k})$。即最大的$b$减去最小的$b$。

于是我们对数据按照b从小到大进行排序，我们选择出的一个数，就是他最右边数的b减去最左边数的b。

**思路一**：我们枚举左右端点，在确定左右端点后，我们只需要在这个区间中找到尽可能小的一些数，让他们相加小于$l - a_l -a_r - (b_r - b_l)$ 即可。

在枚举右端点的时候， 使用一个优先队列来维护”总值不超过$l$“ ，于是就可以在$O(n^2logn)$ 的复杂度内完成枚举所有的左右端点，每当更新一次区间， 就更新一次优先队列，当优先队列中的元素总和不满足要求时便可以快速地出队较大值的元素，从而保证优先队列中的总和满足条件的情况下，数尽可能少，数的数量尽可能多。

**思路二** ： DP， 我们令$dp[i][j]$表示为从i个数中我们选第一个数时视为 贡献了 $a_i - b_i$ ，中间的数可以当作背包来选择，每次枚举j时， 我们都试图将$i$视为最后选择的一项来选出第$j+1$项，这时候就要加$a_i +b_i$ 即要多算一个结尾贡献的$b_i$， 所以我们判断$dp[i][j]+a[i]+b[i] \le l$ 如果成立， 那么就代表这种情况下是可以选出$j+1$ 项的，于是$ans = max(ans,j+1)$

在枚举完j之后，我们让dp[i][1] = min(dp[i-1][1],a[i]-b[i]) , 表示在加入新的第$i$项后，从这i项中选择1项最小是多少。

我们还要考虑只选择一个数的情况，即当$a[i] \le l$ 成立时，$ans = max(ans,1)$

最终输出ans即可。

代码

思路一

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
struct Node{
    int a,b;
    friend bool operator<(Node n1,Node n2){
        return n1.b < n2.b;
    }
};

void solve(){
    int n,x;
    cin>>n>>x;
    vector<Node> vec(n+5);
    rep(i,1,n){
        cin>>vec[i].a>>vec[i].b;
    }
    int ans = 0;
    sort(vec.begin()+1,vec.begin()+1+n);
    for(int i = 1;i<=n;i++){
        priority_queue<int> pq;
        int sum = 0;
        for(int j = i;j<=n;j++){
            pq.push(vec[j].a);sum+=vec[j].a;
            while(pq.size() && vec[j].b-vec[i].b + sum > x){
                sum -= pq.top();
                pq.pop();
            }
            ans = max(ans,(int)pq.size());
        }
    }
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

**思路二**：jiangly的代码

//***jiangly's code ***
//https://codeforces.com/contest/1935/submission/249766518

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1E18;

void solve() {
    int n, l;
    std::cin >> n >> l;
    
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i] >> b[i];
    }
    
    int ans = 0;
    //构造一个p从0~n-1的顺序列，之后按照b数组从小到大排序，就得到了一个下标的映射
    std::vector<int> p(n); 
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](int i, int j) {
            return b[i] < b[j];
        });
    
    std::vector<i64> dp(n + 1, inf);
    // 这时候我们按照排好序的下标顺序作为i来访问a和b数组，就可以保证每次的i都是b[i]逐渐增大的
    for (auto i : p) {
        for (int j = n - 1; j >= 1; j--) {
            dp[j + 1] = std::min(dp[j + 1], dp[j] + a[i]);
            //或许等价于压缩前的dp[i][j+1] = min(d[i-1][j+1],dp[i-1][j]+a[i])
            if (dp[j] + a[i] + b[i] <= l) {
                ans = std::max(ans, j + 1);
            }
        }
        dp[1] = std::min(dp[1], 1LL * a[i] - b[i]);
        if (a[i] <= l) {
            ans = std::max(ans, 1);
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

D. Exam in MAC

题意

给出一个集合s 以及一个整数c ， 问有多少对undefinedx,y), 0\le x \le y \le c$满足$x+y$和$y-x$都不在集合$s$中 。

$0 \le s_1 < s_2 <...<s_n \le c , 1\le c \le 10^9$

思路

容斥题， 所有的undefinedx,y)$的组合数量为$\frac{(c+1)(c+2)}{2}$, 我们让这个数量减去$x+y \in s$以及$y-x \in s$的数量， 再加上同时有$x+y, y-x \in s$ 的数量即可。

先考虑$x+y \in s$ ，在我们选出一个$s_i$ 后， x可以在$[0,\lfloor \frac{s_i}{2}\rfloor]$ 中任选，这样总会有一个y，他可以保证$x \le y \& x+y = s_i$ 。即对于$s_i$ 的贡献为undefinedlfloor \frac{s_i}{2}\rfloor + 1$ 。

再考虑$y-x \in s$ ， 我们选出一个数$s_i$ 后， y则可以在$[s_i,c]$ 中任选，这样总会有一个x，保证$0\le x \& y -x = c$ 。即对于$s_i$ 的贡献为$c - s_i + 1$ 。

最后考虑对于undefinedx,y)$，$x+y, y-x$同时存在于s中， 我们假设$x+y = A, y-x = B$那么就有$x = \frac{B-A}{2} , y = \frac{A+B}{2}$，因为x和y都应该是整数，所以要求$A,B$同奇或同偶。于是我们每选出一组奇数对，或者一组偶数对，就可以为这一部分的答案贡献1。假设奇数数量和偶数数量分别为$odd, even$那么答案为$\frac{odd(odd-1)}{2} + \frac{even(even-1)}{2}$

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,c;
    cin>>n>>c;
    int ans = (c+1)*(c+2)/2;
    int odd ,even;odd = even = 0;
    for(int i = 1;i<=n;i++){
        int num;
        cin>>num; 
        ans -= num/2 + 1;
        ans -= (c - num + 1);
        if(num%2) odd ++;
        else even ++;
    }
    ans += odd*(odd+1)/2 + even*(even+1)/2;
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}