[关闭]
@Dmaxiya 2018-08-17T10:23:04.000000Z 字数 6483 阅读 958

Codeforces Round #494 (Div. 3)

列表项

Codeforces


Contests 链接:Codeforces Round #494 (Div. 3)
过题数:1
排名:5005/8406

A. Polycarp's Pockets

题意

给定 个数字 ,将这 个数字放到任意多个口袋里,使得相同的数字不在同一个口袋里,问最少可以放到多少个口袋。

输入

第一行为一个整数 ,第二行为 个整数

输出

输出最少的口袋数量。

样例

输入 输出
6
1 2 4 3 3 2
2
1
100
1

题解

计算出现次数最多的数字个数。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. const int maxn = 100 + 100;
  23. int n, x, Max;
  24. int cnt[maxn];
  25. int main() {
  26. #ifdef Dmaxiya
  27. freopen("test.txt", "r", stdin);
  28. // freopen("out.txt", "w", stdout);
  29. #endif //Dmaxiya
  30. ios::sync_with_stdio(false);
  31. while(scanf("%d", &n) != EOF) {
  32. Max = 0;
  33. memset(cnt, 0, sizeof(cnt));
  34. for(int i = 1; i <= n; ++i) {
  35. scanf("%d", &x);
  36. ++cnt[x];
  37. Max = max(Max, cnt[x]);
  38. }
  39. printf("%d\n", Max);
  40. }
  41. return 0;
  42. }

B. Binary String Constructing

题意

给定 三个整数,要求构造一个仅含有 的字符串,字符串满足 的数量等于 的数量等于 ,并且对于 ,有 满足条件

输入

输入包含三个整数 ,数据保证有解。

输出

输出一个满足题意的 字符串,如果有多解输出任意一个。

样例

输入 输出 提示
2 2 1 1100 都是合法的答案。
3 3 3 101100 以下答案都是合法的答案:







5 3 6 01010100

题解

第一个字符一定是 中数量比较多的那个字符,然后从 中预留一个数字作为后面将剩下所有的 输出的不同位,其他的 个不同位直接按 或者 穿插填空即可(数位多的在前面)。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. int num[2], x;
  23. char ch[3] = "01";
  24. void Print(int Index) {
  25. while(num[Index] != 0) {
  26. printf("%c", ch[Index]);
  27. --num[Index];
  28. }
  29. }
  30. int main() {
  31. #ifdef Dmaxiya
  32. freopen("test.txt", "r", stdin);
  33. // freopen("out.txt", "w", stdout);
  34. #endif //Dmaxiya
  35. ios::sync_with_stdio(false);
  36. while(scanf("%d%d%d", &num[0], &num[1], &x) != EOF) {
  37. --x;
  38. if(num[0] < num[1]) {
  39. swap(num[0], num[1]);
  40. swap(ch[0], ch[1]);
  41. }
  42. printf("%c", ch[0]);
  43. --num[0];
  44. int Index = 0;
  45. while(x != 0) {
  46. Index = 1 - Index;
  47. printf("%c", ch[Index]);
  48. --num[Index];
  49. --x;
  50. }
  51. Print(Index);
  52. Print(1 - Index);
  53. printf("\n");
  54. }
  55. return 0;
  56. }

C. Intense Heat

题意

给定一个长度为 的序列 ,求这个序列中,所有子段长度不小于 的平均值的最大值。

输入

第一行为两个整数 ,第二行为 个整数

输出

输出答案,如果答案与真实值误差在 以内,则认为输出是正确的。

样例

输入 输出
4 3
3 4 1 2
2.666666666666667

题解

直接按照题意计算即可,用一个前缀和可以更方便计算。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. const int maxn = 5000 + 100;
  23. int n, k;
  24. double ans;
  25. double num[maxn], sum[maxn];
  26. int main() {
  27. #ifdef Dmaxiya
  28. freopen("test.txt", "r", stdin);
  29. // freopen("out.txt", "w", stdout);
  30. #endif //Dmaxiya
  31. ios::sync_with_stdio(false);
  32. while(scanf("%d%d", &n, &k) != EOF) {
  33. ans = 0;
  34. for(int i = 1; i <= n; ++i) {
  35. scanf("%lf", &num[i]);
  36. sum[i] = sum[i - 1] + num[i];
  37. }
  38. for(int kk = k; kk <= n; ++kk) {
  39. for(int i = 0; i + kk <= n; ++i) {
  40. ans = max(ans, (sum[i + kk] - sum[i]) / kk);
  41. }
  42. }
  43. printf("%.10f\n", ans);
  44. }
  45. return 0;
  46. }

D. Coins and Queries

题意

给定 个整数 ,每个整数都等于 的非负整数次幂,对这些数字进行 次询问,每次询问一个整数 ,问 能否由 个整数中的某些数字凑成,如果可以,输出最少的需要的 的数量,否则输出 。任意两次询问之间是独立的。

输入

第一行为两个整数 ,第二行为 个整数 ,数据保证对于每一个 ,一定是 的非负整数次幂,接下来有 个数字 ,表示第 次询问需要得到的数字。

输出

对于每一个询问,如果可以凑成需要的数字,则输出需要的最少的 的数量,否则输出

样例

输入 输出
5 4
2 4 8 2 4
8
5
14
10
1
-1
3
2

题解

来存每一个数字对应出现的次数(最多只有 个关键字),对于每次询问从大到小贪心即可。

过题代码

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

E. Tree Constructing

题意

给定三个整数 ,要求构造出一个 个节点的树,这棵树的直径为 ,且树上每个节点的度最大为 。输出构造的树的方案。

输入

输入包含三个整数

输出

如果可以构造出这样一棵树,第一行输出 ,接下去 行,每行输出树上一条边的两个端点,表示构造出来的树上的一条边,输出必须是一棵合法的树且满足题意。

样例

输入 输出
6 3 3 YES
3 1
4 1
1 2
5 2
2 6
6 2 3 NO
10 4 3 YES
2 9
2 10
10 3
3 1
6 10
8 2
4 3
5 6
6 7
8 5 3 YES
2 5
7 2
3 7
3 1
1 6
8 7
4 3

题解

先将 的情况特判,然后构造一条长度为 的链,将链的中点选为树根,其中一半是一条长度为 的链,另一半是长度为 的链,对链上的每一个节点都标记上以该节点为根子的树的最大深度,其中树根的深度标记为 ,接着一边 一边加边,每个节点所代表的子树的最大深度等于其父节点的子树的最大深度减一,且在加边的过程中要保证每个节点的度不大于

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. const int maxn = 400000 + 100;
  23. struct Node {
  24. int u, v;
  25. Node() {}
  26. Node(int uu, int vv) {
  27. u = uu;
  28. v = vv;
  29. }
  30. };
  31. int n, d, k, cnt, Index, root;
  32. int depth[maxn];
  33. Node ans[maxn];
  34. vector<int> G[maxn];
  35. void Add(int u, int v) {
  36. ans[cnt++] = Node(u, v);
  37. depth[v] = depth[u] - 1;
  38. G[u].push_back(v);
  39. G[v].push_back(u);
  40. }
  41. void dfs(int f, int x) {
  42. if(Index > n || depth[x] == 0) {
  43. return ;
  44. }
  45. int len = G[x].size();
  46. for(int i = 0; i < len; ++i) {
  47. int pos = G[x][i];
  48. if(pos != f) {
  49. dfs(x, pos);
  50. }
  51. }
  52. while((int)G[x].size() < k) {
  53. if(Index > n) {
  54. return ;
  55. }
  56. Add(x, Index);
  57. int tmp = Index;
  58. ++Index;
  59. dfs(x, tmp);
  60. }
  61. }
  62. int main() {
  63. #ifdef Dmaxiya
  64. freopen("test.txt", "r", stdin);
  65. // freopen("out.txt", "w", stdout);
  66. #endif //Dmaxiya
  67. ios::sync_with_stdio(false);
  68. while(scanf("%d%d%d", &n, &d, &k) != EOF) {
  69. if(d >= n) {
  70. printf("NO\n");
  71. continue;
  72. }
  73. if(n == 2) {
  74. printf("YES\n1 2\n");
  75. continue;
  76. }
  77. for(int i = 1; i <= n; ++i) {
  78. G[i].clear();
  79. }
  80. cnt = 0;
  81. for(int i = 2; i <= d + 1; ++i) {
  82. Add(i - 1, i);
  83. }
  84. root = d / 2 + 1;
  85. Index = d + 2;
  86. for(int i = 1; i <= d + 1; ++i) {
  87. if(i <= root) {
  88. depth[i] = d / 2 - (root - i);
  89. } else {
  90. depth[i] = (d - d / 2) - (i - root);
  91. }
  92. }
  93. dfs(root, root);
  94. bool flag = true;
  95. for(int i = 1; i <= n; ++i) {
  96. if((int)G[i].size() > k) {
  97. flag = false;
  98. break;
  99. }
  100. }
  101. if(!flag) {
  102. printf("NO\n");
  103. continue;
  104. }
  105. if(cnt == n - 1) {
  106. printf("YES\n");
  107. for(int i = 0; i < cnt; ++i) {
  108. printf("%d %d\n", ans[i].u, ans[i].v);
  109. }
  110. } else {
  111. printf("NO\n");
  112. }
  113. }
  114. return 0;
  115. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注