A Not Too Hard

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

signed main()
{
	int n = read(), x = read();
	vector<int> a(n);
	for(int i = 0; i < n; i++) a[i] = read();
	int ans = 0;
	for(int i = 0; i < n; i++) {
		if(a[i] <= x) ans += a[i];
	}
	cout << ans << endl;
	return 0;
}

B 11/11

略显丑陋

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

signed main()
{
	int n = read();
	vector<int> d(n + 1);
	for(int i = 1; i <= n; i++) d[i] = read();
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		int x = i;
		int y = i;
		int j = x % 10;
		int k = j;
		bool f = 1;
		while(x) {
			if(x % 10 != j) {
				f = 0;
				break;
			}
			x /= 10;
		}
		if(f) {
			while(j <= d[i])
			{
				ans++;
				j = j * 10 + k;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

C Consecutive

差分，太久没写题了，调了一会

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;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

signed main()
{
	int n = read(), q = read();
	string s;
	cin >> s;
	s = "!" + s;
	vector<int> a(n + 1);
	for(int i = 1; i < n ; i++) {
		if(s[i] == s[i + 1]) a[i + 1] = 1;
	}
	// for(int i = 1; i <= n ; i ++) cout << a[i] << " \n"[i == n];
	for(int i = 1; i <= n; i++) a[i] += a[i - 1];
	for(int i = 0; i < q; i++) {
		int l = read(), r = read();
		cout << a[r] - a[l] << endl;
	}
	return 0;
}

D Take ABC

模拟就行(到处都是多余变量，上一题也是唉)

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

const int N = 2e5 + 10;
char g[N];

signed main()
{
	int hh = 0, tt = -1;
	string s;
	cin >> s;
	int n = s.size();
	char l1, l2;
	for(int i = 0; i < n; i++) {
		if(tt - hh  + 1 >= 2 && s[i] == 'C')
		{
			if(g[tt] == 'B' && g[tt - 1] == 'A')
			{
				tt -= 2;
			}
			else g[++tt] = s[i];
		} else {
			g[++tt] = s[i];
		}
	}
	for(int i = 0; i <= tt; i++) cout << g[i];
		cout << endl;
	return 0;
}

E Modulo MST

读完题很慌，看完数据范围枚举边就是了，枚举n-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
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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

const int N = 1010;
struct Edge {
	int u, v, w;
} e[N];

int ans = 0x3f3f3f3f3f3f3f;
int k, x, y;
int n, m;
int p[11];
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void dfs(int u, int s, int state)
{
    if (s == m)
    {
    	
    	int t = 0, cnt;
    	for(int i  = 1; i <= 10; i++) p[i] = i;
        for (int i = 0; i < n; i ++ )
            if (state >> i & 1)
            {
            	int a = e[i + 1].u, b = e[i + 1].v, w = e[i + 1].w;
            	a = find(a), b = find(b);
            	if (a == b) {
	  				return;
        		}
        		p[a] = b;
        		t += w;
        		t %= k;
            }

        ans = min(ans, t % k);
        return;
    }
    if (u == n) return;

    for (int i = u; i < n; i ++ )
    {
        dfs(i + 1, s + 1, state + (1 << i));
    }
}

signed main()
{
	x = read(), y = read();
	k = read();
	for(int i = 1; i <= y; i++) {
		int u = read(), v = read(), w = read();
		e[i] = {u, v, w};
	}
	n = y, m = x - 1;
	dfs(0, 0, 0);
	cout << ans;
	return 0;
}

F Good Set Query

带权并查集，维护到祖先距离

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

const int N = 2e5 + 10;
int p[N], w[N];

int find(int x) {
	if(p[x] == x) return x;
	int r = find(p[x]);
	w[x] = w[p[x]] + w[x];
	return p[x] = r;
}

bool unite(int i, int j, int x){
	int root_i = find(i), root_j = find(j);
	if(root_i == root_j) return w[j]- w[i] == x;
	p[root_i] = root_j;
	w[root_i] = w[j]- w[i]-x;
	return true;
}

signed main() {
	int n = read(), q = read();
	for(int i = 0; i <= n; i++) p[i] = i, w[i] = 0;
	for(int i = 1; i <= q; i++) {
		int a = read(), b = read(), d = read();
		if(unite(a, b, d)) cout << i << " ";
	}
	return 0;
}