首页 程序设计 杂题集

# 报数游戏

算 101210121012×24101210121012 \times 24
昏迷高精度 C++C++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string mul(string aa, int b) {
	vector<int> a, c;
	for (int i = aa.size() - 1; i >= 0; i--)
		a.push_back(aa[i] - '0');
	
	int t = 0; 
	
	for (int i = 0; i < a.size() || t != 0; i++) {
		if (i < a.size())
			t += a[i] * b;
		c.push_back(t % 10), t /= 10;
	}
	
	string res = "";
	for (int i = c.size() - 1; i >= 0; i--)
		res += to_string(c[i]);
	return res;
}

超级无敌 JavaJava
Java
1
2
3
4
5
6
7
8
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger a = new BigInteger("101210121012");
        System.out.print(a.multiply(new BigInteger("24")));
    }
}

# 分布式队列

模拟模拟模拟模拟

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n;
int cnt[N];
string ask;
int num;

void solve() {
	cin >> n;
	while (cin >> ask) {
		if (ask == "add")
			cin >> num, cnt[0]++;
		else if (ask == "sync") {
			cin >> num;
			if (num != 0)
				cnt[num] = min(cnt[0], cnt[num] + 1);
		}
		else {
			int ans = 0x3f3f3f3f;
			for (int i = 0; i <= n - 1; i++)
				ans = min(cnt[i], ans);
			cout << ans << endl;
		}
	} 
}

# 食堂

# 题目大意

学校里一共有 a2a_2 个两人寝、a3a_3 个三人寝，a4a_4 个四人寝，而食堂里有 b4b_4 个四人桌和 b6b_6 个六人桌。学校想要安排学生们在食堂用餐，并且满足每个寝室里的同学都在同一桌就坐，请问这个食堂最多同时满足多少同学用餐？

# 数据范围

对于 20%20\% 的评测用例，保证 a2+a3+a4≤8a_2+a_3+a_4\leq 8。
对于 100%100\% 的评测用例，保证 q≤100q\leq 100，b4+b6≤a2+a3+a4≤100b_4+b_6\leq a_2+a_3+a_4\leq 100。

# 题解

第一个错解

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
void solve() {
	int a2, a3, a4, b4, b6;
	cin >> a2 >> a3 >> a4 >> b4 >> b6;
	int res = 0;
	
	// 一个四人桌放一个四人寝
	while (a4 > 0 && b4 > 0)
		res += 4, a4--, b4--;
		
	// 一个四人桌放两个二人寝
	while (a2 >= 2 && b4 > 0)
		res += 4, a2 -= 2, b4--;
	
	// 一个六人桌放两个三人寝
	while (a3 >= 2 && b6 > 0)
		res += 6, a3 -= 2, b6--;
	 
	// 一个六人桌放三个二人寝
	while (a2 >= 3 && b6 > 0)
		res += 6, a2 -= 3, b6--;
	
	// 一个六人桌放一个 二人寝 + 一个四人寝
	while (a2 > 0 && a4 > 0 && b6 > 0)
		res += 6, a4--, a2--, b6--;
	
	// 一个六人桌放一个三人寝和一个二人寝 （空1）
	while (a3 > 0 && a2 > 0 && b6 > 0)
		res += 5, a3--, a2--, b6--;
	
	// 一个四人桌放一个三人寝 （空1） 
	while (a3 > 0 && b4 > 0)
		res += 3, a3--, b4--;
	
	// 一个六人桌放两个两人寝 （空2） 
	while (a2 >= 2 && b6 > 0)
		res += 4, b6--, a2 -= 2; 
	
	// 一个六人桌放一个四人寝 （空2）
	while (a4 > 0 && b6 > 0)
		res += 4, a4--, b6--;
		
	// 一个四桌放一个两人寝
	while (a2 > 0 && b4 > 0)
		res += 2, a2--, b4--; 
	
	// 一个六人桌放一个三人寝 （空3）
	while (a3 > 0 && b6 > 0)
		res += 3, a3--, b6--;
	
	// 一个六人桌放一个二人寝 （空4）
	while (a2 > 0 && b6 > 0)
		res += 2, a2--, b6--;
		
	cout << res << endl; 
}

正解：
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
void solve() {
	int a2, a3, a4, b4, b6;
	cin >> a2 >> a3 >> a4 >> b4 >> b6;
	int res = 0;
	
	// 一个四人桌放一个四人寝
	while (a4 > 0 && b4 > 0)
		res += 4, a4--, b4--;
		
	// 一个四人桌放两个二人寝
	while (a2 >= 2 && b4 > 0)
		res += 4, a2 -= 2, b4--;
	
	// 一个六人桌放两个三人寝
	while (a3 >= 2 && b6 > 0)
		res += 6, a3 -= 2, b6--;
	
	// 一个六人桌放一个 二人寝 + 一个四人寝
	while (a2 > 0 && a4 > 0 && b6 > 0)
		res += 6, a4--, a2--, b6--;
	
	// 一个六人桌放三个二人寝
	while (a2 >= 3 && b6 > 0)
		res += 6, a2 -= 3, b6--;
	
	// 一个六人桌放一个三人寝和一个二人寝 （空1）
	while (a3 > 0 && a2 > 0 && b6 > 0)
		res += 5, a3--, a2--, b6--;
	
	// 一个四人桌放一个三人寝 （空1） 
	while (a3 > 0 && b4 > 0)
		res += 3, a3--, b4--;
	
	// 一个六人桌放两个两人寝 （空2） 
	while (a2 >= 2 && b6 > 0)
		res += 4, b6--, a2 -= 2; 
	
	// 一个六人桌放一个四人寝 （空2）
	while (a4 > 0 && b6 > 0)
		res += 4, a4--, b6--;
		
	// 一个四桌放一个两人寝
	while (a2 > 0 && b4 > 0)
		res += 2, a2--, b4--; 
	
	// 一个六人桌放一个三人寝 （空3）
	while (a3 > 0 && b6 > 0)
		res += 3, a3--, b6--;
	
	// 一个六人桌放一个二人寝 （空4）
	while (a2 > 0 && b6 > 0)
		res += 2, a2--, b6--;
		
	cout << res << endl; 
}

重点在于，四人寝和两人寝的摆放顺序：
C++
1
2
3
4
5
6
7
// 一个六人桌放一个 二人寝 + 一个四人寝
while (a2 > 0 && a4 > 0 && b6 > 0)
	res += 6, a4--, a2--, b6--;

// 一个六人桌放三个二人寝
while (a2 >= 3 && b6 > 0)
	res += 6, a2 -= 3, b6--;

应该先考虑四人寝，再考虑二人寝，因为四人寝可以由二人寝拼成，所以四人寝的优先级更高

# 星际旅行

# 题目大意

小明国庆节准备去某星系进行星际旅行，这个星系里一共有 nn 个星球，其中布置了 mm 道双向传送门，第 ii 道传送门可以连接 aia_i，bib_i 两颗星球（ai≠bia_i \neq b_i 且任意两颗星球之间最多只有一个传送门）。他看中了一款 “旅游盲盒”，一共有 QQ 个盲盒，第 ii 个盲盒里的旅行方案规定了旅行的起始星球 xix_i 和最多可以使用传送门的次数 yiy_i。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买，他想知道能旅行到的不同星球的数量的期望是多少。

# 数据范围

  • 对于 20%20 \% 的评测用例，保证 n≤300n \leq 300。
  • 对于 100%100 \% 的评测用例，保证 n≤1000n \leq 1000，m≤min⁡{n(n−1)2,5n}m \leq \min \left\{\dfrac{n(n - 1)}{2}, 5n\right\}，Q≤50000Q \leq 50000，0≤yi≤n0 \leq y_i \leq n，1≤xi≤n1 \leq x_i \leq n.

# 题解

关键在于，怎么理解只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行这句话，题目正确理解应该是，离指定点不超过指定步数的点的个数

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
int n, m, q, dis[N];
vector<int> g[N];

int bfs(int n, int s, int l) {
	int cnt = 0;
	
	queue<int> q;
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	q.push(s);
	
	while (q.size()) {
		int t = q.front();
		q.pop();
		cnt++; 
		
		if (dis[t] == l)
			continue;
		
		for (int v : g[t])
			if (dis[v] == 0x3f3f3f3f) {
				dis[v] = dis[t] + 1;
				q.push(v);
			}
	}
	
	return cnt;
}

void solve() {
	cin >> n >> m >> q;
	for (int i = 1, x, y; i <= m; i++)
		cin >> x >> y, g[x].push_back(y), g[y].push_back(x);
		
	double res = 0;
	for (int i = 1, f, t; i <= q; i++) {
		cin >> f >> t;
		res += (1.0 / q) * bfs(i, f, t);
	}
	
	printf("%.2lf", res);
}