比赛链接

A

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
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ls;
typedef unsigned long long uls;
#define endl '\n'
const int N = 2e5 + 10;
const int M = 1e3 + 10;

void sol(){
	int x; cin >> x;
	if (x <= 1599){
		cout << "Rated" << endl;
	}
	else{
		cout << "Unrated" << endl;
	}
}

int main(){
	IO;
	sol();
}

B

模拟题

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;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ls;
typedef unsigned long long uls;
#define endl '\n'
const int N = 2e5 + 10;
const int M = 1e3 + 10;

void sol(){
	ls a, b, c, x, y; cin >> c >> b >>a >> x >> y;
//	int m = 100;
	while (a >= x || b >= y){
	b += a / x;
	a %= x;
	int t = b / y;
	c += t;
	b %= y;
//	cout << a << ' ' << b << ' ' << c << endl; 
	a += t;
	}
	cout << c << endl;
}

int main(){
	IO;
	sol();
}

C

从前往后做会发现不知道单调不递增序列从哪个数开始，因此选择从后往前来构造从0开始单调不递减序列并且对于任意dic[i]<=d[i]。

公式如下：

1
dic[i] = min(d[i], dic[i + 1] + 1);

最后结果就是dic[1] +1，这里不可以用计数器来记相邻的不同种类数的数量，因为当出现断层，例如3210210时候，计数器值是7而正确结果应该是4。

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
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ls;
typedef unsigned long long uls;
#define endl '\n'
const int N = 2e5 + 10;
const int M = 1e3 + 10;

ls d[N], dic[N];

void sol(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> d[i];
	dic[n] = 0;
	for (int i = n - 1; i >= 1; i--)
		dic[i] = min(d[i], dic[i + 1] + 1);
	ls t = 1;
	for (int i = 2; i <= n; i++){
		if (dic[i] != dic[i - 1])
			t++;
	}
	cout << dic[1] +1 << endl;
}

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

D

经典区间计数问题（给定一个数组a，要求找符合要求的区间数量），对于这类问题，可以考虑枚举右端点R，看有多少个合法的L。首先需要考虑单调性，随着R的递增，L的变化是否在一个连续段里（[L,R]内都合法）,可以发现随着L越来越靠近R，极差会变得越来越小，具备单调性。有了单调性，可以考虑二分或者双指针，这里明显需要使用双指针。维护： 左指针j，右指针i，满足[j, i]极差 <= 1(最多两种数字，同时第一种数字和第二种数字差值不超过1)，不符合的情况while循环过掉就行。问题来了，极差怎么算？我们可以维护一个map，记录区间内所有数字的出现次数。

注意一个点，end()不是尾指针不可以解引用，rbegin()才是。

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
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ls;
typedef unsigned long long uls;
#define endl '\n'
const int N = 2e5 + 10;
const int M = 1e3 + 10;

ls a[N];

void sol(){
    //ans定义为long long类型否则会溢出
	ls ans = 0, n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	map<ls, ls> mp;
    //双指针
	for (int i = 1, j = 1; i <= n; i++){
		mp[a[i]]++;
		while (j < i && (mp.size() > 2 || (mp.size() == 2 && abs(mp.begin()->first - mp.rbegin()->first)>1))){
			//注意end()是尾后迭代器，不可以解引用
			mp[a[j]]--;
			if (mp[a[j]] == 0) mp.erase(a[j]);
			j++;
		}
		ans += i - j + 1;
	}
	cout << ans << endl;
}
int main(){
	IO;
	int t; cin >> t;
	while (t--)
		sol();
}