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

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;
  26. #define LL long long
  27. const int maxn = 200;
  28. int n, cnt;
  29. int ans[maxn];
  30. bool bad[maxn];
  31. int num[maxn][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);
  40.     while(scanf("%d", &n) != EOF) {
  41.         memset(bad, 0, sizeof(bad));
  42.         for(int i = 1; i <= n; ++i) {
  43.             for(int j = 1; j <= n; ++j) {
  44.                 scanf("%d", &num[i][j]);
  45.                 if(num[i][j] == 1) {
  46.                     bad[i] = true;
  47.                 } else if(num[i][j] == 2) {
  48.                     bad[j] = true;
  49.                 } else if(num[i][j] == 3) {
  50.                     bad[i] = true;
  51.                     bad[j] = true;
  52.                 }
  53.             }
  54.         }
  55.         cnt = 0;
  56.         for(int i = 1; i <= n; ++i) {
  57.             if(!bad[i]) {
  58.                 ans[cnt++] = i;
  59.             }
  60.         }
  61.         printf("%d\n", cnt);
  62.         if(cnt != 0) {
  63.             for(int i = 0; i < cnt; ++i) {
  64.                 if(i != 0) {
  65.                     printf(" ");
  66.                 }
  67.                 printf("%d", ans[i]);
  68.             }
  69.             printf("\n");
  70.         }
  71.     }
  73.     return 0;
  74. }

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;
  26. #define LL long long
  27. const int maxn = 100000 + 100;
  28. int cnt;
  29. char s[maxn], t[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);
  39.     while(scanf("%s%s", s, t) != EOF) {
  40.         cnt = 0;
  41.         for(int i = 0; s[i]; ++i) {
  42.             if(s[i] != t[i]) {
  43.                 ++cnt;
  44.             }
  45.         }
  46.         if(cnt % 2 == 1) {
  47.             printf("impossible\n");
  48.             continue;
  49.         }
  50.         int ccnt = cnt / 2;
  51.         for(int i = 0; s[i]; ++i) {
  52.             if(s[i] == t[i]) {
  53.                 printf("%c", s[i]);
  54.             } else {
  55.                 if(cnt > ccnt) {
  56.                     printf("%c", s[i]);
  57.                     --cnt;
  58.                 } else {
  59.                     printf("%c", t[i]);
  60.                 }
  61.             }
  62.         }
  63.         printf("\n");
  64.     }
  66.     return 0;
  67. }

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;
  26. #define LL long long
  27. const LL INF = 1e18;
  28. const int maxn = 100000 + 100;
  29. struct Node {
  30.     LL x, h;
  31. };
  32. int n, ans;
  33. Node node[maxn];
  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.         ans = 0;
  44.         bool flag = false;
  45.         node[0].x = -INF;
  46.         node[n + 1].x = INF;
  47.         node[0].h = node[n + 1]. h = 0;
  48.         for(int i = 1; i <= n; ++i) {
  49.             scanf("%I64d%I64d", &node[i].x, &node[i].h);
  50.         }
  51.         for(int i = 1; i <= n; ++i) {
  52.             if(flag) {
  53.                 if(node[i].x - node[i - 1].x > node[i].h + node[i - 1].h) {
  54.                     ++ans;
  55.                     flag = false;
  56.                 } else {
  57.                     if(node[i + 1].x - node[i].x > node[i].h) {
  58.                         flag = true;
  59.                         ++ans;
  60.                     } else {
  61.                         flag = false;
  62.                     }
  63.                 }
  64.             } else {
  65.                 if(node[i].x - node[i - 1].x > node[i].h) {
  66.                     ++ans;
  67.                     flag = false;
  68.                 } else {
  69.                     if(node[i + 1].x - node[i].x > node[i].h) {
  70.                         flag = true;
  71.                         ++ans;
  72.                     } else {
  73.                         flag = false;
  74.                     }
  75.                 }
  76.             }
  77.         }
  78.         printf("%d\n", ans);
  79.     }
  81.     return 0;
  82. }

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;
  26. #define LL long long
  27. const int maxn = 100000 + 100;
  28. int n;
  29. LL num[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);
  38.     while(scanf("%d", &n) != EOF) {
  39.         for(int i = 0; i < n; ++i) {
  40.             scanf("%I64d", &num[i]);
  41.         }
  42.         sort(num, num + n);
  43.         LL sum = num[0];
  44.         int ans = 1;
  45.         for(int i = 1; i < n; ++i) {
  46.             if(num[i] >= sum) {
  47.                 ++ans;
  48.                 sum += num[i];
  49.             }
  50.         }
  51.         printf("%d\n", ans);
  52.     }
  54.     return 0;
  55. }

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