比赛链接

A

题目链接

首先以ABC顺序排，看最后剩下的至多两个类型的比赛的数量，如果有至少一个比赛数量>=2，那么为NO，否则为YES。

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;

int t;

void sol(){
	int a, b, c, t;
	cin >> a >> b >> c;
	t = min(min(a, b), c);
	a -= t, b -= t, c -= t;
	if (a >= 2 || b >= 2 || c >= 2){
		cout << "NO" << endl;
	}
	else{
		cout << "YES" << endl;
	}
}

int main(){                                          
	cin >> t;
	while (t--){
		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
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int t;

void sol(){
	int n , maxn = -1, cnt = 0;
	int a[N];
	cin >> n;
	for (int i = 1; i <= n; i++){	
		cin >> a[i];
		if (a[i] > maxn)
			maxn = a[i];
	}
	for (int i = 1; i <= n; i++)
		if (a[i] == maxn)
			cnt++;
	if (cnt % 2 == 0){
		for (int i = 1; i <= n; i++)
			if (a[i] == maxn)
				cout << 0;
			else
				cout << 1;
	}
	else{
		for (int i = 1; i <= n; i++)
			if (a[i] == maxn)
				cout << 1;
			else
				cout << 0;
	}
	cout << endl;
}

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

E

题目链接

先构造满足1,2条件的矩阵，如n=5时

11110

11100

11000

10000

00000

接着需要 不破坏原有行列构造数字集合的前提下拆分连通块，考虑偶数行的1变 成列，从右边依次往左放置即可，如n=5时

11110

00000

11010

00010

01010

偶数行按副对角线对称就行

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

#define IO ios::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
typedef long long ls;
const int N = 1e3 + 10;


int n;

void sol(){
	cin >> n;
	int a[N][N];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			a[i][j] = 0;
	for (int i = 0 ; i < n; i++)
		for (int j = 0; j < n - 1 - i; j++)
			if (i % 2 == 0)
				a[i][j] = 1;
			else
				a[n-1-j][n-1-i] = 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++)
			cout << a[i][j];
		cout << endl;
	}
				
}


int main(){
	IO
	sol();
}

F

题目链接

构造题，首先满足第二个条件x和y异或最小为n，那就保证高位相同异或为0，低位异或不变。举例，n=5,x=100000,y=100101。再考虑最大公约数问题，gcd(x,y)=n只需要n乘两个连续的整数就行。

那么x =n×2kn×2^k ，y =n×(2k+1)n×(2^k+1)就是答案。

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

typedef unsigned long long ls;
const int N = 2e5 + 10;
int t;

void sol(){
	ls n;
	cin >> n;
	ls k = 1LL * n << 31;
	cout << k << ' ' << k + n << endl;
}


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

H

题目链接

贡献问题，一个数组的权值：所有前缀中不同数字的个数。

对于一个子数组，看这个数组中所有第一个出现的数字aia_i对这个子数组的贡献就是这个数到最后一个数的长度，累加所有的长度就是这个子数组的权值。

上升到整个数组，在aia_i对于这个数组的贡献时，考虑子数组必然包含aia_i这个位置，所以计算过程只会被上一个aia_i 的位置pre[i]影响，影响的区间左端点个数为i−pre[i] 个， 再看看aia_i可以贡献的右端点r，很显然，i<=r<=ni<=r<=n，所以对固定i，所有r的贡献是∑n(r−i+1)=1+2+⋯+(n−i+1)=(n−i+1)(n−i+2)/2

最终i位置的总贡献就是(i−pre[i])(n−i+1)(n−i+2)/2，把所有i的总贡献里诶加起来即可。

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

#define IO ios::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
typedef long long ls;
const int N = 1e5 + 10;

int t;

void sol(){
	int n, a[N], pre;
	ls ans = 0;
	map<int, int> mp;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++){
		pre = 0;
		auto it = mp.find(a[i]);
		if (it != mp.end()) pre = it->second;
		ans += (1LL*i-pre)*1LL*(n-i+1)*(n-i+2)/2;
		mp[a[i]] = i;
	}	
	cout << ans << endl;
}


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

I

题目链接

第一眼看上去像是dfs，但是看到数据范围就知道不可能。想一下，如果矩阵中有2个1，那么不管中间怎么走，一定可以构成回文数；如果矩阵中有两个以上的1，那么一定有至少1种走法使得两个1构成回文数（问：如果两个1中间有1？答：那我为什么不把中间那个1定为终点？），0同理。因此只需要统计1和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
#include <bits/stdc++.h>
using namespace std;

typedef long long ls;
const int N = 1e6 + 10;
int t;

void sol(){
	int n, m; 
	cin >> n >> m;
	int cnt0 = 0, cnt1 = 0;
	vector<string> s(n);
	for (int i = 0 ; i < n; i++){
		cin >> s[i];
		for (int j = 0; j < m; j++)
			if (s[i][j] == '0')
				cnt0++;
			else
				cnt1++;
	}
	for (int i = 0 ; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			if (s[i][j] == '0') cout << "NY"[cnt0>=2];
			else  cout << "NY"[cnt1>=2];
		cout << endl;
	}
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    cout.tie(0);
	cin >> t;
	while (t--){
		sol();
	}
}

J

题目链接

正向思考每个点到更高级城市的最短距离时间复杂度为O(n ×(n+m))，会TLE。

反向思考，从最高级城市出发，计算到其他城市的最短距离即可。可以发现边最多m条，构造出的不同等级城市最多√m个，所以对 √m 个不同等级的城市做多源BFS即可完成。

代码里有很多细节，比较考验代码基本功。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
typedef long long ls;
const int N = 4e5+10;
const int NN = 2e5 + 10;
const int inf = 1e9;

int head[N], ed[N], nxt[N], idx;
int eg[N], lev[N], vis[N], ans[N], dist[N];
int q[NN];

void add(int a, int b){
	ed[idx] = b;
	nxt[idx] = head[a];
	head[a] = idx++;
}

void sol(){
	//邻接表存储图
	idx = 0;
//	memset(head, -1, sizeof(head));
//	memset(eg, 0, sizeof(eg));
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		head[i] = -1;
		eg[i] = 0;
	}
	for (int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		add(u, v);
		add(v, u);
		eg[u]++;
		eg[v]++;
	}
	//统计度，排序去重
	vector<int> dege;
	for (int i = 1; i <= n; i++)
		dege.push_back(eg[i]);
	sort(dege.begin(), dege.end());
	dege.erase(unique(dege.begin(), dege.end()), dege.end());
	int len = dege.size();
	//标记级别，统计级别对应编号
	vector<vector<int> >tongji(len + 1);
	for (int i = 1; i <= n; i++){
		int k = lower_bound(dege.begin(), dege.end(), eg[i]) - dege.begin();
		lev[i] = k;
		tongji[k].push_back(i);
	}
	//对每个级别进行bfs，迭代比其级别小的节点到这个级别节点的最短距离
	for (int i = 1; i <= n; i++) ans[i] = inf;
	int v = 0;
	for (int i = len - 1; i >= 1; i--){
		++v; //vis的状态，每次变化，vis全局数组不用memset初始化
		//多源bfs
		int hh = 0, tt = -1;
		for (auto &k : tongji[i]){
			q[++tt] = k;
			vis[k] = v;
			dist[k] = 0;//自己距离自己0距离
		}
		while (hh <= tt){
			int s = q[hh++];
			if (lev[s] < i) ans[s] = min(ans[s], dist[s]);
			for (int j = head[s]; j != -1; j = nxt[j]){
				int p = ed[j];
				if (lev[p] < i && vis[p] != v){
					vis[p] = v;
					dist[p] = dist[s] + 1;
					q[++tt] = p;
				}
			}
		}
	}
	//输出
	for (int i = 1; i <= n; i++)
		if (ans[i] == inf)
			cout << -1 << ' ';
		else
			cout << ans[i] << ' ';
}


int main(){
	IO
	sol();
}