题解
6 分钟 读完 (大约 936 个字)

[AtCoder Beginner Contest 133 题解

闲来无事打了场ABC,结果被虐爆了…

AB就不说了。

C

给定两个数$l,r$，选出两个数$i,j$满足$i<j$且 $(i \times j)\mod 2019$最小。
$l,r \leq 2e9$.

直接看$r-l+1$的长度。如果大于等于2019说明一定有一个数含有2019这个因子，乘起来一定是0.

否则暴力枚举。

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

ll l, r;
int main(){
	cin >> l >> r;
	if(r - l + 1 >= 2019) {
		cout << 0 << endl;
		return 0;
	}

	ll ans = 1e18;
	for(ll i = l; i <= r; i++)
		for(ll j = i + 1; j <= r; j++)
			ans = min(ans, i * j % 2019);
	cout << ans << endl;
	return 0;
}

D

给你一个数组$A[0…n-1]$，其中$A_i = B_i + B_{(i + 1)\mod n}$.
请还原出$B$. 输出时每个数要*2.

临项相加可以求出$B_{n-1}-B_{0}$，又因 $A_{n-1}=B_{n-1}+B_{0}$，所以列个方程就可以把这两个数全求出来，然后回代即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200000 + 10;
ll n, a[N], B[N];
int main(){
	scanf("%lld", &n);
	ll sum = 0;
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	sum = a[n];
	ll sum1 = 0;
	for(int i = 1; i <= n - 1; i += 2) sum1 += a[i + 1] - a[i];
	//cout << sum << " " << sum1 << endl;
	ll Bn = (sum + sum1) / 2, B1 = sum - Bn;B[1] = B1 * 2;
	for(int i = 1; i <= n - 1; i++) B[i + 1] = (a[i] - B1) * 2, B1 = B[i + 1] / 2;
	for(int i = 1; i <= n; i++) printf("%lld ", B[i]);
	return 0;
}

E

待更。

F

给一棵树，每条边有对应的颜色以及长度。
每次询问将所有颜色为x的边长度换成y，求u、v两点距离。

$n \leq 100000$.

直接树链剖分。
对于一段区间，颜色为x的边的数量/颜色为x的边的总长都可以在vector上二分。

复杂度 $O(n log^2 n)$.

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;

const int N = 200000 + 10;
ll n, q, f[N][20], col[N], len[N], sum[N];
ll d[N], sz[N], son[N], pos[N];
ll top[N], id[N], df;
vector <ll> g[N];
vector <ll> bels[2][N];

void link(ll u, ll v) {
	g[u].push_back(v);
	g[v].push_back(u);
}

void dfs1(ll u, ll pre) {
	f[u][0] = pre; d[u] = d[pre] + 1; sum[u] = sum[pre] + len[u]; sz[u] = 1;
	for(int i = 1; i <= 18; i++) {
		if(f[f[u][i - 1]][i - 1]) f[u][i] = f[f[u][i - 1]][i - 1];
		else break;
	}
	for(int i = 0; i < g[u].size(); i++) {
		int v = g[u][i]; if(v == pre) continue;
		dfs1(v, u); sz[u] += sz[v];
		if(!son[u] || sz[v] > sz[son[u]]) son[u] = v;
	}
}
int lca(int u, int v) {
	if(d[u] < d[v]) swap(u, v);
	for(int i = 19; i >= 0; i--) if(d[u] - (1 << i) >= d[v]) u = f[u][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
	return f[u][0];
}
void dfs2(ll u, ll t) {
	top[u] = t, id[u] = ++df; pos[df] = u;
	if(son[u]) dfs2(son[u], t);
	for(int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if(v == f[u][0] || v == son[u]) continue;
		dfs2(v, v);
	}
}

ll Bs1(int x, int t) {
	int l = 0, r = bels[0][x].size() - 1;
	ll ans = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(bels[0][x][mid] <= t) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}
ll BinarySearch(int x, int t) {
	int l = 0, r = bels[1][x].size() - 1;
	ll ans = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(bels[0][x][mid] <= t) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	if(ans == -1) return 0;
	return bels[1][x][ans];
}
pair <ll, ll> bsearch(int u, int v, int po) {
	if(bels[0][po].empty()) return make_pair(0, 0);
	ll A = Bs1(po, v) - Bs1(po, u - 1);
	ll C = BinarySearch(po, v), D = BinarySearch(po, u - 1);
	return make_pair(A, C - D);
}
pair <ll, ll> Query(int u, int v, int c) {
	pair <ll, ll> t; t.first = 0, t.second = 0;
	while(top[u] != top[v]) {
		if(d[top[u]] < d[top[v]]) swap(u, v);
		pair <ll, ll> te = bsearch(id[top[u]], id[u], c);
		t.first += te.first, t.second += te.second;
		u = f[top[u]][0];
	}
	if(id[u] > id[v]) swap(u, v);
	pair <ll, ll> te = bsearch(id[u], id[v], c);
	t.first += te.first, t.second += te.second;
	return t;
}
signed main(){
	scanf("%lld%lld", &n, &q);
	for(ll i = 1, u, v, c, d; i < n; i++) {
		scanf("%lld%lld%lld%lld", &u, &v, &c, &d);
		link(u, n + i);
		link(v, n + i);
		col[n + i] = c, len[n + i] = d;
	}
	dfs1(1, 0); dfs2(1, 1);
	for(int i = 1; i <= 2 * n - 1; i++) bels[0][col[pos[i]]].push_back(i),bels[1][col[pos[i]]].push_back(len[pos[i]]);
	for(int i = 1; i <= n - 1; i++)
		for(int j = 1; j < bels[1][i].size(); j++) bels[1][i][j] += bels[1][i][j - 1];

	while(q--) {
		int x, y, u, v;
		scanf("%lld%lld%lld%lld", &x, &y, &u, &v);
		pair <ll, ll> ans = Query(u, v, x);
		//fprintf(stderr, "%lld, %lld\n", ans.first, ans.second);
		ll ans1 = sum[u] + sum[v] - 2 * sum[lca(u, v)];
		ll ans2 =  - ans.second + 1ll * y * ans.first;
		//printf("%lld %lld\n", ans1, ans2);
		printf("%lld\n", ans1 + ans2);
	}
	return 0;
}
# 树链剖分
[EDU 47~67]题解合集
计蒜之道 初赛第一场 题解

评论

关注我

分类

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×