A. Yellow Cards

 

最多的话，先淘汰k值小的人。最少的话，先每个人扣k-1分，最后如果n还有，则剩多少就淘汰多少人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int a1, a2, k1, k2, n;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> a1 >> a2 >> k1 >> k2 >> n;
	if (k1 > k2) {
		swap(a1, a2);
		swap(k1, k2);
	}
	int ansmax, ansmin;
	int num1 = min(a1, n / k1);
	ansmax = min(a1 + a2, num1 + (n - num1 * k1) / k2);
	int num2 = 0;
	num2 = a1 * (k1 - 1) + a2 * (k2 - 1);
	if (n <= num2)ansmin = 0;
	else ansmin = min(a1+a2,n - num2);
	cout << ansmin << ' ' << ansmax;
	return 0;
}

 

B. The Number of Products

 

问题等价于求区间内和为奇数的区间的个数。

由于数组中只含有0和1；则区间端点只有四种情况，左0右0，左1右0，左0右1，左1右1.还有一种区间长度为1的情况。

上述5种情况分类讨论。

把被1分割开个几段连续的0的个数push进vector中，左0右0的情况则是从间隔为1的几段0中选择2个的组合数；区间长度为1的情况是0的个数；左1右1的情况是包含偶数个1的区间的个数，枚举区间长度可以发现等于num1-1+num1-3+num1-5+···；左1右0和左0右1的情况是类似的，可以找到规律，v[0] * 0+v[1] * 0+v[2] * 1+v[3] * 1+v[4] * 2+v[5] * 2+···，另一种是反向类似。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
int a[maxn];
vector<int>vc;
ll cnt0, cnt1;
ll ans0, tot;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] > 0) {//a[i]==0
			cnt++;
			cnt0++;
		}
		else {
			cnt1++;
			vc.push_back(cnt);
			cnt = 0;
		}
	}
	vc.push_back(cnt);
	cnt = 0;
	for (int i = 0; i < vc.size(); i += 2) {
		cnt += vc[i];
	}
	ans0 += 1ll*cnt * (cnt - 1) / 2;
	cnt = cnt0 - cnt;
	ans0 += 1ll*cnt * (cnt - 1) / 2;
	ans0 += cnt0;
	cnt = cnt1 - 1;
	while (cnt > 0) {
		ans0 += cnt;
		cnt -= 2;
	}
	for (int i = 0; i < vc.size(); i++) {
		ans0 += vc[i] * (i / 2);
	}
	for (int i = vc.size() - 1; i >= 0; i--) {
		ans0 += vc[i] * ((vc.size() - 1 - i) / 2);
	}
	for (int i = 1; i <= n; i++) {
		tot += i;
	}
	cout << (tot - ans0) << ' ' << ans0;
	return 0;
}

但是！！这是最傻逼的做法了

我后来看了一眼ac的代码，看到了dp，其实开始我也想过了dp，但是没仔细想，后来考虑了一下。

dp[i] [0]表示以i为区间右端点，区间内和为偶数的组合数，dp[i] [1]也类似。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
ll tot, ans;
int dp[maxn][2];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int b;
		cin >> b;
		if (b > 0) {
			dp[i][0] = dp[i - 1][0] + 1;
			dp[i][1] = dp[i - 1][1];
		}
		else {
			dp[i][0] = dp[i - 1][1];
			dp[i][1] = dp[i - 1][0] + 1;
		}
		ans += dp[i][0];
	}
	tot = 1ll * (1+n)*n / 2;
	cout << (tot - ans) << ' ' << ans;
	return 0;
}

 

C. Swap Letters

 

记录下不同的位置。只有两种情况，‘a b’,‘a,b’和’a,b’,‘b,a’，对于第一种情况，一次就可以交换完，第二种需要2次。

而当两中情况的和为奇数时，则不可能完成。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
string s, t;
queue<int>q[2];
int ans;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	cin >> s >> t;
	for (int i = 0; i < n; i++) {
		if (s[i] != t[i]) {
			if (s[i] == 'a')q[0].push(i);
			else q[1].push(i);
		}
	}
	if ((q[0].size() + q[1].size()) & 1) {
		cout << -1;
		return 0;
	}
	if (q[0].size() & 1) {
		ans = q[0].size() / 2 + q[1].size() / 2 + 2;
	}
	else {
		ans = q[0].size() / 2 + q[1].size() / 2;
	}
	cout << ans << endl;
	for (int i = 0; i < 2; i++) {
		while (q[i].size() >= 2) {
			cout << q[i].front()+1 << ' ';
			q[i].pop();
			cout << q[i].front()+1 << endl;
			q[i].pop();
		}
	}
	if (!q[0].empty()) {
		int a = q[0].front();
		int b = q[1].front();
		cout << a+1 << ' ' << a+1<<endl;
		cout << a+1 << ' ' << b+1 << endl;
	}
	return 0;
}

 

D. Ticket Game

 

根据前半部分和后半部分的空格数的数量关系分为2种情况：

两者相等，两者不等。

  • 前后空格相等时，如果前后已有的数字和不相等，则Monocarp每次都在多的部分填9，或在少的部分填0，则Bicarp最多只能使后填的部分和相等，永远无法使前后所有数字和相等。
  • 前后空格不等时，只有当已有数字和小的那方的空格数多，这样在多出来的那几个空格中，Bicarp可以减小差距，但是当且仅当sum[0]−sum[1]==(space[1]−space[0])∗9/2sum[0] - sum[1] == (space[1] - space[0]) * 9 / 2时，才能取胜，因为若差距太大，则即使Bicarp全填9也无法弥补，而若差距太小，则Monocarp可以在他的回合都填9，使得原先小的那方反而变得更大。
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
int a[maxn];
int space[2], sum[2];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	char c;
	string s;
	cin >> s;
	for (int i = 1; i <= n / 2; i++) {
		c = s[i - 1];
		if (c != '?') {
			sum[0] += c - '0';
		}
		else {
			space[0]++;
		}
	}
	for (int i = n / 2 + 1; i <= n; i++) {
		c = s[i - 1];
		if (c != '?') {
			sum[1] += c - '0';
		}
		else {
			space[1]++;
		}
	}
	if (space[0] > space[1]) {
		swap(space[0], space[1]);
		swap(sum[0], sum[1]);
	}
	if (space[0] == space[1]) {
		if (sum[0] == sum[1]) {
			cout << "Bicarp" << endl;
			return 0;
		}
	}
	if (sum[0] > sum[1]) {
		if (sum[0] - sum[1] == (space[1] - space[0]) * 9 / 2) {
			cout << "Bicarp" << endl;
			return 0;
		}
	}
	cout << "Monocarp" << endl;
	return 0;
}

 

E. Marbles

 

time limit per test: 4 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

Monocarp has arranged nn colored marbles in a row. The color of the ii-th marble is aia_i. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color).

In other words, Monocarp wants to rearrange marbles so that, for every color jj, if the leftmost marble of color jj is ll-th in the row, and the rightmost marble of this color has position rr in the row, then every marble from ll to rr has color jj.

To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.

You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.

Input

The first line contains one integer n(2≤n≤4⋅105)n (2≤n≤4⋅10^5) — the number of marbles.

The second line contains an integer sequence a1,a2,…,ana_1,a_2,…,a_n (1≤ai≤20)(1≤a_i≤20), where aia_i is the color of the ii-th marble.

Output

Print the minimum number of operations Monocarp has to perform to achieve his goal.

Examples

input

1
2
7
3 4 2 3 4 2 2

output

1
3

input

1
2
5
20 1 14 10 2

output

1
0

input

1
2
13
5 5 4 4 3 5 7 6 5 4 4 6 5

output

1
21

Note

In the first example three operations are enough. Firstly, Monocarp should swap the third and the fourth marbles, so the sequence of colors is [3,4,3,2,4,2,2][3,4,3,2,4,2,2]. Then Monocarp should swap the second and the third marbles, so the sequence is [3,3,4,2,4,2,2][3,3,4,2,4,2,2]. And finally, Monocarp should swap the fourth and the fifth marbles, so the sequence is [3,3,4,4,2,2,2][3,3,4,4,2,2,2].

In the second example there’s no need to perform any operations.

 

状压dp

最多有20种颜色，所以开一个1<<20的数组，dp[S]表示达到S状态需要的最少操作数。S中每一位对应一种颜色，1表示该颜色位置已经确定，0表示未确定。

每次找到状态中未确定的颜色，我们假设所有已经确定的颜色在集合中是连续排列在最前面的，所以现在要把下一步要确定的颜色放到已经确定的颜色后面。

所以就需要求出把一种颜色全部放到另一种颜色前面（后面）所需要的最少操作数，注意，当我们新放置一种颜色时，要对所有已放置的颜色求出把它放到新放置的颜色前面的操作数，所以相当于对任何两种颜色独立地计算，而各自计算完后求和就是总的操作数。

独立地把两种颜色拿出来，要求把一种颜色全部放到另一种前面的最小操作数，就是对每一个颜色B求它前面颜色A的个数，然后求和。直接枚举不行，我们可以dp，O(n)O(n)地求出。

如果有一种颜色未在集合里出现过，那么把任何颜色放到它前面的操作数都等于0，所以确定这种颜色的操作数等于0，对结果没有影响。因此可以取dp[(1<<20)-1]作为最终结果。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 4e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
vector<int>vc[25];
int a[maxn];
ll dp[(1 << 20) + 5], cg[25][25];
int tmp[maxn][25], tmpdp[maxn][25];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		vc[a[i]].push_back(i);
	}
	for (int i = 1; i <= 20; i++) {
		if (vc[i].empty())continue;
		memset(tmp, 0, sizeof(tmp));
		memset(tmpdp, 0, sizeof(tmpdp));
		for (int j = 1; j < vc[i][0]; j++) {
			tmp[vc[i][0]][a[j]]++;
		}
		for (int j = 1; j < vc[i].size(); j++) {
			int l = vc[i][j - 1], r = vc[i][j];
			for (int k = l + 1; k < r; k++) {
				tmp[vc[i][j]][a[k]]++;
			}
		}
		for (int j = 1; j <= 20; j++) {
			tmpdp[vc[i][0]][j] = tmp[vc[i][0]][j];
		}
		for (int j = 1; j < vc[i].size(); j++){
			for (int k = 1; k <= 20; k++) {
				tmpdp[vc[i][j]][k] = tmpdp[vc[i][j - 1]][k] + tmp[vc[i][j]][k];
			}
		}
		for (int j = 1; j <= 20; j++) {
			cg[i][j] += tmpdp[vc[i][0]][j];
		}
		for (int j = 1; j < vc[i].size(); j++) {
			for (int k = 1; k <= 20; k++) {
				cg[i][k] += tmpdp[vc[i][j]][k];
			}
		}
	}
	int tot = (1 << 20);
	for (int i = 1; i < tot; i++) {
		dp[i] = 1e18;
	}
	for (int i = 0; i < tot; i++) {
		for (int j = 1; j <= 20; j++) {
			if ((i&(1 << (j - 1))) == 0) {
				ll res = 0;
				for (int k = 1; k <= 20; k++) {
					if (i&(1 << (k - 1))) {
						res += cg[k][j];
					}
				}
				dp[i | (1 << (j - 1))] = min(dp[i | (1 << (j - 1))], dp[i] + res);
			}
		}
	}
	cout << 1ll*dp[tot-1] << endl;
	return 0;
}