YuriCode
0%

有趣的题解

发表于 更新于 分类于
本文字数： 20k 阅读时长 ≈ 18 分钟

此合集收录了各种有趣的题解

K-th Not Divisible by n

https://codeforces.com/contest/1352/problem/C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int main()
{
	int t;
	cin >> t;
	//打印第k个不能被n整除的正整数
	while(t--){
		int k, n;
		cin >> n >> k;
		//计算跳过的数字
		int need = (k - 1) / (n - 1);
		cout << k + need << endl;
	}
	return 0;
}

Raising Bacteria

https://codeforces.com/problemset/problem/579/A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int count = 0;
	while(n > 0) {
		int r = n % 2;
		n /= 2;
		if (r == 1) count++;
	}	
	cout << count << endl;
	
	return 0;
}

Same Differences

https://codeforces.com/contest/1520/problem/D

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 <iostream>
#include <map>
#define int long long
using namespace std;

signed main()
{
	//计算aj - ai = j - i等价于ai - i = aj - j，构造新数组ai - i
	//计算新数组有多少对满足i < j且ai = aj
	//实际上就是统计一个数在它之前的位置还出现过几次这个数
	int t;
	cin >> t;
	while(t--){
		map<int, int> cnt;
		int ans= 0;
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			x -= i;
			ans += cnt[x];
			cnt[x]++;
		}
		cout << ans << endl;
	}

	return 0;
}

最小循环节

https://ac.nowcoder.com/acm/contest/97443/C

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

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//因为可以任意插入字符，所以最小循环节就是所有不同的字符的数量
	string str;  
	cin >> str;
	map<char, int> cnt;
	for(auto t : str){
		cnt[t]++;
	}
	cout << cnt.size() << endl;
	return 0;
}

Move Brackets

https://codeforces.com/problemset/problem/1374/C

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

void solve()
{
	int n;
	cin >> n;
	string str;
	cin >> str;
	int ans = 0;
	int bal = 0;
	// '(' > ')'的数量时总是没问题
	//因为是(()还可以看下一个是什么符号，然后再做决定，但是())已经不成立了
	//当')'有多余的时候，我们便可以移动'('到最前面去，此时前面部分刚好匹配正确，所以bal = 0
	//不用考虑移动哪一个'('，因为这个字符串左右括号的数量相同，移动后面任意一个都不会使得匹配的数量发生变化
	for (int i = 0; i < n; i++) {
		if (str[i] == '(') bal++;
		else {
			bal--;
			if (bal < 0) {
				bal = 0;
				ans++;
			}
		}
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	
	int t;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Sorted Adjacent Differences

https://codeforces.com/problemset/problem/1339/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
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	int n;
	cin >> n;
	int arr[n];		
	int ans[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	int l, r;
	if (n % 2 == 0) {
		l = n / 2 - 1;
		r = n / 2;		
	} else {
		l = n / 2;
		r = n / 2 + 1;
	}
	int k = 0;
	while (1) {
		if (l >= 0) {
			ans[k++] = arr[l--];
		}
		if (r <= n - 1) {
			ans[k++] = arr[r++];
		}
		if (k == n) {
			break;		
		}	
	}
	for (int i = 0; i < n; i++) {
		cout << ans[i] << " ";
	}	
	cout << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) 
	{
		solve();
	}
	
	return 0;
}

pspspsps

https://codeforces.com/contest/2049/problem/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>
#define int long long
using namespace std;

void solve()
{
	int n;
	cin >> n;
	string str;
	cin >> str;
	//首项为s和末项为p都对整体没有影响，直接赋值为.
	if (str[0] == 's') str[0] = '.';
	if (str[n - 1] == 'p') str[n - 1] = '.';
	bool found_p = false;
	bool found_s = false;
	for (int i = 0; i < n; i++) {
		if (str[i] == 'p') {
			found_p = true;
		} else if (str[i] == 's') {
			found_s = true;
		}
	}
	if (found_p && found_s) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
	}
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) 
	{
		solve();
	}
	
	return 0;
}

小红的排列构造

https://ac.nowcoder.com/acm/contest/99277/C

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

void solve()
{
	int n;
	cin >> n;
	int arr[n + 1];
	string str;
	cin >> str;
	str = ' ' + str; 
	if (str[n] == '0') {
		cout << -1 << endl;
		return;
	}
	int flag = 1;
	for (int i = 1; i <= n; i++) {
		//如果是1，那么就赋值为上次1的位置加1的数
		if (str[i] == '1') {
			arr[i] = flag;
			flag = i + 1;
		//如果是0，那么就赋值为当前位置加1的数
		} else {
			arr[i] = i + 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) 
	{
		solve();
	}
	
	return 0;
}

小红的01串（三）

https://ac.nowcoder.com/acm/contest/98256/C

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
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
	int a, b, k;
	cin >> a >> b >> k;
	int max_k;
	if (k == 0 && a != 0 && b != 0) {
		cout << -1 << endl;
		return;
	} 
	if (a == b) {
		max_k = 2 * a - 1;	
	} else {
		max_k = 2 * min(a, b);
	}
	if (k <= max_k) {
		if (a > b) {
			if (k % 2 != 0) {
				int r0 = a - ((k + 1) / 2);
				int r1 = b - ((k + 1) / 2);
				for (int i = 0; i < r0; i++) {
					cout << "0";
				}
				for (int i = 0; i < ((k + 1) / 2); i++) {
					cout << "01";
				}
				for (int i = 0; i < r1; i++) {
					cout << "1";
				}
			} else {
				k--;
				int r0 = a - ((k + 1) / 2) - 1;
				int r1 = b - ((k + 1) / 2);
				for (int i = 0; i < r0; i++) {
					cout << "0";
				}
				for (int i = 0; i < ((k + 1) / 2); i++) {
					cout << "01";
				}
				for (int i = 0; i < r1; i++) {
					cout << "1";
				}
				cout << "0";
			}
			cout << endl;				
		} else {
			if (k % 2 != 0) {
				int r0 = a - ((k + 1) / 2);
				int r1 = b - ((k + 1) / 2);
				for (int i = 0; i < r1; i++) {
					cout << "1";
				}
				for (int i = 0; i < ((k + 1) / 2); i++) {
					cout << "10";
				}
				for (int i = 0; i < r0; i++) {
					cout << "0";
				}
			} else {
				k--;
				int r0 = a - ((k + 1) / 2);
				int r1 = b - ((k + 1) / 2) - 1;
				for (int i = 0; i < r1; i++) {
					cout << "1";
				}
				for (int i = 0; i < ((k + 1) / 2); i++) {
					cout << "10";
				}
				for (int i = 0; i < r0; i++) {
					cout << "0";
				}
				cout << "1";
			}
			cout << endl;				
		}
	} else { 
		cout << -1 << endl;
	}		
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

预知

https://ac.nowcoder.com/acm/contest/99458/D

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

void solve()
{
	int n;
	cin >> n;
	int arr[n];
	int cnt_1 = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] == 1) cnt_1++;
	}
	if (n == 1) {
		cout << -1 << endl;
		return;
	}
	sort(arr, arr + n);
	if (cnt_1 == n) {
		cout << 0 << endl;
		return;
	//当次大值为1的时候，我们考虑最坏的情况。
	//当知道了max - 1张牌（这里可以把这max - 1张牌都看成max的那种类型）后
	//剩下的其实就可以转化为1, 1, 1, ···这种情况
	//那我们不管翻开的是哪两张牌，那么都是不一样的
	} else if (arr[n - 2] == 1) {
		cout << arr[n - 1] - 1 << endl;
		return;
	}
	
	cout << arr[n - 1] << endl;	
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t  = 1;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Petr and a Combination Lock

https://codeforces.com/problemset/problem/1097/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
42
43
44
45
#include <bits/stdc++.h>
#define int long long
using namespace std;


void solve()
{
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) cin >> arr[i];
	//因为对于每个角度而言，要么顺时针旋转，要么逆时针旋转
	//所以一共有2 ^ n种情况
	int sum = 1 << n; 
	for (int mask = 0; mask < sum; mask++) {
		int angle = 0;
		for (int i = 0; i < n; i++) {
			//如果对应位上的数为1，那么就逆时针旋转，否则顺时针旋转
			if (mask & (1 << i)) {
				angle -= arr[i];
			} else {
				angle += arr[i];
			}
		}
		if (angle % 360 == 0) {
			cout << "YES" << endl;
			return;
		} 
	}
	cout << "NO" << endl;
	
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve();
	}
	
	return 0;
}

https://codeforces.com/problemset/problem/1793/C

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

void solve()
{
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int l = 0, r = n - 1;
	int MIN = 1, MAX = n;
	//我们移除所有端点值为最值的点
	//因为这里是排列数，所以可以直接使用++--来动态更新最值
	//从两端向中间逐渐移除的好处是：
	//只要端点处的不是最值，那么最值一定就在中间位置，那就是符合条件的情况
	while (l <= r) {
//		cout << "l = " << l << endl;
//		cout << "r = " << r << endl;
//		cout << "MAX = " << MAX << endl;
//		cout << "MIN = " << MIN << endl;
		if (a[l] == MIN) {
			l++;
			MIN++;
		} else if (a[l] == MAX) {
			l++;
			MAX--;
		} else if (a[r] == MIN) {
			r--;
			MIN++;
		} else if (a[r] == MAX) {
			r--;
			MAX--;
		} else {
			break;
		}
 	}
	//因为l和r是数组下标从0开始的，所以这里要加1
	if (l <= r) {
		cout << l + 1 << " " << r + 1 << endl;
	} else {
		cout << -1 << endl;
	}
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

小红的双生排列

https://ac.nowcoder.com/acm/contest/99784/C

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

const int N = 1e9 + 7;

//计算对应数据的排列数
int factorial(int n) {
	int result = 1;
	for (int i = 1; i <= n; ++i) {
		result = (result * i) % N;
	}
	return result;
} 

void solve()
{
	int n;
	cin >> n;
	if (n % 2 == 0) {
		//如果是偶数，那么有两种情况
		//(1) 偶 奇 偶 奇 偶 奇
		//(2) 奇 偶 奇 偶 奇 偶
		cout <<  2 * factorial(n / 2) * factorial(n / 2) % N << endl;
	} else {
		//如果是奇数，那么只有一种情况
		//(1) 奇 偶 奇 偶 奇
		cout << factorial(n / 2) * factorial(n / 2 + 1) % N << endl;
	}
}		

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
// 	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Two Buttons

https://codeforces.com/problemset/problem/520/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
42
43
44
#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	int n, m;
	cin >> n >> m;
	//我们不妨从 m 倒推回 n
	//所以原先的 * 2 和 - 1 操作变成来现在的 / 2 和 + 1
	//我们注意到两次 + 1 和一次 / 2 的操作等价的一次 / 2 再加上 1
	//而且后者所需的操作次数更少
	//这就意味着连续执行多次 + 1 操作只有后面没有 / 2 操作时才有意义
	
	int ans = 0;
	if (m <= n) {
		ans = n - m;
	} else {
		while (1) {
			//避免一直 / 2
			if (m % 2 == 0 && m >= n) {
				ans++;
				m /= 2;
			} else {
				ans++;
				m++; 
			} 		
			if (m == n) break;
		}
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Sort the Array

https://codeforces.com/problemset/problem/451/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
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
#include <bits/stdc++.h>
#define int long long
using namespace std;


void solve()
{
	//这道题的另一种解法是先从左边开始遍历，找到左边第一个递减的位置L
	//然后再从右边开始遍历，找到右边第一个递减的位置R
	//然后把原数组 L 到 R 的位置上的元素 copy 在一个新数组上面
	//对这个新数组进行反转
	//如果反转之后依旧是正序的那就 yes， 否则 no
	//没找到 L 和 R 也 yes
	
	int n;
	cin >> n;
	vector<int> arr(n + 2);
	//减少边界条件判断
	arr[0] = INT_MIN;
	arr[n + 1] = INT_MAX;
	vector<pair<int, int>> p;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	if (n == 1) {
		cout << "yes" << endl;
		cout << 1 << " " << 1 << endl;
		return;
	} else if (n == 2) {
		cout << "yes" << endl;
		if (arr[1] > arr[2]) {
			cout << 1 << " " << 2 << endl;
		} else {
			cout << 1 << " " << 1 << endl;
		}
		return;
	}
	for (int i = 1; i < n; i++) {
		//如果在 if 里面嵌套 while
		//那么先在 while 外面套一层 if 做条件判断
		//并且用 j 来记录 i
		//如果是枚举两个相邻的数，其实从1开始更加简洁
		if (arr[i] > arr[i + 1]) {
			int l = i;
			int j = i;
			while(j < n && arr[j] > arr[j + 1]) j++;
			int r = j;
			p.push_back({l, r});
			i = j;
		}
	}
	if (p.size() == 1) {
		if (arr[p[0].second] > arr[p[0].first - 1] && arr[p[0].first] < arr[p[0].second + 1]) {
			cout << "yes" << endl;
			cout << p[0].first << " " << p[0].second << endl;
		}  else {
			cout << "no" << endl;
		}
	} else if (p.size() == 0) {
		cout << "yes" << endl;
		cout << 1 << " " << 1 << endl;
	} else {
		cout << "no" << endl;
	}
//	cout << "-----------------------------------" << endl;
//	for (auto x : p) {
//		cout << x.first << " " << x.second << endl;
//	}
//	cout << "-----------------------------------" << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Even-Odd Game

https://codeforces.com/problemset/problem/1472/D

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>
#define int long long
using namespace std;

void solve() {
//  问题显然可以转化为
//	如果 Alice 取偶数x,她会将x分添加到全局结果中，否则为 0
//	如果 Bob 取奇数 x,他会将 −x分添加到全局结果中，否则为 0
//	Alice 希望最大化全局结果，而 Bob 希望最小化全局结果。
	
	int n;
	cin >> n;
	int ans = 0;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.rbegin(), a.rend());
	//每次都选最大的数最优
	//不用管奇偶性
	//我们用Alice来举例
	//如果是偶数，显然最优
	//如果是奇数，那么等价于用了Bob一个大奇数的份额，也是最优
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			if (a[i] % 2 == 0) {
				ans += a[i];
			} 
		} else {
			if (a[i] % 2 == 1) {
				ans -= a[i];
			}
		}
	}
	if (ans == 0) {
		cout << "Tie" << endl;
	} else if (ans > 0) {
		cout << "Alice" << endl;
	} else {
		cout << "Bob" << endl;
	}
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

Mere Array

https://codeforces.com/problemset/problem/1401/C

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

void solve()
{
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int min_num = *min_element(arr.begin(), arr.end());
	vector<int> sorted_arr = arr;
	sort(sorted_arr.begin(), sorted_arr.end());
	int flag = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i] != sorted_arr[i] && arr[i] % min_num != 0) {
			flag = 1;
			break;
		}
	}
	if (flag) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
	} 
	
	// 最大公约数为最小数的所有数的集合，等价于最小数的倍数集合
	// 证明如下：
	
	// 倍数性质：
	// 如果某个数 x 是最小数 m 的倍数，那么有x % m = 0
	// 此时gcd(x, m) = m;
	// 所以 S(倍数) ⊆ S(GCD)
	
	// 最大公约数的性质：
	// 如果某个数 x 与数组中其他数 y 构成gcd(x, y) = m
	// 那么 x 必为 m 的倍数
	// 所以S(GCD) ⊆S (倍数)
	
	//所以这两个集合相等
	
	
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

最大子段和

https://www.luogu.com.cn/problem/P1115

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>
#define int long long
using namespace std;

void solve()
{
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	vector<int> sum(n + 1);
	int ans = INT_MIN;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		if (i == 1) sum[i] = arr[i];
		// 在动态规划中，我们记录了以每个数字为结尾的最优解
		// 而一个子段和能成为全局最优解，那它必然也是以某个数字作为结尾的
		else sum[i] = max(arr[i], sum[i - 1] + arr[i]);
		ans = max(ans, sum[i]);
	} 
	
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

K倍区间

https://www.luogu.com.cn/problem/P8649

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

int C(int n)
{
	return n * (n - 1) / 2;
}

void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> arr(n + 1);
	vector<int> sum(n + 1);
	vector<int> mod(n + 1);
	// 根据简单数论
	// 当两个前缀和 mod k 的值相等的时候才符合要求
	// 所以只用求出所有每个mod的数量对应的两两组合数的个数就行
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		sum[i] = sum[i - 1] + arr[i];
	}
	for (int i = 0; i <= n; i++) {
		mod[sum[i] % k]++;
	}
	for (int i = 0; i < k; i++) {
		ans += C(mod[i]);
	}
	cout << ans << endl;		
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

XXXXX

https://codeforces.com/contest/1364/my

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

void solve()
{
	int n, x;
	cin >> n >> x;
	vector<int> arr(n);
	int sum = 0, l = -1, r;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];	
		// 一个可以被x整除的数如果再减去一可以被x整除的数，那么依旧可以被x整除
		// 但是如果减去的是不能被x整除的数，那么所得结果就不能被x整除
		sum += arr[i];
		if (arr[i] % x != 0) {
			// l代表第一个不能被x整除的数的位置
			if (l == -1) l = i;
			// r会一直更新，直到最后一个
			r = i;
		} 
	}
	
	if (sum % x != 0) {
		cout << n << endl;
	} else if (l == -1) {
		cout << -1 << endl;
	} else {
		cout << max(r, n - l - 1) << endl;
	}
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

https://www.luogu.com.cn/problem/P4552

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

const int N = 1e5 + 9;
int n;
int arr[N];
int diff[N];

void solve()
{
	cin >> n;
	int x = 0, y = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		diff[i] = arr[i] - arr[i - 1];
		if (i != 1) {
			if (diff[i] > 0) x += diff[i];
			else if (diff[i] < 0) y -= diff[i];
		}
		// (1)
		// 我们要把差分数组中除了第一项外都变为0
		// 我们直到对于一个区间而言，通过差分数组+ 1 and - 1或者- 1 and + 1即可修改这个区间上的值
		// 我们采用贪心思路
		// 如果每次既可以把一个差分数组的正数项减小，又可以把一个负数项增大
		// 那么通过一次区间操作即可实现
		// 最后不能再进行区间操作，只能一个个来操作	
		// min(x, y)确保只有一类数
		// abs(x - y)差分数组非1项的其他项进行一步步的+-操作
		// 合并为max(x, y)
		
		// (2)
		// 我们要知道有多少种，实际上就是求diff[1]有几种情况
		// 我们实际上可以做这样的操作
		// diff[i] - 1, diff[i] + 1
		// 或者diff[i] + 1, diff[i] - 1
		// 显然，只有当执行一步步操作的时候，diff[1]才发生变化
		// 所以所有的种类就为abs(x - y) + 1
		// + 1是因为本身就要算一种
	}
	cout << max(x, y) << endl;
	cout << abs(x - y) + 1 << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

积木大赛

https://www.luogu.com.cn/problem/P1969

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>
#define int long long
using namespace std;

void solve()
{
	int n;
	cin >> n;
	int h = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		// 如果右边的比左边的高
		// 那么就需要更多的积木
		// 如果右边的比左边的低
		// 那么左边摆好之后右边一定摆好
		if (t > h) {
			ans += (t - h);
		}
		h = t;
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Cost of the Array

https://codeforces.com/contest/2059/problem/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
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
	int n, k;
	cin >> n >> k;
	k /= 2;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (2 * k == n) {
		// 当分的区间和区间长度是一样的时候
		// 我们只用枚举偶数下标的数
		for (int i = 1; i < n; i += 2) {
			if (a[i] != (i + 1) / 2) {
				cout << (i + 1) / 2 << endl;
				return;
			}
		}
		cout << k + 1 << endl;
	} else {
		// 我们希望第二个数组不以 1 开头
		// 不妨将整个数组分为
		// 1, n - k + 1, 1, 1, 1, 1, ...., 1
		for (int i = 1; i <= n - 2 * k + 1; i++) {
			if (a[i] != 1) {
				cout << 1 << endl;
				return;
			}
		}
		// 如果这个区间全是 1
		// 我们不妨把第二个数组取1, 1
		// 这个区间长度一定大于 1
		// 所以一定可以取到两个 1
		cout << 2 << endl;
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		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

https://www.luogu.com.cn/problem/P3916

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m;
int ans[N];

vector<int> g[N];

void dfs(int x, int d) {
	if (ans[x]) return;
	ans[x] = d;
	for (int i = 0; i < g[x].size(); i++) {
		dfs(g[x][i], d);
	}
}

void solve() {
	// 反向建边
	// 从n -> 1, 较大的数可以到哪个数，那么这个数可以到的最大的数就是这个较大数
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[v].push_back(u);
	}
	for (int i = n; i >= 1; i--) dfs(i, i);
	for (int i = 1; i <= n; i++) cout << ans[i] << " ";
	cout << endl;
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}