[关闭]
@Dmaxiya 2018-08-17T10:14:03.000000Z 字数 6315 阅读 947

Codeforces Round #482 (Div. 2)

Codeforces


Contests 链接:Codeforces Round #482 (Div. 2)
过题数:2
排名:843/10089

A. Pizza, Pizza, Pizza!!!

题意

用最少的线将一个圆平分成 块。

输入

输入只包含一个整数

输出

输出需要的线的数量。

样例

输入
3
输出
2
输入
4
输出
5

题解

如果 为奇数,就要平分成偶数块,就需要 条线,如果 为偶数,就需要平分成奇数块,每条线必须从圆心往外,需要 条线,注意 就不需要线。

过题代码

  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 <functional>
  15. #include <algorithm>
  16. using namespace std;
  17. #define LL long long
  18. LL int n;
  19. int main() {
  20. #ifdef LOCAL
  21. freopen("test.txt", "r", stdin);
  22. // freopen("10.out", "w", stdout);
  23. #endif // LOCAL
  24. while(scanf("%I64d", &n) != EOF) {
  25. if(n == 0) {
  26. printf("0\n");
  27. continue;
  28. }
  29. ++n;
  30. if(n % 2 == 0) {
  31. printf("%I64d\n", n / 2);
  32. } else {
  33. printf("%I64d\n", n);
  34. }
  35. }
  36. return 0;
  37. }

B. Treasure Hunt

题意

三人都有一个长度相同的字符串,每个字符串都只包含小写字母和大写字母,三个人都有 次对自己的字符串进行操作的机会,每次操作可以选择一个字符并将这个字符修改成另一个字符。一个字符串的价值定义为这个字符串中所有子串出现的最大次数,他们三人经过 轮操作后,在采取最优策略下,谁的字符串价值将会最大。

输入

第一行为一个整数 ,接下去三行为三个字符串,分别为 的初始字符串,字符串的长度不超过 ,字符串只包含小写字母和大写字母。

输出

输出三人都采取最优策略下,字符串价值最大的人,如果存在两个或两个以上最大价值,输出

样例

输入
3
Kuroo
Shiro
Katie
输出
Kuro
提示
轮之后, 可以将自己的字符串修改为 ooooo,价值为 ,而另外两个人最多只能得到价值为 的字符串。
输入
7
treasurehunt
threefriends
hiCodeforces
输出
Shiro
输入
1
abcabc
cbabac
ababca
输出
Katie
输入
15
foPaErcvJ
mZaxowpbt
mkuOlaHRE
输出
Draw
提示
每个人都可以将自己的字符串修改成 个相同的字符,因此三人平局。

题解

如果某个长度大于 的子串是字符串中出现次数最多的子串,那么这个子串中的字符一定也是出现最多的子串,因此只要处理所有字符即可,对于每个人都计算出可能的最大价值再进行比较就能知道赢家。如果某个字符串的字符完全相等且 等于 ,那么这个符串的价值只能等于 ,如果 (其中 为字符出现的最大次数),那么最大价值就是 ,否则字符串的价值就可以达到

过题代码

  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 <functional>
  15. #include <algorithm>
  16. using namespace std;
  17. #define LL long long
  18. const int maxn = 100000 + 100;
  19. int n;
  20. char str[3][maxn];
  21. int score[3];
  22. map<char, int> mp[3];
  23. int len[3];
  24. map<int, int> mpp;
  25. map<int, int>::iterator it;
  26. int getscore(int Index, char ch) {
  27. int tmp = n - (len[Index] - mp[Index][ch]);
  28. if(tmp >= 0) {
  29. if(mp[Index][ch] == len[Index] && tmp == 1) {
  30. return len[Index] - 1;
  31. }
  32. return len[Index];
  33. }
  34. return n + mp[Index][ch];
  35. }
  36. int main() {
  37. #ifdef LOCAL
  38. freopen("test.txt", "r", stdin);
  39. // freopen("10.out", "w", stdout);
  40. #endif // LOCAL
  41. while(scanf("%d", &n) != EOF) {
  42. mpp.clear();
  43. memset(score, 0, sizeof(score));
  44. for(int i = 0; i < 3; ++i) {
  45. mp[i].clear();
  46. scanf("%s", str[i]);
  47. len[i] = strlen(str[i]);
  48. for(int j = 0; str[i][j]; ++j) {
  49. ++mp[i][str[i][j]];
  50. }
  51. }
  52. for(char ch = 'a'; ch <= 'z'; ++ch) {
  53. for(int i = 0; i < 3; ++i) {
  54. score[i] = max(score[i], getscore(i, ch));
  55. }
  56. }
  57. for(char ch = 'A'; ch <= 'Z'; ++ch) {
  58. for(int i = 0; i < 3; ++i) {
  59. score[i] = max(score[i], getscore(i, ch));
  60. }
  61. }
  62. int Max = 0;
  63. for(int i = 0; i < 3; ++i) {
  64. Max = max(Max, score[i]);
  65. ++mpp[score[i]];
  66. }
  67. int cnt = 0;
  68. int ans = 0;
  69. for(int i = 0; i < 3; ++i) {
  70. if(score[i] == Max) {
  71. ++cnt;
  72. ans = i;
  73. }
  74. }
  75. if(cnt >= 2) {
  76. printf("Draw\n");
  77. } else {
  78. switch(ans) {
  79. case 0: printf("Kuro\n"); break;
  80. case 1: printf("Shiro\n"); break;
  81. case 2: printf("Katie\n"); break;
  82. }
  83. }
  84. }
  85. return 0;
  86. }

C. Kuro and Walking Route

题意

在一棵 个节点的树上, 表示从节点 到节点 的一条路径,其中 被认为是不同的路径,问有多少条路径不会先经过节点 再经过节点

输入

第一行包含三个整数 ,接下去 行每行两个整数 ,表示节点 和节点 之间有一条边,数据保证给出的边集能构成一棵树。

输出

输出合法的路径数量。

样例

输入
3 1 3
1 2
2 3
输出
5
输入
3 1 3
1 2
1 3
输出
4

题解

将所有路径数 减去不合法的路径数就是答案,不合法路径就是先经过 再经过 的路径,先以 为根 统计 的子树节点数 ,再以 为根 统计 的子树节点数量 ,不合法路径数就是

过题代码

  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 <functional>
  15. #include <algorithm>
  16. using namespace std;
  17. #define LL long long
  18. const int maxn = 300000 + 100;
  19. LL n;
  20. int x, y, u, v;
  21. vector<int> G[maxn];
  22. int sum[maxn];
  23. void dfs(int f, int x) {
  24. sum[x] = 1;
  25. int len = G[x].size();
  26. for(int i = 0; i < len; ++i) {
  27. int pos = G[x][i];
  28. if(pos != f) {
  29. dfs(x, pos);
  30. sum[x] += sum[pos];
  31. }
  32. }
  33. }
  34. int main() {
  35. #ifdef LOCAL
  36. freopen("test.txt", "r", stdin);
  37. // freopen("10.out", "w", stdout);
  38. #endif // LOCAL
  39. while(scanf("%I64d%d%d", &n, &x, &y) != EOF) {
  40. for(int i = 1; i <= n; ++i) {
  41. G[i].clear();
  42. }
  43. for(int i = 1; i < n; ++i) {
  44. scanf("%d%d", &u, &v);
  45. G[u].push_back(v);
  46. G[v].push_back(u);
  47. }
  48. dfs(x, x);
  49. LL ans = sum[y];
  50. dfs(y, y);
  51. ans *= sum[x];
  52. printf("%I64d\n", n * (n - 1) - ans);
  53. }
  54. return 0;
  55. }

D. Kuro and GCD and XOR and SUM

题意

初始有一个空的集合,有 次操作,每次操作有两种选择:

  1. 给定 ,表示将 加入到集合中;
  2. 给定 ,从集合中找到一个整数 ,要求 满足条件 的值最大。

输入

第一行为一个整数 ,接下去 行,每行可以是以下两种格式:

  1. 第一个数字为 ,后面跟着一个整数 ,表示第一种操作;
  2. 第一个数字为 ,后面跟着三个整数 ,表示操作

输出

对于每次操作 ,如果可以找到合法的 ,则输出 的值,否则输出

样例

输入
5
1 1
1 2
2 1 1 3
2 1 1 2
2 1 1 1
输出
2
1
-1
提示
1.向集合中加入数字 ,则集合为
2.向集合中加入数字 ,则集合为
3. 因此答案为
4.只有 满足前两个条件,因此答案为
5.无法找到满足条件的数字,因此答案为
输入
10
1 9
2 9 9 22
2 3 3 18
1 25
2 9 9 20
2 25 25 14
1 20
2 26 26 3
1 14
2 20 20 9
输出
9
9
9
-1
-1
-1

题解

不能整除 ,直接输出 ,如果可以整除,答案就在 的所有倍数中查找,建立 棵字典树,第 棵字典树存的是集合中 的所有倍数,这样每加入一个数字 ,就将 加入到他的所有约数的字典树中,对于每次 操作,直接在第 棵字典树上查找满足条件的答案即可,需要 地预处理所有约数。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <climits>
  6. #include <cmath>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <functional>
  15. #include <algorithm>
  16. using namespace std;
  17. #define LL long long
  18. const int maxn = 100000 + 100;
  19. vector<vector<int> > tree;
  20. vector<int> Min;
  21. int cnt;
  22. bool vis[maxn];
  23. struct Trie {
  24. int root;
  25. int creat(int x) {
  26. int ret = cnt;
  27. ++cnt;
  28. tree.push_back(vector<int>(2, -1));
  29. Min.push_back(x);
  30. return ret;
  31. }
  32. void Init() {
  33. root = creat(1000000000);
  34. }
  35. int id(int x, int Index) {
  36. return ((x >> (20 - Index)) & 1);
  37. }
  38. void add(int x) {
  39. int pos = root;
  40. Min[pos] = min(Min[pos], x);
  41. for(int i = 0; i <= 20; ++i) {
  42. int w = id(x, i);
  43. if(tree[pos][w] == -1) {
  44. tree[pos][w] = creat(x);
  45. }
  46. pos = tree[pos][w];
  47. Min[pos] = min(Min[pos], x);
  48. }
  49. }
  50. int query(int x, int s) {
  51. int ret = 0;
  52. int num = 0;
  53. int pos = root;
  54. for(int i = 0; i <= 20; ++i) {
  55. int w = !id(x, i);
  56. if(tree[pos][w] == -1 || Min[tree[pos][w]] > s) {
  57. w = !w;
  58. } else {
  59. ret |= (1 << (20 - i));
  60. }
  61. if(tree[pos][w] == -1 || Min[tree[pos][w]] > s) {
  62. return -1;
  63. }
  64. num |= (w << (20 - i));
  65. pos = tree[pos][w];
  66. }
  67. return num;
  68. }
  69. };
  70. int q, command, x, k, s;
  71. Trie t[maxn];
  72. vector<int> fac[maxn];
  73. int main() {
  74. #ifdef LOCAL
  75. freopen("test.txt", "r", stdin);
  76. // freopen("10.out", "w", stdout);
  77. #endif // LOCAL
  78. for(int i = 1; i < maxn; ++i) {
  79. t[i].Init();
  80. for(int j = i; j < maxn; j += i) {
  81. fac[j].push_back(i);
  82. }
  83. }
  84. scanf("%d", &q);
  85. for(int i = 0; i < q; ++i) {
  86. scanf("%d", &command);
  87. if(command == 1) {
  88. scanf("%d", &x);
  89. if(vis[x]) {
  90. continue;
  91. }
  92. vis[x] = true;
  93. int len = fac[x].size();
  94. for(int j = 0; j < len; ++j) {
  95. int num = fac[x][j];
  96. t[num].add(x);
  97. }
  98. } else {
  99. scanf("%d%d%d", &x, &k, &s);
  100. if(x % k != 0 || s <= x) {
  101. printf("-1\n");
  102. } else {
  103. printf("%d\n", t[k].query(x, s - x));
  104. }
  105. }
  106. }
  107. return 0;
  108. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注