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

AtCoder ABC371 A-D题解

news 来源：原创 2024/10/1 4:52:30

省流：赛场上不会 C。

比赛链接:ABC371

Problem A:

Sol

if 暴力判断即可。

Code

#include <bits/stdc++.h>
using namespace std;
int main(){char SAB,SAC,SBC;cin>>SAB>>SAC>>SBC;if(SAB=='>' && SBC=='>')cout<<"b"<<endl;else if(SAB=='>' && SBC=='<' && SAC=='>')cout<<"c"<<endl;else if(SAB=='>' && SBC=='<' && SAC=='<')cout<<"a"<<endl;else if(SAB=='<' && SBC=='<')cout<<"b"<<endl;else if(SAB=='<' && SBC=='>' && SAC=='<')cout<<"c"<<endl;else if(SAB=='<' && SBC=='>' && SAC=='>')cout<<"a"<<endl;return 0;
}

Problem B:

Sol

简单哪一个数组记录即可。

Code

#include <bits/stdc++.h>
using namespace std;
bool have[105];
int main(){int N,M;cin>>N>>M;for(int i=1;i<=M;i++){int A;char B;cin>>A>>B;if(B=='M' && !have[A]){cout<<"yes"<<endl;have[A]=true;}elsecout<<"no"<<endl;}return 0;
}

Problem D:

Sol

首先对村庄的位置离散化，用 $loc$ 数组记录。然后用 $sum$ 统计前缀和。然后在 $loc$ 数组上二分 $L_i$ 和 $R_i$ 后求前缀和即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200005;
struct village{int X;int P;
}country[maxn];
int loc[maxn],sum[maxn];
bool cmp(village a,village b){return a.X<b.X;
}
signed main(){int N;cin>>N;for(int i=1;i<=N;i++)cin>>country[i].X;for(int i=1;i<=N;i++)cin>>country[i].P;sort(country+1,country+N+1,cmp);for(int i=1;i<=N;i++){loc[i]=country[i].X;sum[i]=country[i].P+sum[i-1];cout<<sum[i]<<' ';}int Q;cin>>Q;while(Q--){int L,R;cin>>L>>R;int l=lower_bound(loc+1,loc+N+1,L)-loc;int r=upper_bound(loc+1,loc+N+1,R)-loc-1;if(l>r || (l==N+1 && r==N+1)){cout<<0<<endl;continue;}if(l==N+1)l=N;if(r==N+1)r=N;cout<<sum[r]-sum[l-1]<<endl;}return 0;
}

Problem C:

Sol

~~注意到~~本题 $N\leq 8$ ，可以全排列枚举所有情况，取最小值。时间复杂度 $\Theta (n!)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
const int INF=0x3f3f3f3f;
int N,MG,MH,u1[maxn],a1[maxn],v1[maxn],b1[maxn],A[maxn][maxn];
int h[maxn][maxn],g[maxn][maxn],mark[maxn],ans=INF;
void dfs(int pos){if(pos>N){for(int i=1;i<=MG;i++)h[mark[u1[i]]][mark[v1[i]]]=h[mark[v1[i]]][mark[u1[i]]]=1;int sum=0;for(int i=1;i<N;i++){for(int j=i+1;j<=N;j++){if(h[i][j]==g[i][j])continue;sum+=A[i][j];}}ans=min(ans,sum);memset(h,0,sizeof(h));return;}for(int i=1;i<=N;i++){if(!mark[i]){mark[i]=pos;dfs(pos+1);mark[i]=0;}}
}
int main(){cin>>N;cin>>MG;for(int i=1;i<=MG;i++)cin>>u1[i]>>v1[i];cin>>MH;for(int i=1;i<=MH;i++){cin>>a1[i]>>b1[i];g[a1[i]][b1[i]]=g[b1[i]][a1[i]]=1;}for(int i=1;i<N;i++){for(int j=i+1;j<=N;j++){cin>>A[i][j];A[j][i]=A[i][j];}}dfs(1);cout<<ans<<endl;return 0;
}