Codeforces Round 932(div2)||ABD

A-Entertainment in MAC

题意

可以对一个字符串进行两种操作：

1. 将字符串反转
2. 将该字符串反转后接在原串的后面。

可以进行任意次上述操作，获得字典序最小的字符串。

数据范围

$t(1\le t\le 500)$

$n(2\le n\le 10^9)$​

$s(1\le |s|\le 100)$

思路

对比反转前后的字符串字典序大小，再决定是操作1还是操作2

参考代码

void solve() {ll n;cin >> n;string s;cin >> s;string t = s;reverse(t.begin(), t.end());if (s > t) {cout << t << s << endl;}else {cout << s << endl;}
}

B-Informatics in MAC

题意

$MEX$：不属于该数组的最小非负整数。

对一个数组分成$k$个子段，要求每段的$MEX$都等于相同的数。

找到这样的子段分法，或者报告不存在合法的分法。

数据范围

$t(1\le t\le 10^4)$

$n(2\le n\le 10^5)$​

$a_i(0\le a_i<n)$

思路

假设$MEX=2$，则分成$k$段的方式为前$k-1$段只要都出现过$0,1$就进行分段，最后一段保证含$0,1$和达到第$n$个数。

确定$MEX$：遍历数组$a$，找到最小的没有出现过的数（该数不大于$n$），该数即为$MEX$。

参考代码

// MEX:不属于该数组的最小非负整数void solve() {ll n;cin >> n;vector<ll>a(n + 1);vector<bool>ck(n + 1, false);for (int i = 1;i <= n;i++) {ll x;cin >> x;a[i] = x;ck[x] = true;}bool f = false;int y = -1;for (int i = 0;i < n;i++) {if (ck[i] == false) {y = i;f = true;break;}}if (!f) {cout << -1 << endl;return;}// MEX=y// cout << y << endl;if (y == 0) {cout << n << endl;for (int i = 1;i <= n;i++) {cout << i << ' ' << i << endl;}return;}int p = 1;int cnt = 0;vector<pair<int, int>>ans;vector<bool>hs(y, false);vector<bool>hsf(y, false);for (int i = 1;i <= n;i++) {if (a[i] < y && !hs[a[i]]) {hs[a[i]] = true;cnt++;}if (cnt == y) {ans.push_back({ p, i });p = i + 1;cnt = 0;// 会不会Tlehs = hsf;}}if (ans.size() == 1) {cout << -1 << endl;return;}cout << ans.size() << endl;for (int i = 0;i < ans.size();i++) {if (i != ans.size() - 1)cout << ans[i].first << " " << ans[i].second << endl;else {cout << ans[i].first << " " << n << endl;}}}

D-Exam in MAC

题意

有一个集合$s$。

找到满足$0\le x\le y\le c$且$x+y$和$y-x$均不包含在集合$s$中的整数对$(x,y)$的个数。

数据范围

$t(1\le t\le 2\times 10^4)$

$n(1\le n\le 3\times 10^5)$​

$c(1\le c\le 10^9)$

思路

容斥。

合格的整数对=满足$x+y\in s$+满足$y-x\in s$-既满足$x+y\in s$又满足$y-x\in s$。

参考代码

void solve() {ll n, c;cin >> n >> c;ll tot = (c + 1) * (c + 2) / 2;ll cnt0 = 0, cnt1 = 0;for (ll i = 0;i < n;i++) {ll x;cin >> x;tot -= x / 2 + 1;tot -= c + 1 - x;if (x & 1)cnt1++;else cnt0++;}tot += (cnt0 + 1) * cnt0 / 2 + cnt1 * (cnt1 + 1) / 2;cout << tot << endl;
}