A. All-Star
每次操作至多可以把一个点插在根上，因此选择度数最多的点插在根上，然后根据深度标记边的方向。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int,int>;
i32 main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<vi> e(n + 1);
for(int i = 1, x, y; i < n; i ++)
cin >> x >> y, e[x].push_back(y), e[y].push_back(x);
int root = 1;
for(int i = 2; i <= n; i ++)
if(e[i].size() > e[root].size()) root = i;
vi vis(n + 1);
vector<pii> res;
queue<int> q;
q.push(root), vis[root] = 1;
while(not q.empty()) {
int x = q.front();
q.pop();
for(auto y : e[x]) {
if(vis[y]) continue;
q.push(y), vis[y] = 1;
if(x != root) res.emplace_back(x, y);
}
}
cout << res.size() << "\n";
for(auto [x, y] : res)
cout << root << " " << x << " " << y << "\n";
return 0;
}
D. Donkey and Puss in Boots
对于后手来说，只要剩下的石子总和大于\(n\) 就一定可以进行一次操作，并且一次操作把所有的石子全部取完。因此先手要做的就是通过一步操作使得石子总和小于\(n\)。因此先手有一定会选择最多的一堆石子。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using vi = vector<i64>;
i32 main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
i64 n;
cin >> n;
vi a(n);
for(auto &i : a) cin >> i;
if (std::count(a.begin(), a.end(), 0) == n){
std::cout << "Puss in Boots\n";
return 0;
}
if(accumulate(a.begin(), a.end(),0ll) - ranges::max(a) < n)
cout << "Donkey";
else cout << "Puss in Boots";
return 0;
}
G. Shrek's Song of the Swamp
简单的 dp，记录一下上一次出现的位置就好了。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int,int>;
i32 main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vi a(n + 1), lst(n + 1);
map<int,int> vis;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
lst[i] = vis[a[i]], vis[a[i]] = i;
}
vi f(n + 1);
for(int i = 1, j; i <= n ; i ++) {
f[i] = f[i - 1], j = lst[i];
if(j - 1 >= 0) f[i] = max({f[i], f[j - 1] + 2, f[j] + 1});
}
cout << f[n] << "\n";
return 0;
}
H. Shreckless
贪心考虑要给每行至少安排一个逆序对，我们给每一列从大到小排序。然后从后向前贪心考虑相邻的两列，可以构成的逆序对的个数。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using vi = vector<int>;
void solve(){
int n, m;
cin >> m >> n;
vector a(n, vi(m));
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
cin >> a[j][i];
for (int i = 0; i < n; ++i) ranges::sort(a[i], greater<>());
int l = 0, r, cnt = 0;
for (int i = n - 1; i > 0; --i) {
r = l, l = 0;
for (int j = r; j < m; ++j) {
if (a[i][j] < a[i - 1][l]) {
l ++, cnt ++;
}
}
}
if (cnt >= m) cout << "YES\n";
else cout << "NO\n";
}
i32 main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while(T --) solve();
return 0;
}
J. Make Swamp Great Again
如果三元组有两个数是目标数，就可以一次操作把三元组中所有的数变为目标数。
如果三元组中目标数是最大值或最小值，需要两次操作就能三元组中所有数变为目标数。
如果三元组中目标数既不是最大值，也不是最小值，需要三次操作才能三元组中所有数变为目标数。
因此要统计不是目标数的个数，并且检查目标数是否在某一个三元组出现两次或是某个三元组的最大或最小值。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using vi = vector<int>;
i32 main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
map<int,vi> pos;
vi a(n);
for(int i = 0, x; i < n; i ++)
cin >> a[i], pos[a[i]].push_back(i);
for(int i = 0, ret, f; i < n; i ++) {
ret = n - pos[a[i]].size(), f = 1;
for(auto j : pos[a[i]]){
if(f == 0) break;
for(int l = j - 2; l <= j and f; l ++) {
if(max({a[(l + n) % n], a[(l + 1 + n) % n], a[(l + 2 + n) % n]}) == a[j]) f = 0;
if(min({a[(l + n) % n], a[(l + 1 + n) % n], a[(l + 2 + n) % n]}) == a[j]) f = 0;
}
}
cout << ret + f << " ";
}
return 0;
}
K. Intrusive Donkey
我们用线段树可以维护出每一个字母出现次数。对于修改操作\([l,r]\),实际上我们可以通过在前缀和上二分来快速定位左右端点对应的字母。并且每次操作至多会有两个字母是没有被完全包围的。因此我们可以用单点加法和区间乘法来实现修改。查询操作也是用在前缀和上二分实现。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
struct Info{
i64 value, mul;
Info(i64 value = 0) : value(value) {
mul = 1;
}
i64 val() const {
return value * mul;
}
Info operator+(const Info &b) {
Info ret;
ret.value = val() + b.val();
ret.mul = 1;
return ret;
}
};
struct Node {
i32 l, r;
Info info;
Node *left, *right;
Node(i32 p, i64 v = 1) : info(v) {
l = r = p;
left = right = nullptr;
}
Node(i32 l, i32 r, Node *left, Node *right)
: l(l), r(r), left(left), right(right) {
info = left -> info + right -> info;
}
};
void maintain(Node *cur) {
if(cur -> left == nullptr) return;
cur -> info = cur -> left -> info + cur -> right -> info;
return;
}
void pushdown(Node *cur) {
if(cur -> info.mul == 1) return;
cur -> info.value *= cur -> info.mul;
if(cur -> left != nullptr) {
cur -> left -> info.mul *= cur -> info.mul;
cur -> right -> info.mul *= cur -> info.mul;
}
cur -> info.mul = 1;
return;
}
Node *build(i32 l, i32 r) {
if(l == r) return new Node(l);
i32 mid = (l + r) / 2;
auto left = build(l, mid) , right = build(mid + 1, r);
return new Node(l, r, left, right);
}
Info query(i32 l, i32 r, Node *cur) {
if(cur == nullptr) return Info();
if(cur -> r < l or cur -> l > r) return Info();
if(l <= cur -> l and cur -> r <= r) return cur -> info;
pushdown(cur);
return query(l, r, cur -> left) + query(l, r, cur -> right);
}
i64 pre(i32 i, Node *cur) {
return query(1, i, cur).val();
}
void update_add(i32 p, i64 x, Node *cur) {
if(cur == nullptr) return;
if(p > cur -> r or p < cur -> l) return;
pushdown(cur);
if(p == cur -> l and cur -> r == p) {
cur -> info.value += x;
return;
}
update_add(p, x, cur -> left), update_add(p, x, cur -> right);
maintain(cur);
return;
}
void modify_mul(i32 l, i32 r, i64 x, Node *cur) {
if(cur == nullptr) return;
if(l > cur -> r or r < cur -> l) return;
pushdown(cur);
if(l <=cur -> l and cur -> r <= r) {
cur -> info.mul *= x;
return;
}
modify_mul(l, r, x, cur -> left), modify_mul(l, r, x, cur -> right);
maintain(cur);
return;
}
i32 upper(i64 x, Node *cur){
if(cur -> l == cur -> r) return cur -> l;
pushdown(cur);
if(cur -> left -> info.val() < x) {
x -= cur -> left -> info.val();
return upper(x, cur -> right);
} else {
return upper(x, cur -> left);
}
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, q;
cin >> n >> q;
string s;
cin >> s;
s = " " + s;
auto root = build(1, n);
while(q --) {
int op;
cin >> op;
if(op == 1) {
i64 l, r;
cin >> l >> r;
i32 idxl = upper(l, root);
i32 idxr = upper(r, root);
if(idxl != idxr) {
i64 addl = pre(idxl, root) - l + 1;
i64 addr = query(idxr, idxr, root).val() - (pre(idxr, root) - r);
update_add(idxr, addr, root);
if(idxl + 1 <= idxr - 1) {
modify_mul(idxl + 1, idxr - 1, 2, root);
}
update_add(idxl, addl, root);
} else {
update_add(idxl, r - l + 1, root);
}
} else {
i64 x;
cin >> x;
cout << s[upper(x, root)] << "\n";
}
}
return 0;
}