[关闭]
@Dmaxiya 2018-08-17T10:27:00.000000Z 字数 6110 阅读 917

Codeforces Round #488 (Div. 1)

Codeforces


Contests 链接:Codeforces Round #488 (Div. 1)
过题数:2
排名:295/715

A. Two Squares

题意

按顺时针或逆时针的顺序给出两个正方形四个顶点的坐标,第一个正方形四边都平行于坐标轴,第二个正方形的四边与坐标轴夹角都是 ,问两个正方形是否相交(仅顶点有交点或者一个正方形包含于另一个正方形也属于相交)。

输入

输入包含两行,每行四对整数,每对整数表示正方形的其中一个顶点的坐标,每一行的四个坐标都是按照顺时针或者逆时针顺序给出的。
第一行给出边与坐标轴平行的正方形顶点坐标,第二行给出边与坐标轴夹角为 的正方形顶点坐标,所有整数都在 内。

输出

如果两个正方形相交则输出 "Yes",否则输出 "No",大小写任意。

样例

输入 输出
0 0 6 0 6 6 0 6
1 3 3 5 5 3 3 1
YES
0 0 6 0 6 6 0 6
7 3 9 5 11 3 9 1
NO
6 0 6 6 0 6 0 0
7 4 4 7 7 10 10 7
YES

题解

先按照顶点给出的顺序在二维数组上描出正方形的边界,接着填充两个正方形内部,再判断是否相交。

过题代码

  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 <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 200 + 100;
  21. int dx, dy;
  22. int x[8], y[8];
  23. bool vis[2][maxn][maxn];
  24. void pull(bool vis[maxn][maxn]) {
  25. for(int i = 0; i < 4; ++i) {
  26. int ii = (i + 1) % 4;
  27. dx = x[ii] - x[i];
  28. dy = y[ii] - y[i];
  29. if(dx != 0) {
  30. dx /= abs(dx);
  31. }
  32. if(dy != 0) {
  33. dy /= abs(dy);
  34. }
  35. int xx = x[i];
  36. int yy = y[i];
  37. while(yy != y[ii] || xx != x[ii]) {
  38. vis[xx][yy] = true;
  39. xx += dx;
  40. yy += dy;
  41. }
  42. vis[xx][yy] = true;
  43. }
  44. for(int i = 0; i < maxn; ++i) {
  45. int Left = maxn;
  46. int Right = 0;
  47. for(int j = 0; j < maxn; ++j) {
  48. if(vis[i][j]) {
  49. Left = min(Left, j);
  50. Right = max(Right, j);
  51. }
  52. }
  53. for(int j = Left; j <= Right; ++j) {
  54. vis[i][j] = true;
  55. }
  56. }
  57. }
  58. int main() {
  59. #ifdef LOCAL
  60. freopen("test.txt", "r", stdin);
  61. // freopen("test1.out", "w", stdout);
  62. #endif // LOCAL
  63. ios::sync_with_stdio(false);
  64. while(scanf("%d%d", &x[0], &y[0]) != EOF) {
  65. memset(vis, 0, sizeof(vis));
  66. x[0] += 100;
  67. y[0] += 100;
  68. for(int i = 1; i < 4; ++i) {
  69. scanf("%d%d", &x[i], &y[i]);
  70. x[i] += 100;
  71. y[i] += 100;
  72. }
  73. pull(vis[0]);
  74. for(int i = 0; i < 4; ++i) {
  75. scanf("%d%d", &x[i], &y[i]);
  76. x[i] += 100;
  77. y[i] += 100;
  78. }
  79. pull(vis[1]);
  80. bool flag = false;
  81. for(int i = 0; i < maxn; ++i) {
  82. for(int j = 0; j < maxn; ++j) {
  83. if(vis[0][i][j] && vis[1][i][j]) {
  84. flag = true;
  85. break;
  86. }
  87. }
  88. if(flag) {
  89. break;
  90. }
  91. }
  92. if(flag) {
  93. printf("YES\n");
  94. } else {
  95. printf("NO\n");
  96. }
  97. }
  98. return 0;
  99. }

B. Open Communication

题意

两个人分别被分到一对数字,每个数字都在 内,且每对中的两个数字是不同的,两个人被分到的数字对保证只有一个数字是相同的,另一个数字不同。
现在第一个人给出 对数字,第二个人给出 对数字,他们给出的数字对中,必须有一个包含自己被分到的数字,其他数字对必须保证是两个不相同的在 内的数字。你不知道他们被分到的数字对是什么,但是可以看到他们给出的数字对,问你是否能判断出他们被分到的数字对中,相同的那个数字。

输入

第一行包含 ,第二行包含 对数字,第三行包含 对数字。数据保证合法。

输出

如果你可以猜到他们被分到的数字对中相同的那个数字,则输出这个数字,如果你猜不到,但是可以确定他们两个人都知道相同的那个数字,则输出 ,否则输出

样例

输入 输出
2 2
1 2 3 4
1 5 3 4
1
2 2
1 2 3 4
1 5 6 4
0
2 3
1 2 4 5
1 2 1 3 2 3
-1
2 3
1 2 4 5
1 3 2 3 4 6
-1

题解

按照题意模拟:先从第一个人的角度看,对于第一个人给出的每一对数字,如果对方给出的数字对中,与第一个人自己的数字对仅有一个数字相同,且相同的数字一样,则第一个人可以确定相同的数字,如:第一个人给出的是 ,对于第二个人给出的 ,他可以确定那个相同的数字是 ,但是对于第一个人来说,他知道自己那组数据是哪一组,从“你”的角度看,“你”不知道他给出的是哪组数据,如果假设第一个人拿到的是他展示的任一组数据,得到了多于 个的答案(如:,第一个人可以得到是 或者 中的一个答案,但是从“你”的角度看,却不知道是 还是 ),这时候就是输出 的情况。再用同样的逻辑从第二个人的角度看。注意只要有一个人无法唯一确定答案,就是输出 的情况,如样例

过题代码

  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 <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 100;
  21. bool flag;
  22. int n[2];
  23. pair<int, int> par[2][maxn];
  24. set<int> st, stt;
  25. int match(const pair<int, int> &a, const pair<int, int> &b, int &num) {
  26. int ret = 0;
  27. if(a.first == b.first) {
  28. ++ret;
  29. num = a.first;
  30. }
  31. if(a.second == b.second) {
  32. ++ret;
  33. num = a.second;
  34. }
  35. if(a.first == b.second) {
  36. ++ret;
  37. num = a.first;
  38. }
  39. if(a.second == b.first) {
  40. ++ret;
  41. num = b.first;
  42. }
  43. return ret;
  44. }
  45. int main() {
  46. #ifdef LOCAL
  47. freopen("test.txt", "r", stdin);
  48. // freopen("test1.out", "w", stdout);
  49. #endif // LOCAL
  50. ios::sync_with_stdio(false);
  51. while(scanf("%d%d", &n[0], &n[1]) != EOF) {
  52. flag = true;
  53. st.clear();
  54. for(int i = 0; i < 2; ++i) {
  55. for(int j = 0; j < n[i]; ++j) {
  56. scanf("%d%d", &par[i][j].first, &par[i][j].second);
  57. }
  58. }
  59. for(int i = 0; i < 2; ++i) {
  60. int ii = 1 - i;
  61. for(int j = 0; j < n[i]; ++j) {
  62. stt.clear();
  63. for(int k = 0; k < n[ii]; ++k) {
  64. int num;
  65. int cnt = match(par[i][j], par[ii][k], num);
  66. if(cnt == 1) {
  67. st.insert(num);
  68. stt.insert(num);
  69. }
  70. }
  71. if((int)stt.size() > 1) {
  72. flag = false;
  73. }
  74. }
  75. }
  76. if(!flag) {
  77. printf("-1\n");
  78. continue;
  79. }
  80. if((int)st.size() != 1) {
  81. printf("0\n");
  82. } else {
  83. set<int>::iterator it = st.begin();
  84. printf("%d\n", *it);
  85. }
  86. }
  87. return 0;
  88. }

C. Careful Maneuvering

题意

两个小飞船被两列大飞船包围,其中一列飞船的横坐标都是 ,另一列飞船的横坐标都是 ,它们的纵坐标都是整数,两个小飞船的横坐标都为
现在两列飞船同时向小飞船发射激光炮,小飞船拥有防护罩,激光炮无法伤害它们,但是激光会穿过他们射向对面的飞船,所有大飞船的两个激光炮都是瞄准两个小飞船发射的,问小飞船的纵坐标应该在哪个位置(不必为整数),才能使得被激光炮打中的大飞船最多,输出被打中的大飞船的最大数量。

输入

第一行为 ,分别表示 的大飞船数量,第二行包含 个整数 ,表示 的飞船的纵坐标,第三行的 个整数 表示 的飞船的纵坐标,其中

输出

能被击中的最多的大飞船数量。

样例

输入 输出
3 9
1 2 3
1 2 3 7 8 9 11 12 13
9
5 5
1 2 3 4 5
1 2 3 4 5
10

题解

由于两边飞船是对称分布的,所以小飞船的位置一定为整数或 ,所以可以将所有大飞船的纵坐标 ,所有坐标就都为整数了。
第一步预处理,先 计算出每个小飞船的纵坐标 ,对每个小飞船的纵坐标, 计算出当所有大飞船瞄准这个点时,左右两边的飞船被打中的状态(用 位记录被打中的状态),预处理时间复杂度为
接着 枚举小飞船的两个位置,对于每两个小飞船的位置,将两边的飞船击中状态按位或起来,用 计算总的被击落的飞船数,取最大值,总的时间复杂度为

过题代码

  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 <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 200 + 100;
  21. int n, m, ans;
  22. int *it;
  23. int Left[maxn], Right[maxn];
  24. LL statu_Left[40000 + 100], statu_Right[40000 + 100];
  25. int Count(LL x) {
  26. int ret = 0;
  27. for(int i = 0; i < 62; ++i) {
  28. ret += ((x >> i) & 1);
  29. }
  30. return ret;
  31. }
  32. int main() {
  33. #ifdef LOCAL
  34. freopen("test.txt", "r", stdin);
  35. // freopen("test1.out", "w", stdout);
  36. #endif // LOCAL
  37. ios::sync_with_stdio(false);
  38. while(scanf("%d%d", &n, &m) != EOF) {
  39. ans = 0;
  40. for(int i = 0; i < n; ++i) {
  41. scanf("%d", &Left[i]);
  42. Left[i] *= 2;
  43. }
  44. for(int i = 0; i < m; ++i) {
  45. scanf("%d", &Right[i]);
  46. Right[i] *= 2;
  47. }
  48. sort(Left, Left + n);
  49. sort(Right, Right + m);
  50. for(int i = 0; i < n; ++i) {
  51. for(int j = 0; j < m; ++j) {
  52. int pos = (Left[i] + Right[j]) / 2;
  53. int Index = pos + 20000;
  54. statu_Left[Index] = statu_Right[Index] = 0;
  55. for(int k = 0; k < n; ++k) {
  56. int x = 2 * pos - Left[k];
  57. it = lower_bound(Right, Right + m, x);
  58. if(it - Right != m && *it == x) {
  59. statu_Left[Index] |= (1LL << k);
  60. }
  61. }
  62. for(int k = 0; k < m; ++k) {
  63. int x = 2 * pos - Right[k];
  64. it = lower_bound(Left, Left + n, x);
  65. if(it - Left != n && *it == x) {
  66. statu_Right[Index] |= (1LL << k);
  67. }
  68. }
  69. }
  70. }
  71. for(int a = 0; a < n; ++a) {
  72. for(int b = 0; b < m; ++b) {
  73. int pos1 = (Left[a] + Right[b]) / 2 + 20000;
  74. for(int c = 0; c < n; ++c) {
  75. for(int d = 0; d < m; ++d) {
  76. int pos2 = (Left[c] + Right[d]) / 2 + 20000;
  77. bitset<60> bit1(statu_Left[pos1] | statu_Left[pos2]);
  78. bitset<60> bit2(statu_Right[pos1] | statu_Right[pos2]);
  79. ans = max(ans, (int)(bit1.count() + bit2.count()));
  80. }
  81. }
  82. }
  83. }
  84. printf("%d\n", ans);
  85. }
  86. return 0;
  87. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注