当前位置:   article > 正文

2021 RoboCom 世界机器人开发者大赛-本科组(初赛)芬兰木棋(30分)(肥肠煎蛋亿学就会ORZ_7-4 芬兰木棋

7-4 芬兰木棋

WX20200212-152528.png

芬兰木棋(Mölkky,又称芬兰木柱)是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版,现在场上一开始有 N 根立起的小木棋(上面分别标有一个非负整数),哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下:

  • 如果仅击倒 1 根木棋,则得木棋上的分数。
  • 如果击倒 2 根或以上的木棋,则只得击倒根数的分数。(例如击倒 5 根,则得 5 分。)

哲哲固定站在 (0,0) 点上,四周放着若干个小木棋 (Xi​,Yi​),坐标均为整数。每次哲哲可以朝一个方向扔出大木棋,大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超,所以这个 k 可以自由控制。

请问哲哲最多能拿多少分,在获得最多分数的情况下最少需要扔出多少次大木棋?

规则与真实规则有较大出入,真实游玩时请以国际莫尔基组织的规则为准

输入格式:

输入第一行是一个正整数 N (1 ≤ N ≤ 105),表示场上一开始有 N 个木棋。

接下来 N 行,每行 3 个整数 Xi​,Yi​,Pi​,分别表示木棋放置在 (Xi​,Yi​),木棋上的分数是 Pi​。坐标在 32 位整数范围内,分数为小于等于 1000 的正整数。

保证 (0,0) 点没有木棋,也没有木棋重叠放置。

输出格式:

输出一行两个数,表示最多分数以及获得最多分数最少需要投掷大木棋多少次。

输入样例:

  1. 11
  2. 1 2 2
  3. 2 4 3
  4. 3 6 4
  5. -1 2 2
  6. -2 4 3
  7. -3 6 4
  8. -1 -2 1
  9. -2 -4 1
  10. -3 -6 1
  11. -4 -8 2
  12. 2 -1 999

输出样例:

1022 9

思路:

经典斜率的遍历问题,出了老多次了,我们用map去存化简后的斜率的分母和分子,然后第二个map记录x轴的位置,那么我们就可以得出这个点了,然后我们已知需要最多分数那么我需要把得分大于1的木牌都进行单独击倒,而等于1的木牌如果可以的话连续击倒,我们就可以得出最大分数和最小次数(注意特判X和Y轴!!!!)

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define endl '\n'
  6. const int N = 2e5 + 5;
  7. const int inf = 0x3f3f3f3f3f3f3f3f;
  8. int n, m, k, t;
  9. struct node {
  10. int x, y, w;
  11. int tx, ty;
  12. } x[N];
  13. map<pair<int, int>, map<int, int>> mp;
  14. //斜率-----位置------应该连击还是单独
  15. map<int, int> mp1, mp2;
  16. //x轴y轴
  17. signed main() {
  18. cin >> n;
  19. int ans = 0;
  20. int num = 0;
  21. for (int i = 0; i < n; i++) {
  22. cin >> x[i].x >> x[i].y >> x[i].w;
  23. ans += x[i].w;
  24. int tx = x[i].x;
  25. int ty = x[i].y;
  26. if (x[i].x == 0) {//y轴
  27. if (x[i].w != 1)mp1[x[i].y] = 2;
  28. else mp1[x[i].y] = 1;
  29. continue;
  30. }
  31. if (x[i].y == 0) {//x轴
  32. if (x[i].w != 1)mp2[x[i].x] = 2;
  33. else mp2[x[i].x] = 1;
  34. continue;
  35. }
  36. //其余部分(分母分子化简)
  37. int op = __gcd(tx, ty);
  38. tx /= op;
  39. ty /= op;
  40. x[i].tx = tx;
  41. x[i].ty = ty;
  42. if (x[i].w != 1) {
  43. mp[{x[i].tx, x[i].ty}][x[i].x] = 2;
  44. } else {
  45. mp[{x[i].tx, x[i].ty}][x[i].x] = 1;
  46. }
  47. }
  48. int f = 0;
  49. int flag = 0;
  50. for (auto it: mp) {//遍历全图
  51. f = 0;
  52. flag = 0;
  53. for (auto i: it.second) {
  54. if (i.first < 0) {// x轴为负数
  55. if (i.second == 1) {
  56. f = 1;
  57. } else {
  58. num++;
  59. if (f == 1) {
  60. num++;
  61. }
  62. f = 0;
  63. }
  64. } else {//x轴为正数
  65. if (flag == 0) {//第一次进入正数的时候需要去清理f
  66. if (f == 1)num++;
  67. f = 0;
  68. }
  69. flag = 1;
  70. if (i.second == 1) {
  71. f = 1;
  72. } else {
  73. num++;
  74. if (f == 1) {
  75. num++;
  76. }
  77. f = 0;
  78. }
  79. }
  80. }
  81. if (f == 1)num++;
  82. }
  83. f = 0;
  84. flag = 0;
  85. for (auto it: mp1) {//跑y轴
  86. if (it.first < 0) {
  87. if (it.second == 1) {
  88. f = 1;
  89. } else {
  90. num++;
  91. if (f == 1) {
  92. num++;
  93. }
  94. f = 0;
  95. }
  96. } else {
  97. if (flag == 0) {
  98. if (f == 1)num++;
  99. f = 0;
  100. }
  101. flag = 1;
  102. if (it.second == 1) {
  103. f = 1;
  104. } else {
  105. num++;
  106. if (f == 1) {
  107. num++;
  108. }
  109. f = 0;
  110. }
  111. }
  112. }
  113. if(f==1)num++;
  114. f=0;
  115. flag=0;
  116. for (auto it: mp2) {//跑x轴
  117. if (it.first < 0) {
  118. if (it.second == 1) {
  119. f = 1;
  120. } else {
  121. num++;
  122. if (f == 1) {
  123. num++;
  124. }
  125. f = 0;
  126. }
  127. } else {
  128. if (flag == 0) {
  129. if (f == 1)num++;
  130. f = 0;
  131. }
  132. flag = 1;
  133. if (it.second == 1) {
  134. f = 1;
  135. } else {
  136. num++;
  137. if (f == 1) {
  138. num++;
  139. }
  140. f = 0;
  141. }
  142. }
  143. }
  144. if(f==1)num++;
  145. cout << ans << ' ' << num << endl;
  146. return 0;
  147. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/826102
推荐阅读
相关标签
  

闽ICP备14008679号