第四届辽宁省大学生程序设计竞赛（正式赛）A B H F M C

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A题，签到。

print(27)
1

B题，注意精度问题。将d除以100后，需要保证前4位是相同的，因为四舍五入，所以第五位可能需要进位或舍去。那么fabs(d - v)应该要小于5e-5，这样就保证了四舍五入后仍然是对的。如果是乘100，用四舍五入判断可能更简单（

void solve() {
	double d; cin>>d; d /= 100;
	for(int i = 1; i <= 10000; ++i) {
		for(int j = 1; j <= i; ++j) {
			double v = (double) j / i;
			if(fabs(v - d) <=5e-5) {
				cout<<i;
				return ;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

H题，判奇偶。

n = int(input())
for _ in range(n):
    a,b,c = list(map(int, input().split(' ')))
    if c % 2 == 0: print("Bob")
    else: print('Alice')
1
2
3
4
5

F题，感觉很经典，找一个点的前面最优和后面最优结果，最后取个max。

void solve() {
	int n; cin>>n;
	vector<int> a(n + 1), pre(n + 1), suf(n + 1);
	for(int i = 1; i <= n; ++i) cin>>a[i];
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < i; ++j) {
			pre[i] = max(pre[i], min(a[i], a[j]) * (i - j));
		}
	}
	for(int i = n; i >= 1; --i) {
		for(int j = n; j > i; --j) {
			suf[i] = max(suf[i], min(a[i], a[j]) * (j - i));
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		ans = max(ans, pre[i] + suf[i]);
	}
	cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

M题，算期望。直接组合数麻烦，但是每次只考虑单个合法字符串的概率容易实现。

const int mod = 1e9 + 7;
LL inv(LL x, LL mod) {
    if(x == 0 || x == 1) return x;
    return (mod - mod/x) * inv(mod % x, mod) % mod;
}
void solve() {
	int a,b,n; cin>>a>>b>>n;
	if(n < 5) {
		cout<<'0'<<endl;
		return ;
	}
	int iv = inv(b,mod);
	int p1 = a * iv % mod;
	int p0 = (1 - p1 + mod) % mod;
	cout<< (n - 4) * p0% mod * p0%mod * p1%mod * p1%mod *p1%mod<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

C题，范围有点小。

感觉是个dp，因为有很多类似题面的dp题。（不会做，看题解补，

看到了一个是用优先队列的，就补了一下这题。

首先考虑，手动打死的怪一定是除它之外所用的爆炸伤害之和还小于它的生命值的，因为不管怎么弄，最坏情况是其他都死了，产生的爆炸伤害之和都没有把其炸死，那么它一定是要手动打死的。同时，对于爆炸伤害相同的怪，优先让血量高的先手动打死，因为爆炸伤害相同，打死血量高的，那么产生的爆炸伤害可能将血量低的炸死，而打死血量低的，能把血量高的炸死那么一定可以把血量低的炸死。

我们用两个优先队列来优先记录血量和爆炸伤害，还需要一个vis数组来判断是否这个下标对应的怪在之前已经死了。

代码如下：

void solve() {
	int n; cin>>n;
	vector<array<int,2>> a(n); // a, b
	vector<int> vis(n);
	int sum = 0, now = 0,cnt = 0;
	for(auto &t: a) cin>>t[0]>>t[1], sum += t[1];

	// 优先队列：一个优先爆炸值，血量； 一个优先血量
    auto cmp1 = [&](auto pre, auto suf) {
		if(pre[1] == suf[1]) return pre[0] < suf[0];
		return pre[1] < suf[1];
	};
    priority_queue<array<int,3>, vector<array<int,3>>, decltype(cmp1)> atk(cmp1);
	auto cmp2 = [&](auto pre, auto suf) {
		return pre[0] > suf[0];
	};
	priority_queue<array<int,3>, vector<array<int,3>>, decltype(cmp2)> hp(cmp2);

	// 找除它之外的所有爆炸值之和仍小于其血量的，手动处理
	for(int i = 0; i < n; ++i) {
		if(sum - a[i][1] >= a[i][0]) {
			atk.push({a[i][0], a[i][1], i});
			hp.push({a[i][0], a[i][1], i});
		} else {
			cnt++; vis[i] = 1;
			now += a[i][1];
		}
	}
	
	// 先将血量低于当前爆炸值的给处理掉
	// 再进行手动处理
	while(atk.size() && hp.size()) {
		while(hp.size() && now >= hp.top()[0]) {
			if(!vis[hp.top()[2]]) now += hp.top()[1];
			vis[hp.top()[2]] = 1;
			hp.pop();
		}
		while(atk.size() && vis[atk.top()[2]]) atk.pop();
		if(atk.empty() || hp.empty()) break;
		cnt++;
		now += atk.top()[1];
		vis[atk.top()[2]] = 1;
		atk.pop();
	}
	cout<<cnt<<endl;
}
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

L题，莫队。待补…