A 取因数

题目大意

在纸上写一个数字 n，双方每次选择 n 的一个因数，然后划掉 n 并在纸上写下 n 减去这个数字的差使之成为新的 n，最后写数字 0 的人输。Alice先手。

主要思路

  • 奇数的因数都是奇数，因此奇数一定会变成偶数
  • 偶数可以通过-1变成奇数
  • 那么如果先手是偶数，那么可以通过-1维持对手是奇数，自己一直是偶数，持续到自己为2时，对手为1，对手必输，先手必胜

结论：偶数先手必胜，奇数先手必输

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];
  22. signed main(void)
  23. {
  24.     cin >> n;
  25.     if(n % 2) puts("Bob");
  26.     else puts("Alice");
  27.     return 0;
  28. }

B A + B

题目大意

中文题

主要思路

n最大是100，因为k只有2，所以分3种情况即可

  • k == 0，可以从1020往后枚举n个
  • k == 1，可以枚举a = 10, b = 1, c = 11, 每轮b++, c++
  • k == 2，枚举a = 1, b = 11, c = 12，每轮a++, b为两个a合并(比如a = 1，b变为11，a为2，b变为22)，c = a + b，也就是a + aa == aa + a形式

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];
  22. int f(int x)
  23. {
  24.     int t = x;
  25.     int cnt = 0;
  26.     while(x)
  27.     {
  28.         x /= 10;
  29.         cnt++;
  30.     }
  31.     return t * (int)pow(10, cnt) + t;
  32. }
  34. signed main(void)
  35. {
  36.     int n, k;
  37.     cin >> k >> n;
  38.     if(k == 0)
  39.     {
  40.         int t = 1020;
  41.         for(int i = 0; i < n; i++)
  42.         {
  43.             cout << t << endl;
  44.             t++;
  45.         }
  46.     }
  47.     else if(k == 1)
  48.     {
  49.         int a = 10, b = 1, c = 11;
  50.         for(int i = 0; i < n; i++)
  51.         {
  52.             cout << a << b << c << endl;
  53.             b++, c++;
  54.         }
  55.     }
  56.     else
  57.     {
  58.         int a = 1, b = 11, c = 12;
  59.         for(int i = 0; i < n; i++)
  60.         {
  61.             cout << a << b << c << endl;
  62.             a++, b = f(a), c = a + b;
  63.         }
  64.     }
  65.     return 0;
  66. }

C 取钱

题目大意

中文题

主要思路

我们先预处理出用a[i]纸币能凑不超过a[i + 1]金额的金额最大值sum和纸币张数cnt。

读入每一个金额b，先二分出小于等于b的a[i]的最大值，然后获得纸币数量最大值为cnt[i - 1] + (b - sum[i - 1]) / a[i], 金额为sum[i - 1] + (b - sum[i - 1]) / a[i] + a[i]

核心思想：贪心，从小到大将每一个a[i]的数量最大化

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];
  21. int cnt[N];
  22. int sum[N];
  24. signed main(void)
  25. {
  26.     cin >> n;
  27.     for(int i = 1; i <= n; i++) cin >> a[i];
  28.     a[n + 1] = 1e18+1;
  29.     for(int i = 1; i <= n; i++)
  30.     {
  31.         int t = (a[i + 1] - sum[i - 1] - 1) / a[i];//t为最大金额小于a[i + 1]，会用到最多多少a[i]
  32.         cnt[i] = cnt[i - 1] + t;//总纸币数量
  33.         sum[i] = sum[i - 1] + a[i] * t;//总价
  34.     }
  36.     int T;
  37.     cin >> T;
  38.     while(T--)
  39.     {
  40.         int num;
  41.         cin >> num;
  42.         int l = 0, r = n + 1;
  43.         while(l < r)//二分小于等于当前num的最大面额
  44.         {
  45.             int mid = l + r + 1 >> 1;
  46.             if(a[mid] <= num) l = mid;
  47.             else r = mid - 1;
  48.         }
  49.         cout << sum[l - 1] + (num - sum[l - 1]) / a[l] * a[l] << ' ' << cnt[l - 1] + (num - sum[l - 1]) / a[l] << endl;
  50.     }
  51.     return 0;
  52. }