现场4题，第二天补题时发现hard版本的直接用当时写的easy版代码就能过，结果是当时因为网太卡就没试，感觉亏爆。0.o

A. Chips Moving

 

签到，奇数或偶数内部是等价的，只有在奇偶之间转化时才会+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
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
int n;
int c1, c2;
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a & 1)c1++;
		else c2++;
	}
	cout << min(c1, c2);
	return 0;
}

 

B. Bad Prices

 

对于一个数，如果它之后有比它小的数，它就是bad girl，bad price.

所以从后往前找，始终记录后面的数中最小值，如果当前数大于后面数最小值，则当前数为bad，若当前数小于最小值，则更新最小值。

直接变量记录就好了，当时还写了优先队列，完全没必要。

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<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
int n, t;
int a[maxn];
int main() {
	cin.sync_with_stdio(false);
	cin >> t;
	while (t--) {
		int ans = 0;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		priority_queue<int,vector<int>,greater<int> >q;
		for (int i = n; i >= 0; i--) {
			if (q.empty()) {
				q.push(a[i]);
				continue;
			}
			if (a[i] > q.top())ans++;
			else q.push(a[i]);
		}
		cout << ans << endl;
	}
	return 0;
}

 

C. Book Reading

 

一个数的倍数的末尾数字是有规律的，最多以10为周期，因此提前记一下周期，之后再看能出现几个周期，多出来的暴力模拟一下。

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<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
ll n,  m;
int t;
map<int, int>mp;
map<int, int>M;
int main() {
	mp[1] = 10; mp[2] = 5; mp[3] = 10; mp[4] = 5; mp[5] = 2;
	mp[6] = 5; mp[7] = 10; mp[8] = 5; mp[9] = 10; mp[0] = 1;
	for (int i = 0; i < 10; i++) {
		int res = 0;
		for (int j = 1; j <= mp[i]; j++) {
			res += (i*j) % 10;
		}
		M[i] = res;
	}
	cin.sync_with_stdio(false);
	cin >> t;
	while (t--) {
		ll ans = 0;
		cin >> n >> m;
		int t = m % 10;
		ll cnt = n / m;
		ans += M[t] * (cnt / mp[t]);
		int rest = cnt % mp[t];
		for (int i = 1; i <= rest; i++) {
			ans += (i*t) % 10;
		}
		cout << ans << endl;
	}
	return 0;
}

 

D1. Equalizing by Division (easy version)

 

给定一个数列，对每个数能进行整除2的操作任意次，求最小操作几次使数列中有k个相同的数。

对于一个数，由它能得到它经过几次整除2后的数，因此对每一次整除2后得到的数，记录操作的次数，当能得到某一个数的途径大于等于k时，看操作次数是否为最小值。

由于对数列排过序，因此从左到右得到相同数需要的操作次数一定也是由小到大的。贪心是成立的。

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
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n, k;
vector<int>vc[maxn];
int a[maxn];
int main() {
	cin.sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		int b = a[i];
		int cnt = 0;
		while (b) {
			if (vc[b].size() >= k) {
				b >>= 1;
				continue;
			}
			vc[b].push_back(cnt);
			b >>= 1;
			cnt++;
		}
		if (vc[0].size() >= k)continue;
		vc[0].push_back(cnt);
	}
	int ans = INF;
	for (int i = 0; i < maxn; i++) {
		if (vc[i].size() < k)continue;
		int res = 0;
		for (auto v : vc[i])res += v;
		ans = min(ans, res);
	}
	cout << ans;
	return 0;
}

 

D2. Equalizing by Division (hard version)

 

和上一题一样。

 

G. Path Queries

 

似乎是某一年的icpc网络赛类似题，但当时是队友写的。

一数对(u,v)，要求u，v的路径上所有边的边权最大值不能超过q。求数对个数。

带权并查集

我们知道若(a,b),(b,c)满足条件，则(a,c)也满足，那么就是从一堆数任意挑出两个数组成数对，即求组合数。

先对询问排序，以减少不必要的回头次数。

用并查集，根节点的rk表示该并查集有几个点。两个集合合并时把rk相加。

合并集合的同时更新答案。注意计算组合数时精度。

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
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
int n, m;
vector<pair<int,pii>>E;
vector<pii>qus;
ll tmp;
ll ans[maxn];
int par[maxn];
int rk[maxn];
ll cal(int x) {
	return 1ll*x * (x - 1) / 2;
}
void init(int n) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		rk[i] = 1;
	}
}
int find(int x) {
	if (par[x] == x)return x;
	return par[x] = find(par[x]);
}
void unit(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rk[x] < rk[y]) {
		par[x] = y;
		tmp = tmp - cal(rk[x]) - cal(rk[y]) + cal(rk[x] + rk[y]);
		rk[y] = rk[y] + rk[x];
	}
	else {
		par[y] = x;
		tmp = tmp - cal(rk[x]) - cal(rk[y]) + cal(rk[x] + rk[y]);
		rk[x] = rk[x] + rk[y];
	}
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n >> m;
	init(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		E.push_back(make_pair(w, pii(u, v)));
	}
	sort(E.begin(), E.end());
	for (int i = 0; i < m; i++) {
		int k;
		cin >> k;
		qus.push_back(pii(k, i));
	}
	sort(qus.begin(), qus.end());
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int k = qus[i].first;
		while (cnt < n - 1 && E[cnt].first <= k) {
			unit(E[cnt].second.first, E[cnt].second.second);
			cnt++;
		}
		ans[qus[i].second] = tmp;
	}
	for (int i = 0; i < m; i++) {
		cout << ans[i] << ' ';
	}
	return 0;
}