[关闭]
@Dmaxiya 2020-12-12T15:24:04.000000Z 字数 6131 阅读 1141

Codeforces Round #495 (Div. 2)

Codeforces


Contests 链接:Codeforces Round #495 (Div. 2)
过题数:3
排名:844/5878

A. Sonya and Hotels

题意

如果在数轴上的某一个点与数轴上所有 个点 的最小距离为 ,则这个点是合法的,问总共有多少个合法的点。

输入

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

输出

输出合法的点的数量。

样例

输入 输出 提示
4 3
-3 2 9 16
6 个合法的点分别为
5 2
4 8 11 18 19
5 个合法的点为

题解

枚举 个点 ,对每个点判断是否合法,将点放到 中去重,最终 的大小就是答案。

过题代码

  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. LL n, d;
  24. LL x[maxn];
  25. set<LL> st;
  26. LL judge(LL Index) {
  27. LL ret = (1LL << 50);
  28. for(int i = 1; i <= n; ++i) {
  29. ret = min(ret, abs(x[i] - Index));
  30. }
  31. return ret;
  32. }
  33. int main() {
  34. #ifdef Dmaxiya
  35. freopen("test.txt", "r", stdin);
  36. // freopen("out.txt", "w", stdout);
  37. #endif //Dmaxiya
  38. ios::sync_with_stdio(false);
  39. while(scanf("%I64d%I64d", &n, &d) != EOF) {
  40. st.clear();
  41. for(int i = 1; i <= n; ++i) {
  42. scanf("%I64d", &x[i]);
  43. }
  44. for(int i = 1; i <= n; ++i) {
  45. if(judge(x[i] - d) == d) {
  46. st.insert(x[i] - d);
  47. }
  48. if(judge(x[i] + d) == d) {
  49. st.insert(x[i] + d);
  50. }
  51. }
  52. printf("%d\n", (int)st.size());
  53. }
  54. return 0;
  55. }

B. Sonya and Exhibition

题意

构造一个长度为 串,使得对于 个闭区间 最大,其中 表示区间 的数量乘上 的数量的值。

输入

输入第一行为两个整数 ,接下去 行每行两个整数

输出

输出一个满足条件的 串。

样例

输入 输出 提示
5 3
1 3
2 4
2 5
01100


6 3
5 6
1 4
4 6
110010


题解

由固定周长面积最大的四边形是正方形可知,在区间长度为 的区间内, 的数量和 的数量越接近,它们的乘积就越大,只要输出 相间的 串就能满足条件,如果有多解输出任意一个。

过题代码

  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 = 1000 + 100;
  23. struct Node {
  24. int l, r;
  25. };
  26. bool operator<(const Node &a, const Node &b) {
  27. return (a.r == b.r? a.l > b.l: a.r < b.r);
  28. }
  29. int n, m;
  30. int cnt[2];
  31. Node node[maxn];
  32. char ans[maxn];
  33. int main() {
  34. #ifdef Dmaxiya
  35. freopen("test.txt", "r", stdin);
  36. // freopen("out.txt", "w", stdout);
  37. #endif //Dmaxiya
  38. ios::sync_with_stdio(false);
  39. while(scanf("%d%d", &n, &m) != EOF) {
  40. for(int i = 1; i <= m; ++i) {
  41. scanf("%d%d", &node[i].l, &node[i].r);
  42. }
  43. for(int i = 0; i < n; ++i) {
  44. if(i % 2 == 0) {
  45. putchar('1');
  46. } else {
  47. putchar('0');
  48. }
  49. }
  50. printf("\n");
  51. }
  52. return 0;
  53. }

C. Sonya and Robots

题意

有两个机器人在一排 个数字 的两端,只要分别给两个机器人一个数字指令,在左边的机器人就会往右边走,直到走到数字指令 所在的位置停止,在右边的机器人将往左边走,直到走到数字指令 所在的位置停止,在保证两个机器人不相撞的情况下,有多少种合法的数字指令 是满足条件的,两个数字指令是不同的,当且仅当 或者

输入

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

输出

输出所有合法的数字指令数。

样例

输入 输出 提示
5
1 5 4 1 3
9 这些数字指令都是合法的:
7
1 2 1 1 1 3 2
7 这些数字指令是合法的:

题解

统计每一个数字出现的最左边的下标和最右边的下标,对于每一个出现的数字(不能重复统计),计算有多少个数字出现的最右边的下标在这个数字出现的最左边的下标的右边,对每个数字 地二分查找,就可以 地解决问题了。

过题代码

  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 = 100000 + 100;
  23. struct Node {
  24. int Index, num;
  25. Node() {}
  26. Node(int I, int n) {
  27. Index = I;
  28. num = n;
  29. }
  30. };
  31. bool operator<(const Node &a, const Node &b) {
  32. return a.Index < b.Index;
  33. }
  34. LL ans;
  35. int n, cnt;
  36. int num[maxn], Left[maxn], Right[maxn];
  37. Node node[maxn];
  38. Node *it;
  39. int main() {
  40. #ifdef Dmaxiya
  41. freopen("test.txt", "r", stdin);
  42. // freopen("out.txt", "w", stdout);
  43. #endif //Dmaxiya
  44. ios::sync_with_stdio(false);
  45. while(scanf("%d", &n) != EOF) {
  46. ans = 0;
  47. cnt = 0;
  48. memset(Right, 0, sizeof(Right));
  49. memset(Left, 0x3f, sizeof(Left));
  50. for(int i = 1; i <= n; ++i) {
  51. scanf("%d", &num[i]);
  52. Left[num[i]] = min(Left[num[i]], i);
  53. Right[num[i]] = max(Right[num[i]], i);
  54. }
  55. for(int i = 1; i < maxn; ++i) {
  56. if(Right[i] != 0) {
  57. node[cnt++] = Node(Right[i], i);
  58. }
  59. }
  60. sort(node, node + cnt);
  61. for(int i = 1; i < maxn; ++i) {
  62. if(Right[i] != 0) {
  63. it = upper_bound(node, node + cnt, Node(Left[i], i));
  64. ans += cnt - (it - node);
  65. }
  66. }
  67. printf("%I64d\n", ans);
  68. }
  69. return 0;
  70. }

D. Sonya and Matrix

题意

在一个 的网格内,从上到下、从左到右将每个点的坐标设为 ,在网格中选择一个点 ,然后将网格上所有位置都填上数字 ,这样将所有相同的数字连起来,就是一个个嵌套起来的菱形。现在给出 个整数 ,判断这些数字能否填入上述网格内。

输入

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

输出

如果无法满足题意,则输出 ,否则第一行输出两个整数 ,表示构造出来的网格大小,第二行为两个整数 ,表示在网格中数字 的坐标,如果有多解输出任意一个。

样例

输入 输出 提示
20
1 0 2 3 5 3 2 1 3 2 3 1 4 2 1 4 2 3 2 4
4 5
2 2
数字可以按照下图填入 的网格中

也可以将网格旋转 ,将 放到
等位置。
18
2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1
3 6
2 3
6
2 1 0 2 1 2
-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 = 1000000 + 100;
  23. int t, x, Max;
  24. int cnt[maxn], cnttmp[maxn];
  25. bool judge(int n, int m, int x, int y) {
  26. memcpy(cnttmp, cnt, sizeof(cnt));
  27. for(int i = 1; i <= n; ++i) {
  28. for(int j = 1; j <= m; ++j) {
  29. int dis = abs(i - x) + abs(j - y);
  30. --cnttmp[dis];
  31. if(cnttmp[dis] < 0) {
  32. return false;
  33. }
  34. }
  35. }
  36. return true;
  37. }
  38. int main() {
  39. #ifdef Dmaxiya
  40. freopen("test.txt", "r", stdin);
  41. // freopen("out.txt", "w", stdout);
  42. #endif //Dmaxiya
  43. ios::sync_with_stdio(false);
  44. while(scanf("%d", &t) != EOF) {
  45. bool flag = false;
  46. Max = 0;
  47. memset(cnt, 0, sizeof(cnt));
  48. for(int i = 0; i < t; ++i) {
  49. scanf("%d", &x);
  50. ++cnt[x];
  51. Max = max(Max, x);
  52. }
  53. if(t == 1) {
  54. if(Max == 0) {
  55. printf("1 1\n1 1\n");
  56. } else {
  57. printf("-1\n");
  58. }
  59. continue;
  60. }
  61. int x, y, n, m;
  62. for(int i = 1; i < maxn; ++i) {
  63. if(cnt[i] != i * 4) {
  64. x = i;
  65. break;
  66. }
  67. }
  68. for(int i = 1; i <= t / i; ++i) {
  69. if(t % i == 0) {
  70. n = i;
  71. m = t / i;
  72. y = n - x + m - Max;
  73. if(judge(n, m, x, y)) {
  74. flag = true;
  75. break;
  76. }
  77. n = t / i;
  78. m = i;
  79. if(judge(n, m, x, y)) {
  80. flag = true;
  81. break;
  82. }
  83. }
  84. }
  85. if(flag) {
  86. printf("%d %d\n%d %d\n", n, m, x, y);
  87. } else {
  88. printf("-1\n");
  89. }
  90. }
  91. return 0;
  92. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注