T1 最小生成树
题面：给你一个无向带权连通图，每条边是黑色或白色。让你求一棵恰好有 \(need\) 条白色边的
权值和最小的生成树。题目保证有解。
题解:
最小生成树，自然而然想到kruskal算法，但我们要让白点恰好有 \(need\) 条，在白点多的时候，要多选黑点，在白点少的时候，要多选白点，所以我们可以根据白点选择情况对黑点的权值进行调整，在白点多的时候，减少黑点权值，在白点少的时候，增加黑点权值，然后发现随着黑点权值增加量的增加，白点数量单调递增，所以考虑二分。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k,fa[N],ans,need,sum,cnt;
struct node
{int u,v,w,cl;
}bi[N];
int find(int x)
{if(x==fa[x])return x;else return fa[x]=find(fa[x]);
}
bool cmp(node x,node y)
{if(x.w!=y.w)return x.w<y.w;else return x.cl<y.cl;
}
void kus()
{sum=0,cnt=0,need=0;for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++){int f1=find(bi[i].u),f2=find(bi[i].v);if(f1==f2)continue;cnt++;if(bi[cnt].cl==0)need++;fa[f2]=f1;sum+=bi[i].w;if(cnt==n-1)return;}
}
int main()
{freopen("e.in","r",stdin);freopen("e.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);cin>>n>>m>>k;for(int i=1;i<=m;i++)cin>>bi[i].u>>bi[i].v>>bi[i].w>>bi[i].cl;int l=-1005,r=1005;while(l<r){int mid=l+(r-l)/2;for(int i=1;i<=m;i++)if(bi[i].cl==0)bi[i].w+=mid;sort(bi+1,bi+m+1,cmp);kus();for(int i=1;i<=m;i++)if(bi[i].cl==0)bi[i].w-=mid;if(need>=k)ans=sum-mid*k,l=mid+1;else r=mid;}cout<<ans<<endl;return 0;
}
反思：做过这道题，甚至不止一次，但考场上没做出来，还是自己学的不太好。
T2 矩阵游戏
反向思考，一个正对角线上都有黑点，每个黑点都来自原图的某一行某一列，因为交换操作，同一列同一行的点始终在同一列同一行。所以原图的这一行和这一列绑定起来贡献一个点在对角线上，所以对每个黑点行列连边。跑二分匹配图，有完美匹配就有解，否则无解。
#include <bits/stdc++.h>
using namespace std;
const int M=4e4+10,N=4e4+10;
int t,n,tot,nxt[M],go[M],hd[N],girl[N],ans;
bool vis[N];
void add(int x,int y)
{nxt[++tot]=hd[x];go[tot]=y;hd[x]=tot;return ;
}
bool find(int x)
{for(int i=hd[x];i;i=nxt[i]){int v=go[i];if(vis[v])continue;vis[v]=1;if(!girl[v]||find(girl[v])){girl[v]=x;return 1;}} return 0;
}
int main()
{freopen("f.in","r",stdin);freopen("f.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--){tot=0,ans=0;memset(hd,0,sizeof(hd)); memset(girl,0,sizeof(girl));cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int x;cin>>x;if(x==1)add(i+n,j);}for(int i=1+n;i<=2*n;i++){ans+=find(i);for(int i=1;i<=n;i++)vis[i]=0;}if(ans==n)cout<<"Yes"<<'\n';else cout<<"No"<<'\n';} return 0;
}
反思：想到了做法，同时写出了程序，但因为一开始遇到不符合条件就输出No，所以有地方没清零，挂了20分，以后每次输出清零后的数组检查。
T3 贪吃蛇
爆搜加一种alpha-beta剪枝，直接做。
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 25
#define CT 51
#define inf 0x3f3f3f3f
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int grid[maxn][maxn],n,m;
int dfs(int rnd,int player,int alpha,int beta,int fx,int fy,int px,int py)
{int flag=0,ans;if(player==1)ans=beta;else ans=alpha;for(int i=0;i<4;i++){int x=fx+dx[i],y=fy+dy[i];if(x&&y&&x<=n&&y<=m&&!grid[x][y]){flag=1;int cur;grid[x][y]=player;if(player==1)cur=dfs(rnd+1,2,alpha,ans,px,py,x,y);else cur=dfs(rnd+1,1,ans,beta,px,py,x,y);grid[x][y]=0;if(player==2&&cur<=beta)return beta;if(player==1&&cur>=alpha)return alpha;if(player==1)ans=max(ans,cur);else ans=min(ans,cur);}}if(!flag){if(player==1)return -CT+rnd;else return CT-rnd;//提示：如果自己能赢,一定会尽量快地赢;如果自己会输,一定会死得尽量晚.}return ans;
}
int main()
{freopen("h.in","r",stdin);freopen("h.out","w",stdout);scanf("%d%d",&n,&m);int x1,y1,x2,y2;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++){scanf("%d",&grid[i][j]);if(grid[i][j]==1) x1=i,y1=j;if(grid[i][j]==2) x2=i,y2=j;}int ans=dfs(1,1,inf,-inf,x1,y1,x2,y2); if(ans<0) printf("2 %d\n",ans+CT);else printf("1 %d\n",CT-ans);return 0;
}
反思：至少应该把爆搜写出来。
T4 信息拦截
挖坑。
