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");
}赛后补。要把相同颜色的大理石放在一起。首先要注意到其实颜色之间的逆序是独立的，每次交换不影响两种颜色和其他颜色的逆序，同时可以远程交换（相当于只是提前做了而已）。cost[i][j]表示把颜色i全部排在颜色j之前所需的“内部”交换次数，也就是把i和j都抽出来单独看，不理其他颜色，这个可以用归并排序求出来。然后算法就对了，不过可以优化（？不一定是优化），因为每次往二进制状态中加入新的k，要对i中所有已有的1计算一次cost[j][k]，假如用cost2[i][j]表示二进制状态为i的所需的值就可以……（浪费自己的空间？）其实这的确是优化，因为代码中用的i^j会被多次计算，因为是刷表法。花一点空间挺不错的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[1 << 20];
ll cost[20][20];
ll cost2[1 << 20][20];
int a[400005];
vector<int> pos[20];
ll calc(int id1, int id2) {
if(id1 == id2)
return 0;
//使得id1全部在id2前面
int n = pos[id1].size();
int m = pos[id2].size();
int i = 0, j = 0;
int cnt = 0;
ll sum = 0;
//i全部在j前面，计算逆序
while(i < n || j < m) {
if(i == n) {
++j;
} else if(j == m) {
sum += cnt;
++i;
} else {
if(pos[id1][i] <= pos[id2][j]) {
sum += cnt;
++i;
} else {
++cnt;
++j;
}
}
}
return sum;
}
const int MAXN = 20;
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
--a[i];
pos[a[i]].push_back(i);
}
for(int i = 0; i < MAXN; ++i) {
for(int j = 0; j < MAXN; ++j)
cost[i][j] = calc(i, j);
}
for(int i = 1; i < (1 << MAXN); ++i) {
for(int k = 0; k < MAXN; ++k) {
int j = 1 << k;
if(i & j) {
int t = i ^ j, t2 = t & -t;
int idt2 = __builtin_ffs(t2) - 1;
cost2[t][k] = cost2[t ^ t2][k] + cost[idt2][k];
}
}
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i < (1 << MAXN); ++i) {
for(int k = 0; k < MAXN; ++k) {
int j = 1 << k;
if(i & j)
dp[i] = min(dp[i], dp[i ^ j] + cost2[i ^ j][k]);
}
}
printf("%lld\n", dp[(1 << MAXN) - 1]);
}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]);
}
}F - The Number of Products
给一个数列，求这个数列的所有子区间，统计子区间积为正数、负数和零的数量。
首先一个非常简单的开头就是容斥掉，含有0的就直接0了，所以我们在不含0的段里面求出里面的-1和+1的数量，容斥一下就是0的数量。
考虑一个只有+1和-1的数列，dpm[i]表示以i为结尾的积为-1的区间的数量，dpp[i]就是+1的区间的数量，发现什么？每次遇到+1的时候+1的区间会+1，每次遇到-1的时候正负区间数量会刚好换过来，然后-1的数量+1，而遇到0的时候把这两个直接清空。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200005];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // localll
int n;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if(a[i] > 0)
a[i] = 1;
else if(a[i] < 0)
a[i] = -1;
}
ll sump1 = 0, summ1 = 0;
int dpp1 = 0, dpm1 = 0;
for(int i = 1; i <= n; ++i) {
if(a[i] == 1) {
dpp1 += 1;
sump1 += dpp1;
summ1 += dpm1;
} else if(a[i] == -1) {
swap(dpp1, dpm1);
dpm1 += 1;
sump1 += dpp1;
summ1 += dpm1;
} else {
dpp1 = 0;
dpm1 = 0;
}
}
printf("%lld %lld %lld\n", summ1, 1ll * (n + 1)*n / 2 - summ1 - sump1, sump1);
}
}H - Berland Prospect
给一个数列，升序的，求他的一个最长子序列，满足这个子序列是等差数列。
林哥说得对，这个东西像埃筛一样，每次步进一个固定的值把这堆数全部筛掉。实测vector不需要reserve更快，比静态数组还快，不清楚为什么，总之高速的STL+1，一般开O2的地方大胆STL。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, ans;
bool f[3005][3005];
vector<ll> v[3005];
ll a[3005];
void check(int x, ll y) {
int res = 1;
while(1) {
int t = lower_bound(v[x].begin(), v[x].end(), y) - v[x].begin();
if(t == v[x].size() || v[x][t] != y || f[x][x + t + 1])
break;
res++;
f[x][x + t + 1] = 1;
x = x + t + 1;
}
ans = max(ans, res);
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d", &n);
ans = 0;
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for(int i = 1; i <= n; i++) {
v[i].reserve(n - i);
for(int j = i + 1; j <= n; j++)
v[i].push_back(a[j] - a[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < v[i].size(); j++)
if(!f[i][i + j + 1])
check(i, v[i][j]);
}
printf("%d\n", ans);
}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);
}