2023 CCPC 桂林站 B G I K M

写在前面

每一次 i++ 都是变强的步伐，未来的 ++i 也是为了迎接更多挑战的准备！

---

G. Hard Brackets Problem

time limit per test: 1 second memory limit per test: 1024 megabytes input: standard input outputL: standard output

Putata is coding with his favorite IDE. The best part of this IDE is the parentheses completion function. The function works as follows: assume that $S|T$ is currently displayed on the screen, where | is the current position of the cursor and $S$ and $T$ are two (possibly empty) strings.

• Putata enters left parenthesis ‘(’, $S(|)T$ will be displayed on the screen, where | is the new position of the cursor.

• Putata enters right parenthesis ‘)’. If $T=)T^{\prime }$, which means that $T$ begins with a right parenthesis, then the string will not change, and the cursor will move to the right of the next character, $S)|T^{\prime }$ will be displayed on the screen, otherwise $S)|T$ will be displayed on the screen.

Putata worked very hard last night and when he wakes up in the morning, he only remembers the code saved on his computer and that he only entered several parentheses. Help him find the parenthesis sequence he typed in order or tell him it is impossible to type this string by only entering parentheses.

Input

The first line contains an integer $t$ ($1\le t\le 10^6$), denoting the number of test cases.

For each test case, the only line contains one string $S$ ($1\le |S|\le 10^6$). It is guaranteed that $S$ only consists of parentheses, ‘(’ and ‘)’.

It is guaranteed that the sum of $|S|$ over all testcases does not exceed $10^6$.

Output

For each test case, if it is possible to type the string by entering parentheses, output one string in one line, denoting the answer. Otherwise, output “impossible” in one line. If there are multiple answers, you can output any of them.

Please notice that you don’t have to minimize the length of the answer. Your answer should only contain parentheses and the length of your answer should be no greater than the input string for each test case if the answer exists.

Example
input

3
((()))
(
)))()
1
2
3
4

output

(((
impossible
)))(
1
2
3

Tutorial

括号匹配问题，可以参考好串

但本题右括号 ) 可以比左括号 ( 多，如果 ( 比 ) 多，则输出 $impossible$，否则直接输出全部字符串

Solution

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

void solve() {
    string s;
    cin >> s;
    int cnt = 0;
    for (char c : s) {
        if (c == '(') {
            cnt++;
        } else {
            cnt = max(cnt - 1, 0ll);
        }
    }
    cout << (cnt ? "impossible" : s) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    int Test; cin >> Test; while (Test--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Bonus

如果最后要求输出最短串，那么在判断完是否可能之后，如何处理最短串

---

M. Flipping Cards

time limit per test: 2.5 second memory limit per test: 1024 megabytes input: standard input outputL: standard output

$n$ cards are placed in a row, where $n$ is an odd number. Each card has numbers written on both sides. On the $i$-th card, $a_i$ is facing up and $b_i$ is facing down.

Grammy wants to maximize the median of all the numbers that are facing up. In order to achieve this, she can do the following operation at most once.

• Choose an interval $[l,r]$ and flip all the cards in the interval. After flipping the cards, $b_i$ will be facing up and $a_i$ will be facing down for $i\in [l,r]$.

Please help Grammy to calculate the median of all the numbers that are facing up under her optimal strategy.

Recall that the median of a sequence of numbers is the $\frac{n+1}{2}$-th largest number in the sequence.

Input

The first line contains two integers $n$ ($1\le n<3\cdot 10^5,n\mathrm{mod}2=1$), denoting the number of cards.

Each of the next $n$ lines contains $2$ integers $a_i,b_i$ ($1\le a_i,b_i\le 10^9$), denoting the initial number that is facing up and the initial number that is facing down for each card.

Output

Output one integer, denoting the median of all the numbers that are facing up under Grammy’s optimal strategy.

Example
input1

5
3 6
5 2
4 7
6 4
2 8
1
2
3
4
5
6

output1

6
1

input2

1
2 1
1
2

output2

2
1

Tutorial

二分答案最终的中位数：

• 如果 $a_i<mid$，而 $b_i\ge mid$，那么交换后会贡献 1
• 如果 $a_i$ 和 $b_i$ 同时满足 $<$ 或 $>=mid$，那么交换后会贡献 0
• 如果 $a_i\ge mid$，而 $b_i<mid$，那么交换后会贡献 -1
• 最后只需要判断 初始贡献 $+$ 反转后的贡献 $\ge$ (n + 1) / 2

Solution

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define endl '\n'
#define int long long
#define PII pair<int, int>

void solve() {
    int n, left = 1, right = 1;
    cin >> n;
    vector<PII> a(n);
    for (PII &ai : a) {
        cin >> ai.ff >> ai.ss;
        right = max({right, ai.ff + 1, ai.ss + 1});
    }

    function<bool(int)> check = [&](int mid) -> bool {
        int ans = 0, cnt = 0, cur = 0;
        vector<int> b(n);
        for (int i = 0; i < n; ++i) {
            b[i] = (a[i].ss >= mid) - (a[i].ff >= mid);
        }
        for (int i = 0; i < n; ++i) {
            if (a[i].ff >= mid) {
                cnt++;
            }
            cur = max(b[i], cur + b[i]);
            ans = max(ans, cur);
        }
        return ans + cnt >= (n + 1) / 2;
    };
    
    while (left + 1 < right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }
    cout << left << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

---

K. Randias Permutation Task

time limit per test: 2 second memory limit per test: 1024 megabytes input: standard input outputL: standard output

For two permutations $A$ and $B$ of length $n$, Randias can generate a permutation $C$ of length $n$ as $C=A\circ B$ in this way: for each $1\le i\le n$, $C[i]=A[B[i]]$.

Now he is given $m$ permutations $A_1,A_2,\dots ,A_m$, each of them is of length $n$. He wants to choose a non-empty set of indices $i_1,i_2,\dots ,i_k$ ($1\le k\le m$,$1\le i_1<i_2\cdots <i_k\le m$), and calculate $C=(((A_{i_1}\circ A_{i_2})\circ A_{i_3})\circ A_{i_4})\cdots \circ A_{i_k}$. Randias wants to know, how many possible permutations $C$ he can generate? Output the answer modulo $10^9+7$.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array)

Input

The first line contains two positive integers $n,m$ ($1\le n\cdot m\le 180$), denoting the length of the permutation and the number of permutations.

The following $m$ lines, each line contains $n$ distinct integers, denoting one permutation.

Output

One single integer, denoting the number of possible permutations $C$ Randias can generate, modulo $10^9+7$.

Example
input1

5 4
1 2 3 4 5
5 1 3 4 2
3 4 1 5 2
5 2 4 1 3
1
2
3
4
5

output1

8
1

input2

2 1
2 1
1
2

output2

1
1

Tutorial

根据题意可知答案不超过 $min(2m,n!)\le 362880$，所以可以直接利用 STL 直接暴力匹配搜索

每次计算出排列的集合后，在枚举下一次排列时，只需对当前排列和已有排列进行选还是不选对判断即可

时间复杂度 $O(nm\cdot min(2m,n!)\cdot log(min(2m,n!)))$

Solution

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    map<vector<int>, int> mp;
    vector<int> tmp(n + 1);
    vector nums(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> nums[i][j];
        }
    }
    for (int i = 1; i <= m; ++i) {
        map<vector<int>, int> mid(mp);
        mid[nums[i]] = 1;
        for (auto [a, _] : mp) {
            for (int j = 1; j <= n; ++j) {
                tmp[j] = a[nums[i][j]];
            }
            mid[tmp] = 1;
        }
        mp = mid;
    }
    cout << mp.size() << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

I. Barkley II

time limit per test: 2 second memory limit per test: 1024 megabytes input: standard input outputL: standard output

Prof.Hui is the coach of Pigeland University Programming Team. There are $n$ students in his team. All algorithms are numbered by Prof.Hui in ascending order of difficulty, from $1$ to $m$. Which means that algorithm $1$ is the easiest algorithm, while algorithm $m$ is the hardest. The $i$-th student masters the $a_i$-th easiest algorithm.

Now Prof.Hui wants to choose a team satisfying the following conditions:

• The index of the students in the team forms an interval. Which means that there exists two integers $l,r$ such that $1\le l\le r\le n$ and student $x$ is in the team if and only if $l\le x\le r$.

• The rating of the team is maximized. The more algorithms the team mastered, the stronger they are, but if they cannot solve a hard problem in one contest, they will feel more disappointed. So the rating of the team is the number of different algorithms that the students in the team mastered minus the index of the easiest algorithm that no one in the team mastered. If the students in the team masters all the algorithms, the index of the easiest algorithm that no student in the team mastered is considered to be $m+1$. For example, if $m=5$ and there are $6$ students in the team, mastering algorithm $2,5,4,4,1,1$ respectively, the rating of the team is $4-3=1$.

Please help Prof.Hui to find the maximum rating of a team.

Input

The first line contains an integer $t$ ($1\le t\le 5\cdot 10^5$), denoting the number of test cases.

For each test case, the first line contains two integer $n,m$ ($1\le n,m\le 5\cdot 10^5$), denoting the number of students and the number of algorithms.

The second line contains $n$ integers, the $i$-th integer $a_i$ ($1\le a_i\le m$) denoting the number of algorithm the $i$-th student masters.

It is guaranteed that the sum of $n$ over all testcases does not exceed $5\cdot 10^5$. Please notice that there is no limit on sum of $m$.

Output

For each test case, output one integer in one line, denoting the answer.

Example
input

2
5 4
1 2 2 3 4
5 10000
5 2 3 4 1
1
2
3
4
5

output

2
3
1
2

Tutorial

我们可以对 $MEX$ 枚举 $1$ ~ $(n-1)$，考虑以 $MEX$ 为分界线把区间分割成一个一个的子区间，此时问题就转换成了：给定一个区间，求这个区间内数字的种类数

对于每个子区间，不包含当前枚举到的 $MEX$ 的最长连续区间，就是 $MEX$ 所分割的区间

然后计算每一段子区间的价值，即区间不同元素的个数 $-$ 当前枚举到的 $MEX$，

在计算时，可以先预处理，按照右端点排序所有区间，然后顺序枚举所有区间 $i$ ，同时将新下标 $j$ 更新到树状数组，因为一个数只有最后一次出现的位置对答案有贡献，所以与此同时删除之前出现的重复数字的对应下表

在区间更新答案后，不重复元素的个数就是 query(r) - query(l - 1)

Solution

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define lowbit(x) x & -x

struct section {
    int left;   // 区间左边界
    int right;  // 区间右边界
    int mex;    // 区间的 MEX
};

vector<int> sum(500010), pre(500010);

void solve() {
    int n, m, ans = -1;
    cin >> n >> m;
    vector<int> a(n + 2);
    vector<section> sections;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    function<int(int)> query = [&](int x) -> int {
        int ans = 0;
        for (; x; x -= lowbit(x)) {
            ans += sum[x];
        }
        return ans;
    };

    function<void(int, int)> update = [&](int idx, int x) {
        for (; idx <= n + 10; idx += lowbit(idx)) {
            sum[idx] += x;
        }
    };

    for (int i = 1; i <= n; ++i) { // 记录区间
        if (a[i] <= n + 1 and pre[a[i]] + 1 < i) {
            sections.push_back({pre[a[i]] + 1, i - 1, a[i]});
        }
        pre[a[i]] = i;
    }

    for (int i = 1; i <= n + 1; ++i) {
        if (pre[i] + 1 <= n) { // 还有最后一次出现的位置 到 末尾
            sections.push_back({pre[i] + 1, n, i});
        }
    }

    // 直接排序后遍历即可
    ranges::sort(sections.begin(), sections.end(), [](section a, section b) {
        return a.right < b.right;
    });

    for (int i = 1; i <= n + 1; ++i) {
        pre[a[i]] = 0;
        sum[i] = 0;
    }
    for (int i = 0, j = 0; i < sections.size(); ++i) {
        while (j < sections[i].right) {
            ++j;
            // 一个数只有最后一次出现的位置对答案有贡献
            if (pre[a[j]]) { // 如果出现过就设之前的位置无效
                update(pre[a[j]], -1);
            }
            update(j, 1);
            pre[a[j]] = j;
        }
        ans = max(ans, query(sections[i].right) - query(sections[i].left - 1) - sections[i].mex);
    }
    cout << ans << endl;

    for (int i = 1; i <= n + 1; ++i) {
        pre[a[i]] = 0;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    int Test; cin >> Test; while (Test--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

---

B. The Game

time limit per test: 2 second memory limit per test: 1024 megabytes input: standard input outputL: standard output

Randias is playing a game. He is given two multisets (a set which can contain duplicate elements) $A$ and $B$, consists of $n$ and $m$ integers $A_1,A_2,\dots ,A_n$, $B_1,B_2.\dots ,B_m$ repsectively. He can perform the following operation any number of times:

• Choose one element $x$ where $x\in A$, change $x$ to $x+1$. Then remove the minimal element in $A$, Note that if there are more than one minimal element in $A$, we only remove one of them.

For example, if A = { 4 , 4 , 5 , 5 , 6 } A=\{4,4,5,5,6\} A={4,4,5,5,6} and we choose $x=5$, $A$ will become { 4 , 5 , 6 , 6 } \{4,5,6,6\} {4,5,6,6} after one operation.

He wants to know whether he can make $A=B$ after several (possibly zero) operations? If he can make it, please help him to determine which operations need to be performed.

Two multisets are consider to be the same, if for all $x$, the number of occurrence of $x$ in $A$ and $B$ are the same.

Input

The first line contains $t$ ($1\le t\le 5\cdot 10^4$), representing the number of testcases.

For each testcase, the first line contains two integers $n,m$ ($1\le m\le n\le 3\cdot 10^5$), representing the size of two multisets.

The following line contains $n$ integers $A_1,A_2,\dots ,A_n$ ($1\le A_i\le 10^9$).

The following line contains $m$ integers $B_1,B_2,\dots ,B_m$ ($1\le B_i\le 10^9$).

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $3\cdot 10^5$.

Output

For each test case, if Randias cannot let $A=B$, output “$-1$”.

Otherwise, on the first line, output the number of operations $L$ ($0\le L\le n$) Randias needs to make.

The following line contains $L$ integers $x_1,x_2,\dots ,x_L$, representing the integer $x$ each operation choose. You must ensure that $x\in A$ before each operation.

If there are multiple solutions, output any.

Example
input

6
5 3
1 2 2 3 3
2 3 4
4 2
1 2 2 4
2 4
5 2
2 3 3 4 4
5 5
6 1
1 1 1 1 1 1
4
4 2
1 1 1 2
2 2
4 1
1 1 1 1
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

output

2
1 3 
-1
3
2 4 4 
5
1 1 1 2 3 
2
1 1 
-1
1
2
3
4
5
6
7
8
9
10

Tutorial

将 $A,B$ 输入后，为了方便处理可以先对它们进行升序排序处理

由题意可知，操作次数总是 $n-m$ 次，每次操作都不会让 $A$ 中最大的 $m$ 个数变小，所以需要满足 $A_{n-(m-1)}\le b_i$，且 $\sum B_i-A_{n-m+i}\le n-m$

对于 $\sum B_i-A_{n-m+i}<n-m$ 的情况，需要构造出一些“无效”操作，只需要贪心地去最小值即可

我们可以用两个最小对，分别维护 $A$ 的前 $m$ 大的元素，以及 $A$ 的其他元素，模拟 $n-m-\sum B_i-A_{n-m+i}$ 次，直到 $\sum B_i-A_{n-m+i}=n-m$

在模拟过程中需要考虑是否会造成无解情况

Solution

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define endl '\n'
#define int long long
#define PII pair<int, int>

void solve() {
    int n, m, op, cnt = 0; // op 是必须要删除的元素个数，cnt 为总差值
    bool flag = false;
    cin >> n >> m;
    op = n - m;
    vector<PII> a(n); // first 为该位置的值，second 为该位置对应的 B 元素
    vector<int> b(m), ans;
    for (PII &ai : a) {
        cin >> ai.ff;
    }
    for (int &bi : b) {
        cin >> bi;
    }
    ranges::sort(a);
    ranges::sort(b);

    for (int i = op; i < n; ++i) {
        if (a[i].ff > b[i - op]) {
            flag = true;
            break;
        }
        a[i].ss = b[i - op];
        cnt += b[i - op] - a[i].ff;
        if (cnt > op) {
            flag = true;
            break;
        }
    }
    if (flag) {
        cout << -1 << endl;
        return;
    }

    priority_queue<PII, vector<PII>, greater<PII>> q1, q2;
    for (int i = 0; i < op; ++i) { // 不是最大的 m 个元素
        q2.emplace(a[i]);
    }
    for (int i = op; i < n; ++i) { // 最大的 m 个元素
        q1.emplace(a[i]);
    }

    while (cnt < op) { // 先把多余操作消耗掉
        if (q2.empty()) { // 没有多余的数删除了
            flag = true;
            break;
        }
        PII now = q2.top();
        q2.pop();
        ans.emplace_back(now.ff); // 操作的值
        ++now.ff;
        if (now.ff > q1.top().ff) { // 此时成为最大的 m 个数
            --cnt; // 更新差值
            PII cur = q1.top();
            q1.pop();
            if (now.ff > cur.ss) { // 超过了对应的 B 元素
                flag = true;
                break;
            }
            // 二者交换
            now.ss = cur.ss;
            q1.emplace(now);
            q2.emplace(cur);
        } else { // 否则插回去
            q2.emplace(now);
        }
        q2.pop(); // 删除最小元素
        --op;
    }
    if (flag or cnt > op) {
        cout << -1 << endl;
        return;
    }

    while (q1.size()) { // 把剩余操作数用干净
        PII now = q1.top();
        q1.pop();
        int diff = now.ss - now.ff;
        while (diff--) {
            ans.emplace_back(now.ff);
            ++now.ff;
        }
    }

    n = ans.size();
    cout << n << endl;
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " \n"[i == n - 1];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    int Test; cin >> Test; while (Test--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

写在后面

对于一个大三老小白，这场属于我的第一次也是最后一次XCPC现场赛打得很不尽人意，但这趟桂林之旅对我来说仍是一次意义非凡的旅程。
补题还在继续，希望有朝一日能为这次遗憾留下一个完美的句号…