AtCoder ABC376A-D题解

个人以为 ABC 变得越来越难了/kk/kk/kk
比赛链接:ABC376

Problem A:

Code

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.         int N,C;
5.         cin>>N>>C;
6.         for(int i=1;i<=N;i++)
7.                 cin>>T[i];
8.         int ans=0,pre=-1e5;
9.         for(int i=1;i<=N;i++){
10.                 if(T[i]-pre>=C){
11.                         ans++;
12.                         pre=T[i];
13.                 }
14.         }
15.         cout<<ans<<endl;
16.         return 0;
17. }

复制代码

Problem B:

我愿称之为史上最难 B 没有之一。
Sol

暴力模仿即可。注意细节。
Code

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.         int N,Q;
5.         cin>>N>>Q;
6.         int l=1,r=2,ans=0;
7.         while(Q--){
8.                 char H;
9.                 int T;
10.                 cin>>H>>T;
11.                 if(H=='L'){
12.                         if((l<T && T<r) || (T<r && r<l) || (r<l && l<T)){
13.                                 for(;l!=T;l++){
14.                                         if(l==N+1)
15.                                                 l=1;
16.                                         if(l==T)
17.                                                 break;
18.                                         ans++;
19.                                 }
20.                         }
21.                         else{
22.                                 for(;l!=T;l--){
23.                                         if(l==0)
24.                                                 l=N;
25.                                         if(l==T)
26.                                                 break;
27.                                         ans++;
28.                                 }
29.                         }
30.                 }
31.                 else{
32.                         if((l<T && T<r) || (r<l && l<T) || (T<r && r<l)){
33.                                 for(;r!=T;r--){
34.                                         if(r==0)
35.                                                 r=N;
36.                                         if(r==T)
37.                                                 break;
38.                                         ans++;
39.                                 }
40.                         }
41.                         else{
42.                                 for(;r!=T;r++){
43.                                         if(r==N+1)
44.                                                 r=1;
45.                                         if(r==T)
46.                                                 break;
47.                                         ans++;
48.                                 }
49.                         }                       
50.                 }
51.         }
52.         cout<<ans<<endl;
53.         return 0；
54. }

复制代码

Problem C:

我以为 C>D。
Sol

二分套二分。思量二分答案。在 check 函数中又要二分第一个大于等于

的数。在代码中，我选择了二分答案的下标。
Code

1. #include <bitch/stdc++.h>
2. using namespace std;
3. const int maxn=200005;
4. int N,A[maxn],B[maxn];
5. bool check(int x){
6.         for(int i=1;i<=N;i++){
7.                 if(i==x)
8.                         continue;
9.                 if(A[i]>B[i-(i>x)])
10.                         return false;
11.         }
12.         return true;
13. }
14. int main(){
15.         cin>>N;
16.         for(int i=1;i<=N;i++)
17.                 cin>>A[i];
18.         for(int i=1;i<N;i++)
19.                 cin>>B[i];
20.         sort(A+1,A+N+1);
21.         sort(B+1,B+N);
22.         int l=1,r=N;
23.         while(l<r){
24.                 int mid=(l+r)>>1;
25.                 if(check(mid))
26.                         r=mid;
27.                 else
28.                         l=mid+1;
29.         }
30.         if(check(l))
31.                 cout<<A[l]<<endl;
32.         else
33.                 cout<<-1<<endl;
34.     return 0;
35. }

复制代码

Problem D:

Sol

思量 bfs。从 1 开始，只要第二次遍历到 1 就输出即可。
Code

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int maxn=200005;
4. bool vis[maxn];
5. vector<int> graph[maxn];
6. queue<pair<int,int>> que;
7. int bfs(){
8.         while(!que.empty()){
9.                 pair<int,int> u=que.front();
10.                 que.pop();
11.                 for(auto v:graph[u.first]){
12.                         if(v==1)
13.                                 return (u.second+1);
14.                         if(!vis[v]){
15.                                 que.push(make_pair(v,u.second+1));
16.                                 vis[v]=true;
17.                         }
18.                 }
19.         }
20.         return -1;
21. }
22. int main(){
23.         int N,M;
24.         cin>>N>>M;
25.         for(int i=1;i<=M;i++){
26.                 cin>>a>>b;
27.                 graph[a].push_back(b);
28.         }
29.         que.push(make_pair(1,0));
30.         cout<<bfs()<<endl;
31.     return 0;
32. }

复制代码

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


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。