codeforces round 932 div2(a,b,c)

本文主要是介绍codeforces round 932 div2(a,b,c)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

d题容斥出的人比c反悔贪心还多…打完蓝桥再补补数论吧
比赛连接

A

题目大意

每次询问给定字符串$s$和$n$次操作，$n$为不小于$2$的偶整数，每次操作可在以下两种任选其一

• 把$s$反转之后的结果接入$s$的后面
• 反转$s$

输出$n$次操作后的最小字典序字符串

思路

注意$n$是偶数且大于等于$2$，所以我们只需要判断$s$本身是否已经为最小字典序即可，若是，则可每次均反转，因为$n$是正偶数，所以必然最后输出原字符串。若不是，则先反转再插入反转序列，继续反转再反转即可

ACcode

#include<bits/stdc++.h>using namespace std;#define int long longvoid solve()
{int n;cin >> n;string str;cin >> str;int be = 0;int en = str.size() - 1;int flag = 2;while (be < en) {if (str[be] > str[en]) {flag = 1;break;}if (str[be] < str[en]) {flag = 2;break;}be++;en--;}if (flag == 1) {reverse(str.begin(), str.end());cout << str;reverse(str.begin(), str.end());cout << str << '\n';}else if (flag == 2) {cout << str << '\n';}
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

B

题目大意

给定长度$n$的数组$a$，请把$a$分为$k$段，每段$MEX$值相同，$k>1$，$MEX$值为不属于数组的最小非负整数

思路

注意到两个子段可以合成一个，所以只要能分成$k$个，无论有多少个子段，都能最终合成为$2$个。
所以我们从前后分别扫一遍，记录$MEX$值，最后对比输出即可，若没有则输出-1

ACcode

#include<bits/stdc++.h>using namespace std;#define int long longvoid solve()
{int n;cin >> n;vector<int>a(n + 3);vector<int>pre(n + 3), nex(n + 3);map<int, int>b;int now = 0;for (int i = 1;i <= n;i++) {cin >> a[i], b[a[i]]++;while (b[now] > 0)now++;pre[i] = now;}b.clear(), now = 0;for (int i = n;i > 0;i--) {b[a[i]]++;while (b[now] > 0)now++;nex[i] = now;}for (int i = 1;i < n;i++) {if (pre[i] == nex[i + 1]) {cout << 2 << '\n';cout << 1 << ' ' << i << '\n';cout << i + 1 << ' ' << n << '\n';return;}}cout << -1 << '\n';
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

C

题目大意

有$n$条消息，每条由一个二元组$(a,b)$描述，你需要找到最大的$k$个并重新排序，使得这$k$个的$a$的和加上相邻$b$的差的绝对值小于$l$，输出$k$

思路

用大顶堆实现反悔贪心
读题发现，排序只跟$b$有关，所以先按$b$由小到大排序
$n$个元素每个作为开始元素，遍历第$i+1$到第$n$个，若满足$<=l$，贪心的入堆
后面加判断，若当前元素$a$小于堆顶且满足条件，扔掉堆顶，当前元素入堆，实现反悔

ACcode

#include<bits/stdc++.h>using namespace std;#define int long long
using PII = pair<int, int>;bool cmp(PII a, PII b) {return a.second < b.second;
}void solve()
{int n, l;cin >> n >> l;vector<PII>a(n);for (int i = 0;i < n;i++)cin >> a[i].first >> a[i].second;sort(a.begin(), a.end(), cmp);int ans = 0;for (int i = 0;i < n;i++) {priority_queue<int>q;if (a[i].first > l)continue;int sum = a[i].first;for (int j = i + 1;j < n;j++) {if (sum + a[j].first + a[j].second - a[i].second <= l) {sum += a[j].first;q.push(a[j].first);continue;}if (!q.empty()) {if (q.top() > a[j].first && sum - q.top() + a[j].first + a[j].second - a[i].second <= l) {sum -= q.top();q.pop();q.push(a[j].first);sum += a[j].first;}}}ans = max(ans, (int)q.size() + 1);}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

这篇关于codeforces round 932 div2(a,b,c)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---