\(\textbf{C.}\)
事实上, 若 \(d(1,2)\neq 1\), 则 \(d(1,2)=\min\{d(1,x)+d(2,x):x\geq3\}\).
然后发现若存在 \(x \geq 3\), 使 \(|d(1,x)-d(2,x)|\neq1\), 则必有 \(d(1,2)=\min\{d(1,x)+d(2,x):x\geq3\}\). 剩下的情况可以认为 \(d(1,2)=1\).
但是注意这个corner case! \(n = 4\), \(\mathcal{T} = \{ (1, 2), (1, 3), (2, 4) \}\).
void solve(){
auto ask = [&](int u, int v) -> int {cout << "? " << u + 1 << ' ' << v + 1 << '\n', cout.flush(); int x; cin >> x; return x;} ;
auto answer = [&](int ans) -> void {cout << "! " << ans << '\n', cout.flush();} ;
int n; cin >> n;
vector<int> d0(n); for(int i = 2; i < n; i ++) d0[i] = ask(0, i);
vector<int> d1(n); for(int i = 2; i < n; i ++) d1[i] = ask(1, i);
bool flag = true; for(int i = 2; i < n; i ++) flag &= (abs(d0[i] - d1[i]) == 1);
if(n == 4 && d0[2] + d1[2] == 3 && d0[3] + d1[3] == 3 && ask(2, 3) == 1) flag = false;
if(flag){answer(1);}
else{int ans = n; for(int i = 2; i < n; i ++) ans = min(ans, d0[i] + d1[i]); answer(ans);}
}
\(\textbf{D.}\)
我们说 \(\mathcal{X}\to\mathcal{Y}\) 表示集合 \(\mathcal{X}\) 通过 \(1\) 次移动变为集合 \(\mathcal{Y}\). 那么若 \(\mathcal{X}\to\mathcal{Y}\) 则必有 \(\mathcal{Y}\to\mathcal{X}\). 定义 \(\mathrm{op}(\mathcal{X})=\mathcal{Y}\), 其中 \(\mathcal{Y}\) 是唯一的 \(\mathcal{X}\to\mathcal{Y}\).
所以原题等价于求 \(\#\{\mathcal{X},\mathcal{Y}:\mathcal{X}=\mathrm{op}(\mathcal{Y}),\mathcal{Y}=\mathrm{op}(\mathcal{X})\}\).
事实上, 把 \(\mathcal{X}\to\mathcal{Y}\) 的移动中经过的边一定是若干树链的并(即若 \(v_1\to\cdots\to v_k\) 是树链, 则相当于是 \(\{v_1,\cdots,v_{k-1}\}\leftrightarrow\{v_2,\cdots,v_k\}\) 的移动)
所以设 \(f(u,p,q)\) 表示: \(u\) 子树内, \(\mathrm{kind}(u,\mathcal{X})=p\), \(\mathrm{kind}(u,\mathcal{Y})=q\) 的方案数. 其中 \(\mathrm{kind}(u,\mathcal{X})=\begin{cases}0&,u\notin\mathcal{X}\\1&,u没有找到第二步去哪里\\2&,u找到第二步去哪里\end{cases}\).
考虑 \(f(u,*,*)\) 初始值为:
- \(f(u,0,0)=f(u,0,1)=f(u,1,0)=f(u,1,1)=1\); \(f(u,\mathrm{otherwise})=0\).
同时合并子树 \(v\) 到到 \(u\) 时更新如下:
- \(\forall p_u,q_u,p_v,q_v\in\{0,1,2\}\). 则转移需要满足如下条件:
- \(q_v=1\) 时有 \(p_u=1\). 若否, 则 \(v\in\mathcal{Y}\) 可以走到 \(u\in\mathcal{X}\), 但若 \(f(u,p_u,q_u)\)表示 \(u\notin\mathcal{X}\) 或 \(u\) 第二步已经确定且不是 \(u\), 不合法! 也就是说此时必有 \(p_u=1\), 说明 \(u\to v\) 是 \(\mathcal{X}\to\mathcal{Y}\) 的移动之一.
- \(p_u=1\) 时有 \(q_v=1\). 同(1).
- \(p_v,q_v\) 不同时为 \(1\), 否则若 \(p_v=q_v=1\), 由(1), (2)有 \(p_u=q_u=1\). 说明 \(u\to v\) 是 \(\mathcal{X}\to\mathcal{Y}\) 的移动之一且 \(v\to u\) 且 \(\mathcal{X}\to\mathcal{Y}\) 的移动之一(用到 \(1\) 次: 若 \(u\to v\) 是 \(\mathcal{X}\to\mathcal{Y}\) 的移动之一, 则 \(v\to u\) 是 \(\mathcal{Y}\to\mathcal{X}\) 的移动之一). 故重复经过了边 \((u,v)\). 不合法!
- \(p_u=0\), \(q_v\neq0\) 时有 \(q_u=p_v=1\). 因为考虑 \(v\in\mathcal{Y}\) 也可以向 \(u\) 移动, 但是因为操作的唯一性, 说明这个移动时不符合条件的(也就是会重复经过边 \((u,v)\)). 根据上面的讨论发现此时必有 \(q_u=p_v=1\) 然后让 \(u\to v\) 是 \(\mathcal{Y}\to\mathcal{X}\)的移动之一, 也就是 \(q_u=1,p_v=1\).
- \(p_u\neq0\), \(q_v=0\) 时有 \(q_u=p_v=1\). 同(4).
- \(q_u=0\), \(p_v\neq0\) 时有 \(p_u=q_v=1\). 同(4).
- \(q_u\neq0\), \(p_v=0\) 时有 \(p_u=q_v=1\). 同(4).
- 之后转移到状态 \(p_u',q_u'\) 为:
- \(p_u'=\begin{cases}2&,p_u=q_v=1\\p_u&,\mathrm{otherwise}\end{cases}\). 因为只有 \(p_u=q_v=1\) 会让 \(u\to v\) 确定成为 \(\mathcal{X}\to\mathcal{Y}\) 的移动之一且改变 \(p_u'\).
- \(q_u'=\begin{cases}2&,q_u=p_v=1\\q_u&,\mathrm{otherwise}\end{cases}\). 同(1).
- 所以更新 \(f(u,p_u',q_u')\gets f(u,p_u,q_u)f(v,p_v,q_v)\) 即可.
时间复杂度: \(\mathcal{O}(20n)\).
void solve(){
int n; cin >> n;
vector<vector<int>> nxt(n);
for(int i = 0; i < n - 1; i ++){int u, v; cin >> u >> v; u --, v --; nxt[u].push_back(v), nxt[v].push_back(u);}
vector<vector<vector<modint>>> dp(n, vector<vector<modint>>(3, vector<modint>(3)));
auto dfs = [&](auto dfs, int u, int pa) -> void {
dp[u][0][0] = dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = modint(1);
for(int v : nxt[u]) if(v != pa){
dfs(dfs, v, u);
vector<vector<modint>> newdp(3, vector<modint>(3));
for(int pu = 0; pu < 3; pu ++) for(int qu = 0; qu < 3; qu ++){
for(int pv = 0; pv < 3; pv ++) for(int qv = 0; qv < 3; qv ++){
if(qv == 1 && pu != 1) continue;
if(pv == 1 && qu != 1) continue;
if(pv == 1 && qv == 1) continue;
if(pu == 0 && qv && (qu != 1 || pv != 1)) continue;
if(pu && qv == 0 && (qu != 1 || pv != 1)) continue;
if(qu == 0 && pv && (pu != 1 || qv != 1)) continue;
if(qu && pv == 0 && (pu != 1 || qv != 1)) continue;
int pr = (pu == 1 && qv == 1) ? (2) : (pu);
int qr = (qu == 1 && pv == 1) ? (2) : (qu);
newdp[pr][qr] += dp[u][pu][qu] * dp[v][pv][qv];
}
}
dp[u] = newdp;
}
} ;
dfs(dfs, 0, -1);
cout << (dp[0][0][0] + dp[0][0][2] + dp[0][2][0] + dp[0][2][2] - modint(1)).val() << '\n';
}
\(\textbf{E.}\)
先不妨让 \(\forall (x,y)\), \(\min(a_x,a_y)\geq\min(b_x,b_y)=b_y\)(不妨假设 \(b_x\geq b_y\)). 于是只需要满足 \(a_x\geq b_x\) 或 \(a_y\geq b_x\).
设 \(\mathcal{P}=\{x:a_x<b_x\}\), \(\mathcal{Q}=\{1,\cdots,n\}-\mathcal{P}\). 则只需要讨论 \(x\in\mathcal{P},y\in\mathcal{Q}\)的情况.
考虑最小割建图 \(\mathcal{G}\), 其中:
- \(V_\mathcal{G}=\{S,T\}\cup\{x:x\in\mathcal{P}\}\cup\{(y,i):y\in\mathcal{Q},i=1,\cdots,W\}\).
- \(E_\mathcal{G}=\{(S,x,b_x-a_x):x\in\mathcal{P}\}\cup\{((y,i),(y,i-1),+\infty):y\in\mathcal{Q},i=1,\cdots,W\}\cup\{((y,i),T,1)\}\cup\{(x,(y,b_x-a_y),+\infty)\}\).
说明: 事实上, 此时割掉点 \(x\) 就表示 \(a_x\gets b_x\), 割掉 \((y,t)\) 中最大的 \(t\) 就表示 \(a_y\gets t+a_y\).
所以就做完了. 因为 \(|E_\mathcal{G}|\in\mathcal{O}(n^2+nV)\), \(\mathrm{flow}\in\mathcal{O}(nV)\). 所以复杂度是\(\mathcal{O}(n^3V+n^2V^2)\), 但是常数很小, 可以通过.
void solve(){
int n; cin >> n;
vector<int> a(n), b(n); for(int i = 0; i < n; i ++) cin >> a[i] >> b[i];
int m; cin >> m;
vector<vector<int>> nxt(n); for(int i = 0; i < m; i ++){int x, y; cin >> x >> y; x --, y --; nxt[x].push_back(y), nxt[y].push_back(x);}
int ans = 0;
for(int x = 0; x < n; x ++) for(int y : nxt[x]){
int w = min(b[x], b[y]);
if(a[x] < w) ans += w - a[x], a[x] = w;
if(a[y] < w) ans += w - a[y], a[y] = w;
}
vector<int> P; for(int i = 0; i < n; i ++) if(a[i] < b[i]) P.push_back(i);
vector<int> Q; for(int i = 0; i < n; i ++) if(a[i] >= b[i]) Q.push_back(i);
int cnt = 2, S = 0, T = 1;
vector<vector<int>> id(n, vector<int>(100, 0));
for(int i = 0; i < n; i ++) for(int t = 0; t < 100; t ++) id[i][t] = cnt ++;
MaxFlow G(cnt, S, T);
for(int x : P) G.add(S, id[x][0], b[x] - a[x]);
for(int y : Q) for(int t = 0; t < 100; t ++) G.add(id[y][t], T, 1);
for(int y : Q) for(int t = 1; t < 100; t ++) G.add(id[y][t], id[y][t - 1], inf);
for(int x : P) for(int y : nxt[x]) if(binary_search(Q.begin(), Q.end(), y) && b[x] > a[y]) G.add(id[x][0], id[y][b[x] - a[y] - 1], inf);
cout << ans + G.maxflow() << '\n';
}
\(\textbf{F.}\)
咕咕咕.
标签：qu,int,++,arc142,vector,&&,mathcal From： https://www.cnblogs.com/zhangmj2008/p/arc142.html