【Codeforces Round #813 (Div. 2)(A~C)】

$更好的阅读体验$

---

A. Wonderful Permutation

---

题目大意

Origional Link

• 给定长度为 $n$ 的数组 $a$，元素互不相同
• 每次可选择 $a_i,a_j$ 进行交换
• 求使得长度为 $k$ 的子序列之和达到最小的交换次数

---

思想

• 对于子序列的和最小，应遵循最小排列
• 即判断原序列中，前 $k$ 个元素，有多少满足 $a_i\le k$，满足该条件则不需要交换，否则需要交换

---

代码

#include 
using namespace std;

#define re register

const int N = 1e6 + 3;

int a[N];

void solve(){
	
	int n, k;
	
	cin >> n >> k;
	
	for(re int i = 1; i <= n; i ++) cin >> a[i];
	
	int cnt = 0;
	
	for(re int i = 1; i <= k; i ++) if(a[i] > k) cnt ++;
	
	cout << cnt << endl;
	
}

int main(){
	
//	solve();
	
	int _;
	cin >> _;
	
	while(_ --){
		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

---

B. Woeful Permutation

---

题目大意

Origional Link

• 给定元素为 $1\sim n$ 的数组 $a$
• 求使得 $lcm(1,a_1)+lcm(2,a_2)+\dots lcm(i,a_i)$ 最大的子序列

---

思想

• 已知 $lcm(a,b)=\frac{a\times b}{gcd(a,b)}$
• 若使得 $lcm(a,b)$ 最大，则应尽可能使得 $gcd(a,b)=1$
• 对于序列中的元素 $a_i=i$
• 则有 $gcd(i,a_i+1)=1$
• 故 $a_i=i+1,a_{i+1}=i$ 时，满足题意
• 即：
  • $n$ 为偶数时，遵循排列：$2,1,4,3,6,5,\dots ,n,n-1$
  • $n$ 为奇数时，遵循排列：$1,3,2,5,4,7,6\dots ,n,n-1$

---

代码

#include 
using namespace std;

#define re register

void solve(){
	
	int n;
	
	cin >> n;
	
	if(n % 2 == 0){
		for(re int i = 2; i <= n; i += 2) cout << i << " " << i - 1 << " ";
	}
	else{
		cout << 1 << " ";
		for(re int i = 3; i <= n; i += 2) cout << i << " " << i - 1 << " ";
	}
	
	cout << endl;

}

int main(){
	
//	solve();
	
	int _;
	cin >> _;
	
	while(_ --){
		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

---

C. Sort Zero

---

题目大意

Origional Link

• 给定长度为 $n$ 的数组 $a$
• 每次操作，可以将所有 $a_i=x$ 的元素操作变为 $a_i=0$
• 求最少操作多少次，可以使得原数组元素不严格单调递增

---

思想

• int a[N]存储数组元素，set b存储当前枚举到i之前，需要将 $a_i$ 变为 $0$ 的 $x$ 值
• 从i = 2开始枚举a[i]：
  • 先判断a[i]是否在b中，若存在，则更新a[i] = 0
  • 若a[i - 1] > a[i]，说明需要将a[i - 1]更新，将b.insert(a[i - 1])，且要使得i之前所有的a[j] == a[i - 1]的元素更新为 $0$，且在更新时，要将a[j] != 0的元素也加入b中
• 由于我们按顺序枚举，故在i之前的序列一定满足不严格单调递增，在枚举结束之后，b中元素个数即为操作次数

---

代码

#include 
using namespace std;

#define re register

const int N = 1e6 + 3;

int a[N];

set<int> b;

void solve(){
	
	int n;
	cin >> n;
	
	for(re int i = 1; i <= n; i ++) cin >> a[i];
	
	for(re int i = 2; i <= n; i ++){
		
		if(b.count(a[i]) > 0) a[i] = 0;

		if(a[i - 1] > a[i]){
			b.insert(a[i - 1]);
			a[i - 1] = 0;
			for(re int j = i - 1; a[j] != 0 && j >= 1; j --){
				b.insert(a[j]);
				a[j] = 0;
			}
		}
		
	}
	
	cout << b.size() << endl;
	
	b.clear();

}

int main(){
	
//	solve();
	
	int _;
	cin >> _;
	
	while(_ --){
		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

---

后记

• $A$ 没有什么难度，但是做的太急(permutation是无重复元素的排列数组)，没有思考好规律
• $B$ 真的是 $WA$ 到飞起，怎么会有我这种笨比推出来 $gcd(i,a_i+1)=1$ 规律还解不出来的人，建议自己remake
• $C$ 一开始思路很乱，后来发现模拟就好了，写完直接交一发就过，没什么算法难度
• 手速场狂 $WA$两道 $A,B$ nt题的我真是没救了，前几场着实给我打破防了，这回还好最后没放弃，继续努力吧