T1 货车运输
Kruskal 重构树模板，没什么好说的，不会的把自己重构了算了，跳过。
T2 Slagalica
可以发现拼图 1 和 2、3 拼起来还是拼图 1，拼图 4 和 2、3 拼起来也还是拼图 4，这两种拼图还都不能和自己拼，所以我们可以看作只有拼图 1 和拼图 4 来做。
对于边界拼图分别是 5、7 的情况，只有形如 414，41414 的情况可以拼进去，所以如果拼图 4 的数量不等于拼图 1 的数量 +1 就无解。
其它情况可以类推：边界是 5、8 就应该形如 41，4141；边界是 6、7 就应该形如 14，1414；边界是 6、8 就应该形如 141，14141。
考虑如何让字典序最小，很明显对于拼图 1、2、3、4，我们应该分别把四种拼图各自从小到大排序。
接下来以边界为 5、7 来举例，根据上面所说的，第一块应该放 4，而 4 前面可以放任意块 3，最后得到的拼图还是 4。
所以可以先把拼图 3 中所有小于 4 中最小值的先拼上，然后再拼上一块 4。
同理，因为接下来要拼 1，而 1 前面可以放任意块 2，所以可以先把拼图 2 中所有小于 1 中最小值的先拼上，然后再拼上一块 1。
接下来就循环到拼完就可以了，4 前面拼 3，1 前面拼 2 的这一步，可以用等同于归并排序的方式来完成。
值得注意的是拼到最后一块 4 的时候，前后要分别把 3、2 全部都给拼上去，这就是唯一有点坑的点、地方了。
边界是其它拼图的情况就以此类推了，具体可以看下面的代码。
代码写的略显臃肿，有的地方其实可以写函数的，但我比较懒，所以贴的代码看着玩就行了,时间复杂度 $O(n \log n)，$(100pts)：
vector<int> v[5];
int n,l,r,ls,rs,now2,now3,sz[5];
void work(int x,int y,int &i,int j){
while(i<sz[x]&&v[x][i]<v[y][j]) printf("%d ",v[x][i++]);
printf("%d ",v[y][j]);
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
if(x==5||x==6) l=x,ls=y;
if(x==7||x==8) r=x,rs=y;
if(x<=4) v[x].push_back(y),sz[x]++;
}
for(int i=1;i<=4;i++) sort(v[i].begin(),v[i].end());
if(l==5&&r==7){
if(sz[1]+1!=sz[4]) return printf("-1"),0;
printf("%d ",ls);
for(int i=0;i<sz[1];i++) work(3,4,now3,i),work(2,1,now2,i);
while(now3<sz[3]) printf("%d ",v[3][now3++]);
printf("%d ",v[4][sz[1]]);
while(now2<sz[2]) printf("%d ",v[2][now2++]);
}
if(l==5&&r==8){
if(sz[1]!=sz[4]) return printf("-1"),0;
printf("%d ",ls);
for(int i=0;i<sz[1]-1;i++) work(3,4,now3,i),work(2,1,now2,i);
if(sz[1]){
work(3,4,now3,sz[4]-1);
while(now2<sz[2]) printf("%d ",v[2][now2++]);
printf("%d ",v[1][sz[1]-1]);
while(now3<sz[3]) printf("%d ",v[3][now3++]);
}
else{
while(now3<sz[3]) printf("%d ",v[3][now3++]);
while(now2<sz[2]) printf("%d ",v[2][now2++]);
}
}
if(l==6&&r==7){
if(sz[1]!=sz[4]) return printf("-1"),0;
printf("%d ",ls);
for(int i=0;i<sz[1]-1;i++) work(2,1,now2,i),work(3,4,now3,i);
if(sz[1]){
work(2,1,now2,sz[1]-1);
while(now3<sz[3]) printf("%d ",v[3][now3++]);
printf("%d ",v[4][sz[4]-1]);
while(now2<sz[2]) printf("%d ",v[2][now2++]);
}
else{
while(now2<sz[2]) printf("%d ",v[2][now2++]);
while(now3<sz[3]) printf("%d ",v[3][now3++]);
}
}
if(l==6&&r==8){
if(sz[1]!=sz[4]+1) return printf("-1"),0;
printf("%d ",ls);
for(int i=0;i<sz[4];i++) work(2,1,now2,i),work(3,4,now3,i);
while(now2<sz[2]) printf("%d ",v[2][now2++]);
printf("%d ",v[1][sz[4]]);
while(now3<sz[3]) printf("%d ",v[3][now3++]);
}
printf("%d\n",rs);
}
T3 华容道
看到题目就能想到一种非常简单又能得到很多分的做法：
每个询问搜索维护空白方块和目标方块的位置，复杂度 $O(qn2m2)$，能拿到 60pts 的部分分，实际甚至更多。
接下来我们来考虑怎么去进行优化。
已知想要目标方块可以移动，空白方块就必须与它相邻，所以我们只需要维护这些状态，然后建图跑最短路就行了。
至于为什么能想到，或许是因为 ABC 平均 3 场就有一种这类型的题？
考虑怎么建图，我们先给每一种状态给个编号，编号数量的上限是只有 $4nm$ 的。
然后对于每种状态，先与两个方块移动，也就是交换位置后的状态，连一条长度为 1 的双向边。
而对于目标方块不动，只有空白方块动的情况，直接将同一目标方块位置的 4 种状态把边连起来就行了，至于边长，我们跑遍 BFS 求就行了。
这样我们最多跑 $nm$ 遍 BFS 每次复杂度也只有 $O(nm)$，所以时间是充裕的。
需要注意的是，空白方块间的连边跑 BFS 的时候不能经过目标方块，不然状态就发生改变了，如果跑不到直接不连边就行了，正确性可以手模一下。
建完图了，我们接下来只需要处理询问就行了。
对于每次询问，我们先 BFS 一下将空白方块移动到目标方块起始点四周的距离，注意和刚才一样，不能经过目标方块。
然后对于四个状态分别跑 dijkstra，然后对于每次最短路跑出来的结果，将到终点四个状态的距离取最小值就可以了，记得加上最开始空白方块的移动距离。
最后对于这种方法还用一个天坑：那就是起终点相同要直接输出 0，就不用做其它的了，至于为什么，你试一下就知道了。
其它应该就没什么需要注意的了，时间复杂度 $O(n2m2+qnm\log(nm))$，代码贴在下面(100pts)：
#define N 35
bool vis[N][N],viv[N*N*5];
int n,m,q,a[N][N],dis[N*N*5];
vector<pair<int,int>> v[N*N*5];
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int get(int x,int y,int z){return (x-1)*m*4+(y-1)*4+z;}
int bfs(int sx,int sy,int tx,int ty){
queue<tuple<int,int,int>> q;
while(!q.empty()) q.pop();
q.emplace(sx,sy,0),memset(vis,0,sizeof vis),vis[sx][sy]=1;
while(!q.empty()){
auto [x,y,w]=q.front();q.pop();
if(x==tx&&y==ty) return w;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m||!a[nx][ny]||vis[nx][ny]) continue;
q.emplace(nx,ny,w+1),vis[nx][ny]=1;
}
}
return -1;
}
void dijkstra(int s){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
while(!q.empty()) q.pop();
memset(dis,0x3f,sizeof dis),dis[s]=0;
memset(viv,0,sizeof viv),q.emplace(0,s);
while(!q.empty()){
auto [sum,num]=q.top();q.pop();
if(viv[num]) continue;
viv[num]=1;
for(auto [y,w]:v[num])
if(dis[y]>sum+w)
q.emplace(dis[y]=sum+w,y);
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",a[i]+j);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!a[i][j]) continue;
a[i][j]=0;
for(int k=0;k<4;k++){
if(!a[i+dx[k]][j+dy[k]]) continue;
int num1=get(i,j,k),num2=get(i+dx[k],j+dy[k],k^1);
v[num1].emplace_back(num2,1),v[num2].emplace_back(num1,1);
for(int u=k+1;u<4;u++){
if(!a[i+dx[u]][j+dy[u]]) continue;
int num3=get(i,j,u),sum=bfs(i+dx[k],j+dy[k],i+dx[u],j+dy[u]);
if(sum!=-1) v[num1].emplace_back(num3,sum),v[num3].emplace_back(num1,sum);
}
}
a[i][j]=1;
}
}
for(int i=1,ex,ey,sx,sy,tx,ty;i<=q;i++){
int ans=0x3f3f3f3f;
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty),a[sx][sy]=0;
if(sx==tx&&sy==ty){a[sx][sy]=1,printf("0\n");continue;}
for(int j=0;j<4;j++){
if(!a[sx+dx[j]][sy+dy[j]]) continue;
int num=get(sx,sy,j),sum=bfs(sx+dx[j],sy+dy[j],ex,ey);
if(sum==-1) continue;dijkstra(num);
for(int k=0;k<4;k++) ans=min(ans,sum+dis[get(tx,ty,k)]);
}
a[sx][sy]=1,printf("%d\n",ans==0x3f3f3f3f?-1:ans);
}
}
T4 Džumbus
一眼树形 DP，看数据范围 $n \leq 1000$，一个经典的状态定义就出现了：
$dp_{i,j,0/1}$ 表示 $i$ 的子树中有 $j$ 个点满足条件，且 $i$ 满足/不满足条件时的最小花费。
接下来考虑如何转移，假设现在枚举到结点 $x$ 以及子节点 $y$。
首先，$dp_{x,i,0}$ 非常好转移，这没什么好说的对吧：
$
dp_{x,i,0}=\min_{j=1}^{j\leq \min(i,sz_y)} dp_{x,i-j,0}+\min(dp_{y,j,0},dp_{y,j,1})
$
对于 $dp_{x,i,1}$ 显然也有一个类似的不新增满足要求节点的转移：
$
dp_{x,i,1}=\min_{j=1}^{j\leq \min(i,sz_y)} dp_{x,i-j,1}+\min(dp_{y,j,0},dp_{y,j,1})
$
接下来我们考虑 $dp_{x,i,1}$ 要新增满足要求节点的转移：
第一种，$x$ 原本不满足要求，且 $y$ 满足要求，现在要让 $x$ 满足要求，因为 $y$ 已经满足要求了，所以加上 $d_x$ 的值就行了，转移式：
$
dp_{x,i,1}=\min_{j=1}^{j < \min(i,sz_y)} dp_{x,i-j-1,0}+dp_{y,j,1}+d_x)
$
第二种，$x$ 满足要求，且 $y$ 原本不满足要求，现在要让 $y$ 满足要求，因为 $x$ 已经满足要求了，所以加上 $d_y$ 的值就行了，转移式：
$
dp_{x,i,1}=\min_{j=1}^{j \leq \min(i,sz_y)} dp_{x,i-j,1}+dp_{y,j-1,0}+d_y)
$
第三种，$x$ 和 $y$ 都不满足要求，现在要让两个数都满足要求，将前两个转移方程结合一下就可以了。
$
dp_{x,i,1}=\min_{j=1}^{j < \min(i,sz_y)} dp_{x,i-j-1,0}+dp_{y,j-1,0}+d_x+d_y)
$
因为图有可能不连通，所以最后我们还要把每棵树的结果都整合起来，记 $s_i$ 表示要求 $i$ 个点满足要求的最小值，对于每次询问我们直接二分就可以了。
复杂度 $O(n^2+q \log n)$，代码贴在下面(100pts)：
#define N 1005
#define LL long long
bool vis[N];
vector<int> v[N];
int n,m,q,d[N],sz[N];
LL sum[N],tmp[N],dp[N][N][2];
void dfs(int x){
vis[x]=sz[x]=1,dp[x][0][0]=0;
for(auto y:v[x]){
if(vis[y]) continue;
dfs(y),sz[x]+=sz[y];
for(int i=sz[x];i>=0;i--){
for(int j=min(sz[y],i);j>=0;j--){
dp[x][i][0]=min(dp[x][i][0],dp[x][i-j][0]+min(dp[y][j][0],dp[y][j][1]));
dp[x][i][1]=min(dp[x][i][1],dp[x][i-j][1]+min(dp[y][j][0],dp[y][j][1]));
if(j>=1) dp[x][i][1]=min(dp[x][i][1],dp[x][i-j][1]+dp[y][j-1][0]+d[y]);
if(i-j>=1) dp[x][i][1]=min(dp[x][i][1],dp[x][i-j-1][0]+dp[y][j][1]+d[x]);
if(i-j>=1&&j>=1) dp[x][i][1]=min(dp[x][i][1],dp[x][i-j-1][0]+dp[y][j-1][0]+d[x]+d[y]);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",d+i);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y),v[y].push_back(x);
}
memset(dp,0x3f,sizeof dp);
memset(sum,0x3f,sizeof sum),sum[0]=0;
memset(tmp,0x3f,sizeof tmp),tmp[0]=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
for(int j=1;j<=sz[i];j++)
for(int k=n;k>=j;k--)
sum[k]=min(sum[k],tmp[k-j]+min(dp[i][j][0],dp[i][j][1]));
for(int j=0;j<=n;j++) tmp[j]=sum[j];
}
}
scanf("%d",&q);
for(int i=1,x;i<=q;i++){
scanf("%d",&x);
printf("%d\n",upper_bound(sum+1,sum+n+1,x)-sum-1);
}
}