A - Yellow Cards
给一堆黄牌，给1队、2队的人数和每个人还能吃的黄牌数，求最少和最多罚下去几个人？
数据量过小，直接模拟即可，最少就给所有非1的分配完之后，取黄牌数和人数的最小值（貌似题目数据连这个都不卡）。最多就集中火力罚当前承受度最低的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int> > pq2;
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // localll
int a1, a2, k1, k2, n;
scanf("%d%d%d%d%d", &a1, &a2, &k1, &k2, &n);
for(int i = 1; i <= a1; ++i) {
pq.push(k1);
pq2.push(k1);
}
for(int i = 1; i <= a2; ++i) {
pq.push(k2);
pq2.push(k2);
}
int n1 = n;
while(pq.top() > 1 && n1) {
int tmp = pq.top();
pq.pop();
int t = min(tmp - 1, n1);
tmp -= t;
n1 -= t;
pq.push(tmp);
}
printf("%d ", min(a1 + a2, n1));
int ans2 = 0, n2 = n;
while(pq2.size() && pq2.top() <= n2) {
ans2++;
n2 -= pq2.top();
pq2.pop();
}
printf("%d\n", ans2);
}B - Interesting Vertices
树形dp入门经典？还WA了好多发以示敬意？类似换根法树形dp，首先钦定1作为根求出每个节点子树的染色情况，然后从1开始计算ans。需要注意的是，传入p=-1的时候ans[1]是只和1是不是被染色有关的，然后进入其中的一棵子树v之后，u以及上面的点都会变成新的子树，还有u的除v以外的子树，这里要特殊处理u以及上面的点，很容易搞错。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
bool dp[MAXN];
bool color[MAXN];
bool ans[MAXN];
vector<int> G[MAXN];
void dfs(int u, int p) {
for(auto v : G[u]) {
if(v == p)
continue;
dfs(v, u);
dp[u] |= dp[v];
}
}
int cnt;
void dfs2(int u, int p, bool pc) {
ans[u] = color[u] ? false : (p == -1 ? true : pc);
int cntdpv = 0;
for(auto v : G[u]) {
if(v == p)
continue;
cntdpv += dp[v];
}
for(auto v : G[u]) {
if(v == p)
continue;
if(color[u])
dfs2(v, u, true);
else {
if(cntdpv >= 2)
dfs2(v, u, true);
else if(cntdpv == 1)
dfs2(v, u, dp[v] ? pc : true);
else
dfs2(v, u, pc);
}
ans[u] &= dp[v];
}
if(ans[u])
++cnt;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // localll
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= k; ++i) {
int x;
scanf("%d", &x);
color[x] = 1;
dp[x] = 1;
}
for(int i = 1; i <= n - 1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1);
dfs2(1, -1, false);
printf("%d\n", cnt);
bool fir = true;
for(int i = 1; i <= n; ++i) {
if(ans[i]) {
if(fir) {
printf("%d", i);
fir = false;
} else
printf(" %d", i);
}
}
if(cnt)
printf("\n");
}E - Painting The Fence
贪心，类似当时和林哥他们做的那个修学分的树形，当时是每次推进剩余深度的点，这里是每次尽可能选余量最多的。要注意并不是一定要连续涂k块，这个和韩国首尔那场不同，首尔那一场是规定要涂k块。贪心的道理也是，决策包容性。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue< pair<int, int> > pq;
pair<int, int> tmpp, tmpq;
int ans[200005];
int lx[200005];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // localll
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; ++i) {
int ai;
scanf("%d", &ai);
pq.push({ai, i});
}
for(int i = 1; i <= n; ++i) {
tmpp.second = -1;
if(lx[i - 1] == k) {
if(!pq.empty() && pq.top().second == ans[i - 1]) {
tmpp = pq.top();
pq.pop();
}
}
if(pq.empty()) {
puts("-1");
exit(0);
}
tmpq = pq.top();
pq.pop();
ans[i] = tmpq.second;
tmpq.first--;
if(tmpq.first != 0)
pq.push(tmpq);
if(ans[i] == ans[i - 1])
lx[i] = lx[i - 1] + 1;
else
lx[i] = 1;
if(tmpp.second != -1)
pq.push(tmpp);
}
for(int i = 1; i <= n; ++i) {
printf("%d%c", ans[i], " \n"[i == n]);
}
}J - Monocarp and T-Shirts
有n场比赛，每场比赛申请一个型号ai，得到所有的衣服之后把对应号数的衣服给朋友们，求满足的朋友们的数量的期望。
根据期望的线性性，朋友的数量的期望直接等于每个朋友被满足的概率求和。
一个朋友被满足，需要x，x-1，x+1至少其中一个被满足，记录哪个状态出现过然后容斥一下就直接出来了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200005];
const int mod = 998244353;
int qpow(ll x, int n) {
ll res = 1;
while(n) {
if(n & 1) {
res = res * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return res;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // localll
int n, p, q, r;
scanf("%d%d%d", &n, &p, &q);
p = 1ll * p * qpow(1e6, mod - 2) % mod;
q = 1ll * q * qpow(1e6, mod - 2) % mod;
r = ((1 - p - q) % mod + mod) % mod;
int pq = 1ll * p * q % mod;
int qr = 1ll * q * r % mod;
int pr = 1ll * p * r % mod;
int pqr = 1ll * pq * r % mod;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
ll sum = 0;
for(int i = 1; i <= n; ++i) {
bool haveq = false, havep = false;
if(i - 1 >= 1 && a[i - 1] == a[i] - 1) {
sum += q;
haveq = true;
}
if(i + 1 <= n && a[i + 1] == a[i] + 1) {
sum += p;
havep = true;
}
sum += r;
sum %= mod;
if(havep && haveq) {
sum -= pq;
sum -= pr;
sum -= qr;
sum += pqr;
} else {
if(havep)
sum -= pr;
else if(haveq)
sum -= qr;
}
sum %= mod;
if(sum < 0)
sum += mod;
}
printf("%lld\n", sum);
}