AtCoder ABC374 A-D题解

省流：忘记打了。其实是 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;
	else
		cout<<"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;
}

友情提醒:不要无脑Ctrl C+Ctrl V