[关闭]
@Dmaxiya 2018-08-17T10:28:48.000000Z 字数 5669 阅读 1163

Codeforces Round #458 (Div. 1 + Div. 2)

Codeforces

Contests 链接：Codeforces Round #458 (Div. 1 + Div. 2)
过题数：2
排名：1691/8398

A. Perfect Squares

题意

给定一个长度为 的序列 ，找到这个序列中最大的开方不是整数的数字。

数据范围

题解

按照题意跑一遍。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. int n;
  22. LL tmp;
  24. bool judge(LL x) {
  25.     if(x < 0) {
  26.         return true;
  27.     }
  28.     LL xx = sqrt(x);
  29.     if(xx * xx == x) {
  30.         return false;
  31.     }
  32.     return true;
  33. }
  35. int main() {
  36.     #ifdef LOCAL
  37.     freopen("test.txt", "r", stdin);
  38. //    freopen("out.txt", "w", stdout);
  39.     #endif // LOCAL
  40.     ios::sync_with_stdio(false);
  42.     while(scanf("%d", &n) != EOF) {
  43.         LL ans = INT_MIN;
  44.         for(int i = 0; i < n; ++i) {
  45.             scanf("%I64d", &tmp);
  46.             if(judge(tmp)) {
  47.                 ans = max(ans, tmp);
  48.             }
  49.         }
  50.         printf("%I64d\n", ans);
  51.     }
  53.     return 0;
  54. }

B. Conan and Agasa play a Card Game

题意

柯南和阿笠博士玩一场博弈游戏，给定 张卡片，每张卡片上的数字为 ，对于每次操作，一方可以选择一张卡片，然后将其他所有小于该数字的卡片拿掉，最后无法进行操作的一方失败。柯南先手，如果两人都采取最优策略，问谁会获胜。

数据范围

题解

如果最大的数字有 个，如果 为偶数，则先拿最大的数字的人必败，否则必胜，所以如果最大的数字有偶数个，则双方肯定尽量不先拿最大的数字，对于次大的数字也是如此，一直往小了找，如果某个数字出现的次数为奇数，则先拿到这个数字的一方必胜，所以先手一定会直接取这个个数为奇数的数字。所以只要存在个数为奇数的数字，先手必胜，否则必败。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. int n, tmp;
  22. bool flag;
  23. map<int, int> mp;
  25. int main() {
  26.     #ifdef LOCAL
  27.     freopen("test.txt", "r", stdin);
  28. //    freopen("out.txt", "w", stdout);
  29.     #endif // LOCAL
  30.     ios::sync_with_stdio(false);
  32.     while(scanf("%d", &n) != EOF) {
  33.         mp.clear();
  34.         for(int i = 0; i < n; ++i) {
  35.             scanf("%d", &tmp);
  36.             ++mp[tmp];
  37.         }
  38.         flag = false;
  39.         map<int, int>::iterator it;
  40.         for(it = mp.begin(); it != mp.end(); ++it) {
  41.             if(it->second % 2 == 1) {
  42.                 flag = true;
  43.                 break;
  44.             }
  45.         }
  46.         if(flag) {
  47.             printf("Conan\n");
  48.         } else {
  49.             printf("Agasa\n");
  50.         }
  51.     }
  53.     return 0;
  54. }

C. Travelling Salesman and Special Numbers

题意

定义一个操作，对于数字 ，进行一次操作后， 变为 对应的二进制数中，数字 的个数，例如， 进行一次操作后变为 ，再进行一次操作后变为 。现在，对于数字 ，询问从 到 中，最少进行 次操作后变为 的数字有多少个，输出对 后的答案， 以二进制形式给出。

数据范围

题解

对于 以内的数字，进行一次操作后，必然变成 以内的数字，所以可以先预处理出 以内的数字，至少进行多少次操作后变为 ，然后对 到 的数字，询问哪些数字最少可以经过 次操作变为 ，若数字 可以经过 次操作变为 ，则用数位 算出从 到 之间有多少个二进制中含有 个 的数字，加到答案上。注意特判 和 的情况。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 1000 + 100;
  22. const int MOD = 1000000000 + 7;
  23. char n[maxn];
  24. int k, len, ans;
  25. int step[maxn];
  26. int dp[maxn][maxn][2];
  28. int dfs(int pos, int r, int limit) {
  29.     if(r < 0) {
  30.         return 0;
  31.     }
  32.     if(pos == len) {
  33.         if(r == 0) {
  34.             return 1;
  35.         } else {
  36.             return 0;
  37.         }
  38.     }
  39.     if(!limit && dp[pos][r][limit] != -1) {
  40.         return dp[pos][r][limit];
  41.     }
  42.     int up = limit? (n[pos] - '0'): 1;
  43.     int ans = 0;
  44.     for(int i = 0; i <= up; ++i) {
  45.         if(i == 1) {
  46.             ans += dfs(pos + 1, r - 1, limit && i == n[pos] - '0');
  47.             ans %= MOD;
  48.         } else {
  49.             ans += dfs(pos + 1, r, limit && i == n[pos] - '0');
  50.             ans %= MOD;
  51.         }
  52.     }
  53.     if(!limit) {
  54.         dp[pos][r][limit] = ans;
  55.     }
  56.     return ans;
  57. }
  59. int get_one(int x) {
  60.     int ret = 0;
  61.     while(x != 0) {
  62.         if(x % 2 == 1) {
  63.             ++ret;
  64.         }
  65.         x /= 2;
  66.     }
  67.     return ret;
  68. }
  70. int main() {
  71.     #ifdef LOCAL
  72.     freopen("test.txt", "r", stdin);
  73. //    freopen("out.txt", "w", stdout);
  74.     #endif // LOCAL
  75. //    ios::sync_with_stdio(false);
  77.     step[1] = 0;
  78.     for(int i = 2; i < maxn; ++i) {
  79.         step[i] = step[get_one(i)] + 1;
  80.     }
  81.     while(scanf("%s%d", n, &k) != EOF) {
  82.         if(k == 0) {
  83.             printf("1\n");
  84.             continue;
  85.         }
  86.         ans = 0;
  87.         len = strlen(n);
  88.         memset(dp, -1, sizeof(dp));
  89.         for(int i = 1; i < maxn; ++i) {
  90.             if(step[i] == k - 1) {
  91.                 ans += dfs(0, i, 1);
  92.                 ans %= MOD;
  93. //                printf("dfs(%d) = %d\n", i, dfs(0, i, 1));
  94.             }
  95.         }
  96.         if(k == 1) {
  97.             --ans;
  98.             ans = (ans + MOD) % MOD;
  99.         }
  100.         printf("%d\n", ans);
  101.     }
  103.     return 0;
  104. }

D. Bash and a Tough Math Puzzle

题意

给定 个数字的序列 ，进行 次操作，每次操作有两种形式：

  • 询问能否在区间 上最多修改一个数字，使得该区间上所有数字都是 的倍数；
  • 将第 个数字修改为 。

对于每次询问，输出 或者 。

数据范围

题解

用线段树存区间 ，对于每次询问，判断区间 上不是 的倍数的数字是否多于一个，若多于 个，则不是。判断的时候注意剪枝，若左子节点已经有多于两个数字不是 的倍数，则不必判断右子节点。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 500000 + 100;
  22. int n, q, command, l, r, x, Index, y;
  23. int ans;
  24. int Gcd[maxn << 2];
  26. int gcd(int x, int y) {
  27.     if(y == 0) {
  28.         return x;
  29.     }
  30.     return gcd(y, x % y);
  31. }
  33. void push_up(int rt) {
  34.     Gcd[rt] = gcd(Gcd[rt << 1], Gcd[rt << 1 | 1]);
  35. }
  37. void build(int l, int r, int rt) {
  38.     if(l == r) {
  39.         scanf("%d", &Gcd[rt]);
  40.         return ;
  41.     }
  42.     int m = (l + r) >> 1;
  43.     build(l, m, rt << 1);
  44.     build(m + 1, r, rt << 1 | 1);
  45.     push_up(rt);
  46. }
  48. void update(int Index, int tmp, int l, int r, int rt) {
  49.     if(l == r) {
  50.         Gcd[rt] = tmp;
  51.         return ;
  52.     }
  53.     int m = (l + r) >> 1;
  54.     if(Index <= m) {
  55.         update(Index, tmp, l, m, rt << 1);
  56.     } else {
  57.         update(Index, tmp, m + 1, r, rt << 1 | 1);
  58.     }
  59.     push_up(rt);
  60. }
  62. int query(int L, int R, int tmp, int l, int r, int rt) {
  63.     if(L <= l && r <= R) {
  64.         if(Gcd[rt] % tmp == 0) {
  65.             return 0;
  66.         }
  67.     }
  68.     if(l == r) {
  69.         return (Gcd[rt] % tmp != 0);
  70.     }
  71.     int m = (l + r) >> 1;
  72.     int ret = 0;
  73.     if(L <= m) {
  74.         ret += query(L, R, tmp, l, m, rt << 1);
  75.     }
  76.     if(ret >= 2) {
  77.         return 2;
  78.     }
  79.     if(R > m) {
  80.         ret += query(L, R, tmp, m + 1, r, rt << 1 | 1);
  81.     }
  82.     if(ret >= 2) {
  83.         ret = 2;
  84.     }
  85.     return ret;
  86. }
  88. void Print() {
  89.     for(int i = 1; i <= 10; ++i) {
  90.         printf("Gcd[%d] = %d\n", i, Gcd[i]);
  91.     }
  92. }
  94. int main() {
  95.     #ifdef LOCAL
  96.     freopen("test.txt", "r", stdin);
  97. //    freopen("out.txt", "w", stdout);
  98.     #endif // LOCAL
  99. //    ios::sync_with_stdio(false);
  101.     while(scanf("%d", &n) != EOF) {
  102.         build(1, n, 1);
  103.         scanf("%d", &q);
  104.         for(int i = 0; i < q; ++i) {
  105.             scanf("%d", &command);
  106.             if(command == 1) {
  107.                 scanf("%d%d%d", &l, &r, &x);
  108. //                printf("l = %d  r = %d  x = %d\n", l, r, x);
  109.                 ans = query(l, r, x, 1, n, 1);
  110. //                printf("ans = %d\n", ans);
  111.                 if(ans <= 1) {
  112.                     printf("YES\n");
  113.                 } else {
  114.                     printf("NO\n");
  115.                 }
  116.             } else {
  117.                 scanf("%d%d", &Index, &y);
  118.                 update(Index, y, 1, n, 1);
  119. //                Print();
  120.             }
  121.         }
  122.     }
  124.     return 0;
  125. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注