GYM 105293 C
题目描述
有 \(N\) 个怪物排成一排，第 \(i\) 个怪物的血量为 \(h_i\)。当一个怪物的血量 \(h_i\le 0\) 时，则它死亡。
你可以进行以下操作：
- 选择一个正整数 \(x\)。
- 找到第一个 \(h_i\ge x\) 的 \(i\)，并令 \(h_i\leftarrow h_i -x\)。
- 如果该次操作没有影响到任何怪物，或有怪物死亡，则游戏结束。
求在在游戏结束前能做的最多操作。
思路
我们考虑尽量让前面的怪物血量降至 \(1\)，接着去令后面的怪物血量降至 \(1\)。
在打后面的怪物时，为了不打中前面的，所以必须保证 \(x>h_i\)。
假设现在最少能打 \(x\)，那么很明显最多能打 \(\lceil\frac{h_i}{x}\rceil-1\) 次。
时空复杂度均为 \(O(N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 300001;
int t, n, a[MAXN], Max = 1;
ll ans;
void Solve() {
cin >> n;
ans = 0, Max = 1;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 1; i <= n; ++i) {
if(Max < a[i]) {
ans += (a[i] + Max - 1) / Max - 1, a[i] = 1;
}
Max = max(Max, a[i] + 1);
}
cout << ans + 1 << "\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}
GYM 105293 D
题目描述
给定一个集合 \(S=\{1,2,\dots,N\}\)，你可以对其进行以下操作恰好 \(N-1\) 次：
- 选择两个 \(S\) 中的数 \(x,y\)，从 \(S\) 中删除他们，并插入 \(x-y\)。
求是否能有一种方法使得最终 \(S=\{m\}\)。如果有，则构造一种方案。
思路
我们先证明，假设我们已经把 \(S\) 分成了两个集合 \(A,B\)，且 \(\sum \limits_{x\in A} x - \sum \limits_{x\in B}x=m\)，且 \(A,B\ne \varnothing\)，那么一定存在一种方案符合要求。具体如下：
- 首先我们令 \(B_1\) 减去 \(A_2,\dots,A_{|A|}\)。
- 接着我们令 \(A_1\) 减去 \(B_1,B_2,\dots,B_{|B|}\)。
这样最终的值为 \(A_1-(B_1-A_2-\dots-A_{|A|})-B_2-\dots-B_{|B|}=\sum \limits_{x\in A} x - \sum \limits_{x\in B}x=m\)，符合要求。
又因为我们能凑出 \(1+2+\dots+N-\sum 2x\)，所以 \(m\) 的奇偶性必须与 \(1+2+\dots+N\) 相同，并且 \(m\ne 1+2+\dots+N或-1-2-\dots-N\)。
如果满足上述条件，那么我们贪心地求 \(A,B\)。先令 \(S=1+2+\dots+N\)，接着倒着枚举 \(1\) 到 \(N\)。只要 \(S-x\ge m\) 就令 \(x\in B\)。否则令 \(x\in A\)。
最后使用上述方法构造即可。
时空复杂度均为 \(O(N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int t, n;
ll m, sum;
vector<ll> a, b;
void Solve() {
cin >> n >> m;
if(1ll * (1 + n) * n / 2 % 2 != (m % 2 + 2) % 2 || m == 1ll * (1 + n) * n / 2 || m == -1ll * (1 + n) * n / 2) {
cout << "NO\n";
return;
}
cout << "YES\n";
sum = -1ll * (1 + n) * n / 2, a.clear(), b.clear();
for(int i = n; i >= 1; --i) {
if(sum + 2ll * i <= m) {
sum += 2 * i, a.emplace_back(i);
}else {
b.emplace_back(i);
}
}
for(int i = 1; i < int(a.size()); ++i) {
cout << b[0] << " " << a[i] << "\n";
b[0] -= a[i];
}
for(int i = 0; i < int(b.size()); ++i) {
cout << a[0] << " " << b[i] << "\n";
a[0] -= b[i];
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}