2023校赛复盘

发表于 更新于 分类于 阅读次数：

2023校赛复盘

我是个菜菜。

链接：

T1 卷无止境

  • 签到题。
  • 取 30 个奖项的的最高分即可。
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
//@Dreamskycx
#include <bits/stdc++.h>
#define ll long long
#define MAXN 10000
using namespace std;

int score[5][4] = {{0, 0, 0, 0}, {200, 100, 50, 25}, {100, 75, 25, 15}, {75, 25, 15, 15}, {20, 15, 10, 5}};
int type[35];
int ans;

void solve() {
	int n, a, b, c;
	memset(type, 0, sizeof(type));
	ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b >> c;
		type[a] = max(type[a], score[b][c]);
	}
	for (int i = 1; i <= 30; i++) {
		ans += type[i];
	}
	cout << ans << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

T2 测样例

  • $\sum_{i=1}^ni(i-1)=\frac{(n-1)n(n+1)}{3}$，详细证明略。
  • 根据公式计算即可，需要注意的是需要使用 unsigned long long，且需要提前将 $n-1,n+1,n+1$ 这三个数剔除 3 的因子，以防止溢出。
  • 参照校网赛 T1 。
  • 复杂度 $O(T)$ 。
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
//@Dreamskycx
#include <bits/stdc++.h>
#define ll long long
#define MAXN 10000
using namespace std;

void solve() {
	unsigned long long n, a, b, c, ans;
	cin >> n;
	a = n - 1;
	b = n;
	c = n + 1;
	if (a % 3 == 0)
		a /= 3;
	else if (b % 3 == 0)
		b /= 3;
	else if (c % 3 == 0)
		c /= 3;
	ans = a * b * c;
	cout << ans << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}
  • 该题亦可以用前缀和，不需要考虑数据范围的问题。
  • 复杂度 $O(T+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
//@Dreamskycx
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MAXN 10000
using namespace std;
ull ans[4000000];

void solve() {
	int n;
	cin >> n;
	cout << ans[n] << endl;
}

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= 3000000; i++) {
		ans[i] = ans[i - 1] + (ull)i * (i - 1);
	}
	while (t--)
		solve();
	return 0;
}

T3 又是杠杆

  • 对于一个点 $i$ ，其上的质量为 $m_i$ ，杠杆的位置为 $j$ ，取杠杆左侧的力矩为负力矩，杠杆右侧的力矩为正力矩，我们可以很容易地统计出力矩为 $m_i(i-j)$。
  • 因此，只要统计各个点的质量和 $\sum_{i=1}^n m_i$ 以及加权的质量和 $\sum_{i=1}^n m_ii$。可以很容易地看到，所有点的力矩和就是 $S=\sum_{i=1}^n m_ii-j\sum_{i=1}^n m_i$。
  • 如果这个力矩为正，很容易想到在左边最远端（也就是 i=1）的时候放置物品，力矩为 $S/(j-1)$，反之，在右边最远端（i=n）放置物品，力矩为 $S/(n-j)$。对于 n 个点进行依次判断即可（也可以二分？）。
  • 需要特别注意的是，在只有一个点的时候，是恒平衡的，而在两个点的时候，只要这两个点的值都不为 0 ，就不存在平衡的可能。
  • 注意最简分数和 gcd 的运用。
  • 会爆 int ，要用 long long 。
  • 复杂度 $O(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
//@Dreamskycx
#include <bits/stdc++.h>
#define ll long long
#define MAXN 10000
using namespace std;
ll wei[200005];
ll sum;
ll basicsum;
ll dis, chazhi, dispd;
ll div1 = 1e13, div2;
ll savediv1, savediv2;
ll pd;
int flag = 0;

ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

void solve() {
	int n;
	cin >> n;
	//cinnum
	for (int i = 1; i <= n; i++) {
		cin >> wei[i];
		sum += wei[i];
		basicsum += wei[i] * i;
	}
	//
	dis = -1 * basicsum;
	for (int i = 1; i <= n; i++) {
		dis += sum;
		dispd = dis;
		if (i == 1 || i == n) {
			if ((sum - wei[i]) == 0) {
				cout << "0/1" << endl;
				return;
			} else {
				continue;
			}
		}
		flag = 1;
		if (dispd == 0) {
			cout << "0/1" << endl;
			return;
		} else if (dispd < 0) {
			dispd = abs(dispd);
			chazhi = abs(i - 1);
			pd = dispd * div2 - chazhi * div1;
			if (pd < 0) {
				div1 = dispd / gcd(dispd, chazhi);
				div2 = chazhi / gcd(dispd, chazhi);
			}
		} else if (dispd > 0) {
			chazhi = abs(n - i);
			pd = dispd * div2 - chazhi * div1;
			if (pd < 0) {
				div1 = dispd / gcd(dispd, chazhi);
				div2 = chazhi / gcd(dispd, chazhi);
			}
		}
	}
	if (flag)
		cout << div1 << "/" << div2 << endl;
	else {
		cout << "1/0" << endl;
	}
	return ;
}

int main() {
	int t = 1;
	while (t--)
		solve();
	return 0;
}

T4 燃起来了

  • 期望题。
  • 对于一段燃烧的时间段，我们可以将其分为 $d=\frac{x}{y}$ 次成功判定和最后一段剩余燃烧时间 $r=x%y$ 。
  • 记成功概率 $p=\frac{a}{b}$ ，可以发现在经过 $i$ 次失败后，第$i+1$次成功的燃烧时间长度期望为 $E_i=y+p \cdot E_0+(1-p) \cdot E_{i+1}(i=0,1..d-1)$ ，且最后的剩余燃烧时间期望为 $r$。
  • 此时 $E_0$ 即为持续燃烧的时间 $E_0=r+y\sum_{i=1}^d(\frac{1}{1-p})^i$，也就是$E_0=r+y\cdot\frac{(1-p)^d-1}{(1-p)^d\cdot(-p)}$。
  • 需要注意到当 $p$ 为 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
//@Dreamskycx
#include <bits/stdc++.h>
#define ll long long
#define MAXN 10000
const ll MOD = 1e9 + 7;
using namespace std;

ll power(ll a, ll b) {
	ll ans = 1 % MOD;
	while (b) {
		if (b & 1)
			ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return ans;
}

void solve() {
	ll a, b, x, y;
	cin >> a >> b >> x >> y;
	if (a == b && y <= x) {
		cout << "forever" << endl;
		return;
	}
	ll p = a * power(b, MOD - 2) % MOD, d = x / y, r = x % y;
	ll ans = (y * (power(1 - p, d) - 1) % MOD * power(power(1 - p, d) * (-p) % MOD, MOD - 2) + r) % MOD;
	ans = (ans + MOD) % MOD;
	cout << ans << endl;

}

int main() {
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}