当前位置：首页 > news >正文

AtCoder ABC374 A-D题解

news 2025/4/6 8:46:29

省流：忘记打了。其实是 dfs 爆搜专场。

比赛链接:ABC374

Problem A:

#include <bits/stdc++.h>
using namespace std;
int main(){string S;cin>>S;if(S[(int)S.size()-3]=='s' && S[(int)S.size()-2]=='e' && S[(int)S.size()-1]=='n')cout<<"Yes"<<endl;elsecout<<"No"<<endl;return 0;
}

Problem B:

#include <bits/stdc++.h>
using namespace std;
int main(){string S,T;cin>>S>>T;if(S==T){cout<<0<<endl;return 0;}for(int i=0;i<max(S.size(),T.size());i++){if(i==S.size() || i==T.size() || S[i]!=T[i]){cout<<i+1<<endl;return 0;}}return 0;
}

Problem C:

Sol

~~注意到~~ N 很小，因此dfs 爆搜即可。

Code

#include <bits/stdc++.h>
using namespace std;
int N,K[50],ans=INT_MAX+1;
void dfs(int pos,int asum,int bsum){if(pos==N+1){ans=min(ans,max(asum,bsum));return;}dfs(pos+1,asum+K[pos],bsum);dfs(pos+1,asum,bsum+K[pos]);
}
int main(){cin>>N;for(int i=1;i<=N;i++)cin>>K[i];dfs(1,0,0);cout<<ans<<endl;return 0;
}

Problem D:

Sol

我们~~又注意到~~ N 很小，所以 dfs 爆搜。先枚举排列，再枚举每一道线从哪里开始，哪里结束即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn=20;
bool vis[maxn];
double ans=DBL_MAX;
int N,S,T,A[maxn],B[maxn],C[maxn],D[maxn];
double get_dis(int a,int b,int c,int d){return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
void dfs(int num,double t,int x,int y){if(num==N){ans=min(ans,t);return;}for(int i=1;i<=N;i++){if(vis[i])continue;vis[i]=true;dfs(num+1,t+get_dis(x,y,A[i],B[i])/S+get_dis(A[i],B[i],C[i],D[i])/T,C[i],D[i]);dfs(num+1,t+get_dis(x,y,C[i],D[i])/S+get_dis(C[i],D[i],A[i],B[i])/T,A[i],B[i]);vis[i]=false;}
}
int main(){scanf("%d%d%d",&N,&S,&T);for(int i=1;i<=N;i++)scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);dfs(0,0,0,0);printf("%.60lf",ans);return 0;
}