• Atcoder Beginner Contest 294

    A - Filter

    AC代码：

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. int main()
    6. {
    7.     int n;
    8.     cin>>n;
    9.     for(int i=0;i
    10.         int x;
    11.         cin>>x;
    12.         if(x%2==0)cout<" ";
    13.      }
    14.     return 0;
    15. }

    B - ASCII Art

    AC代码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. const int N=110;
    7. int a[N][N];
    8. int main()
    9. {
    10.     int h,w;
    11.     cin>>h>>w;
    12.     for(int i=1;i<=h;i++){
    13.         for(int j=1;j<=w;j++){
    14.             cin>>a[i][j];
    15.         }
    16.     }
    17.     for(int i=1;i<=h;i++){
    18.         for(int j=1;j<=w;j++){
    19.             if(a[i][j]==0) cout<<'.';
    20.             else{
    21.                 printf("%c",'A'+a[i][j]-1);
    22.             }
    23.         }
    24.         cout<
    25.     }
    26.     return 0;
    27. }

    C - Merge Sequences

    大致题意就是对于A的每一个数，输出它们在所有数中(A和B的所有数)是第几小的数，对于B的每一个数，输出它们在所有数中是第几小的数

    可以用两个指针分别遍历A和B中的每个数，然后两两比较，小的那个数就可以给它标记是第几小的数，双指针要注意边界问题，之前也做过类似的题目，经常搞不清边界，在这时就可以

    用样例来试，发现如果A或B一边全部标记完了，那么剩下的就需要全部依次标记，可以将a[n+1]和b[m+1]初始化为超级大的数，这样的话，一边全部标记好之后，就可以把剩下的数依次标记了

    注意while(l<=n||r<=m)用或而不是且

    AC代码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. const int N=1e5+10;
    7. int a[N],b[N];
    8. int idxa[N],idxb[N];
    9. int main()
    10. {
    11.     int n,m;
    12.     cin>>n>>m;
    13.     for(int i=1;i<=n;i++) cin>>a[i];
    14.     a[n+1]=1e9+10;
    15.     for(int i=1;i<=m;i++) cin>>b[i];
    16.     b[m+1]=1e9+10;
    17.     int l=1,r=1;
    18.     int idx=1;
    19.     while(l<=n||r<=m){
    20.         if(a[l]
    21.             idxa[l]=idx;
    22.             l++;
    23.             idx++;
    24.         }
    25.         else if(a[l]>b[r]){
    26.             idxb[r]=idx;
    27.             r++;
    28.             idx++;
    29.         }
    30.     }
    31.     for(int i=1;i<=n;i++) cout<" ";
    32.     cout<
    33.     for(int i=1;i<=m;i++) cout<" ";
    34.     cout<
    35.     return 0;
    36. }

    D - Bank 

     

    超时代码： 

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. const int N=5e5+10;
    8. bool flag[N];//表示是否被呼叫过 
    9. set<int>s;
    10. int main()
    11. {
    12.     int n,q;
    13.     cin>>n>>q;
    14.     for(int i=1;i<=n;i++) s.insert(i);
    15.     while(q--){
    16.         int op;
    17.         cin>>op;
    18.         if(op==1){
    19.             for(auto v:s){
    20.                 if(!flag[v]){
    21.                     flag[v]=true;
    22.                     break;
    23.                 }
    24.             }
    25.         }
    26.         else if(op==2){
    27.             int x;
    28.             cin>>x;
    29.             s.erase(x);
    30.         }
    31.         else{
    32.             for(auto v:s){
    33.                 if(flag){
    34.                     cout<
    35.                     break;
    36.                 }
    37.             }
    38.         }
    39.     } 
    40.     return 0;
    41. }

    实际上根本没必要用flag标记是否被呼叫过，如果是第一次被呼叫，那么直接将其放入set中，set中的就表示被呼叫过但没来的人，如果呼叫过然后来了的人就从set中删去

    AC代码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. set<int>s;
    8. int main()
    9. {
    10.     int n,q;
    11.     cin>>n>>q;
    12.     int idx=1;
    13.     while(q--){
    14.         int op;
    15.         cin>>op;
    16.         if(op==1){
    17.             s.insert(idx);//表示被呼叫过但没来
    18.             idx++;
    19.         }
    20.         else if(op==2){
    21.             int x;
    22.             cin>>x;
    23.             s.erase(x);//被呼叫过然后来了的
    24.         }
    25.         else{
    26.             cout<<*s.begin()<
    27.         }
    28.     }
    29.     return 0;
    30. }

    E - 2xN Grid

    大致题意是有一个行为2列为L的矩阵

    这样输入：输入N1对数字(x,y),表示数字x有y个，依次填入第一行

    同理，输入N2对数字(x,y)，表示数字x有y个，依次填入第二行

    最终，同一列的两个数字相等算一组，问一共有几组

    首先，不能一个一个的填，因为L可以达到1e12，一个一个的填必定超时，共有N1+N2对，可以一对一对填，这样不会超时

    然后填完之后，可以利用双指针进行判断，同时枚举上一边和下一边

     

     代码如下：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define int long long
    8. using namespace std;
    9. vectorint,int>>a,b;
    10. signed main()
    11. {
    12.     int len,n1,n2;
    13.     cin>>len>>n1>>n2;
    14.     for(int i=1;i<=n1;i++){
    15.         int x,y;
    16.         cin>>x>>y;
    17.         a.push_back({x,y});
    18.     }
    19.     for(int i=1;i<=n2;i++){
    20.         int x,y;
    21.         cin>>x>>y;
    22.         b.push_back({x,y});
    23.     }
    24.     int l=0,r=0;
    25.     int len1=a[0].second,len2=b[0].second;
    26.     int res=0;
    27.     if(a[0].first==b[0].first) res+=min(len1,len2);
    28.     while(len1<=len||len2<=len){
    29.         if(len1<=len2){
    30.             l++;
    31.             if(a[l].first==b[r].first) res+=min(a[l].second,len2-len1);
    32.             len1+=a[l].second;
    33.         }
    34.         else{
    35.             r++;
    36.             if(b[r].first==a[l].first) res+=min(b[r].second,len1-len2);
    37.             len2+=b[r].second;
    38.         }
    39.     }
    40.     cout<
    41.     return 0;
    42. }

    进行改进：加上 

    if(len1==len&&len2==len) break;//如果双指针用while加if和else的话，最后不要忘记再加一句以退出循环

     这样就没有RE了，此时还有点小错误，看来大方向是没问题的，只不过有一些小细节没有处理好，可能有特殊情况没有考虑到

    代码如下： 

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define int long long
    8. using namespace std;
    9. vectorint,int>>a,b;
    10. signed main()
    11. {
    12.     int len,n1,n2;
    13.     cin>>len>>n1>>n2;
    14.     for(int i=1;i<=n1;i++){
    15.         int x,y;
    16.         cin>>x>>y;
    17.         a.push_back({x,y});
    18.     }
    19.     for(int i=1;i<=n2;i++){
    20.         int x,y;
    21.         cin>>x>>y;
    22.         b.push_back({x,y});
    23.     }
    24.     int l=0,r=0;
    25.     int len1=a[0].second,len2=b[0].second;
    26.     int res=0;
    27.     if(a[0].first==b[0].first) res+=min(len1,len2);
    28.     while(len1<=len||len2<=len){
    29.         if(len1<=len2){
    30.             l++;
    31.             if(a[l].first==b[r].first) res+=min(a[l].second,len2-len1);
    32.             len1+=a[l].second;
    33.         }
    34.         else{
    35.             r++;
    36.             if(b[r].first==a[l].first) res+=min(b[r].second,len1-len2);
    37.             len2+=b[r].second;
    38.         }
    39.         if(len1==len&&len2==len) break;
    40.     }
    41.     cout<
    42.     return 0;
    43. }

    再进行改进，依旧是对边界的改进，改完之后又对了一个测试点 

    1. if(len1
    2. if(len2

     代码如下：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define int long long
    8. using namespace std;
    9. vectorint,int>>a,b;
    10. signed main()
    11. {
    12.     int len,n1,n2;
    13.     cin>>len>>n1>>n2;
    14.     for(int i=1;i<=n1;i++){
    15.         int x,y;
    16.         cin>>x>>y;
    17.         a.push_back({x,y});
    18.     }
    19.     for(int i=1;i<=n2;i++){
    20.         int x,y;
    21.         cin>>x>>y;
    22.         b.push_back({x,y});
    23.     }
    24.     int l=0,r=0;
    25.     int len1=a[0].second,len2=b[0].second;
    26.     int res=0;
    27.     if(a[0].first==b[0].first) res+=min(len1,len2);
    28.     while(len1<=len||len2<=len){
    29.         if(len1<=len2){
    30.             if(len1
    31.             if(a[l].first==b[r].first) res+=min(a[l].second,len2-len1);
    32.             len1+=a[l].second;
    33.         }
    34.         else{
    35.             if(len2
    36.             if(b[r].first==a[l].first) res+=min(b[r].second,len1-len2);
    37.             len2+=b[r].second;
    38.         }
    39.         if(len1==len&&len2==len) break;
    40.     }
    41.     cout<
    42.     return 0;
    43. }

    此时样例错了一个，而且是样例二，第一行为1e10个1，第二行也为1e10个1

    试了一下，发现res一开始+=1e10，然后len1变成了2e10，导致没有退出循环，后面res又加了，真是个巧合，这边可以避免len1变成2e10，即将res+=和len1+=都放到if(len1

    AC代码： 

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define int long long
    8. using namespace std;
    9. vectorint,int>>a,b;
    10. signed main()
    11. {
    12.     int len,n1,n2;
    13.     cin>>len>>n1>>n2;
    14.     for(int i=1;i<=n1;i++){
    15.         int x,y;
    16.         cin>>x>>y;
    17.         a.push_back({x,y});
    18.     }
    19.     for(int i=1;i<=n2;i++){
    20.         int x,y;
    21.         cin>>x>>y;
    22.         b.push_back({x,y});
    23.     }
    24.     int l=0,r=0;
    25.     int len1=a[0].second,len2=b[0].second;
    26.     int res=0;
    27.     if(a[0].first==b[0].first) res+=min(len1,len2);
    28.     while(len1<=len||len2<=len){
    29.         if(len1<=len2){
    30.             if(len1
    31.                 l++;
    32.                    if(a[l].first==b[r].first) res+=min(a[l].second,len2-len1);
    33.                 len1+=a[l].second;
    34.             }
    35.         
    36.         }
    37.         else{
    38.             if(len2
    39.                 r++;
    40.                 if(b[r].first==a[l].first) res+=min(b[r].second,len1-len2);
    41.                 len2+=b[r].second;
    42.             }
    43.         }
    44.         if(len1==len&&len2==len) break;
    45.     }
    46.     cout<
    47.     return 0;
    48. }

    或者将len1==len改为大于等于

    AC代码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define int long long
    8. using namespace std;
    9. vectorint,int>>a,b;
    10. signed main()
    11. {
    12.     int len,n1,n2;
    13.     cin>>len>>n1>>n2;
    14.     for(int i=1;i<=n1;i++){
    15.         int x,y;
    16.         cin>>x>>y;
    17.         a.push_back({x,y});
    18.     }
    19.     for(int i=1;i<=n2;i++){
    20.         int x,y;
    21.         cin>>x>>y;
    22.         b.push_back({x,y});
    23.     }
    24.     int l=0,r=0;
    25.     int len1=a[0].second,len2=b[0].second;
    26.     int res=0;
    27.     if(a[0].first==b[0].first) res+=min(len1,len2);
    28.     while(len1<=len||len2<=len){
    29.         if(len1<=len2){
    30.             if(len1
    31.             if(a[l].first==b[r].first) res+=min(a[l].second,len2-len1);
    32.             len1+=a[l].second;
    33.         }
    34.         else{
    35.             if(len2
    36.             if(b[r].first==a[l].first) res+=min(b[r].second,len1-len2);
    37.             len2+=b[r].second;
    38.         }
    39.         if(len1>=len&&len2>=len) break;
    40.     }
    41.     cout<
    42.     return 0;
    43. }

     总的来说，一开始大致方向是对的，双指针主要难点在于处理边界问题

  • 相关阅读:
    【C++】unordered_map和unordered_set
    vivado时序分析-2时序分析关键概念
    MMKV（2）
    前端面试题（14）｜求职季面试题分享｜答案
    一个基于RedisTemplate静态工具类
    (01)ORB-SLAM2源码无死角解析-(38) EPnP 源代码分析(1)→PnPsolver总体流程与思路
    SQL Server详细使用教程(包含启动SQL server服务、建立数据库、建表的详细操作) 非常适合初学者
    Linux常用命令——clock命令
    论文阅读《Robust Monocular Depth Estimation under Challenging Conditions》
    单行函数，聚合函数课后练习
  • 原文地址：https://blog.csdn.net/m0_74087709/article/details/131142517