Codeforces Round 932 (Div. 2 ABCDE题) 视频讲解
A. Entertainment in MAC
Problem Statement
Congratulations, you have index.php/tags-41973.html" class="superseo">been accepted to the Master’s Assistance Center! However, you were extremely bored in class and got tired of doing nothing, so you came up with a game for yourself.
You are given a string s s s and an even integer n n n. There are two types of operations that you can apply to it:
- Add the reversed string s s s to the end of the string s s s (for example, if $s = $ cpm, then after applying the operation $s = $ cpmmpc).
- Reverse the current string s s s (for example, if $s = $ cpm, then after applying the operation $s = $ mpc).
It is required to determine the lexicographically smallest † ^{\dagger} † string that can be obtained after applying exactly n n n operations. Note that you can apply operations of different types in any order, but you must apply exactly n n n operations in total.
† ^{\dagger} †A string a a a is lexicographically smaller than a string b b b if and only if one of the following holds:
- a a a is a prefix of b b b, but a ≠ b a \ne b a=b;
- in the first position where
a
a
a and
b
b
b differ, the string
a
a
a has a letter that appears earlier in the alphabet than the corresponding letter in
b
b
b.
Input
Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 500 1 \leq t \leq 500 1≤t≤500) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single even integer n n n ( 2 ≤ n ≤ 1 0 9 2 \leq n \leq 10^9 2≤n≤109) — the number of operations applied to the string s s s.
The second line of each test case contains a single string s s s ( 1 ≤ ∣ s ∣ ≤ 100 1 \leq |s| \leq 100 1≤∣s∣≤100), consisting of lowercase English letters, — the string to which the operations are applied.
Output
For each test case, output a single line — the lexicographically smallest string that can be obtained after applying exactly n n n operations.
Example
Example
input 5 4 cpm 2 grib 10 kupitimilablodarbuz 1000000000 capybara 6 abacaba output cpm birggrib kupitimilablodarbuz arabypaccapybara abacaba Note
In the first test case, you can apply the operation of the second type (i.e., reverse the string s s s) 4 4 4 times. Then the string s s s will remain equal to cpm.
In the second test case, you can do the following:
- Apply the operation of the second type, after which s s s will become equal to birg.
- Apply operation of the first type (i.e., add the reversed string
s
s
s to the end of the string
s
s
s), after which
s
s
s will become equal to birggrib.
Solution
具体见文后视频。
Code
#include #define int long long using namespace std; typedef pair PII; typedef long long LL; void solve() { int n; string s; cin >> n >> s; int l = 0, r = s.size() - 1; while (l r) cout string t = s; reverse(t.begin(), t.end()); t += s; cout cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int Data; cin Data; while (Data --) solve(); return 0; }hr / h2B. Informatics in MAC/h2 h3Problem Statement/h3 pIn the Master’s Assistance Center, Nyam-Nyam was given a homework assignment in informatics./p pThere is an array a a a of length n n n, and you want to divide it into k 1 k 1 k>1 subsegments † ^{\dagger} † in such a way that the MEX ‡ \operatorname{MEX} ^{\ddagger} MEX‡ on each subsegment is equal to the same integer.Help Nyam-Nyam find any suitable division, or determine that it does not exist.
† ^{\dagger} †A division of an array into k k k subsegments is defined as k k k pairs of integers ( l 1 , r 1 ) , ( l 2 , r 2 ) , … , ( l k , r k ) (l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k) (l1,r1),(l2,r2),…,(lk,rk) such that l i ≤ r i l_i \le r_i li≤ri and for each 1 ≤ j ≤ k − 1 1 \le j \le k - 1 1≤j≤k−1, l j + 1 = r j + 1 l_{j + 1} = r_j + 1 lj+1=rj+1, and also l 1 = 1 l_1 = 1 l1=1 and r k = n r_k = n rk=n. These pairs represent the subsegments themselves.
‡ MEX ^{\ddagger}\operatorname{MEX} ‡MEX of an array is the smallest non-negative integer that does not belong to the array.
For example:
- MEX \operatorname{MEX} MEX of the array [ 2 , 2 , 1 ] [2, 2, 1] [2,2,1] is 0 0 0, because 0 0 0 does not belong to the array.
- MEX \operatorname{MEX} MEX of the array [ 3 , 1 , 0 , 1 ] [3, 1, 0, 1] [3,1,0,1] is 2 2 2, because 0 0 0 and 1 1 1 belong to the array, but 2 2 2 does not.
-
MEX
\operatorname{MEX}
MEX of the array
[
0
,
3
,
1
,
2
]
[0, 3, 1, 2]
[0,3,1,2] is
4
4
4, because
0
0
0,
1
1
1,
2
2
2, and
3
3
3 belong to the array, but
4
4
4 does not.
Input
Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n n n ( 2 ≤ n ≤ 1 0 5 2 \le n \le 10^5 2≤n≤105) — the length of the array a a a.
The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an ( 0 ≤ a i n; std::vector a(n), vis(n, 0); for (int i = 0; i > a[i], vis[a[i]] = 1; int mex = 0; for (int i = 0; i 1) { cout cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int Data; cin Data; while (Data --) solve(); return 0; } return a.second mes[i].second; sort(mes + 1, mes + 1 + n, cmp); for (int i = 0; i for (int j = i; j = 2; j --) { f[i][j] = g[j - 1] + mes[i].first + mes[i].second; if (g[j] f[i][j] - mes[i].second) g[j] = f[i][j] - mes[i].second, p[j] = i; } f[i][1] = mes[i].first; if (f[i][1] - mes[i].second > y[i]; while (bit[i] >= 0 && (x[i] >> bit[i] & 1) == (y[i] >> bit[i] & 1)) bit[i] --; bit[i] ++; for (int j = bit[i]; j > j & 1); x[i] &= ((1 cnt[i] = cnt[i - 1]; for (int j = 30; j = 0; j --) cnt[i][j] += (y[i - 1] j & 1), vis[i][j] += vis[i - 1][j]; } cin >> q; while (q --) { int l, r; cin >> l >> r; int res = 0, flg = 1; for (int i = 30; i >= 0; i --) if (vis[r][i] - vis[l - 1][i] > 0) res += (1 = 0; i --) { // if (l == 3 && r == 4) cout if (cnt[r][i] - cnt[l - 1][i] 0) { res |= ((1 if (cnt[r][i] - cnt[l - 1][i] 1) { res |= ((1 cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int Data; cin Data; while (Data --) solve(); return 0; }