比赛链接

https://www.bilibili.com/video/BV1pxcrz6EKm

A

考察顺序结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;
typedef long long ls;

void sol(){
	ls n; cin >> n;
	cout << n / 3 * 3 << endl;
}

int main(){
	sol();
}

B

这道trick题目卡了我一整个比赛，我用dp写超时了然后就用map来优化，结果还是超时。头脑直接干报废了，活该不看数据范围就开始写题。其实一项之后就可以发现可以化简为 元素-下标相等 。对于任意选出来的数都要满足元素-下标相等，题目让我求最长的这种序列，那就是求这个差值的众数，可以用map来求解。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;
typedef long long ls;



void sol(){
	int n; cin >> n;
	map<int, int> mp;
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		mp[x - i]++;
	}
	int maxn = -1;
	for (auto i : mp)
		maxn = max(maxn, i.second);
	cout << maxn << endl;
}

int main(){
	int t; cin >> t;
	while (t--)
	sol();
}

C

依然是一道trick题，多列一下就可以发现规律，当n>=4时候不论给出什么序列都可以通过有限次不相邻交换之后变成升序，<4的情况用if-else特判就行。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;
typedef long long ls;



void sol(){
	int n; cin >> n;
	vector<int> arr(n + 10);
	for (int i = 1; i <= n; i++) cin >> arr[i];
	if (n >= 4){
		cout << "YES" << endl;
		return;
	}
	else if (n == 3){
		if (arr[2] == 2 && (arr[1] == 3 || arr[1] == 1))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	else if (n == 2){
		if (arr[1] == 1 && arr[2] == 2)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	else
		cout << "YES" << endl;
		
}

int main(){
	int t; cin >> t;
	while (t--)
	sol();
}

D

本题值得深究。由于两个操作对于总值的影响分别为 +1和 +0，因此最终的和必然大于等于初始的 sum ，那么最优解显然是取最终值为 p=⌈sum/n⌉⌈sum/n⌉，我们需靠考虑能否达到这个值，不难考虑到两种操作下来一定可以使得序列达到全部为p的效果。由于减少的次数一定小于增加的次数，操作次数只需要每次累加减少了多少就行（因为有时候+1有时候+1-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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;
typedef long long ls;

void sol(){
	int n; cin >> n;
	vector<int> arr(n + 10);
	ls sum = 0;
	
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
		sum += arr[i];
	}
	ls x = ceil(1.0 * sum /  n);
	ls ans = 0;
	
	for (int i = 1; i <= n; i++)
		ans += max(0LL, x - arr[i]);
	cout << ans << endl;
}

int main(){
	int t; cin >> t;
	while (t--)
		sol();
}