A. Two Friends
Problem Statement
Monocarp wants to throw a party. He has n n n friends, and he wants to have at least 2 2 2 of them at his party.
The i i i-th friend’s best friend is p i p_i pi. All p i p_i pi are distinct, and for every i ∈ [ 1 , n ] i \in [1, n] i∈[1,n], p i ≠ i p_i \ne i pi=i.
Monocarp can send invitations to friends. The i i i-th friend comes to the party if both the i i i-th friend and the p i p_i pi-th friend receive an invitation (note that the p i p_i pi-th friend doesn’t have to actually come to the party). Each invitation is sent to exactly one of the friends.
For example, if p = [ 3 , 1 , 2 , 5 , 4 ] p = [3, 1, 2, 5, 4] p=[3,1,2,5,4], and Monocarp sends invitations to the friends [ 1 , 2 , 4 , 5 ] [1, 2, 4, 5] [1,2,4,5], then the friends [ 2 , 4 , 5 ] [2, 4, 5] [2,4,5] will come to the party. The friend 1 1 1 won’t come since his best friend didn’t receive an invitation; the friend 3 3 3 won’t come since he didn’t receive an invitation.
Calculate the minimum number of invitations Monocarp has to send so that at least 2 2 2 friends come to the party.
Input
The first line contains one integer t t t ( 1 ≤ t ≤ 5000 1 \le t \le 5000 1≤t≤5000) — the number of test cases.
Each test case consists of two lines:
- the first line contains one integer n n n ( 2 ≤ n ≤ 50 2 \le n \le 50 2≤n≤50) — the number of friends;
- the second line contains n n n integers p 1 , p 2 , … , p n p_1, p_2, \dots, p_n p1,p2,…,pn ( 1 ≤ p i ≤ n 1 \le p_i \le n 1≤pi≤n; p i ≠ i p_i \ne i pi=i; all p i p_i pi are distinct).
Output
Print one integer — the minimum number of invitations Monocarp has to send.
Example
Example
| input |
|---|
| 3 |
| 5 |
| 3 1 2 5 4 |
| 4 |
| 2 3 4 1 |
| 2 |
| 2 1 |
| output |
|---|
| 2 |
| 3 |
| 2 |
Note
In the first testcase, Monocarp can send invitations to friends 4 4 4 and 5 5 5. Both of them will come to the party since they are each other’s best friends, and both of them have invitations.
In the second testcase, Monocarp can send invitations to friends 1 , 2 1, 2 1,2 and 3 3 3, for example. Then friends 1 1 1 and 2 2 2 will attend: friend 1 1 1 and his best friend 2 2 2 have invitations, friend 2 2 2 and his best friend 3 3 3 have invitations. Friend 3 3 3 won’t attend since his friend 4 4 4 doesn’t have an invitation. It’s impossible to send invitations to fewer than 3 3 3 friends in such a way that at least 2 2 2 come.
In the third testcase, Monocarp can send invitations to both friends 1 1 1 and 2 2 2, and both of them will attend.
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
void solve() {
int n;
cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 1; i <= n; i ++)
if (i == a[a[i]]) {
cout << 2 << endl;
return;
}
cout << 3 << endl;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int dt;
cin >> dt;
while (dt --)
solve();
return 0;
}
B. Shifts and Sorting
Problem Statement
Let’s define a cyclic shift of some string s s s as a transformation from s 1 s 2 … s n − 1 s n s_1 s_2 \dots s_{n-1} s_{n} s1s2…sn−1sn into s n s 1 s 2 … s n − 1 s_{n} s_1 s_2 \dots s_{n-1} sns1s2…sn−1. In other words, you take one last character s n s_n sn and place it before the first character while moving all other characters to the right.
You are given a binary string s s s (a string consisting of only 0-s and/or 1-s).
In one operation, you can choose any substring s l s l + 1 … s r s_l s_{l+1} \dots s_r slsl+1…sr ( 1 ≤ l < r ≤ ∣ s ∣ 1 \le l < r \le |s| 1≤l<r≤∣s∣) and cyclically shift it. The cost of such operation is equal to r − l + 1 r - l + 1 r−l+1 (or the length of the chosen substring).
You can perform the given operation any number of times. What is the minimum total cost to make s s s sorted in non-descending order?
Input
The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
The first and only line of each test case contains a binary string s s s ( 2 ≤ ∣ s ∣ ≤ 2 ⋅ 1 0 5 2 \le |s| \le 2 \cdot 10^5 2≤∣s∣≤2⋅105; s i ∈ s_i \in si∈ {0, 1}) — the string you need to sort.
Additional constraint on the input: the sum of lengths of strings over all test cases doesn’t exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
For each test case, print the single integer — the minimum total cost to make string sorted using operation above any number of times.
Example
Example
| input |
|---|
| 5 |
| 10 |
| 0000 |
| 11000 |
| 101011 |
| 01101001 |
| output |
|---|
| 2 |
| 0 |
| 9 |
| 5 |
| 11 |
Note
In the first test case, you can choose the whole string and perform a cyclic shift: 10 → \rightarrow → 01. The length of the substring is 2 2 2, so the cost is 2 2 2.
In the second test case, the string is already sorted, so you don’t need to perform any operations.
In the third test case, one of the optimal strategies is the next:
- choose substring [ 1 , 3 ] [1, 3] [1,3]: 11000 → \rightarrow → 01100;
- choose substring [ 2 , 4 ] [2, 4] [2,4]: 01100 → \rightarrow → 00110;
- choose substring [ 3 , 5 ] [3, 5] [3,5]: 00110 → \rightarrow → 00011.
The total cost is 3 + 3 + 3 = 9 3 + 3 + 3 = 9 3+3+3=9.
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
void solve() {
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
int tot = 0, res = 0;
for (int i = 1; i <= n; i ++)
if (s[i] == '1')
tot ++;
else {
if (!tot) continue;
res += tot + 1;
}
cout << res << endl;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int dt;
cin >> dt;
while (dt --)
solve();
return 0;
}
C. Minimizing the Sum
Problem Statement
You are given an integer array a a a of length n n n.
You can perform the following operation: choose an element of the array and replace it with any of its neighbor’s value.
For example, if a = [ 3 , 1 , 2 ] a=[3, 1, 2] a=[3,1,2], you can get one of the arrays [ 3 , 3 , 2 ] [3, 3, 2] [3,3,2], [ 3 , 2 , 2 ] [3, 2, 2] [3,2,2] and [ 1 , 1 , 2 ] [1, 1, 2] [1,1,2] using one operation, but not [ 2 , 1 , 2 [2, 1, 2 [2,1,2] or [ 3 , 4 , 2 ] [3, 4, 2] [3,4,2].
Your task is to calculate the minimum possible total sum of the array if you can perform the aforementioned operation at most k k k times.
Input
The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n n n and k k k ( 1 ≤ n ≤ 3 ⋅ 1 0 5 1 \le n \le 3 \cdot 10^5 1≤n≤3⋅105; 0 ≤ k ≤ 10 0 \le k \le 10 0≤k≤10).
The second line contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai≤109).
Additional constraint on the input: the sum of n n n over all test cases doesn’t exceed 3 ⋅ 1 0 5 3 \cdot 10^5 3⋅105.
Output
For each test case, print a single integer — the minimum possible total sum of the array if you can perform the aforementioned operation at most k k k times.
Example
| input |
|---|
| 4 |
| 3 1 |
| 3 1 2 |
| 1 3 |
| 5 |
| 4 2 |
| 2 2 1 3 |
| 6 3 |
| 4 1 2 2 4 3 |
| output |
|---|
| 4 |
| 5 |
| 5 |
| 10 |
Note
In the first example, one of the possible sequences of operations is the following: [ 3 , 1 , 2 ] → [ 1 , 1 , 2 [3, 1, 2] \rightarrow [1, 1, 2 [3,1,2]→[1,1,2].
In the second example, you do not need to apply the operation.
In the third example, one of the possible sequences of operations is the following: [ 2 , 2 , 1 , 3 ] → [ 2 , 1 , 1 , 3 ] → [ 2 , 1 , 1 , 1 ] [2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1] [2,2,1,3]→[2,1,1,3]→[2,1,1,1].
In the fourth example, one of the possible sequences of operations is the following: [ 4 , 1 , 2 , 2 , 4 , 3 ] → [ 1 , 1 , 2 , 2 , 4 , 3 ] → [ 1 , 1 , 1 , 2 , 4 , 3 ] → [ 1 , 1 , 1 , 2 , 2 , 3 ] [4, 1, 2, 2, 4, 3] \rightarrow [1, 1, 2, 2, 4, 3] \rightarrow [1, 1, 1, 2, 4, 3] \rightarrow [1, 1, 1, 2, 2, 3] [4,1,2,2,4,3]→[1,1,2,2,4,3]→[1,1,1,2,4,3]→[1,1,1,2,2,3].
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 3e5 + 20;
int n, k;
int a[N], f[N][20];
int mn[N][20];
void build() {
int m = log2(n) + 1;
for (int j = 0; j < m; j ++)
for (int i = 1; i <= n - (1ll << j) + 1; i ++)
if (!j) mn[i][j] = a[i] - a[i - 1];
else mn[i][j] = min(mn[i][j - 1], mn[i + (1ll << j - 1)][j - 1]);
}
int query(int l, int r) {
int t = log2(r - l + 1);
return min(mn[l][t], mn[r - (1ll << t) + 1][t]);
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> a[i], a[i] += a[i - 1];
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= k; j ++)
f[i][j] = -1e16;
build();
f[0][k] = 0;
for (int i = 1; i <= n; i ++)
for (int t = 0; t <= k; t ++) {
f[i][t] = f[i - 1][t];
for (int j = max(1ll, i - k); j <= i; j ++) {
if (t + (i - j) <= k)
f[i][t] = max(f[i][t], f[j - 1][t + (i - j)] + a[i] - a[j - 1] - query(j, i) * (i - j + 1));
}
}
int res = 0;
for (int i = 0; i <= k; i ++)
res = max(res, f[n][i]);
cout << a[n] - res << endl;
for (int i = 0; i <= n; i ++)
a[i] = 0;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int dt;
cin >> dt;
while (dt --)
solve();
return 0;
}
D. Shop Game
Problem Statement
Alice and Bob are playing a game in the shop. There are n n n items in the shop; each item has two parameters: a i a_i ai (item price for Alice) and b i b_i bi (item price for Bob).
Alice wants to choose a subset (possibly empty) of items and buy them. After that, Bob does the following:
- if Alice bought less than k k k items, Bob can take all of them for free;
- otherwise, he will take k k k items for free that Alice bought (Bob chooses which k k k items it will be), and for the rest of the chosen items, Bob will buy them from Alice and pay b i b_i bi for the i i i-th item.
Alice’s profit is equal to ∑ i ∈ S b i − ∑ j ∈ T a j \sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j i∈S∑bi−j∈T∑aj, where S S S is the set of items Bob buys from Alice, and T T T is the set of items Alice buys from the shop. In other words, Alice’s profit is the difference between the amount Bob pays her and the amount she spends buying the items.
Alice wants to maximize her profit, Bob wants to minimize Alice’s profit. Your task is to calculate Alice’s profit if both Alice and Bob act optimally.
Input
The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n n n and k k k ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1≤n≤2⋅105; 0 ≤ k ≤ n 0 \le k \le n 0≤k≤n).
The second line contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai≤109).
The third line contains n n n integers b 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1,b2,…,bn ( 1 ≤ b i ≤ 1 0 9 1 \le b_i \le 10^9 1≤bi≤109).
Additional constraint on the input: the sum of n n n over all test cases doesn’t exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
For each test case, print a single integer — Alice’s profit if both Alice and Bob act optimally.
Example
Example
| input |
|---|
| 4 |
| 2 0 |
| 2 1 |
| 1 2 |
| 4 1 |
| 1 2 1 4 |
| 3 3 2 3 |
| 4 2 |
| 2 1 1 1 |
| 4 2 3 2 |
| 6 2 |
| 1 3 4 9 1 3 |
| 7 6 8 10 6 8 |
| output |
|---|
| 1 |
| 1 |
| 0 |
| 7 |
Note
In the first test case, Alice should buy the 2 2 2-nd item and sell it to Bob, so her profit is 2 − 1 = 1 2 - 1 = 1 2−1=1.
In the second test case, Alice should buy the 1 1 1-st, the 2 2 2-nd and the 3 3 3-rd item; then Bob takes the 1 1 1-st item for free and pays for the 2 2 2-nd and the 3 3 3-rd item. Alice’s profit is ( 3 + 2 ) − ( 1 + 2 + 1 ) = 1 (3+2) - (1+2+1) = 1 (3+2)−(1+2+1)=1. Bob could take 2 2 2-nd item for free instead; this does not change Alice’s profit. Bob won’t take the 3 3 3-rd item for free, since this would lead to a profit of 2 2 2.
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2e5 + 10;
int n, k;
PII item[N], cpy[N];
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> item[i].fi;
for (int i = 1; i <= n; i ++)
cin >> item[i].se, cpy[i] = item[i];
if (!k) {
int res = 0;
for (int i = 1; i <= n; i ++)
res += max(0ll, item[i].se - item[i].fi);
cout << res << endl;
return;
}
sort(item + 1, item + 1 + n, [&](PII a, PII b) {
if (a.se == b.se) return a.fi > b.fi;
return a.se < b.se;
});
int tot = 0, res = 0, sum = 0;
for (int i = 1; i <= n; i ++)
sum += max(0ll, item[i].se - item[i].fi);
multiset<int> s;
for (int i = n; i >= n - k + 1; i --) {
s.insert(item[i].fi), tot += item[i].fi;
sum -= max(0ll, item[i].se - item[i].fi);
}
for (int i = n - k; i >= 0; i --) {
// cout << item[i].se << ":" << sum << " " << tot << "->" << sum - tot << endl;
res = max(res, sum - tot);
auto it = s.end();
it --;
if (*it > item[i].fi) {
tot -= *it, s.erase(it), s.insert(item[i].fi), tot += item[i].fi;
}
sum -= max(0ll, item[i].se - item[i].fi);
}
cout << res << endl;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int dt;
cin >> dt;
while (dt --)
solve();
return 0;
}
E. Unique Array
Problem Statement
You are given an integer array a a a of length n n n. A subarray of a a a is one of its contiguous subsequences (i. e. an array [ a l , a l + 1 , … , a r ] [a_l, a_{l+1}, \dots, a_r] [al,al+1,…,ar] for some integers l l l and r r r such that 1 ≤ l < r ≤ n 1 \le l < r \le n 1≤l<r≤n). Let’s call a subarray unique if there is an integer that occurs exactly once in the subarray.
You can perform the following operation any number of times (possibly zero): choose an element of the array and replace it with any integer.
Your task is to calculate the minimum number of aforementioned operation in order for all the subarrays of the array a a a to be unique.
Input
The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n n n ( 1 ≤ n ≤ 3 ⋅ 1 0 5 1 \le n \le 3 \cdot 10^5 1≤n≤3⋅105).
The second line contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( 1 ≤ a i ≤ n 1 \le a_i \le n 1≤ai≤n).
Additional constraint on the input: the sum of n n n over all test cases doesn’t exceed 3 ⋅ 1 0 5 3 \cdot 10^5 3⋅105.
Output
For each test case, print a single integer — the minimum number of aforementioned operation in order for all the subarrays of the array a a a to be unique.
Example
| input |
|---|
| 4 |
| 3 |
| 2 1 2 |
| 4 |
| 4 4 4 4 |
| 5 |
| 3 1 2 1 2 |
| 5 |
| 1 3 2 1 2 |
| output |
|---|
| 0 |
| 2 |
| 1 |
| 0 |
Note
In the second test case, you can replace the 1 1 1-st and the 3 3 3-rd element, for example, like this: [ 3 , 4 , 1 , 4 ] [3, 4, 1, 4] [3,4,1,4].
In the third test case, you can replace the 4 4 4-th element, for example, like this: [ 3 , 1 , 2 , 3 , 2 ] [3, 1, 2, 3, 2] [3,1,2,3,2].
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 3e5 + 10;
int n;
int a[N], l[N], r[N], p[N];
struct Segment {
int l, r;
int mn, len, lazy;
}tr[N << 2];
int q[N], hh, tt, f[N];
void pushup(int u) {
tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn), tr[u].len = 0;
if (tr[u << 1].mn == tr[u].mn) tr[u].len += tr[u << 1].len;
if (tr[u << 1 | 1].mn == tr[u].mn) tr[u].len += tr[u << 1 | 1].len;
}
void pushdown(int u) {
if (tr[u].lazy) {
tr[u << 1].mn += tr[u].lazy, tr[u << 1].lazy += tr[u].lazy;
tr[u << 1 | 1].mn += tr[u].lazy, tr[u << 1 | 1].lazy += tr[u].lazy;
tr[u].lazy = 0;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r}, tr[u].len = r - l + 1;
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].mn += d, tr[u].lazy += d;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (mid >= l) modify(u << 1, l, r, d);
if (mid < r) modify(u << 1 | 1, l, r, d);
pushup(u);
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
if (tr[u].mn > 0) return tr[u].r - tr[u].l + 1;
return tr[u].r - tr[u].l + 1 - tr[u].len;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1, res = 0;
if (mid >= l) res += query(u << 1, l, r);
if (mid < r) res += query(u << 1 | 1, l, r);
return res;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) p[i] = 0;
for (int i = 1; i <= n; i ++)
cin >> a[i], l[i] = p[a[i]] + 1, p[a[i]] = i;
for (int i = 1; i <= n; i ++) p[i] = n + 1;
for (int i = n; i >= 1; i --)
r[i] = p[a[i]] - 1, p[a[i]] = i;
// (l[i], i) -> (i, r[i])
std::vector<array<int, 4>> opr;
for (int i = 1; i <= n; i ++) {
opr.push_back({i, l[i], i, 1});
opr.push_back({r[i] + 1, l[i], i, -1});
}
sort(opr.begin(), opr.end());
build(1, 1, n);
q[0] = 0, q[ ++ tt] = 1, hh = 0, tt = 0, f[1] = 1;
int lim = 0;
for (int i = 1, j = 0; i <= n; i ++) {
while (j < opr.size() && opr[j][0] == i) {
modify(1, opr[j][1], opr[j][2], opr[j][3]);
j ++;
}
int l = 1, r = i;
while (l < r) {
int mid = l + r + 1 >> 1;
if (query(1, mid, i) == i - mid + 1) r = mid - 1;
else l = mid;
}
if (query(1, 1, i) == i) p[i] = 0;
else p[i] = l;
lim = max(lim, p[i]);
while (hh <= tt && q[hh] < lim) hh ++;
f[i + 1] = f[q[hh]] + 1;
while (hh <= tt && f[q[tt]] > f[i + 1]) tt --;
q[ ++ tt] = i + 1;
}
int res = 2e9;
for (int i = lim; i <= n; i ++)
res = min(res, f[i]);
cout << res << endl;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int dt;
cin >> dt;
while (dt --)
solve();
return 0;
}
视频讲解
Educational Codeforces Round 165 (Rated for Div. 2)（A ~ E 题讲解）
最后祝大家早日
