T1 石油采集
这题可以建一张二分图跑最大匹配，也可以直接染色然后数数
#include<bits/stdc++.h>
using namespace std;
char s[60][60];
int c0,c1,n;
void dfs(int x,int y){
if (x>=n||y>=n||x<0||y<0||s[x][y]==‘.‘) return;
(x+y)&1?++c0:++c1;
s[x][y]=‘.‘;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main(){
int t;
scanf("%d",&t);
for (int i=1; i<=t; ++i){
scanf("%d",&n);
int ans=0;
for (int i=0; i<n; ++i) scanf("%s",s[i]);
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (s[i][j]==‘#‘){
c0=0; c1=0;
dfs(i,j);
ans+=min(c0,c1);
}
printf("Case %d: %d
",i,ans);
}
}
T2 道路建设
这题是一道裸的最小生成树
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10010;
int fa[N];
pair<int,pair<int,int> > e[M];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
int c,n,m; scanf("%d%d%d",&c,&m,&n);
for (int i=1; i<=m; ++i) scanf("%d%d%d",&e[i].second.first,&e[i].second.second,&e[i].first);
sort(e+1,e+m+1);
for (int i=1; i<=n; ++i) fa[i]=i;
long long ans=0;
for (int i=1; i<=m; ++i){
int x=e[i].second.first,y=e[i].second.second,z=e[i].first;
x=find(x);
y=find(y);
if (x==y) continue;
fa[x]=y;
ans+=z;
}
printf(ans<=c?"Yes":"No");
}
/*
20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2*/
T3 求交集
这题只需要扫一下即可（输出格式巨坑无比）
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],b[N];
int main(){
int n,m;
vector<int> ans;
scanf("%d%d",&n,&m);
for (int i=1; i<=n; ++i) scanf("%d",&a[i]);
for (int j=1; j<=m; ++j) scanf("%d",&b[j]);
int j=1;
for (int i=1; i<=n; ++i){
for (; j<=m&&b[j]<a[i]; ++j);
if (b[j]==a[i]) ans.push_back(b[j]),++j;
}
if (ans.size()){
for (int i=0; i<(int)ans.size()-1; ++i) printf("%d ",ans[i]); printf("%d",ans.back());
}else printf("empty");
}
T4 小明的挖矿之旅
这题相对来说比较复杂
我的做法是从没有dfs过的最左上的点开始dfs，数dfs到的有几个点下边和右边都是“#”,这题有一个特判很容易漏，就是如果只有一个“.”,就不需要传送门。
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1010;
int ans,n,m,tot;
char mp[N][M];
bool dfs(int x,int y){
if (x<=0||y<=0||x>n||y>m||mp[x][y]==‘#‘) return 1;
// cerr<<x<<" "<<y<<" "<<ans<<endl;
if (mp[x][y]==‘_‘) return 0;
mp[x][y]=‘_‘;
ans+=dfs(x+1,y)&dfs(x,y+1);
return 0;
}
int main(){
cin>>n>>m;
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
cin>>mp[i][j];
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
if (mp[i][j]!=‘#‘){
if (mp[i][j]==‘.‘) dfs(i,j);
++tot;
}
if (tot==1) ans=0;
cout<<ans;
}
T5 通知小弟
这题我的做法好像复杂了，有可能是我想多了
先缩点成一张DAG，再考虑是否所有入度为0的新点都至少包含一个HA可联系的点，如果不是，就输出-1
否则答案就是入度为0的新点个数
#include<bits/stdc++.h>
using namespace std;
const int N=510,M=250010;
stack<int> s;
int nscc,n,m,isc[N],pre[N],low[N],b[M],fi[N],ne[M],k,clk,a[N],rd[N];
void tajan(int x){
s.push(x);
low[x]=pre[x]=++clk;
for (int j=fi[x]; j; j=ne[j]){
if (!pre[b[j]]) tajan(b[j]);
if (!isc[b[j]]) low[x]=min(low[x],low[b[j]]);
}
if (pre[x]==low[x]){
++nscc;
while (1){
int u=s.top(); s.pop();
isc[u]=nscc;
if (u==x) break;
}
}
}
inline void add(int x,int y){
// cerr<<"add:"<<x<<" "<<y<<endl;
b[++k]=y; ne[k]=fi[x]; fi[x]=k;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1; i<=m; ++i) cin>>a[i];
for (int i=1; i<=n; ++i){
int x,y; cin>>x;
while (x--){
cin>>y;
add(i,y);
}
}
for (int i=1; i<=n; ++i) if (!pre[i]) tajan(i);
for (int i=1; i<=n; ++i)
for (int j=fi[i]; j; j=ne[j])
if (isc[i]!=isc[b[j]]) ++rd[isc[b[j]]];
for (int i=1; i<=m; ++i) if (rd[isc[a[i]]]==0) rd[isc[a[i]]]=-1;
for (int i=1; i<=nscc; ++i) if (rd[i]==0) return cout<<-1,0;
int ans=0;
for (int i=1; i<=nscc; ++i) if (rd[i]==-1) ++ans;
cout<<ans;
}
T6 Call to your teacher
这题是一道dfs裸题
#include<bits/stdc++.h>
using namespace std;
const int N=51;
int n,m;
bool b[N];
vector<int> e[N];
void dfs(int x){
b[x]=1;
for (vector<int>::iterator i=e[x].begin(); i!=e[x].end(); ++i)
if (!b[*i]) dfs(*i);
}
int main(){
cin>>n>>m;
while (m--){
int x,y; cin>>x>>y;
e[x].push_back(y);
}
dfs(1);
cout<<(b[n]?"Yes":"No");
}
T7 老子的意大利炮呢
这题先从李云龙所在的终点bfs，处理出每个点据他的距离（不能经过墙）
再暴力枚举三个零件点到达的顺序，算出答案
答案取min。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pa;
const int N=110,C=10;
int dis[N][N];
char mp[N][N];
int n,m,be,px[C],py[C],pz[C],p[C];
inline int di(int x1,int y1,int x2,int y2){
return abs(x1-x2)+abs(y1-y2);
}
void bfs(pa x){
queue<pa> q;
q.push(x);
while (!q.empty()){
int a=q.front().first,b=q.front().second; q.pop();
mp[a][b]=‘#‘;
if (a+1<=n&&mp[a+1][b]==‘.‘){
dis[a+1][b]=dis[a][b]+1;
q.push(pa(a+1,b));
}
if (a-1>=1&&mp[a-1][b]==‘.‘){
dis[a-1][b]=dis[a][b]+1;
q.push(pa(a-1,b));
}
if (b+1<=m&&mp[a][b+1]==‘.‘){
dis[a][b+1]=dis[a][b]+1;
q.push(pa(a,b+1));
}
if (b-1>=1&&mp[a][b-1]==‘.‘){
dis[a][b-1]=dis[a][b]+1;
q.push(pa(a,b-1));
}
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1; i<=n; ++i) cin>>(mp[i]+1);
for (int i=0; i<5; ++i) cin>>px[i]>>py[i];
for (int i=1; i<=3; ++i) cin>>pz[i];
for (int i=1; i<=n; ++i)
memset(dis,0x3f,sizeof(dis));
dis[px[4]][py[4]]=0; bfs(pa(px[4],py[4]));
long long ans=1e18;
for (int i=0; i<3; ++i) p[i]=i+1;
do{
long long pp=di(px[0],py[0],px[p[0]],py[p[0]]);
int g=pz[p[0]]+1;
// cerr<<pp<<" "<<g<<endl;
pp+=di(px[p[0]],py[p[0]],px[p[1]],py[p[1]])*g,g+=pz[p[1]];
// cerr<<pp<<" "<<g<<endl;
pp+=di(px[p[1]],py[p[1]],px[p[2]],py[p[2]])*g,g+=pz[p[2]];
// cerr<<pp<<" "<<g<<endl;
pp+=1ll*dis[px[p[2]]][py[p[2]]]*g;
ans=min(ans,pp);
}while (next_permutation(p,p+3));
cout<<ans;
}
T8 老子的全排列呢
这题直接next_permutation即可（输出格式坑人）
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10];
for (int i=1; i<=8; i++) a[i]=i;
do{
for (int i=1; i<=7; i++) printf("%d ",a[i]); printf("%d",a[8]); puts("");
}while (next_permutation(a+1,a+9));
}