• 题解2023.5.23（欧拉筛）

    C.Hossamand Trainees
     欧拉筛,预处理先筛出质数，分解质因数对于出现两次及以上的输出yes
     我们需要筛出根号(1e9)以内的所有质数，根据质数定理，大约有4e^3个质数，
     时间复杂度分析：le5*4e3=4e8

    1. #include
    2. #pragma GCC optimize(2)
    3. #pragma GCC optimize(3)
    4. #pragma GCC optimize(fast) 
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #define ms(x,y) memset(x,y,sizeof x)
    15. #define int long long 
    16. const int maxn = 2e5 + 10, INF = 0x3f3f3f3f;
    17. using namespace std;
    18. int a[maxn];
    19. int cnt = 0;
    20. int st[1000060];
    21. int p[1000060];
    22. void init() {
    23.     for (int i = 2; i < 40000; i++) {
    24.         if (!st[i])
    25.             p[cnt++] = i;
    26.         for (int j = 0; p[j] * i < 40000; j++) {
    27.             st[p[j] * i] = true;
    28.             if (i % p[j] == 0)
    29.                 break;
    30.         }
    31.     }
    32. }
    33. void solve() {
    34.     int n;
    35.     cin >> n;
    36.     map<int, int>mp;
    37.     for (int i = 1; i <= n; i++) {
    38.         cin >> a[i];
    39.     }
    40.     for (int i = 1; i <= n; i++) {
    41.         int num = a[i];
    42.         for (int j = 0; p[j] * p[j] <= num; j++) {
    43.             int p1 = p[j];
    44.             if (num % p1 == 0) {
    45.                 while (num % p1 == 0) {
    46.                     num /= p1;
    47.                 }
    48.                 mp[p1]++;
    49.                 if (mp[p1] > 1) {
    50.                     cout << "YES" << '\n';
    51.                     return;
    52.                 }
    53.  
    54.             }
    55.         }
    56.         if (num >1)mp[num]++;
    57.         if (mp[num] > 1) {
    58.             cout << "YES" << '\n';
    59.             return;
    60.         }
    61.     }
    62.     cout << "NO" << '\n';
    63. }
    64. signed main()
    65. {
    66.     ios::sync_with_stdio(false);
    67.     init();
    68.     int t;
    69.     cin >> t;
    70.     while (t--) {
    71.         solve();
    72.     }
    73. }


    B.Hossamand Friends
     思路：双指针，用一个数组记录右指针可取的最大左边界
     

    1. #include
    2. #pragma GCC optimize(2)
    3. #pragma GCC optimize(3)
    4. #pragma GCC optimize(fast) 
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13.  #include
    14. #define ms(x,y) memset(x,y,sizeof x)
    15. #define int long long 
    16. const int maxn=2e5+10,INF = 0x3f3f3f3f ; 
    17. using namespace std;
    18. int a[maxn];
    19.  void solve(){
    20.      int n, m;
    21.      cin >> n >> m;
    22.      vector<int>l(n+1);  //左边界
    23.      for (int i = 1; i <= m; i++) {
    24.          int x, y;
    25.          cin >> x >> y;
    26.          if (x < y)swap(x, y);
    27.          l[x] = max(l[x], y);
    28.      }
    29.      int sum = 0;
    30.      int r = 1;
    31.      for (int i = 1; i <=n; i++) {
    32.          while (r + 1 <= n && l[r + 1] < i) ++r;
    33.          sum += (r-i + 1);
    34.      }
    35.      cout << sum << '\n';
    36.  }
    37. signed main()
    38. {
    39.     ios::sync_with_stdio(false);
    40.     int t;
    41.     cin >> t;
    42.     while (t--) {
    43.         solve();
    44.     }
    45. }


    G.Chevonne’s Necklace
    思路：采用dp,01背包,可取大小视为体积，
    因为选择移除的珍珠(p1,p2...)可取大小(ap1+ap2...)的和<=n,至少存在一个下一次选中的珍珠与上一次选中珍珠的距离dis>cpi,否则矛盾
    故移除顺序不影响方案数，最终选中的珍珠是从珍珠1开始的连续编号.
     

    1. #include
    2. #pragma GCC optimize(2)
    3. #pragma GCC optimize(3)
    4. #pragma GCC optimize(fast) 
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13.  #include
    14. #define ms(x,y) memset(x,y,sizeof x)
    15. #define int long long 
    16. const int maxn=2e5+10,INF = 0x3f3f3f3f ; 
    17. const int mod = 998244353;
    18. using namespace std;
    19. int a[maxn];
    20. int dp[maxn];   //记录方案数,dp[i]表示当取i个珍珠时的最大方案数
    21. bool vis[maxn];
    22. void solve(){
    23.      int n;
    24.      cin >> n;
    25.      for (int i = 0; i
    26.          cin >> a[i];
    27.      }
    28.      dp[0] = 1;
    29.      vis[0] = 1;
    30.      for (int i = 0; i < n; i++) {  //枚举珍珠编号
    31.          if (a[i] >= 1) {
    32.              for (int j = n; j >= a[i]; j--) {    //01
    33.                  vis[j] |= vis[j-a[i]];   //记录珍珠状态
    34.                  dp[j] = (dp[j] + dp[j - a[i]]) % mod;
    35.              }
    36.          }
    37.      }
    38.      int sum = n;
    39.      while (!vis[sum]) {
    40.          sum--;
    41.      }
    42.      cout << sum << ' ' << dp[sum]%mod << '\n';
    43.  }
    44. signed main()
    45. {
    46.     ios::sync_with_stdio(false);
    47.         solve();
    48. }


    G - ORXOR
    思路：状态压缩，枚举所有状态，对标记点集合异或，集合元素或运算
     

    1. #include
    2. #pragma GCC optimize(2)
    3. #pragma GCC optimize(3)
    4. #pragma GCC optimize(fast) 
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13.  #include
    14.  #include
    15. #define ms(x,y) memset(x,y,sizeof x)
    16. #define int long long 
    17. const int maxn=2e5+10,INF = 1e18 ; 
    18. using namespace std;
    19. int a[maxn];
    20.  void solve(){
    21.      int n;
    22.      cin >> n;
    23.      for (int i = 0; i < n; i++) {
    24.          cin >> a[i];
    25.      }
    26.      int Min = INF;
    27.      for (int i = 0; i <(1<//枚举所有状态
    28.          int t1=0, t2=0;
    29.          for (int j = 0; j <= n; j++) {  //枚举所有元素,多一次进行最终合并
    30.              if (j < n)  t1 |= a[j];      //|00为0
    31.              if (j == n || i & ((1) << j)) {
    32.                  t2 ^= t1;
    33.                  t1 = 0;
    34.              }
    35.          }
    36.          Min = min(Min, t2);
    37.      }
    38.      cout << Min << '\n';
    39.  }
    40. signed main()
    41. {
    42.     ios::sync_with_stdio(false);
    43.     int t;
    44.     solve();
    45. }

    C:Hamiltonian Wall
    题意：能否一笔把B格子全部画完(一笔画完)
    思路：使用dp，记录最后一个B位置和第一个B位置,若最后一列的B能否由开头转移过来,则YES,否则NO
    转移的策略有三种，
    1.一列有两个B,转移位置与上一列B转移位置相异；
    2.一列有一个B,位置与上一列(一个B)位置相同
    3.一列有一个B,位置与上一列(两个B)转移位置相同

    1. #pragma GCC optimize(2)
    2. #pragma GCC optimize(3)
    3. #pragma GCC optimize(fast) 
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12.  #include
    13.  #include
    14. #define ms(x,y) memset(x,y,sizeof x)
    15. #define int long long 
    16. const int maxn=2e5+10,INF = 1e18 ; 
    17. using namespace std;
    18. int a[3][maxn];
    19. int f[maxn][3];   
    20.  void solve(){
    21.      int n;
    22.      cin >> n;
    23.      for (int i = 1;i<=2; i++) {
    24.          for (int j = 1; j <= n; j++) {
    25.              char c;
    26.              cin >> c;
    27.              if (c == 'B')
    28.                  a[i][j] = 1;
    29.              else
    30.                  a[i][j] = 0;
    31.          }
    32.      }
    33.      int Min = n+1, Max = -1, flag = 0;
    34.      for (int i = 1; i <= n; i++) {
    35.          f[i][1] = 0;
    36.          f[i][2] = 0;
    37.          if (a[1][i] || a[2][i]) {
    38.              Min = min(Min, i);
    39.              Max = max(Max, i);
    40.              flag = 1;
    41.          }
    42.      }
    43.      if (!flag) {
    44.          cout << "YES" << '\n';
    45.          return;
    46.      }
    47.      f[Min][1] = (a[1][Min] == 1);
    48.      f[Min][2] = (a[2][Min] == 1);
    49.      for (int i = Min+1; i <= Max; i++) {
    50.          if (a[1][i] == 1 && a[2][i] == 1) {
    51.              f[i][1] = f[i - 1][2];
    52.              f[i][2] = f[i - 1][1];
    53.          }
    54.          if (a[1][i] == 1 && a[2][i] == 0) {
    55.              f[i][1] = f[i - 1][1];
    56.          }
    57.          if (a[1][i] == 0 && a[2][i] == 1) {
    58.              f[i][2] = f[i - 1][2];
    59.          }
    60.      }
    61.      if (f[Max][1] || f[Max][2]) {
    62.          cout << "YES" << '\n';
    63.      }
    64.      else {
    65.          cout << "NO" << '\n';
    66.      }
    67.  
    68.  }
    69. signed main()
    70. {
    71.     ios::sync_with_stdio(false);
    72.     int t;
    73.     cin >> t;
    74.     while (t--) {
    75.         solve();
    76.     }
    77. }


     

  • 相关阅读:
    Apollo配置更新通知
    Linux64Bit下安装MySQL5.6-不能修改root密码
    【强烈推荐】视频转gif、图片拼gif，嘎嘎好用，免费免费真的免费，亲测有效，无效过来打我
    shared_ptr初始化、循环引用、线程安全问题
    同步FIFO的verilog实现（2）——高位扩展法
    Qt 设置程序置顶
    CSS设置鼠标样式和添加视频样式
    【FPGA教程案例62】硬件开发板调试2——使用ila核在线调试，ila数据保存，读取，matlab辅助分析
    Skywalking流程分析_8(拦截器插件的加载)
    springboot 如何解决循环依赖
  • 原文地址：https://blog.csdn.net/m0_75027890/article/details/130837997