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 信息拦截
挖坑。
标签：总结,return,int,白点,黑点,ans,girl,考试,10.16 From： https://www.cnblogs.com/storms11/p/18474581