A AquaMoon and Two Arrays

题目大意

给两个长度为n的数组，问a数组是否能通过给一个数+1，另一个数-1操作变成数组b，如果能输出操作步数且打印方案

主要思路

如果suma == sumb那么一定能变成，用st数组记录每个ai - bi的值，所有st数组中大于0的值的和就是操作步数，然后再用两个指针一个指向st中的负数，一个指向st中的正数，输出即可

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 200010;
  20. int n, a[N], b[N];
  21. int st[N];
  23. signed main(void)
  24. {
  25.     int T;
  26.     cin >> T;
  27.     while(T--)
  28.     {
  29.         cin >> n;
  30.         int suma = 0, sumb = 0;
  31.         int cnt = 0;
  32.         for(int i = 0; i < n; i++) cin >> a[i], suma += a[i];
  33.         for(int i = 0; i < n; i++)
  34.         {
  35.             cin >> b[i];
  36.             st[i] = a[i] - b[i];
  37.             sumb += b[i];
  38.             if(st[i] > 0) cnt += st[i];
  39.         }
  41.         if(suma != sumb)
  42.         {
  43.             puts("-1");
  44.         }
  45.         else
  46.         {
  47.             int pos1 = -1, pos2 = -1;
  48.             for(int i = 0; i < n; i++)
  49.             {
  50.                 if(st[i] < 0 && pos1 == -1) pos1 = i;
  51.                 if(st[i] > 0 && pos2 == -1) pos2 = i;
  52.                 if(pos1 != -1 && pos2 != -1)
  53.                 {
  54.                     break;
  55.                 }
  56.             }
  58.             cout << cnt << endl;
  60.             while(pos1 < n || pos2 < n)
  61.             {
  62.                 while(st[pos1] >= 0 && pos1 < n) pos1++;
  63.                 while(st[pos2] <= 0 && pos2 < n) pos2++;
  65.                 if(pos1 < n && pos2 < n && st[pos1] < 0 && st[pos2] > 0)
  66.                 {
  67.                     cout << pos2 + 1 << ' ' << pos1 + 1 << endl;
  68.                     st[pos1]++, st[pos2]--;
  69.                 }
  70.             }
  71.         }
  72.     }
  73.     return 0;
  74. }

B AquaMoon and Stolen String

题目大意

给定n个长度为m的字符串，再给n-1个长度为m的字符串，其中n - 1个字符串是由n个字符串中的n-1个交换每个位置上的元素得到，问n个字符串中没有参与交换的是哪个

主要思路

统计每一列中某个字母的个数，如果某一行的所有字母在每一列中都是奇数 那么这一行就是答案

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 100010;
  20. int n, m;
  21. int st[N][30];
  22. string s[N];
  24. signed main(void)
  25. {
  26.     int T;
  27.     cin >> T;
  28.     while(T--)
  29.     {
  30.         cin >> n >> m;
  31.         memset(st, 0, sizeof(st));
  32.         for(int i = 0; i < n; i++)
  33.         {
  34.             cin >> s[i];
  35.             for(int j = 0; j < m; j++)
  36.             {
  37.                 st[j][s[i][j] - 'a']++;
  38.             }
  39.         }
  40.         for(int i = 0; i < n - 1; i++)
  41.         {
  42.             string s;
  43.             cin >> s;
  44.             for(int j = 0; j < m; j++)
  45.             {
  46.                 st[j][s[j] - 'a']++;
  47.             }
  48.         }
  50.         for(int i = 0; i < n; i++)
  51.         {
  52.             bool flag = true;
  53.             for(int j = 0; j < m; j++)
  54.             {
  55.                 if(st[j][s[i][j] - 'a'] % 2 == 0)
  56.                 {
  57.                     flag = false;
  58.                     break;
  59.                 }
  60.             }
  61.             if(flag)
  62.             {
  63.                 cout << s[i] << endl;
  64.                 break;
  65.             }
  66.         }
  67.     }
  68.     return 0;
  69. }

C AquaMoon and Strange Sort

题目大意

给定一个长度为n的数组，刚开始每个元素都指向右，每次交换相邻两个元素都会是元素指向改变，问能否给该数组排序，同时使最后所有元素还是都指向右

主要思路

每个元素都交换两次才能保证最后每个元素还是指向右边，那么开始在奇数位置的元素还在奇数位置，开始在偶数位置的元素还在偶数位置，那么我们把奇数位置元素记下，偶数元素位置元素记下，直接对原数组排序，如果奇数位置还是那些数，则说明能该边，如果奇数位置不是原来那些数，则说明不能改变

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 100010;
  20. int n, a[N];
  21. int f[2][N];
  23. signed main(void)
  24. {
  25.     int T;
  26.     cin >> T;
  27.     while(T--)
  28.     {
  29.         memset(f, 0, sizeof(f));
  30.         cin >> n;
  31.         for(int i = 0; i < n; i++)
  32.         {
  33.             cin >> a[i];
  34.             f[i % 2][a[i]]++;
  35.         }
  37.         sort(a, a + n);
  38.         for(int i = 0; i < n; i++)
  39.         {
  40.             f[i % 2][a[i]]--;
  41.         }
  43.         bool flag = true;
  44.         for(int i = 0; i < N; i++)
  45.         {
  46.             if(f[0][i] || f[1][i])
  47.             {
  48.                 flag = false;
  49.                 break;
  50.             }
  51.         }
  53.         if(flag) puts("YES");
  54.         else puts("NO");
  55.     }
  56.     return 0;
  57. }

D AquaMoon and Chess

题目大意

给你一个0 1串，1只能隔一个1跳到相邻位置的0(象棋的炮), 问有多少种排列方式

主要思路

1的移动是以11为单位，因此我们可以计算出有多少个11，和计算出有多少个0，相当于n个相同的球放进m个盒子中，且允许空箱，那么答案就为C(n + m - 1, m - 1)，m为1可以在0中插入的位置个数，也就是0的个数+1

不同情况组合数公式见：https://blog.csdn.net/u012720552/article/details/80961684

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 100010, mod = 998244353;
  20. int n;
  22. int qmi(int a, int k, int p)  // 快速幂模板
  23. {
  24.     int res = 1 % p;
  25.     while (k)
  26.     {
  27.         if (k & 1) res = res * a % p;
  28.         a = a * a % p;
  29.         k >>= 1;
  30.     }
  31.     return res;
  32. }
  34. int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
  35. {
  36.     if (a < b) return 0;
  38.     int x = 1, y = 1;  // x是分子，y是分母
  39.     for (int i = a, j = 1; j <= b; i --, j ++ )
  40.     {
  41.         x = x * i % p;
  42.         y = y * j % p;
  43.     }
  45.     return x * qmi(y, p - 2, p) % p;
  46. }
  48. int lucas(int a, int b, int p)
  49. {
  50.     if (a < p && b < p) return C(a, b, p);
  51.     return (int)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
  52. }
  54. signed main(void)
  55. {
  56.     int T;
  57.     cin >> T;
  58.     while(T--)
  59.     {
  60.         cin >> n;
  61.         string s;
  62.         cin >> s;
  63.         int a = 0, b = 0;
  64.         for(int i = 0; i < n; i++)
  65.         {
  66.             if(s[i] == '0') a++;
  67.             else
  68.             {
  69.                 int cnt = 0;
  70.                 while(s[i] == '1')
  71.                 {
  72.                     cnt++;
  73.                     i++;
  74.                 }
  75.                 b += cnt / 2;
  76.                 i--;
  77.             }
  78.         }
  79.         a++;
  80.         cout << lucas(a + b - 1, a - 1, mod) << endl;
  81.     }
  82.     return 0;
  83. }