The 1st Universal Cup. Stage 8: Slovenia
D. Deforestation
这道题出题人比较谜语人，对于一个分叉点，只能选择若干个儿子和父亲组成一组，剩下的儿子之间不能相互组合。所以从叶子节点开始贪心处理就好。对于一个父亲他有若干个儿子，就贪心的选择剩下部分更小的儿子。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using vi = vector<int>;
constexpr int inf = 1E18;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int w;
cin >> w;
int res = 0;
auto dfs = [&](auto &&self) -> int {
int v, n;
cin >> v >> n;
vector<int> t(n);
for (int x; auto &i: t)
x = self(self), res += x / w, i = x % w;
sort(t.begin(), t.end());
int cnt = 0;
for (auto i: t) {
if (cnt + i <= w) cnt += i;
else res++;
}
return v + cnt;
};
res += ( dfs(dfs) + w - 1 ) / w;
cout << res << "\n";
return 0;
}
E. Denormalization
因为每次除的数字相同，所以数组的比值并不会发生改变，只要先枚举出一个数，然后根据比值算出其他的数，然后验证一下最大公约数就好。但问题是枚举哪一个数呢？我通过罚时试出来枚举最大值，其他值会被卡精度
#include <bits/stdc++.h>
using namespace std;
using ldb = long double;
#define int long long
constexpr ldb eps = 1E-6;
int32_t main() {
int n;
cin >> n;
vector<ldb> a(n);
for (auto &i: a)
cin >> i;
int t = max_element(a.begin(), a.end()) - a.begin();
for (int i = 0; i < n; i++)
if( i != t ) a[i] /= a[t];
a[t] = 1;
vector<int> b(n);
for (b[t] = 1; b[t] <= 10000; b[t]++) {
int d = b[t];
for (int i = 0; i < n; i++) {
if (i == t) continue;
ldb x = (ldb) b[t] * a[i];
if (x - floor(x) < eps) b[i] = floor(x);
else if (ceil(x) - x < eps) b[i] = ceil(x);
else {
d = -1;
break;
}
d = gcd(d, b[i]);
}
if (d != 1) continue;
for (auto i: b)
cout << i << "\n";
return 0;
}
return 0;
}
L. The Game
阅读题加模拟题，读懂之后很好写
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int32_t main() {
vi pile(98);
for (auto &i: pile) cin >> i;
reverse(pile.begin(), pile.end());
vector<vi> que(4);
que[0].push_back(1);
que[1].push_back(1);
que[2].push_back(100);
que[3].push_back(100);
vi hand;
for (int i = 0; i < 8; i++)
hand.push_back(pile.back()), pile.pop_back();
while (true) {
int op = -1;
auto it = hand.begin();
for (; it != hand.end(); it = next(it)) {
if (que[0].back() > *it and que[0].back() - *it == 10) {
op = 0;
break;
} else if (que[1].back() > *it and que[1].back() - *it == 10) {
op = 1;
break;
} else if (que[2].back() < *it and *it - que[2].back() == 10) {
op = 2;
break;
} else if (que[3].back() < *it and *it - que[3].back() == 10) {
op = 3;
break;
}
}
if (op != -1) {
que[op].push_back(*it);
hand.erase(it);
} else {
it = hand.begin();
auto jt = it;
int deta = 1e9;
for (int dd, opp; it != hand.end(); it = next(it)) {
dd = 1e9, opp = -1;
if (que[0].back() < *it and *it - que[0].back() < dd) {
dd = *it - que[0].back(), opp = 0;
}
if (que[1].back() < *it and *it - que[1].back() < dd) {
dd = *it - que[1].back(), opp = 1;
}
if (que[2].back() > *it and que[2].back() - *it < dd) {
dd = que[2].back() - *it, opp = 2;
}
if (que[3].back() > *it and que[3].back() - *it < dd) {
dd = que[3].back() - *it, opp = 3;
}
if (opp == -1) continue;
if (dd < deta)
deta = dd, jt = it, op = opp;
}
if (op == -1) break;
que[op].push_back(*jt);
hand.erase(jt);
}
// 第二张
op = -1;
it = hand.begin();
for (; it != hand.end(); it = next(it)) {
if (que[0].back() > *it and que[0].back() - *it == 10) {
op = 0;
break;
} else if (que[1].back() > *it and que[1].back() - *it == 10) {
op = 1;
break;
} else if (que[2].back() < *it and *it - que[2].back() == 10) {
op = 2;
break;
} else if (que[3].back() < *it and *it - que[3].back() == 10) {
op = 3;
break;
}
}
if (op != -1) {
que[op].push_back(*it);
hand.erase(it);
} else {
it = hand.begin();
auto jt = it;
int deta = 1e9;
for (int dd, opp; it != hand.end(); it = next(it)) {
dd = 1e9, opp = -1;
if (que[0].back() < *it and *it - que[0].back() < dd) {
dd = *it - que[0].back(), opp = 0;
}
if (que[1].back() < *it and *it - que[1].back() < dd) {
dd = *it - que[1].back(), opp = 1;
}
if (que[2].back() > *it and que[2].back() - *it < dd) {
dd = que[2].back() - *it, opp = 2;
}
if (que[3].back() > *it and que[3].back() - *it < dd) {
dd = que[3].back() - *it, opp = 3;
}
if (opp == -1) continue;
if (dd < deta)
deta = dd, jt = it, op = opp;
}
if (op == -1) break;
que[op].push_back(*jt);
hand.erase(jt);
}
for (int i = 0; !pile.empty() and i < 2; i++)
hand.push_back(pile.back()), pile.pop_back();
}
for (auto it: que) {
for (auto i: it)
cout << i << " ";
cout << "\n";
}
for (auto i: hand)
cout << i << " ";
cout << "\n";
reverse(pile.begin(), pile.end());
for (auto i: pile)
cout << i << " ";
cout << "\n";
return 0;
}