坏了就我的日期和大家不太一样。
注意到ZGC没有计算休假日期，怎么回事呢。
并没有做完全不可做的好题选讲，因为实在是太不可做了，联赛T4难度 = 黑 这个逻辑不是很能理解。
上午调了一上午的 ABC418F 然后发现修改前没有 erase，悲伤。
下午和晚上在带花树上反复开花最终想开了。
[ABC 418F]
神秘矩阵乘法并使用线段树维护，这很 brat。
调了一个上午，这很 nat。
先考虑第二种限制只有一个的情况下，答案是组合数 \binom{n – r + 1}{r}。
考虑对于多个限制，引入矩阵乘法快速计算。
最后发现还有修改，把它放在线段树上维护就可以了。
答案可能还需要乘上一个斐波那契数列。
至于前驱后继这些，用 map 或 set 维护。
代码不贴了，自己没绷住修改前没 erase。
[带花树与一般图匹配]
在非常非常远古的时候我们学会了匈牙利跑二分图匹配。
这个逻辑还可以继续使用，除了碰到奇环就死机。
我们于是考虑把这个奇环缩成一个点，继续操作。
然后就是带花树所蕴含的思想了。
至于具体实现……简而言之就是先黑白染色跑 bfs，并查集维护祖先，缩换的时候先暴力跳求 LCA 然后更改一下记录前驱的 pre 数组（点头
说的很简单但是实现还是较为困难的，放一个板子
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5, M = 5e4 + 5;
int n, m, par[N], st[N];
int h[N], e[M << 1], ne[M << 1], idx;
int match[N], q[N], pre[N];
void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
int find(int x)
{
if (par[x] == x)return x;
else return par[x] = find(par[x]);
}
int dfn[N], timestamp;
int LCA(int a, int b)
{
++ timestamp;
a = find(a), b = find(b);
while (dfn[a] != timestamp)
{
dfn[a] = timestamp;
a = find(pre[match[a]]);
if (b)swap(a, b);
}
return a;
}
int hh, tt;
void blossom(int x, int y, int w)
{
while (find(x) != w)
{
pre[x] = y, y = match[x];
if (st[y] == 2)
{
st[y] = 1;
q[++ tt] = y;
}
if (find(x) == x)par[x] = w;
if (find(y) == y)par[y] = w;
x = pre[y];
}
}
int bfs(int S)
{
for (int i = 1; i <= n; i ++)
{
par[i] = i;
pre[i] = st[i] = 0;
}
hh = 0, tt = 0;
q[0] = S, st[S] = 1;
while (hh <= tt)
{
int u = q[hh ++];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (find(u) == find(j) || st[j] == 2)continue;
if (!st[j])
{
st[j] = 2, pre[j] = u;
if (!match[j])
{
for (int x = j, last; x; x = last)
{
last = match[pre[x]];
match[x] = pre[x];
match[pre[x]] = x;
}
return 1;
}
st[match[j]] = 1;
q[++ tt] = match[j];
}
else
{
int lca = LCA(u, j);
blossom(u, j, lca);
blossom(j, u, lca);
}
}
}
return 0;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m --)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
int res = 0;
for (int i = 1; i <= n; i ++)
{
if (!match[i])res += bfs(i);
}
printf("%d\n", res);
for (int i = 1; i <= n; i ++)printf("%d ", match[i]);
return 0;
}
以下是例题，考虑到带花树部分不变，因此后续只放主函数部分。
然而这题是可做的，否则出题人也不会出。
既然一个框能塞三个球，不妨考虑把一个框拆成三个点两两两边，然后对于符合条件的球，一个框对应三个点都连一下。
跑一下一般图最大匹配，答案是 res – n。
为什么？
- 该框没有球，那么会产生一对虚空的贡献。
- 该框有 1 个球，剩下的两点产生了一对虚空的贡献。
- 该框有 2 个球，内部不再产生多余贡献，但是本来贡献是 0。
- 该框有 3 个球，与 (2) 同理。
于是就这样结束了，建图代码：
void work()
{
idx = timestamp = 0;
memset(dfn, 0, sizeof dfn);
memset(h, -1, sizeof h);
memset(match, 0, sizeof match);
int k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i ++)
{
add(n + i, n + m + i);
add(n + m + i, n + i);
add(n + i, n + 2 * m + i);
add(n + 2 * m + i, n + i);
add(n + m + i, n + 2 * m + i);
add(n + 2 * m + i, n + m + i);
id[n + i] = id[n + m + i] = id[n + 2 * m + i] = i;
}
while (k --)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, n + y);
add(n + y, x);
add(x, n + m + y);
add(n + m + y, x);
add(x, n + 2 * m + y);
add(n + 2 * m + y, x);
}
int res = 0;
for (int i = 1; i <= n + (m * 3); i ++)
{
if (!match[i])res += bfs(i);
}
printf("%d\n", res - n);
for (int i = 1; i <= n; i ++)printf("%d ", id[match[i]]);
puts("");
}
P9792 Bimatching
比上题还容易想。
把男性代表的点拆成两个，并连边。
之后对于女性代表的点，对应两点都连边。
然后跑一般图最大匹配，答案还是 res – n。
怎么回事呢？
- 这个男性没有人匹配，那么自己代表的两点匹配了，因此减去
- 这个男性只有一个女性匹配，该贡献不算
- 这个男性有两个女性匹配，这两对受题目定义只算一对。
建图代码：
void work()
{
idx = timestamp = 0;
memset(dfn, 0, sizeof dfn);
memset(h, -1, sizeof h);
memset(match, 0, sizeof match);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
{
add(i, n + i);
add(n + i, i);
for (int j = 1, x; j <= m; j ++)
{
scanf("%1d", &x);
if (x)
{
add(i, 2 * n + j);
add(2 * n + j, i);
add(n + i, 2 * n + j);
add(2 * n + j, n + i);
}
}
}
int res = 0;
for (int i = 1; i <= m + 2 * n; i ++)
{
if (!match[i])res += bfs(i);
}
printf("%d\n", res - n);
}
然后就可以复健 CSP-S/NOIP 2021~2024 了。
然后可能发现不会的还是不会。
（恼