搬题人：\(\text{D}\color{red}\text{eaphetS}\)
#A. [NOI Online #1 提高组] 序列
不妨把所有的 \(b_i\) 变成 \(b_i-a_i\)，这样所有 \(a_i\) 就变成 \(0\) 了。然后考虑建图。把 \(i\) 号点的权值设为 \(a_i\) 的值，对于每个 \(t_i = 2\) 的操作，在图中连一条无向边 \((u_i,v_i)\)。那么每条这样的边的意义就是把它其中一个端点的部分权值“转运”到另一个端点，但对总权值没有影响。可以看出每个连通块中的任意两点的权值都是可以互相转运的。若某个连通块内所有点的权值之和等于 \(b_i\) 之和，这个连通块就是有解的。答案为 YES 当且仅当所有连通块都有解。下面记点 \(u\) 所在的连通块编号为 \(bel_u\)。
而 \(t_i = 1\) 的操作就可以对总权值产生影响了。我们把它也看成这张图里的一条边，由上面的内容容易看出 \(u_i\) 或 \(v_i\) 连在同一个连通块中的任意一点都是相同的（对该连通块的权值和贡献相同）。那么我们把连通块缩点，在新图上连边 \((bel_{u_i},bel_{v_i})\) 即可。若 \(u_i\) 和 \(v_i\) 所在连通块相同，则将这个连通块打上标记 \(tag = 1\)，表示该连通块内部可以对自身权值和产生 \(2\) 的倍数的贡献。
考虑新图的一条路径 \((x,y)\)（不一定是简单路径），发现若这条路径长度为偶数，则 \(x\) 与 \(y\) 之间的权值也是可以相互转运的（可以画图看一下）。那么对于新图中包含奇环的连通块，任意两点间一定存在一条长度为偶数的路径。也就是说，可以将这个大的连通块再次缩成一个点。由于这个连通块里一定有 \(t_i = 1\) 的边，所以可以认为它的 \(tag = 1\)，那么它有解的条件就是权值和为偶数。
而对于不包含奇环的连通块，它一定是一个二分图。将其黑白染色，那么黑点到黑点、白点到白点的权值都可以互相转运，我们将黑点集和白点集分别缩点。黑点与白点之间只有长度为奇数的路径，即可以将黑点集的权值和 与 白点集的权值和同时加上一个值。那么我们现在已经可以得出这个连通块有解的条件了：
- 权值和为偶数；
- 若该连通块中所有点的 \(tag\) 都为 \(0\)，则黑点和白点的 \(b_i\) 之和相等。
证明比较显然。第二次的“缩点”不需要真缩，DFS 判断一下就可以了。
于是这道题就做完了，复杂度 \(O(Tn)\)。记得开 long long。
#include <bits/stdc++.h>
using namespace std;
struct Node
{
long long u, v;
Node() {}
Node(long long a, long long b) : u(a), v(b) {}
}Edge[100010];
vector<long long> g[100010], h[100010];
long long T, a[100010], bel[100010], bw[100010], sum[100010];
bool tag[100010];
inline void dfs1(long long u, long long c)
{
bel[u] = c;
sum[c] += a[u];
for (long long i = 0; i < g[u].size(); i++)
{
long long v = g[u][i];
if (!bel[v])
dfs1(v, c);
}
}
inline bool dfs2(long long u, long long c, bool& t, long long& sb, long long& sw)
{
if (~bw[u])
return bw[u] == c;
bw[u] = c;
t |= tag[u];
if (!c)
sb += sum[u];
else sw += sum[u];
bool ret = 1;
for (long long i = 0; i < h[u].size(); i++)
{
long long v = h[u][i];
ret &= dfs2(v, c ^ 1, t, sb, sw);
}
return ret;
}
int main()
{
scanf("%lld", &T);
while (T--)
{
long long n, m, p = 0, k = 0;
scanf("%lld %lld", &n, &m);
for (long long i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (long long i = 1; i <= n; i++)
{
long long x;
scanf("%lld", &x);
a[i] = x - a[i];
g[i].clear(), h[i].clear();
}
for (long long i = 1; i <= m; i++)
{
long long t, u, v;
scanf("%lld %lld %lld", &t, &u, &v);
if (t == 1) Edge[++p] = Node(u, v);
else g[u].push_back(v), g[v].push_back(u);
}
memset(bel, 0, sizeof bel);
memset(sum, 0, sizeof sum);
memset(tag, 0, sizeof tag);
for (long long i = 1; i <= n; i++)
if (!bel[i])
dfs1(i, ++k);
for (long long i = 1; i <= p; i++)
if (bel[Edge[i].u] == bel[Edge[i].v])
tag[bel[Edge[i].u]] = 1;
else {
h[bel[Edge[i].u]].push_back(bel[Edge[i].v]);
h[bel[Edge[i].v]].push_back(bel[Edge[i].u]);
}
memset(bw, -1, sizeof bw);
bool ans = 1;
for (long long i = 1; i <= k; i++)
if (bw[i] == -1)
{
bool flag = 0;
long long sumb = 0, sumw = 0;
if (dfs2(i, 0, flag, sumb, sumw))
if (flag)
ans &= (sumb + sumw) % 2 == 0;
else ans &= sumb == sumw;
else ans &= (sumb + sumw) % 2 == 0;
}
printf(ans ? "YES\n" : "NO\n");
}
return 0;
}
#B. Maximize Mex
翻译中有一句话：校长将会从每个社团中各选出一个人。
就是一些人被分为一组，从每组中选一些人出来。
这就很容易想到通过二分图的匹配。
\(\text{mex}\) 运算有一个显而易见的贪心：枚举每个值能否被匹配，第一个找不到的值就是答案。
由于 \(\text{mex}\) 运算的值域与 \(n\) 同级，就可以从这方面入手。
我们从每个能力值 \(p_i\) 向社团 \(c_i\) 建边。
假如枚举的值为 \(i\)，与增广路算法相似，如果 \(i\) 能再找到匹配，那么 \(\text{mex}\) 的值一定会大于 \(i\)，否则就找到了 \(\text{mex}\) 运算的答案。
但如果是这样的话，外层需要枚举到 \(d\)，内层要枚举到最大值 \(W\)，再加上匈牙利算法的单次的时间复杂度 \(O(m)\)，就会使总时间复杂度高达 \(O(dmW)\)，当然会 TLE。
于是就想到了一个玄学优化：用时间戳来优化常数。不知道能不能过。先试一下。
#include <bits/stdc++.h>
#define inf 1000000007
using namespace std;
long long n, m, now, D, T, c[5050], p[5050], d[5050], mat[5050], vis[5050], cnt, head[5050];
struct Node
{
long long v, ti, nxt;
}Edge[5050];
inline void add(long long u, long long v, long long ti)
{
Edge[++cnt].nxt = head[u];
Edge[cnt].v = v;
Edge[cnt].ti = ti;
head[u] = cnt;
}
inline bool dfs(long long x)
{
for (long long i = head[x]; i; i = Edge[i].nxt)
if (Edge[i].ti > T && vis[Edge[i].v] != now)
{
vis[Edge[i].v] = now;
if (mat[Edge[i].v] == -1 || dfs(mat[Edge[i].v]))
{
mat[Edge[i].v] = x;
return true;
}
}
return false;
}
int main()
{
scanf("%lld %lld", &n, &m);
long long W = 0;
for (long long i = 1; i <= n; i++)
{
scanf("%lld", &p[i]);
W = max(W, p[i]);
}
for (long long i = 1; i <= n; i++)
scanf("%lld", &c[i]);
scanf("%lld", &D);
for (long long i = 0; i <= n; i++)
d[i] = inf;
for (long long i = 1, x; i <= D; i++)
{
scanf("%lld", &x);
d[x] = i;
}
for (long long i = 1; i <= n; i++)
add(p[i], c[i], d[i]);
for (long long i = 1; i <= D; i++)
{
T = i;
for (long long j = 0; j <= m; j++)
vis[j] = mat[j] = -1;
bool flag = 0;
for (long long j = 0; j <= W; j++)
{
now = j;
if (!dfs(j))
{
printf("%lld\n", j);
flag = 1;
break;
}
}
if (!flag)
printf("%lld\n", W + 1);
}
return 0;
}
#C. 「2017 山东一轮集训 Day2」Pair
Hall 定理：对于一个二分图 \(G~(X,Y)\)，\(X\) 存在一个匹配的充分必要条件为对于 \(X\) 的任意子集 \(S\)，\(S\) 的邻居个数\(N(S)\) 必须大于等于S的大小。
首先 \(b_i\) 的孙序不影响匹配，有 hall 定理，二分图存在完全匹配当且仅当对于,集合 \(∀X,|N(X)|≥|X|\),再分析 \(a_i\) , 他能匹配的 \(b_i\) 一定是一个后缀，反过来考虑 \(b_i\) 若，对于第 \(i\) 的元素，他能匹配的个数为 \(N_i\),那么大于 \(b_i\) 的元素 \(b_j,b_j≥b_i\) 能匹配的个数 \(N_j≥N_i\), 因此只要每个集合 \(1…i,|N(B_{1…i})|≥|i|\) 就行，我们维护 \(N_i−i\) 的最小值判断它是否大于等于 \(0\) 就行．
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int ans, b[15050], a[15050], n, m, h, min_val[60060], add_val[60060];
inline void pushdown(int K)
{
if (add_val[K])
{
int lc = K << 1, rc = K << 1 | 1;
add_val[lc] += add_val[K];
add_val[rc] += add_val[K];
min_val[lc] += add_val[K];
min_val[rc] += add_val[K];
add_val[K] = 0;
}
}
inline void add(int L, int R, int x = 1, int l = 1, int r = m, int K = 1)
{
if (l >= L && r <= R)
{
add_val[K] += x;
min_val[K] += x;
return;
}
pushdown(K);
int mid = (l + r) >> 1;
if (L <= mid)
add(L, R, x, l, mid, K << 1);
if (R > mid)
add(L, R, x, mid + 1, r, K << 1 | 1);
min_val[K] = min(min_val[K << 1], min_val[K << 1 | 1]);
}
inline int query(int L, int R, int l = 1, int r = m, int K = 1)
{
if (l >= l && r <= R)
return min_val[K];
pushdown(K);
int mid = (l + r) >> 1, ret = INF;
if (L <= mid)
ret = min(query(L, R, l, mid, K << 1), ret);
if (R > mid)
ret = min(query(L, R, mid + 1, r, K << 1 | 1), ret);
return ret;
}
int main()
{
scanf("%d %d %d", &n, &m, &h);
for (int i = 1; i <= m; ++i)
scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
sort(b + 1, b + m + 1);
for (int i = 1; i <= m; ++i)
add(i, i, -i);
for (int i = 1; i <= n; ++i)
{
int p = lower_bound(b + 1, b + m + 1, h - a[i]) - b;
add(p, m);
if (i >= m)
{
if (query(1, m) >= 0)
ans++;
int p = lower_bound(b + 1, b + m + 1, h - a[i - m + 1]) - b;
add(p, m, -1);
}
}
printf("%d", ans);
return 0;
}
#D. 「JOISC 2022 Day3」蚂蚁与方糖
Hall 定理：对于一个二分图 \(G~(X,Y)\)，\(X\) 存在一个匹配的充分必要条件为对于 \(X\) 的任意子集 \(S\)，\(S\) 的邻居个数\(N(S)\) 必须大于等于 \(S\) 的大小。
为方便表述，下文记 \(R_i,B_i\) 分别表示坐标 \(\le i\) 红/蓝点个数。
Hall 定理转为选若干不交区间（这里一个区间是连续一段红点的管辖区间并）\([l_i,r_i]\)，最大化下式：
\(\sum_i(R_{r_i} - R_{l_i - 1}) - \sum_i(B_{r_i + L} - B_{l_i - L - 1})\)
\(=\sum_i(B_{l_i−L−1}−R_{l_i−1})+(R_{r_i}−B_{r_i+L})\)
\(=\sum_i(p_{l_i} + q_{r_i})\)
其中 \(p_i=B_{i−L−1}−R_{i−1}\)，\(q_i=R_{i}−B_{i+L}\)。那也就是说我要交替选取一些 \(p\) 和 \(q\) 使得权值和最大。直接对数轴建立线段树，每个节点上维护 \(f_{0/1,0/1}\) 表示区间内以 \(p/q\) 开头，\(p/q\) 结尾的序列的权值最大值。
那我们考虑修改时如何维护，不难发现 \(p,q\) 数组支持单点修改了。两种修改是本质不同的，需要分类讨论。
- 加入红点
相当于对 \(p[x+1,+∞]\) 后缀 \(−a\)，\(q[x,+∞]\) 后缀 \(+a\)。
看似不好处理，但我们发现对 \(p,q\) 的同一段区间进行一个 \(+a\)，一个 \(−a\) 的操作时，某个决策的改变量只与 \(p,q\) 个数差有关，而这在 \(f\) 中已经做过记录，故 \(f\) 的四个决策并不会改变，其变化只是简单的区间加。那么就可以把这个操作拆成 \(p,q\) 对 \([x,+∞]\) 区间一个 \(+a\)，一个 \(−a\)，然后 \(p_x\) 单点修改。
- 加入蓝点
相当于对 \(p[x+L+1,+∞]\) 后缀 \(+a\)，\(q[x−L,+∞]\) 后缀 \(−a\)。
同理拆成可做的 \([x+L+1,+∞]\) 的一加一减，和 \([x−L,x+L+1]\) 的区间加。后面一个东西就与 \(p,q\) 的个数和有关了，这咋处理？
发现对于 \([x−L,x+L+1]\) 的任意一个子区间，我不可能选出三个及以上的 \(p\)，因为如果选了三个 \(p_x,p_y,p_z\) 且 \(x<y<z\)，则 \([p_y−L,q_y+L]\) 必然会被 \([p_x−L,q_x+L]\) 与 \([p_z−L,q_z+L]\) 的区间并给覆盖，这是不优的：直接去掉 \(y\)，红点区间并不变，而蓝点贡献变少。
那么给长度 \(\le 2L+1\) 的区间的 \(f\) 多加一维 \(k\) 记录区间里选了 \(k\) 个 \(p\) 时的最优决策即可，复杂度 \(O(nlogn)\)。
//算是这几周练习以来质量最高的一道题？？？
#include <bits/stdc++.h>
using namespace std;
long long n, L, id[500050], p[500050], a[500050], tot, b[500050], f[500050], val[2000200], tg[2000200], sum[2000200][3][3], ans;
inline void pushup(long long k)
{
for (long long i = 0; i <= 1; i++)
for (long long j = 0; j <= 1; j++)
sum[k][i][j] = max(sum[k << 1][i][0] + sum[k << 1 | 1][0][j], sum[k << 1][i][1] + sum[k << 1 | 1][1][j] + val[k]);
return;
}
inline void Lazy(long long k, long long v)
{
val[k] += v;
tg[k] += v;
sum[k][0][0] = max(sum[k][0][0] - v, 0ll);
sum[k][0][1] -= v;
sum[k][1][0] -= v;
sum[k][1][1] -= v;
return;
}
inline void pushdown(long long k)
{
if (!tg[k])
return;
long long x = tg[k];
tg[k] = 0;
Lazy(k << 1, x);
Lazy(k << 1 | 1, x);
return;
}
inline void modify(long long k, long long l, long long r, long long p)
{
if (l == r)
{
sum[k][0][0] = max(f[p] - val[k], 0ll);
sum[k][0][1] = sum[k][1][0] = sum[k][1][1] = f[p] - val[k];
return;
}
pushdown(k);
long long mid = (l + r) >> 1;
if (p <= mid)
modify(k << 1, l, mid, p);
else modify(k << 1 | 1,mid+1,r, p);
pushup(k);
return;
}
inline void update(long long k, long long l, long long r, long long pl, long long pr, long long v)
{
if (pl <= l && r <= pr)
{
Lazy(k, v);
return;
}
pushdown(k);
long long mid = (l + r) >> 1;
if (pl <= mid && mid < pr)
{
val[k] += v;
update(k << 1, l, mid, pl, pr, v);
update(k << 1 | 1,mid+1,r, pl, pr, v);
}
else if (pl <= mid)
update(k << 1, l, mid, pl, pr, v);
else update(k << 1 | 1,mid+1,r, pl, pr, v);
pushup(k);
return;
}
int main()
{
scanf("%lld %lld", &n, &L);
for (long long i = 1; i <= n; i++)
{
scanf("%lld %lld %lld", &id[i], &p[i], &a[i]);
if (id[i] == 1)
b[++tot] = p[i];
}
sort(b + 1, b + tot + 1);
tot = unique(b + 1, b + tot + 1) - b - 1;
for (long long i = 1; i <= n; i++)
{
if (id[i] == 1)
{
long long x = lower_bound(b + 1, b + tot + 1, p[i]) - b;
ans += a[i];
f[x] += a[i];
modify(1, 1, tot, x);
}
else
{
long long x = lower_bound(b + 1, b + tot + 1, p[i] - L) - b, y = upper_bound(b + 1, b + tot + 1, p[i] + L) - b - 1;
if (x <= y)
update(1, 1, tot, x, y, a[i]);
}
printf("%lld\n", ans - sum[1][0][0]);
}
return 0;
}
#E. Alice and Recoloring 2
有一张 \(n \times m\) 的方格图，初始全白，目标状态给定。
有 4 种操作（反转的意思是黑 \(\to\) 白，白 \(\to\) 黑）：
- 反转一个包含 \((1, 1)\) 的子矩形，花费 \(1\)。
- 反转一个包含 \((n, 1)\) 的子矩形，花费 \(3\)。
- 反转一个包含 \((1, m)\) 的子矩形，花费 \(4\)。
- 反转一个包含 \((n, m)\) 的子矩形，花费 \(2\)。
求达成目标状态的最小花费。
\(1 \le n, m \le 500\)。
2s, 256MB
引理 1：第 2 和第 3 种操作不会用到。
证明：考虑到不管是第 2 种还是第 3 种操作，都可以用两次第 1 种操作代替，而且代价显然更优。所以永远不会使用第 2 和第 3 种操作。
现在的问题就转化为了只存在第 1 和第 4 种操作的情况了。
将目标状态与初始状态对换，即给定一个初始有黑白两色的方格图，花最小的代价使得全部变成白色。
矩形反转显然是不好处理的，考虑弄一个类似前缀和的东西来优化掉。
将黑色视为 \(1\)，白色视为 \(0\)。构造一个数组 \(a\)，其中 \(a_{i, j} = s_{i, j} \oplus s_{i + 1, j} \oplus s_{i, j + 1} \oplus s_{i + 1, j + 1}\)（超出网格的部分默认是白色）。
非常显然，当 \(a\) 数组全部变为 \(0\) 时，\(s\) 数组也就全部变为了 \(0\)。
观察 1, 4 两种操作对 \(a\) 数组的影响，发现是：
- 对于第 1 种操作，只会有 1 个格子的 \(a\) 发生了反转。
- 对于第 4 种操作，会有 4 个格子的 \(a\) 发生反转，且这 4 个格子形如 \((x, y)\)，\((n, y)\)，\((x, m)\)，\((n, m)\)。记这样的操作为 \(op(x, y)\)。
引理 2：不会同时使用 \(op(x, y_1)\) 和 \(op(x, y_2)\)。同理不会同时使用 \(op(x_1, y)\) 和 \(op(x_2, y)\)。
证明：以前一种为例，\((n, m)\) 和 \((x, m)\) 都被反转了两次，所以不会发生改变。那么也就是花费了 \(4\) 的代价来反转了 \(2\times 2=4\) 个格子。这显然可以被第 1 种操作代替。
引理 3：除非 \((x, y)\)，\((n, y)\) 和 \((x, m)\) 都为 \(1\)，才会使用 \(op(x, y)\)。
证明：如果这中间有一个不为 \(1\)，那么这次操作就产生了一个错误的反转。为了达成最终目标，显然会使用一次第 1 种操作把它反转回来（注：不会是另一个第 4 种操作，根据引理 2 可以得知）。那么仅仅是反转了另外 3 个格子，代价都至少为 \(1 + 2 = 3\)，完全可以使用第 1 种操作代替。
于是就可以做题了，建立一个二分图，左部有 \(n - 1\) 个点代表行，右部有 \(m - 1\) 个点代表列。
对于 \((x, y)\)，如果它满足引理 3 的条件，则把左部的 \(x\) 和右部的 \(y\) 连边。
求这个二分图的最大匹配数 \(k\) 即可。答案为 \(\textit{rem} - k\)。\(\textit{rem}\) 表示剩下的 \(1\) 的个数。
我使用的是 dinic 求二分图最大匹配，时间复杂度为 \(O(n^2 \sqrt{n})\)。
#include <bits/stdc++.h>
using namespace std;
char str[550][550];
int n, m, cnt = -1, cur[1010], a[550][550], h[1010], S, T, que[1010], hd, tl, lev[1010];
struct edge
{
int v, w, nxt;
}e[500050];
inline void add_edge(int u, int v)
{
e[++cnt] = (edge){v, 1, h[u]};
h[u] = cnt;
e[++cnt] = (edge){u, 0, h[v]};
h[v] = cnt;
}
inline bool bfs()
{
memset(lev, 0, sizeof(lev));
hd = tl = lev[S] = 1; que[1] = S;
while(hd <= tl)
{
int u = que[hd++];
for(int i = h[u]; ~i; i = e[i].nxt)
{
int v = e[i].v;
if(!lev[v] && e[i].w > 0)
{
que[++tl] = v;
lev[v] = lev[u] + 1;
}
}
}
return lev[T];
}
inline int dfs(int u, int can_flow)
{
if(u == T)
return can_flow;
int res_flow = 0;
for(int &i = cur[u]; ~i; i = e[i].nxt)
{
int v = e[i].v;
if(lev[v] == lev[u] + 1 && e[i].w > 0)
{
int will_flow = dfs(v, min(can_flow, e[i].w));
res_flow += will_flow;
can_flow -= will_flow;
e[i ^ 1].w += will_flow;
e[i].w -= will_flow;
if(!can_flow)
break;
}
}
if(!res_flow)
lev[u] = 0;
return res_flow;
}
inline int dinic()
{
int res = 0;
while(bfs())
{
memcpy(cur, h, sizeof(h));
res += dfs(S, 2147483647);
}
return res;
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d %d", &n, &m);
S = n + m + 1;
T = n + m + 2;
for(int i = 1; i <= n; i++)
scanf("%s", str[i] + 1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] = (str[i][j] == 'B') ^ (str[i][j + 1] == 'B') ^ (str[i + 1][j] == 'B') ^ (str[i + 1][j + 1] == 'B');
for(int i = 1; i < n; i++)
for(int j = 1; j < m; j++)
if(a[i][j] && a[n][j] && a[i][m])
add_edge(i, j + n);
for(int i = 1; i < n; i++)
add_edge(S, i);
for(int j = 1; j < m; j++)
add_edge(j + n, T);
int k = dinic(), ans = 0;
a[n][m] ^= (k & 1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
ans += a[i][j];
ans -= k;
printf("%d", ans);
return 0;
}
#F. Sum of Matchings
记 \(g(l,r,L,R)=MM(G(l,r,L,R))\)，设 \(f(l,r)=\sum_{n+1\le L\le R\le 2n} g(l,r,L,R)\)。
考虑对于 \(\forall 1\le l \le r\le n\)，计算 \(f(l,r)\) 的和。
考虑增量法。注意到 \(g(l,r,L,R)-g(l,r-1,L,R)\in\{0,1\}\)，因此可以考虑由 \(f(l,r-1)\) 得到 \(f(l,r)\)。
对于 \(g(l,r,L,R)-g(l,r-1,L,R)=1\) 的情况，首先 \(r\) 一定要被匹配到，否则答案不会增大。题目中每个点的度数为 \(2\) 保证了图由若干个偶环构成，且每个偶环由 \([1,n]\) 与 \([n+1,2n]\) 中的数交替构成。因此直接考虑 \(r\) 所在的环，记 \(r\) 所在的环按环上的顺序分别为 \(a_1,a_2,\dots,a_{2m}\)，且 \(a_1=r\)。
假设 \(g(l,r-1,L,R)\) 中前若干个连续的匹配为 \((a_2,a_3),(a_4,a_5),\dots,(a_{2k},a_{2k+1})\)，则 \(a_1\) 与 \(a_2\) 匹配后能改变最大匹配当且仅当 \(a_{2k+2}\in [L,R]\)，同时由于 \(a_{2k+2}\) 不能与 \(a_{2k+3}\) 匹配，则 \(a_{2k+3}\notin [l,r]\)。那么这样的 \(k\) 对于确定的 \(l,r\) 来说是唯一的，所以通过限制 \(a_2,a_4,\dots,a_{2k+2}\in [L,R]\)，则符合要求的 \([L,R]\) 的对数可以直接计算得出。对于 \(a_1\) 与 \(a_{2m}\) 匹配的情况是类似的。将两种方案合并在一起，即可计算出满足 \(g(l,r,L,R)-g(l,r-1,L,R)=1\) 的 \((L,R)\) 的对数。对于 \(a_1,a_3,\dots,a_{2m-1}\) 全部在 \([l,r]\) 内的情况可以单独讨论。
枚举 \(l,r\) 后直接暴力找到 \(r\) 所在环上的分界点，即可做到效率 \(O(n^3)\)，由于 \((l,r)\) 的对数有限，且环上分界点对于 \((l,r)\) 不同的情况也互不相同，因此实际计算的次数远低于 \(n^3\)，在极限数据下也能通过。如果采用倍增/数据结构优化找到分界点与求最值的过程可以做到 \(O(n^2\log n)\)。
#include<bits/stdc++.h>
using namespace std;
long long n, tot, id[3030], id0[3030], id1[3030], cir[3030][6010], cnt[3030], Min[3030][2], Max[3030][2], ans[3030][3030], Ans;
vector<long long> G[3030];
inline void dfs(long long u)
{
id[u] = tot;
cir[tot][++cnt[tot]] = u;
if (!id[G[u][0]])
dfs(G[u][0]);
if (!id[G[u][1]])
dfs(G[u][1]);
}
int main()
{
scanf("%lld", &n);
for (long long i = 1, u, v; i <= 2 * n; i++)
{
scanf("%lld %lld", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (long long i = 1; i <= n; i++)
if (!id[i])
{
++tot;
dfs(i);
Min[tot][0] = Max[tot][0] = cir[tot][1];
Min[tot][1] = Max[tot][1] = cir[tot][2];
for (long long j = 3; j <= cnt[tot]; j += 2)
Min[tot][0] = min(Min[tot][0], cir[tot][j]), Max[tot][0] = max(Max[tot][0], cir[tot][j]);
for (long long j = 4; j <= cnt[tot]; j += 2)
Min[tot][1] = min(Min[tot][1], cir[tot][j]), Max[tot][1] = max(Max[tot][1], cir[tot][j]);
Min[tot][1] -= n;
Max[tot][1] -= n;
for (long long j = 1; j <= cnt[tot]; j++)
cir[tot][j + cnt[tot]] = cir[tot][j], id0[cir[tot][j]] = j, id1[cir[tot][j]] = j + cnt[tot];
}
for (long long l = 1; l <= n; l++)
{
for (long long r = l; r <= n; r++)
{
long long i = id[r];
if (l <= Min[i][0] && Max[i][0] <= r)
ans[l][r] = ans[l][r - 1] + Min[i][1] * (n - Max[i][1] + 1);
else
{
long long endpos1 = 0, endpos2 = 0, l1 = n + 1, r1 = 0, l2 = n + 1, r2 = 0;
for (long long p = id0[r];; p += 2)
if (cir[i][p]<l || cir[i][p]>r)
{
endpos1 = p;
break;
}
for (long long p = id1[r]; ; p -= 2)
if (cir[i][p]<l || cir[i][p]>r)
{
endpos2 = p;
break;
}
for (long long p = id0[r] + 1; p < endpos1; p += 2)
{
l1 = min(l1, cir[i][p] - n);
r1 = max(r1, cir[i][p] - n);
}
for (long long p = id1[r] - 1; p > endpos2; p -= 2)
{
l2 = min(l2, cir[i][p] - n);
r2 = max(r2, cir[i][p] - n);
}
ans[l][r] = ans[l][r - 1] + l1 * (n - r1 + 1) + l2 * (n - r2 + 1) - min(l1, l2) * (n - max(r1, r2) + 1);
}
}
for (long long r = l; r <= n; r++)
Ans += ans[l][r];
}
printf("%lld", Ans);
return 0;
}
#G. Fishermen
思路分析
对于 \(\{b_i\}\) 可以作为一组可能的答案的充分必要条件是 \(a_i|b_i\)，所有 \(b_i\) 互不相同，注意到我们只需要 \(\sum b_i\) 尽可能小即可得到合法的 \(\{b_i\}\)。
可以证明每个 \(b_i\) 都不可能超过 \(n\times a_i\)，又 \(b_i\) 互不相同，因此我们可以对于 \(a_i\) 向每个 \(k\times a_i,k\in [1,n]\) 连一条边，注意两侧点不同。
因此原问题就转化成了一个二分图带权匹配问题，但显然这样做会超时。
考虑用二分图无权匹配艹过去，即对于每一个可能的 \(b_i\) 做一次匈牙利算法，假如我们从小到大枚举每个 \(b_i\) 匹配，就一定能够得到最优解。
注意到如果在没有匹配的情况下不清空 vis 数组可以将算法复杂度优化到 \(\Theta(n^3)\)。
#include <bits/stdc++.h>
using namespace std;
long long match[1010], a[1010];
bool vis[1010];
vector<long long> G[1000010];
inline bool Mat(long long u)
{
for (long long x : G[u])
{
if (vis[x])
continue;
vis[x] = true;
if (!match[x] || Mat(match[x]))
{
match[x] = u;
return true;
}
}
return false;
}
signed main()
{
vector <long long> val;
long long n, ans = 0;
scanf("%lld", &n);
for (long long i = 1; i <= n; ++i)
{
scanf("%lld", &a[i]);
for (long long p = 1; p <= n; ++p)
val.push_back(p * a[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
long long m = val.size();
for (long long i = 1; i <= n; ++i)
for (long long p = 1; p <= n; ++p)
{
long long x = lower_bound(val.begin(), val.end(), a[i] * p) - val.begin() + 1;
G[x].push_back(i);
}
for (long long i = 1, cnt = 0; i <= m && cnt <= n; ++i)
if (Mat(i))
{
ans += val[i - 1];
++cnt;
memset(vis, false, sizeof(vis));
}
printf("%lld", ans);
return 0;
}