【解题报告】联合省选 2021 A卷
本人被省选搞无语了，水平较低，若被叉请直接私信 $\text{D}$ 我（bushi）。
$\text{card}$
考虑二分答案。
设二分的极差为 $l$，枚举的最小值为 $x$，那么所有数字都要在 $[x,x+l]$ 之间。
把 $a,b$ 混在一起排序，双指针维护区间内出现了多少个 $a$，多少个 $b$，多少个 $a,b$ 都出现了。当所有位置的 $a,b$ 在区间中都至少出现了一个，区间才可能合法。
对于一个合法区间，区间内只出现了 $b$ 的那些需要翻，这等价于区间外有多少 $a$，前缀和后缀和维护即可。
时间复杂度 $\mathcal{O}(n\log n)$。
#include<bits/stdc++.h>
using namespace std;
#define FILE
//#define int long long
#define LL long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define fst first
#define scd second
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? -(x) : (x))
const int MAXN = 2e6 + 10;
const int INF = 2e9;
//const int mod = 998244353;
//const int mod = 1e9 + 7;
int n, m;
int a[MAXN], b[MAXN];
int pre[MAXN], suf[MAXN];
int buk[MAXN];
struct NODE {
int x, opt;
NODE(int _x = 0, int _o = 0) : x(_x), opt(_o) {}
bool operator < (const NODE &b) const {return x < b.x;}
} s[MAXN];
template<typename T> inline void read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while('0' <= c && c <= '9') {a = (a * 10) + (c ^ 48); c = getchar();}
a *= f;
}
bool chk(int add) {
int p = 1, in = 0;
for(int i = 1; i <= n; ++i) buk[i] = 0;
for(int i = 1, to; i <= (n * 2); ++i) {
while(p <= (n * 2) && s[p].x <= s[i].x + add) {
to = s[p].opt; if(to > n) to -= n;
if(!(buk[to]++)) in++;
p++;
}
if(in == n && pre[i - 1] + suf[p] <= m) return true;
to = s[i].opt; if(to > n) to -= n;
if(!(--buk[to])) in--;
}
return false;
}
signed main() {
#ifdef FILE
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
#endif
read(n); read(m);
for(int i = 1; i <= n; ++i) read(a[i]), s[i] = NODE(a[i], i);
for(int i = 1; i <= n; ++i) read(b[i]), s[i + n] = NODE(b[i], i + n);
sort(s + 1, s + (n * 2) + 1);
for(int i = 1; i <= (n << 1); ++i) pre[i] = pre[i - 1] + (s[i].opt <= n);
for(int i = (n << 1); i >= 1; --i) suf[i] = suf[i + 1] + (s[i].opt <= n);
int L = 0, R = 1e9, mid;
while(L < R) {
mid = (L + R) >> 1;
if(chk(mid)) R = mid;
else L = mid + 1;
}
printf("%d\n", L);
return 0;
}$\text{matrix}$
首先考虑如果没有 $[0,10^6]$ 的限制要怎么做：可以随便构造，比如先令第一行第一列都是 $0$，然后从左上到右下依次推过来。
考虑如何调整到 $[0,10^6]$ 之内。如果需要一个位置 $(i,j)+1$，那么可以让第 $i$ 行 $+1,-1,+1,-1\cdots$ 交替进行，使得原本的方案修改后依旧合法。或者让第 $j$ 列进行这个操作，同样可以使得当前状态仍然合法。
不妨设 $p_i,q_j$ 分别表示第 $i$ 行、第 $j$ 列进行了多少次这样的操作，然后就会发现对于每一个点 $(i,j)$，若需要他在 $[0,10^6]$ 之内，那么就形如一个差分约束的形式了。
但是，有时候可能会出现 $x+y\le w$ 的形式，也就是两个未知数中间是加号，这是差分约束无法解决的。观察发现，这种情况当且仅当当前行、列都恰好是 $+1$ 或者 $-1$ 的时候会出现。
那么考虑调整一下 $p_i,q_j$ 加数的方法，可以这样分配加减：
对于行的操作：
$$ \begin{bmatrix} +\ -\ +\ -\ +\\ -\ +\ -\ +\ -\\ +\ -\ +\ -\ +\\ -\ +\ -\ +\ -\\ +\ -\ +\ -\ + \end{bmatrix} $$
对于列的操作：
$$ \begin{bmatrix} -\ +\ -\ +\ -\\ +\ -\ +\ -\ +\\ -\ +\ -\ +\ -\\ +\ -\ +\ -\ +\\ -\ +\ -\ +\ - \end{bmatrix} $$
这样之后同一个点的 $p_i,q_j$ 就都是差分的形式了，直接上差分约束就可以了。本题图十分稠密，用 $\text{SPFA}$ 还不如 $\text{Bellman-Ford}$ 快。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 610;
const int MAXM = 5e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int T, n, m;
int a[MAXN][MAXN], b[MAXN][MAXN];
int dis[MAXN], cnt[MAXN], w[MAXN][MAXN];
bool inq[MAXN];
queue<int> Q;
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
void add(int a, int b, int v) {
w[a][b] = v, w[b][a] = (int)1e6 - v;
}
bool BellmanFord() {
memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n + m; ++i)
dis[i] = 0, inq[i] = true;
for(int t = 1; t <= n + m + 1; ++t) {
bool flag = false;
for(int i = 1, l, r; i <= n + m; ++i) {
if(i <= n) l = n + 1, r = n + m;
else l = 1, r = n;
for(int j = l; j <= r; ++j)
if(dis[j] > dis[i] + w[i][j])
dis[j] = dis[i] + w[i][j], flag = true;
}
if(!flag) break;
if(t == n + m + 1) return false;
}
return true;
}
void solve() {
read(n), read(m); memset(w, 0, sizeof w);
for(int i = 1; i < n; ++i)
for(int j = 1; j < m; ++j)
read(b[i][j]);
for(int i = 1; i <= n; ++i) a[i][1] = 0;
for(int i = 1; i <= m; ++i) a[1][i] = 0;
for(int i = 2; i <= n; ++i)
for(int j = 2; j <= m; ++j)
a[i][j] = b[i - 1][j - 1] - a[i - 1][j] - a[i - 1][j - 1] - a[i][j - 1];
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if((i + j) & 1) add(j + n, i, a[i][j]);
else add(i, j + n, a[i][j]);
}
}
if(!BellmanFord()) return puts("NO"), void();
puts("YES");
for(int i = 1; i <= n; ++i) {
for(int j = 1, opt; j <= m; ++j) {
opt = ((i + j) & 1) ? -1 : 1;
printf("%lld ", a[i][j] + (dis[i] - dis[j + n]) * opt);
}
putchar('\n');
}
}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(T);
while(T--) solve();
return 0;
}$\text{graph}$
发现若在 $f(u,G)$ 中，$u$，$v$ 有贡献，当且仅当：
- 存在一条从 $u$ 到 $v$，且路径上点标号均不小于 $v$ 的路径。
- 存在一条从 $v$ 到 $u$，且路径上点标号均不小于 $v$ 的路径。
两个东西对称，讨论一个即可。
先讨论第二个条件。可以枚举 $v$，然后考虑倒序加边，看要加到什么时候，一对 $u,v$ 才会存在合法的路径。对于一条边 $x\rightarrow y$，显然只有 $y$ 一侧的联通块中有贡献，那么对于起始点 $v$，且当前已经存在从 $v$ 到 $x$ 的合法路径，那么就可以更新 $y$ 可以到的位置。可以发现，由于每一对 $u,v$ 都只会记录使其合法的最大编号的边，所以对于一个固定的 $v$，整张图只会被遍历一次。
第一个条件，只需要把边反过来建即可。最后只需要计算出倒序加入每一条边之后，新增加了多少合法点对，做一个后缀和就行。时间复杂度 $\mathcal{O}(nm)$，民间数据卡常。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 1e3 + 10;
const int MAXM = 2e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
struct EDGE {
int head[MAXN], siz;
int nxt[MAXM], to[MAXM];
inline void add(int x, int y) {
nxt[++siz] = head[x];
to[siz] = y, head[x] = siz;
}
} e[2];
int n, m;
int X[MAXM], Y[MAXM];
int val[2][MAXN][MAXN];
int Ans[MAXM];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
void DFS(int opt, int x, int st, int v) {
val[opt][st][x] = v;
for(int &i = e[opt].head[x], to; i; i = e[opt].nxt[i]) {
to = e[opt].to[i];
if(to < st || val[opt][st][to] != m + 2) continue;
DFS(opt, to, st, v);
}
}
signed main () {
#ifdef FILE
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
#endif
read(n), read(m);
for(int i = 1; i <= m; ++i) read(X[i]), read(Y[i]);
for(int i = 1; i <= n; ++i) {
for(int j = i; j <= n; ++j) val[0][i][j] = val[1][i][j] = m + 2;
val[0][i][i] = val[1][i][i] = m + 1, e[0].siz = e[1].siz = 0;
for(int j = i; j <= n; ++j) e[0].head[j] = e[1].head[j] = 0;
for(int j = m; j >= 1; --j) {
if(X[j] < i || Y[j] < i) continue;
e[0].add(X[j], Y[j]), e[1].add(Y[j], X[j]);
if(val[0][i][X[j]] != m + 2 && val[0][i][Y[j]] == m + 2)
DFS(0, Y[j], i, j);
if(val[1][i][Y[j]] != m + 2 && val[1][i][X[j]] == m + 2)
DFS(1, X[j], i, j);
}
}
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j)
if(max(val[0][i][j], val[1][i][j]) < m + 2)
Ans[min(val[0][i][j], val[1][i][j])]++;
for(int i = m; i >= 1; --i) Ans[i] += Ans[i + 1];
for(int i = 1; i <= m + 1; ++i) printf("%d ", Ans[i]);
return 0;
}$\text{gem}$
套路地把路径按 $\text{lca}$ 拆开，把权值按照 $P$ 中顺序重新编号。
先考虑从 $s$ 到 $\text{lca}$ 的部分，设 $f_{x}$ 为当前节点向上的最近的，编号为 $x$ 的点。然后就可以倍增了，这里是一个 $\log$。
那么现在所有询问都到了 $\text{lca}$，考虑到 $t$ 的路径中可以到哪里。显然这个东西是单调的，所以可以二分。二分一个询问的答案，然后从 $t$ 同样维护类似的倍增数组，检查一下能不能接上就行。
考场脑抽了写了主席树但是懒得重新写了就这样吧
貌似可以用点分治什么的做到一个 $\log$，但这个做法是 $\mathcal{O(n\log n+q\log^2 n)}$。
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define LL long long
#define vec vector
#define pii pair<int, int>
#define fst first
#define scd second
#define pb push_back
#define abs(x) ((x) < 0 ? -(x) : (x))
const int MAXN = 2e5 + 10;
const int MAXM = 5e4 + 10;
const int INF = 2e9;
//const int mod = 998244353;
//const int mod = 1e9 + 7;
struct EDGE {
int head[MAXN], siz;
int nxt[MAXN << 1], to[MAXN << 1];
inline void add(int x, int y) {
nxt[++siz] = head[x];
to[siz] = y; head[x] = siz;
}
} e;
struct Query {
int lca, id;
Query(int _lca = 0, int _id = 0) : lca(_lca), id(_id) {}
};
int n, m, c, q;
int P[MAXM], w[MAXN], fa[MAXN], dep[MAXN];
int dfn[MAXN], dfnc, top[MAXN], p[MAXN][21];
int nxt[MAXN][21], num[MAXM];
int sum[MAXN * 30], ls[MAXN * 30], rs[MAXN * 30], cnt, root[MAXN];
int ss[MAXN], tt[MAXN], Ans[MAXN];
bool vis[MAXN];
vec<Query> qs[MAXN];
template<typename T> inline void read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while('0' <= c && c <= '9') {a = (a * 10) + (c ^ 48); c = getchar();}
a *= f;
}
void DFS(int x, int f) {
fa[x] = f;
p[x][0] = f, dep[x] = dep[f] + 1;
for(int i = 1; i < 20; ++i)
p[x][i] = p[p[x][i - 1]][i - 1];
for(int i = e.head[x], to; i; i = e.nxt[i]) {
to = e.to[i];
if(to == f) continue;
DFS(to, x);
}
}
int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 19; ~i; --i)
if(dep[p[x][i]] >= dep[y]) x = p[x][i];
if(x == y) return x;
for(int i = 19; ~i; --i)
if(p[x][i] ^ p[y][i]) x = p[x][i], y = p[y][i];
return p[x][0];
}
void trans() {
static int id[MAXM];
for(int i = 1; i <= c; ++i) id[P[i]] = i, P[i] = i;
for(int i = 1; i <= n; ++i) w[i] = id[w[i]];
}
void calc1(int x) {
int sav = num[w[x]];
if(w[x]) {
num[w[x]] = x;
nxt[x][0] = num[w[x] + 1];
for(int i = 1; i < 20; ++i)
nxt[x][i] = nxt[nxt[x][i - 1]][i - 1];
}
if(qs[x].size()) {
for(int i = 0; i < qs[x].size(); ++i) {
int s = num[1];
if(dep[s] < dep[qs[x][i].lca]) continue;
for(int j = 19; ~j; --j)
if(dep[nxt[s][j]] >= dep[qs[x][i].lca]) s = nxt[s][j];
Ans[qs[x][i].id] = w[s];
}
qs[x].clear();
}
for(int i = e.head[x], to; i; i = e.nxt[i]) {
to = e.to[i];
if(to == fa[x]) continue;
calc1(to);
}
num[w[x]] = sav;
}
void add(int &x, int pre, int l, int r, int p, int v) {
if(p < l || p > r) return;
x = ++cnt;
sum[x] = sum[pre], ls[x] = ls[pre], rs[x] = rs[pre];
sum[x] += v;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) add(ls[x], ls[pre], l, mid, p, v);
else add(rs[x], rs[pre], mid + 1, r, p, v);
}
int kth(int a, int b, int l, int r, int k) {
if(sum[a] - sum[b] < k) return -1;
if(l == r) return l;
int mid = (l + r) >> 1, v = sum[ls[a]] - sum[ls[b]];
if(k <= v) return kth(ls[a], ls[b], l, mid, k);
else return kth(rs[a], rs[b], mid + 1, r, k - v);
}
void solve(int ii, int x) {
static int lca, lim, l, r, mid, st, j;
lca = qs[x][ii].lca;
lim = Ans[qs[x][ii].id];
l = 1, r = sum[root[x]] - sum[root[lca]];
if(l > r) return;
while(l < r) {
mid = (l + r + 1) >> 1;
st = num[kth(root[x], root[lca], 1, c, mid)];
for(j = 19; ~j; --j)
if(dep[nxt[st][j]] >= dep[lca]) st = nxt[st][j];
if(w[st] <= lim + 1) l = mid;
else r = mid - 1;
}
st = num[kth(root[x], root[lca], 1, c, l)];
for(j = 19; ~j; --j)
if(dep[nxt[st][j]] >= dep[lca]) st = nxt[st][j];
if(w[st] <= lim + 1)
Ans[qs[x][ii].id] = max(Ans[qs[x][ii].id], kth(root[x], root[lca], 1, c, l));
}
void calc2(int x) {
if(w[x]) add(root[x], root[fa[x]], 1, c, w[x], 1);
else root[x] = root[fa[x]];
int sav = num[w[x]];
if(w[x]) {
num[w[x]] = x;
nxt[x][0] = num[w[x] - 1];
for(int i = 1; i < 20; ++i)
nxt[x][i] = nxt[nxt[x][i - 1]][i - 1];
}
for(int ii = 0, j; ii < qs[x].size(); ++ii) solve(ii, x);
for(int i = e.head[x]; i; i = e.nxt[i])
if(e.to[i] != fa[x]) calc2(e.to[i]);
num[w[x]] = sav;
}
signed main() {
#ifdef FILE
freopen("gem.in", "r", stdin);
freopen("gem.out", "w", stdout);
#endif
read(n), read(m), read(c);
for(int i = 1; i <= c; ++i) read(P[i]);
for(int i = 1; i <= n; ++i) read(w[i]);
trans();
for(int i = 1, x, y; i < n; ++i) {
read(x), read(y);
e.add(x, y), e.add(y, x);
}
DFS(1, 0); read(q);
for(int i = 1; i <= q; ++i) {
read(ss[i]), read(tt[i]);
qs[ss[i]].pb(Query(LCA(ss[i], tt[i]), i));
}
calc1(1);
memset(nxt, 0, sizeof nxt), memset(num, 0, sizeof num);
for(int i = 1; i <= n; ++i) qs[i].clear();
for(int i = 1; i <= q; ++i)
qs[tt[i]].pb(Query(LCA(ss[i], tt[i]), i));
calc2(1);
for(int i = 1; i <= q; ++i) printf("%d\n", Ans[i]);
return 0;
}$\text{ranklist}$
被题面送退役了的题......就 $\text{nm}$ 毁一生。
考虑 $\mathcal{O}(n!n)$ 的做法，直接暴力枚举一个顺序，然后贪心地做，尽量少地放 $b$ 即可。
套路地用状压 $\text{dp}$ 优化这个东西，一个 $\text{naive}$ 的想法是设 $\text{dp}_{S,i,x,y}$ 表示已经填了 $S$ 集合中的数，当前榜首为 $i$，$b_i=x$，当前 $b$ 的和为 $y$ 的时候的方案数。这个转移要 $\mathcal{O}(2^nn^2m^2)$，可能还没有上面那个暴力快。
考虑优化，观察到 $b$ 是单调不降的，这引导我们进行差分。差分之后，我们实际上就不需要知道上一个数的 $b$ 的实际值，只需要考虑当前的 $b$ 要比上一个 $b$ 大多少即可。那么先考虑省略一维 $x$，设 $\text{dp}_{S,i,y}$ 为上述状态删掉 $b_i=x$ 这个限制之后的状态。
那么当前只需要枚举一下前驱状态中，$\sum b$ 的值，然后贪心地加尽量少的 $b$ 即可。但是由于我们仍然需要判断 $\sum b\le m$，所以要类似提前计算贡献，把后面那些还没有填上的位置都加上当前的 $\Delta b$。这样就可以 $\mathcal{O}(2^nn^2m)$，可以通过。
不知道考场上脑子里是装了什么搞得连题都没看懂，活该退役
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 14;
const int MAXM = 510;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, Ans, maxp;
int a[MAXN], popc[(1 << (MAXN - 1)) + 10], p2[MAXN];
int dp[(1 << (MAXN - 1)) + 10][MAXN][MAXM];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(n), read(m); p2[0] = 1;
for(int i = 1; i <= n; ++i) p2[i] = p2[i - 1] << 1;
for(int i = 1; i <= n; ++i) read(a[i]);
maxp = max_element(a + 1, a + n + 1) - a;
for(int i = 1; i < p2[n]; ++i) popc[i] = popc[i >> 1] + (i & 1);
for(int i = 1; i <= n; ++i) {
if(n * (a[maxp] - a[i] + (i > maxp)) > m) continue;
dp[1 << (i - 1)][i][(a[maxp] - a[i] + (i > maxp)) * n] = 1;
}
for(int S = 1; S < p2[n]; ++S) {
for(int y = 1; y <= n; ++y) {
if((S & p2[y - 1]) == 0) continue;
for(int x = 1, nxt; x <= n; ++x) {
if(S & p2[x - 1]) continue;
nxt = S | p2[x - 1];
for(int pre = 0, add; pre <= m; ++pre) {
add = max(a[y] - a[x] + (x > y), 0ll);
if(pre + add * (n - popc[S]) > m) break;
dp[nxt][x][pre + add * (n - popc[S])] += dp[S][y][pre];
}
}
}
}
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= m; ++j)
Ans += dp[p2[n] - 1][i][j];
printf("%lld\n", Ans);
return 0;
}$\text{dominator}$
先考虑建立支配树，那么一个点的受支配集就是支配树上的所有祖先。由于本题范围很小，所以可以考虑 $\mathcal{O}(n^2)$ 建支配树：
由于一开始 $1$ 可以到所有点，所以可以删除每一个点，求出 $1$ 不再能到的那些点，这些点被删除的点支配。接着记录每一个点被多少点支配了，用类似拓扑排序的方式，将点依次入队，然后把他所支配的点的计数器减一。若他支配的点的计数器被减后为 $1$，那么当前点就是这个被支配的点的父亲，接着把这个被支配的点入队即可。
分类讨论 考虑一个询问 $(s,t)$，若在支配树上是返祖边或重边，那么显然不会有任何用处。
若 $(s,t)$ 是前向边，也就是从祖先到后代，那么：找到 $s$ 的一个儿子 $x$，使得 $t$ 在 $x$ 的子树中。那么受支配集会改变的点是：
从 $t$ 出发，走原图的边且不经过 $x$，所能达到的所有在支配树上在 $x$ 子树内的点。
有以下的结论：
若 $t$ 指向一个点 $v$，使得 $v$ 不在 $x$ 的子树内，那么 $v$ 的受支配集不改变。
若 $v$ 是 $x$ 的祖先，其受支配集显然不会改变。若 $v$ 不是 $x$ 的祖先，那么 $v$ 一定是 $\text{LCA}(x,v)$ 的儿子，因为如果是 $\text{LCA}(x,v)$ 的孙子或更深的子孙，那么 $v$ 的父亲就不一定需要被经过了，这不符合支配树的定义。而 $v$ 是 $\text{LCA}(x,v)$ 的儿子的话，其受支配集同样不会改变——因为这条路径同样需要经过 $\text{LCA}(x,v)$。
那么，只要我不经过 $x$，且在 $x$ 的子树内，那么就一定出现了一条路径，使得可以不经过 $x$。这样其受支配集就减小了。
若 $(s,t)$ 是横叉边，那么询问等价于 $(\text{LCA}(s,t),t)$，这就转化为了前向边的情况。
若我通过 $(s,t)$ 这条边，那么相当于我没有经过 $\text{LCA}(s,t)$ 以下，到 $\text{fa}(t)$ 的所有点，而是经过了 $\text{LCA}(s,t)$ 到 $s$ 这段路径。而经过这段新路径，也不可能使得一个点的受支配集加入这条路径中的任何点，因为显然加边不会增大任何点的支配集。
因此，这条路径的贡献等价于 $(\text{LCA}(s,t),t)$ 的贡献——都是跳过了 $t$ 的一些祖先，因此转化不会有问题。
时间复杂度 $\mathcal{O}(nq)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 3010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
struct EDGE {
int head[MAXN], siz;
int nxt[MAXN << 1], to[MAXN << 1];
inline void add(int x, int y) {
nxt[++siz] = head[x];
to[siz] = y, head[x] = siz;
}
} e, T;
int n, m, q, Ans;
int fa[MAXN], dep[MAXN], dfn[MAXN], siz[MAXN], dfnc;
int dom[MAXN][MAXN];
bool vis[MAXN];
queue<int> Q;
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
void build() {
static int cnt[MAXN];
for(int i = 1; i <= n; ++i)
dom[1][i] = dom[i][i] = true;
for(int ban = 2; ban <= n; ++ban) {
memset(vis, 0, sizeof(bool) * (n + 2));
Q.push(1);
while(Q.size()) {
int x = Q.front(); Q.pop();
if(x == ban || vis[x]) continue;
vis[x] = true;
for(int i = e.head[x], to; i; i = e.nxt[i]) {
to = e.to[i];
if(to == ban || vis[to]) continue;
Q.push(to);
}
}
for(int i = 1; i <= n; ++i)
if(!vis[i]) dom[ban][i] = true;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(dom[i][j]) cnt[j]++;
Q.push(1);
while(Q.size()) {
int x = Q.front(); Q.pop();
for(int i = 1; i <= n; ++i) {
if(!dom[x][i]) continue;
if((--cnt[i]) == 1) T.add(x, i), Q.push(i);
}
}
}
void DFS(int x, int f) {
dfn[x] = ++dfnc, fa[x] = f, dep[x] = dep[f] + 1, siz[x] = 1;
for(int i = T.head[x], to; i; i = T.nxt[i]) {
to = T.to[i];
if(to == f) continue;
DFS(to, x); siz[x] += siz[to];
}
}
bool isanc(int x, int y) {
while(y) {
if(x == y) return true;
y = fa[y];
}
return false;
}
int LCA(int x, int y) {
while(x ^ y) {
if(dep[x] < dep[y]) swap(x, y);
x = fa[x];
}
return x;
}
void calc(int x, int ban) {
if(vis[x] || ban == x) return;
vis[x] = true;
if(dfn[ban] <= dfn[x] && dfn[x] <= dfn[ban] + siz[ban] - 1) Ans++;
for(int i = e.head[x], to; i; i = e.nxt[i]) {
to = e.to[i];
calc(to, ban);
}
}
void solve() {
int s, t; read(s), read(t);
if(isanc(t, s)) return puts("0"), void();
if(!isanc(s, t)) s = LCA(s, t);
if(fa[t] == s) return puts("0"), void();
int ban = t; while(fa[ban] ^ s) ban = fa[ban];
memset(vis, 0, sizeof(bool) * (n + 2));
Ans = 0; calc(t, ban);
printf("%d\n", Ans);
}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(n), read(m), read(q);
for(int i = 1, x, y; i <= m; ++i) {
read(x), read(y);
e.add(x, y);
}
build(); DFS(1, 0);
while(q--) solve();
return 0;
}
woshishabi
香蕉
我爱上了ywjj
我是giagiagiagiagiagia
我是cxy09
ywjj好漂亮我好爱
ywjj好漂亮我好爱