[关闭]
@Dmaxiya 2018-08-17T10:30:32.000000Z 字数 7088 阅读 1103

Codeforces Round #303(Div.2)

Codeforces


Contests 链接:Codeforces Round #303(Div.2)
过题数:4
排名:2/16

A. Toy Cars

题意

给出一个二维矩阵,其中第 行第 列表示第 辆车与第 辆车相遇后的状态, 表示两辆车没有相遇,题目保证 只会出现在对角线上, 表示两辆车相遇后不回头, 表示第 辆车相遇后回头, 表示第 辆车相遇后回头, 表示第 辆车与第 辆车相遇后,两辆车都回头。如果某一辆车在与其他车相遇后从没有回头过,那么这辆车就是一辆“好车”,求好车的数量。

数据范围

题解

先假设所有的车都是“好车”,回头一次则这辆车就不是好车,用一个数组来标记状态,最后输出结果即可。

过题代码

  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 <sstream>
  10. #include <vector>
  11. #include <list>
  12. #include <queue>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <bitset>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <functional>
  20. #include <iomanip>
  21. #include <sstream>
  22. #include <io.h>
  23. #include <conio.h>
  24. using namespace std;
  25. #define LL long long
  26. const int maxn = 200;
  27. int n, cnt;
  28. int ans[maxn];
  29. bool bad[maxn];
  30. int num[maxn][maxn];
  31. int main() {
  32. #ifdef LOCAL
  33. freopen("test.txt", "r", stdin);
  34. // freopen("out.txt", "w", stdout);
  35. #endif // LOCAL
  36. // ios::sync_with_stdio(false);
  37. while(scanf("%d", &n) != EOF) {
  38. memset(bad, 0, sizeof(bad));
  39. for(int i = 1; i <= n; ++i) {
  40. for(int j = 1; j <= n; ++j) {
  41. scanf("%d", &num[i][j]);
  42. if(num[i][j] == 1) {
  43. bad[i] = true;
  44. } else if(num[i][j] == 2) {
  45. bad[j] = true;
  46. } else if(num[i][j] == 3) {
  47. bad[i] = true;
  48. bad[j] = true;
  49. }
  50. }
  51. }
  52. cnt = 0;
  53. for(int i = 1; i <= n; ++i) {
  54. if(!bad[i]) {
  55. ans[cnt++] = i;
  56. }
  57. }
  58. printf("%d\n", cnt);
  59. if(cnt != 0) {
  60. for(int i = 0; i < cnt; ++i) {
  61. if(i != 0) {
  62. printf(" ");
  63. }
  64. printf("%d", ans[i]);
  65. }
  66. printf("\n");
  67. }
  68. }
  69. return 0;
  70. }

B. Equidistant String

题意

定义两个字符串的距离为:两个字符串所有不同字符的个数,给定两个字符串 ,输出任意一个到这两个字符串距离相等的字符串 ,如果不存在字符串 满足上述条件,则输出 "".

数据范围


所有字符串只有'0','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 <sstream>
  10. #include <vector>
  11. #include <list>
  12. #include <queue>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <bitset>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <functional>
  20. #include <iomanip>
  21. #include <sstream>
  22. #include <io.h>
  23. #include <conio.h>
  24. using namespace std;
  25. #define LL long long
  26. const int maxn = 100000 + 100;
  27. int cnt;
  28. char s[maxn], t[maxn];
  29. int main() {
  30. #ifdef LOCAL
  31. freopen("test.txt", "r", stdin);
  32. // freopen("out.txt", "w", stdout);
  33. #endif // LOCAL
  34. // ios::sync_with_stdio(false);
  35. while(scanf("%s%s", s, t) != EOF) {
  36. cnt = 0;
  37. for(int i = 0; s[i]; ++i) {
  38. if(s[i] != t[i]) {
  39. ++cnt;
  40. }
  41. }
  42. if(cnt % 2 == 1) {
  43. printf("impossible\n");
  44. continue;
  45. }
  46. int ccnt = cnt / 2;
  47. for(int i = 0; s[i]; ++i) {
  48. if(s[i] == t[i]) {
  49. printf("%c", s[i]);
  50. } else {
  51. if(cnt > ccnt) {
  52. printf("%c", s[i]);
  53. --cnt;
  54. } else {
  55. printf("%c", t[i]);
  56. }
  57. }
  58. }
  59. printf("\n");
  60. }
  61. return 0;
  62. }

C. Woodcutters

题意

最初有 棵树排列成一行,每棵树的位置为 ,高度为 ,一个伐木工人砍树,每砍一棵树,这棵树就会往左或者往右倾倒,这棵树就占据了 或者 的区间,且初始每棵树占据区间 ,要求每棵树被砍倒的时候,在它倒下的范围内没有其他树种植或者在这个区间内。

数据范围

题解

先在负无穷的位置种第 棵树,高度为 ,在正无穷的位置种第 棵树,高度为 ,用一个变量 标记第 树是否向右倒,如果第 棵树是向右倒的,就判断 是否小于 ,如果小于,则第 棵树向左倒,否则判断 是否小于 ,如果小于,则这棵树向右倒,否则这棵树就不倒。

过题代码

  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 <sstream>
  10. #include <vector>
  11. #include <list>
  12. #include <queue>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <bitset>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <functional>
  20. #include <iomanip>
  21. #include <sstream>
  22. #include <io.h>
  23. #include <conio.h>
  24. using namespace std;
  25. #define LL long long
  26. const LL INF = 1e18;
  27. const int maxn = 100000 + 100;
  28. struct Node {
  29. LL x, h;
  30. };
  31. int n, ans;
  32. Node node[maxn];
  33. int main() {
  34. #ifdef LOCAL
  35. freopen("test.txt", "r", stdin);
  36. // freopen("out.txt", "w", stdout);
  37. #endif // LOCAL
  38. // ios::sync_with_stdio(false);
  39. while(scanf("%d", &n) != EOF) {
  40. ans = 0;
  41. bool flag = false;
  42. node[0].x = -INF;
  43. node[n + 1].x = INF;
  44. node[0].h = node[n + 1]. h = 0;
  45. for(int i = 1; i <= n; ++i) {
  46. scanf("%I64d%I64d", &node[i].x, &node[i].h);
  47. }
  48. for(int i = 1; i <= n; ++i) {
  49. if(flag) {
  50. if(node[i].x - node[i - 1].x > node[i].h + node[i - 1].h) {
  51. ++ans;
  52. flag = false;
  53. } else {
  54. if(node[i + 1].x - node[i].x > node[i].h) {
  55. flag = true;
  56. ++ans;
  57. } else {
  58. flag = false;
  59. }
  60. }
  61. } else {
  62. if(node[i].x - node[i - 1].x > node[i].h) {
  63. ++ans;
  64. flag = false;
  65. } else {
  66. if(node[i + 1].x - node[i].x > node[i].h) {
  67. flag = true;
  68. ++ans;
  69. } else {
  70. flag = false;
  71. }
  72. }
  73. }
  74. }
  75. printf("%d\n", ans);
  76. }
  77. return 0;
  78. }

D. Queue

题意

个人在排队,排在队首的人先被服务,每个人都有一个服务时间 ,如果某个人的等待时间超过服务时间,这个人就会感到不满,但是可以交换每个人的位置,使得尽可能多的人感到满意,输出最多能够使多少人感到满意。

数据范围

题解

要使每个人的等待时间都最短,就让 小的人排在前面, 大的人排在后面, 扫一遍就可以了。

过题代码

  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 <sstream>
  10. #include <vector>
  11. #include <list>
  12. #include <queue>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <bitset>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <functional>
  20. #include <iomanip>
  21. #include <sstream>
  22. #include <io.h>
  23. #include <conio.h>
  24. using namespace std;
  25. #define LL long long
  26. const int maxn = 100000 + 100;
  27. int n;
  28. LL num[maxn];
  29. int main() {
  30. #ifdef LOCAL
  31. freopen("test.txt", "r", stdin);
  32. // freopen("out.txt", "w", stdout);
  33. #endif // LOCAL
  34. // ios::sync_with_stdio(false);
  35. while(scanf("%d", &n) != EOF) {
  36. for(int i = 0; i < n; ++i) {
  37. scanf("%I64d", &num[i]);
  38. }
  39. sort(num, num + n);
  40. LL sum = num[0];
  41. int ans = 1;
  42. for(int i = 1; i < n; ++i) {
  43. if(num[i] >= sum) {
  44. ++ans;
  45. sum += num[i];
  46. }
  47. }
  48. printf("%d\n", ans);
  49. }
  50. return 0;
  51. }

E. Paths and Trees

题意

给定一个 个节点 条边的无向图,和图上的一个点 ,找到一棵以 点为根的树,这棵树上所有点到 点的距离都是图上到 点的最短距离,输出这棵树的最小边权和以及被选中的边的编号。

数据范围

题解

跑迪杰斯特拉最短路的时候,记录一下每个节点到节点 的最短距离的边的下标 ,如果 ,则更新 ,如果 ,则比较 ,如果 的长度更短,则更新。

过题代码

  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 <sstream>
  10. #include <vector>
  11. #include <list>
  12. #include <queue>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <bitset>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <functional>
  20. #include <iomanip>
  21. #include <sstream>
  22. #include <io.h>
  23. #include <conio.h>
  24. using namespace std;
  25. #define LL long long
  26. const int maxn = 300000 + 100;
  27. struct Node {
  28. int pos;
  29. LL dis;
  30. int Index;
  31. int Next;
  32. Node() {}
  33. Node(int p, LL d) {
  34. pos = p;
  35. dis = d;
  36. }
  37. };
  38. bool operator<(const Node &a, const Node &b) {
  39. return a.dis > b.dis;
  40. }
  41. int n, m, u, v, pos, cnt;
  42. LL d, ans;
  43. LL dis[maxn];
  44. int pre[maxn];
  45. LL ddis[maxn];
  46. int IIndex[maxn];
  47. Node node[maxn << 1];
  48. int head[maxn];
  49. priority_queue<Node> que;
  50. bool st[maxn];
  51. void unit(int x, int y, LL d, int I) {
  52. node[cnt].dis = d;
  53. node[cnt].Index = I;
  54. node[cnt].pos = y;
  55. node[cnt].Next = head[x];
  56. head[x] = cnt++;
  57. }
  58. void dij(int s) {
  59. memset(dis, 0x3f, sizeof(dis));
  60. dis[s] = 0;
  61. que.push(Node(s, 0));
  62. while(!que.empty()) {
  63. Node tmp = que.top();
  64. que.pop();
  65. for(int i = head[tmp.pos]; i != -1; i = node[i].Next) {
  66. pos = node[i].pos;
  67. d = node[i].dis;
  68. int Index = node[i].Index;
  69. if(dis[pos] > tmp.dis + d) {
  70. st[pre[pos]] = false;
  71. st[Index] = true;
  72. pre[pos] = Index;
  73. dis[pos] = tmp.dis + d;
  74. que.push(Node(pos, dis[pos]));
  75. } else if(dis[pos] == tmp.dis + d) {
  76. st[pre[pos]] = false;
  77. st[Index] = true;
  78. pre[pos] = Index;
  79. }
  80. }
  81. }
  82. }
  83. int main() {
  84. #ifdef LOCAL
  85. freopen("test.txt", "r", stdin);
  86. // freopen("out.txt", "w", stdout);
  87. #endif // LOCAL
  88. // ios::sync_with_stdio(false);
  89. while(scanf("%d%d", &n, &m) != EOF) {
  90. ans = 0;
  91. cnt = 0;
  92. memset(head, -1, sizeof(head));
  93. memset(st, 0, sizeof(st));
  94. memset(pre, 0, sizeof(pre));
  95. for(int i = 1; i <= m; ++i) {
  96. scanf("%d%d%I64d", &u, &v, &d);
  97. ddis[i] = d;
  98. unit(u, v, d, i);
  99. unit(v, u, d, i);
  100. }
  101. scanf("%d", &pos);
  102. dij(pos);
  103. int ccnt = 0;
  104. for(int i = 1; i <= m; ++i) {
  105. if(st[i]) {
  106. ans += ddis[i];
  107. IIndex[ccnt++] = i;
  108. }
  109. }
  110. printf("%I64d\n", ans);
  111. for(int i = 0; i < ccnt; ++i) {
  112. if(i != 0) {
  113. printf(" ");
  114. }
  115. printf("%d", IIndex[i]);
  116. }
  117. printf("\n");
  118. }
  119. return 0;
  120. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注