test31

3-A 視頻監控 (video.cpp)

橫縱獨立，分開處理，選擇最大空隙中操作次數最小的，操作次數比較向上向下即可。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back

using namespace std;

const int N=100005;

int R, C, tot, n, m, x[N], y[N], lenx, leny, ansx, ansy;

signed main() {
//	freopen("1.txt","r",stdin);
	freopen("video.in","r",stdin);
	freopen("video.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> R >> C >> tot;
	up(i,1,tot) cin >> x[i] >> y[i];
	sort(x+1,x+1+tot), n=unique(x+1,x+1+tot)-x-1;
	sort(y+1,y+1+tot), m=unique(y+1,y+1+tot)-y-1;
	lenx=x[1]-1+R-x[n], leny=y[1]-1+C-y[m];
	up(i,2,n) {
		int d=x[i]-x[i-1]-1, cnt=min(x[i-1],R-x[i]+1);
		if(d>lenx||d==lenx&&cnt<ansx) lenx=d, ansx=cnt;
	}
	up(i,2,m) {
		int d=y[i]-y[i-1]-1, cnt=min(y[i-1],C-y[i]+1);
		if(d>leny||d==leny&&cnt<ansy) leny=d, ansy=cnt;
	}
	cout << (R-lenx)*(C-leny) << ' ' << ansx+ansy << '\n';
	return 0;
}

3-B 卡牌游戲 (card.cpp)

我都懶得說了，枚舉多拿幾張 \(1\)，然后暴力 dp 方案數，注意順序的貢獻要乘對，對 \(1\) 的處理考慮哪些集合可以給對手。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=505, P=998244353;

int n, m, f[N][N], g[N][N], Ans, dp[N][N];

inline void add(int &a,int b) { a=(a+b)%P; }

signed main() {
//	freopen("1.txt","r",stdin);
	freopen("card.in","r",stdin);
	freopen("card.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	f[0][0]=g[1][0]=dp[0][0]=1;
	up(i,1,m) up(j,0,i) {
		if(j+1<=i) add(f[i][j+1],f[i-1][j]);
		if(j-1>=0) add(f[i][j-1],f[i-1][j]);
	}
	up(i,2,n) up(j,0,m) up(k,0,j) add(g[i][j],g[i-1][j-k]*f[m][k]%P);
	up(i,1,m) up(j,0,i) {
		if((j+1)<=i-(j+1)) add(dp[i][j+1],dp[i-1][j]);
		if(j<=i-j) add(dp[i][j],dp[i-1][j]);
	}
	up(x,0,m) if(x%2==0) add(Ans,dp[m][(m-x)/2]*g[n][x]%P);
	cout << Ans << '\n';
	return 0;
}

3-C 旅行 (travel.cpp)

樹形 dp 形態考慮第一問怎么求，發現子樹狀態關心「子樹根到父親這條邊走的次數」、以及「子樹內部的答案」。肯定希望經過根邊的次數盡量小，所以盡可能匹配 \(s/t\) 讓它們可能不用產生根邊的貢獻。

現在再考慮一下根邊具體有多少條，首先如果子樹里面 \(s/t\) 兩兩匹配，那么貢獻是 \(2\times 1\)，如果不完全匹配，設子樹 \(s/t\) 分別有 \(p/q\) 個，顯然至少要向連 \(2\times |p-q|\) 條邊。

現在考慮匹配的部分的貢獻。手玩一下發現，我們希望在獲取某個不匹配（未來匹配）的 \(s\) 前做匹配的部分、或者 \(t\) 后做匹配的部分，消除匹配部分的額外貢獻。又發現連接之后未來仍然能將一些東西接在這個段的前后來消除額外貢獻，意思是，你可以現在 \(st...st+s\to st...sts\)，在未來 \(st...st+st...sts\to st...sts\)，或者 \(t+st...st\to tst..st\)，在未來 \(tst...st+st...st\to tst...st\)，所以你消除額外貢獻這個操作對未來是沒有后效性的。那么對于根邊，貢獻就是 \(2\sum \max\{1,|p-q|\}\)，這里要去掉空的子樹。

現在考慮怎么構造操作方案，先考慮一個點上可以會出現什么形態的東西？完全匹配的段 \(st...st\)、若干綁 \(s\) 的段 \((st...st)s\)、若干綁 \(t\) 的段 \(t(st...st)\)，綁 \(s\) 和綁 \(t\) 的段肯定會被匹配掉不共存，完美匹配的段和綁定的段也應該合并消除貢獻也不共存，所以一個點上是三種段之一。我們分類討論一下怎么合并段可以保持子樹的一些欽定了的順序。

• 完全匹配+完全匹配，簡單拼接即可。
• 綁 \(s\) + 完全匹配，把完全匹配拼到前綴。
• 綁 \(t\) + 完全匹配，把完全匹配拼到后綴。
• 綁 \(s\) + 綁 \(t\)，綁 \(s\) 的放在前面、綁 \(t\) 的放在后面，然后如果條件允許的話把合并出來的完全匹配段按照上面兩種方式消除貢獻。

快速合并我們可以維護一個鏈表，實現的時候可以選擇更好的順序，以及可以用啟發式合并來合并綁 \(s\) 和綁 \(t\) 的集合來讓實現更簡便，以及不能使用 queue，空間會爆。

更具體滴，在點上預設鏈表 \(normal_x\) 表示完全匹配段，\(L_x/R_x\) 表示綁 \(s\) / 綁 \(t\) 的鏈表集合。

• 遞歸處理子樹 \(y\)。
• 將 \(normal_y\) 接在 \(normal_x\) 上。
• 將 \(L_y/R_y\) 啟發式合并到 \(L_x/R_x\) 里。
• 在 \(x\) 上盡量合并 \(L_x/R_x\) 加入到 \(normal_x\)。
• 如果 \(L_x/R_x\) 不都為空，將 \(normal_x\) 合并進去。

#include<bits/stdc++.h>
#define ll long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define hd first
#define tl second

using namespace std;

const int N=600005;

int n, m, tmp, nxt[N], pre[N], tag[N];
ll Ans;
vector<int> to[N];
vector<pii> L[N], R[N];
pii normal[N];

pii lnk(pii i,pii j) {
	if(!i.hd) return j;
	if(!j.hd) return i;
	nxt[i.tl]=j.hd, pre[j.hd]=i.tl;
	return mp(i.hd,j.tl);
}

void merge(vector<pii> &a,vector<pii> &b) {
	if(b.size()>a.size()) swap(a,b);
	for(pii u:b) a.pb(u); b.clear(); 
}

void dfs(int x,int fad) {
	normal[x]=mp(0,0);
	if(L[x].size()||R[x].size()) tag[x]=1;
	for(int y:to[x]) if(y!=fad) {
		dfs(y,x), tag[x]|=tag[y];
		normal[x]=lnk(normal[x],normal[y]);
		merge(L[x],L[y]);
		merge(R[x],R[y]);
	}
	while(L[x].size()&&R[x].size()) {
		pii l=L[x].back(); L[x].pop_back();
		pii r=R[x].back(); R[x].pop_back();
		normal[x]=lnk(normal[x],lnk(l,r));
	}
	if(L[x].size()) {
		pii u=L[x].back(); L[x].pop_back();
		L[x].pb(lnk(normal[x],u)), normal[x]=mp(0,0);
	}
	if(R[x].size()) {
		pii u=R[x].back(); R[x].pop_back();
		R[x].pb(lnk(u,normal[x])), normal[x]=mp(0,0);
	}
	if(tag[x]) Ans+=max(1,(int)L[x].size()+(int)R[x].size());
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	up(i,1,m) cin >> tmp, L[tmp].pb(mp(i,i));
	up(i,1,m) cin >> tmp, R[tmp].pb(mp(i+m,i+m));
	up(i,2,n) {
		int u, v;
		cin >> u >> v;
		to[u].pb(v);
		to[v].pb(u);
	}
	dfs(1,0), cout << 2*(Ans-1) << '\n';
	for(int i=normal[1].hd; i; i=nxt[i]) cout << (i>m?(i-m):i) << ' ';
	return 0;
}