Codeforces Round 932 (Div. 2 ABCDE题) 视频讲解

A. Entertainment in MAC

Problem Statement

Congratulations, you have index.php/tags-41973.html" >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:

1. 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).
2. 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 longusing 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 pide 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 pision, or determine that it does not exist.

    † ^{\dagger} †A pision 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;}