7.3 测试

7.3 测试

混氏新子 蒟蒻
  2023-07-03 21:47:40 2023-07-03 21:47:40 创建   2023-09-24 19:12:49 2023-09-24 19:12:49 更新    1.4k 字  7 分钟  

前情提要

题目链接

成绩表

成绩表

不骄不躁，继续保持，持续进步。

题解

T1

简单题，枚举各个区间就行了，但是注意要排序！由于可能会有小数，我将数据乘了2。

code
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
#include <bits/stdc++.h>
#define N 100010
using namespace std;
using ll = long long;
int n;
ll t;
struct house {
	ll x, a;
	inline bool operator < (const house &tmp) const {
		return x < tmp.x;
	}
}hs[N];
int ans = 2;
int main() {
	freopen("house.in", "r", stdin);
	freopen("house.out", "w", stdout);
	scanf("%d%lld", &n, &t);
	t <<= 1;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &hs[i].x, &hs[i].a);
		hs[i].x <<= 1;
	}
	sort(hs + 1, hs + n + 1);
	for (int i = 2; i <= n; ++i) {
		auto tmp = hs[i].x - hs[i - 1].x - hs[i].a - hs[i - 1].a;
		if (tmp == t) {
			++ans;
		} else if (tmp > t) {
			ans += 2;
		}
	}
	printf("%d", ans);
	return 0;
}

T2

#倍增

当时考试时有许多思路，有一种算是已经走上正解，但是继续的话没有想下去，还有一种用了贪心 + 二分，不保证正确性，但是考试时有个地方写错了，不晓得对不对，于是就暴力搞了50 pts。

正解就是找到每个点加满油最远到的地方，然后用倍增去找（当时没想到倍增这种做法）。

注意倍增找小于终点的点，类似于找 lca 找深度大于 lca 的点。

code
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 N 50010
using namespace std;
using ll = long long;
int n, k;
ll w[N << 1], maxw, totw, revw[N];
ll v;
int tp[N << 1][17], ans;
int main() {
	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", w + i);
		maxw = max(maxw, w[i]);
		totw += w[i];
		w[i + n] = w[i];
	}
	while (k--) {
		scanf("%lld", &v);
		if (v < maxw) {
			puts("-1");
			continue;
		}
		if (v >= totw) {
			puts("1");
			continue;
		}
		ans = n;
		ll tot = 0;
		for (int i = 1, j = 1; i <= (n << 1); ++i) {
			while (tot + w[j] <= v && j <= (n << 1)) tot += w[j++];
			tp[i][0] = j;
			tot -= w[i];
		}
		for (int i = 16; ~i; --i)
		tp[((n << 1) | 1)][i] = ((n << 1) | 1);
		for (int i = 1; i < 17; ++i) {
			for (int j = 1; j <= (n << 1); ++j) {
				tp[j][i] = tp[tp[j][i - 1]][i - 1];
//				cout << j << ' ' << i << ' ' << tp[j][i - 1] << ' ' << tp[tp[j][i - 1]][i -1] << endl;
			}
		}
		
		for (int i = 1; i <= n; ++i) {
			int x = i, y = 0;
			for (int j = 16; ~j; --j) {
//				cout << x << ' ' << j << ' ' << tp[x][j] << endl;
				if (tp[x][j] < i + n) x = tp[x][j], y |= (1 << j);
			}
			ans = min(ans, y + 1);
		}
		printf("%d\n", ans);
	}
	return 0;
}

T3

#树的重心

相当于两道题，最小值相当于就贪心相邻的来，弄几个菊花就行了（不会证明）。

最大值相对感觉更好理解，让所有根的儿子都经过根到根的另一个子树里面去肯定是最大的，而重心每个子树都小于一半大小，肯定是行的。（具体我还是不会证，因为所有点到根的距离和最小的就是重心为根时）。然后输出方案黄嘉玮大佬提供了一个，每个点都放到后的点去，就绝对是其它子树了，十分地方便。

树的重心(转)

code
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
#include <bits/stdc++.h>
#define N 100010
#define int long long
using namespace std;
int n, t;
int u, x;
vector <int> g[N];
int co[N], cnt;
int v[N];
vector <int> coa[N];
void dfs1(int u, int v) {
	for (auto &i : g[u]) {
		if (i == v) continue;
		dfs1(i, u);
	}
	if (!co[u] && u != 1) {
		if (!co[v]) co[v] = co[u] = ++cnt;
		else co[u] = co[v];
	}
}
int siz[N], zx = 1;
int dep[N];
int arr[N], tot;
void dfs2(int u, int v) {
	int mtr = 0;
	siz[u] = 1;
	for (auto &i : g[u]) {
		if (i == v) continue;
		dfs2(i, u);
		siz[u] += siz[i];
		mtr = max(mtr, siz[i]);
	}
	mtr = max(mtr, n - siz[u]);
	if (mtr <= n / 2) zx = u;
}
void dfs3(int u, int v) {
	arr[tot++] = u;
	dep[u] = dep[v] + 1;
	for (auto &i : g[u]) {
		if (i == v) continue;
		dfs3(i, u);
	}
}
signed main() {
	freopen("home.in", "r", stdin);
	freopen("home.out", "w", stdout);
	scanf("%lld%lld", &n, &t);
	for (int i = 1; i < n; ++i) {
		scanf("%lld%lld", &u, &x);
		g[u].emplace_back(x);
		g[x].emplace_back(u);
	}
	if (t == 1) {
		dfs1(1, 0);
		if (!co[1]) co[1] = co[g[1][0]];
		printf("%lld\n", (n - cnt) * 2);
		for (int i = 1; i <= n; ++i) coa[co[i]].emplace_back(i);
		for (int i = 1; i <= cnt; ++i) {
			for (int j = 0; j < coa[i].size(); ++j) {
				v[coa[i][j]] = coa[i][(j + 1) % coa[i].size()];
			}
		}
		for (int i = 1; i <= n; ++i) printf("%lld ",v[i]);
	} else {
		dfs2(1, 0);
		dfs3(zx, 0);
		int ans = 0;
		for (int i = 1; i <= n; ++i) ans += dep[i] - 1;
		printf("%lld\n", ans * 2);
		for (int i = 0; i < n; ++i) v[arr[i]] = arr[(i + n / 2) % n];
		for (int i = 1; i <= n; ++i) printf("%lld ", v[i]);
	}
	return 0;
}

T4

#数位dp #dp

就暴力数位 dp 就行了，dp 的内容有位数，进位，和的差， 从第一位到现在的数是否超过原数。

通过观察方大佬的代码，得知了一种记忆化递归的方法，可以排除很多无用的状态，缺点是耗空间大，但是时间快，更好理解。

code
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;
using ll = long long;
ll r, k, ans;
ll f[25][1000][400][2];
bool vis[20][1000][400][2];
int a[25], len;
ll dfs(int p, int j, int c, bool ex) {
	if (p == len + 3) {
		if (c == 0 && !ex) {
			return 1;
		}
		return 0;
	}
	if (vis[p][j][c + 200][ex]) return f[p][j][c + 200][ex];
	vis[p][j][c + 200][ex] = 1;
	auto &ff = f[p][j][c + 200][ex] = 0;
	for (int i = 0; i < 10; ++i) {
		int nj = (k * i + j) / 10;
		int xw = (k * i + j) % 10;
		if (i > a[p]) ff += dfs(p + 1, nj, c + i - xw, 1);
		else if (i == a[p]) ff += dfs(p + 1, nj, c + i - xw, ex);
		else ff += dfs(p + 1, nj, c + i - xw, 0);
	}
	return ff;
}
int main() {
	freopen("number.in", "r", stdin);
	freopen("number.out", "w", stdout);
	scanf("%lld%lld", &r, &k);
	for (len = 0; r; ++len) {
		a[len] = r % 10;
		r /= 10;
	}
	printf("%lld", dfs(0, 0, 0, 0) - 1);
	return 0;
}

后记

继续努力！

  • 标题: 7.3 测试
  • 作者: 混氏新子
  • 创建于 : 2023-07-03 21:47:40
  • 更新于 : 2023-09-24 19:12:49
  • 链接: https://blog.huasushis.cn/2023/7.3 测试/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
6.29 测试 6.29 测试 7.4 测试 7.4 测试 6.27 测试 6.27 测试
推荐阅读
6.29 测试 6.29 测试 7.4 测试 7.4 测试
评论
此页目录
7.3 测试
  1. 前情提要
  2. 题解
    1. T1
    2. T2
    3. T3
    4. T4
  3. 后记