title: 算法学习刷题记录-210717
tags:

  • 算法
  • acwing
  • 每日一题
    abbrlink: 4a21f2a
    date: 2021-07-17 12:29:08

3768. 字符串删减 - AcWing题库

思路

双指针的练习

C++代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. int main()
  8. {
  9.     int n;
  10.     string s;
  11.     cin>>n>>s;
  12.     int res=0;
  13.     for(int i=0;i<n;i++)
  14.     {
  15.         if(s[i]!='x')   continue;
  16.         int j=i+1;
  17.         while(j<n && s[j]=='x') j++;
  18.         res+=max(0, j-i-2);
  19.         i=j-1;
  20.     }
  21.     cout<<res<<endl;
  22.     return 0;
  23. }

3769. 移动石子 - AcWing题库

思路

经典的贪心移动石子问题

C++代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. int main()
  8. {
  9.     int T;
  10.     cin>>T;
  11.     while(T--)
  12.     {
  13.         int n,d;
  14.         cin>>n>>d;
  15.         int res=0;
  16.         for(int i=0;i<n;i++)
  17.         {
  18.             int x;
  19.             cin>>x;
  20.             if(!i)  res+=x;
  21.             else
  22.             {
  23.                 int t=min(x, d/i);
  24.                 res+=t;
  25.                 d-=t*i;
  26.             }
  27.         }
  28.         cout<<res<<endl;
  29.     }
  30.     return 0;
  31. }

3761. 唯一最小数 - AcWing题库

思路

哈希表

代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  6. using namespace std;
  8. const int N = 200010;
  10. int n;
  11. int w[N], cnt[N];
  13. int main()
  14. {
  15.     int T;
  16.     cin>>T;
  17.     while(T--)
  18.     {
  19.         cin>>n;
  20.         memset(cnt, 0, (n+1) * 4);
  21.         for(int i=0;i<n;i++)
  22.         {
  23.             cin>>w[i];
  24.             cnt[w[i]]++;
  25.         }
  26.         int res=-1;
  27.         for(int i=0;i<n;i++)
  28.         {
  29.             if(cnt[w[i]]==1)
  30.             {
  31.                 if(res==-1 || w[res] > w[i])
  32.                     res=i;
  33.             }
  34.         }
  35.         if(res!=-1) res++;
  36.         cout<<res<<endl;
  37.     }
  38.     return 0;
  39. }

3762. 二进制矩阵 - AcWing题库

思路

找规律，每操作三次就可以改变一个方格内的值而不影响其他方格的值，题目未要求最优解，所以以此为据直接进行枚举即可

代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 110;
  9. int n, m;
  10. char g[N][N];
  12. void pL(int i, int j, int k)
  13. {
  14.     if (!k) printf("%d %d %d %d %d %d\n", i, j, i + 1, j, i, j + 1);
  15.     else if (k == 1) printf("%d %d %d %d %d %d\n", i, j - 1, i, j, i + 1, j);
  16.     else if (k == 2) printf("%d %d %d %d %d %d\n", i - 1, j, i, j, i, j - 1);
  17.     else printf("%d %d %d %d %d %d\n", i - 1, j, i, j, i, j + 1);
  18. }
  20. int main()
  21. {
  22.     int T;
  23.     cin >> T;
  24.     while (T -- )
  25.     {
  26.         cin >> n >> m;
  27.         int res = 0;
  28.         for (int i = 1; i <= n; i ++ )
  29.         {
  30.             cin >> g[i] + 1;
  31.             for (int j = 1; j <= m; j ++ )
  32.                 if (g[i][j] == '1')
  33.                     res += 3;
  34.         }
  35.         cout << res << endl;
  36.         for (int i = 1; i <= n; i ++ )
  37.             for (int j = 1; j <= m; j ++ )
  38.                 if (g[i][j] == '1')
  39.                 {
  40.                     if (i < n && j < m)
  41.                         pL(i, j, 0), pL(i, j + 1, 1), pL(i + 1, j, 3);
  42.                     else if (i == n && j == m)
  43.                         pL(i, j, 2), pL(i - 1, j, 1), pL(i, j - 1, 3);
  44.                     else if (i == n)
  45.                         pL(i, j, 3), pL(i - 1, j, 0), pL(i, j + 1, 2);
  46.                     else
  47.                         pL(i, j, 1), pL(i, j - 1, 0), pL(i + 1, j, 2);
  48.                 }
  49.     }
  50.     return 0;
  51. }

3767. 最小的值 - AcWing题库

思路

贪心

代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 110;
  9. int n;
  10. int a[N], b[N];
  12. int main()
  13. {
  14.     cin>>n;
  15.     for(int i=0;i<n;i++)    cin>>a[i];
  16.     for(int i=0;i<n;i++)    cin>>b[i];
  17.     int x=0, y=0;
  18.     for(int i=0;i<n;i++)
  19.         if(a[i]<b[i])   x++;
  20.         else if(a[i] > b[i])    y++;
  21.     if(!y)  puts("-1");
  22.     else cout<<(x+y)/y<<endl;
  24.     return 0;
  25. }