CODEFORCES-PROBLEMSET

悠悠 2021-12-24 03:43 338阅读 0赞

1A

水题 然而看不仔细爆int了

c++

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 typedef long long ll;
  4.  4 int main(){
  5.  5     double n, m, a;
  6.  6     cin >> n >> m >> a;
  7.  7     ll ans = ll(ceil(n / a)) * ll(ceil(m / a));
  8.  8     cout << ans << endl;
  9.  9     return 0;
  10. 10 }

py3

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 import math
  2. 2 t = input().split()
  3. 3 n, m, a = map(int, t)
  4. 4 print(int(math.ceil(n / a) * math.ceil(m / a)))

1B

有毒的模拟水题……

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int main(){
  5.  5     int n;
  6.  6     cin >> n;
  7.  7     while(n--){
  8.  8         string s;
  9.  9         cin >> s;
  10. 10         bool flag = false;
  11. 11         int i = 0;
  12. 12         while(i < s.size() && 'A' <= s[i] && s[i] <= 'Z') ++i;
  13. 13         for(; i < s.size(); ++i){
  14. 14             if('A' <= s[i] && s[i] <= 'Z'){
  15. 15                 flag = true;
  16. 16                 break;
  17. 17             }
  18. 18         }
  19. 19         if(flag){
  20. 20             int c = 0;
  21. 21             int index = s.find('C');
  22. 22             string ans = "";
  23. 23             for(int i = index + 1; i < s.size(); ++i) c = 10 * c + s[i] - '0';
  24. 24             while(c){
  25. 25                 int k = c % 26;
  26. 26                 if(k == 0){
  27. 27                     ans += 'Z';
  28. 28                     --c;
  29. 29                 }
  30. 30                 else ans += ('A' + k - 1);
  31. 31                 c /= 26;
  32. 32             }
  33. 33             reverse(ans.begin(), ans.end());
  34. 34             cout << ans << s.substr(1, index-1) << endl;
  35. 35         }
  36. 36         else{
  37. 37             int index = 0;
  38. 38             string ans = "R";
  39. 39             int r = 0;
  40. 40             for(; index < s.size(); ++index){
  41. 41                 if('0' <= s[index] && s[index] <= '9') break;
  42. 42                 r = 26 * r + (s[index] - 'A' + 1);
  43. 43             }
  44. 44             ans += s.substr(index, s.size());
  45. 45             ans += 'C';
  46. 46             cout << ans << r << endl;
  47. 47         }
  48. 48     }
  49. 49     return 0;
  50. 50 }

1C

mdzz。。。

余弦定理求三角形内角，也是圆上的圆周角，乘以2得圆心角

求三圆心角最大公约数得正多边形每一份的圆心角ang，2*pi/ang得出边数n

海伦公式+正弦定理得三角形外接圆半径r = (a * b * c) / (4 * s)

s = n * r * r * sin(ang) / 2

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 const double eps = 1e-2;
  4.  4 double fgcd(double a, double b){
  5.  5      if (fabs(a) < eps)
  6.  6          return b;
  7.  7      if (fabs(b) < eps)
  8.  8          return a;
  9.  9      return fgcd(b, fmod(a, b));
  10. 10 }
  11. 11 double diameter(double a, double b, double c) {
  12. 12     double p = (a + b + c) / 2;
  13. 13     double s = sqrt(p * (p - a) * (p - b) * (p - c));
  14. 14     return a * b * c / (4 *s);
  15. 15 }
  16. 16 int main() {
  17. 17     double x[3], y[3], line[3];
  18. 18     for(int i = 0; i < 3; ++i) scanf("%lf %lf", &x[i], &y[i]);
  19. 19     for(int i = 0; i < 3; ++i)
  20. 20         line[i] = sqrt((x[i] - x[(i+1)%3]) * (x[i] - x[(i+1)%3]) + (y[i] - y[(i+1)%3]) * (y[i] - y[(i+1)%3]));
  21. 21     double r = diameter(line[0], line[1], line[2]);
  22. 22     double angle[3];
  23. 23     for(int i = 0; i < 2; ++i)
  24. 24         angle[i] = acos(1 - line[i] * line[i] / (2 * r * r));
  25. 25     angle[2] = 2 * acos(-1) - angle[0] - angle[1];
  26. 26     double ang = fgcd(angle[0], fgcd(angle[1], angle[2]));
  27. 27     printf("%.6f\n", r * r * sin(ang) / 2 * (2 * acos(-1) / ang));
  28. 28     return 0;
  29. 29 }

2A

模拟水题 略麻烦(说到底是思路不清淅不严谨+弱)

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 struct info{
  5.  5     string name;
  6.  6     int score;
  7.  7 }aaa[1111];
  8.  8 map<string, int> game;
  9.  9 int main(){
  10. 10     int n;
  11. 11     cin >> n;
  12. 12     string name, ans;
  13. 13     int score;
  14. 14     for(int i = 0; i < n; ++i){
  15. 15         cin >> name >> score;
  16. 16         aaa[i].name = name;
  17. 17         aaa[i].score = score;
  18. 18         game[name] += score;
  19. 19     }
  20. 20     int maxScore = -1;
  21. 21     for(int i = 0; i < n; ++i) maxScore = max(maxScore, game[aaa[i].name]);
  22. 22     map<string, int> tmp;
  23. 23     for(int i = 0; i < n; ++i){
  24. 24         if(game[aaa[i].name] < maxScore) continue;
  25. 25         tmp[aaa[i].name] += aaa[i].score;
  26. 26         if(tmp[aaa[i].name] >= maxScore){
  27. 27             ans = aaa[i].name;
  28. 28             break;
  29. 29         }
  30. 30     }
  31. 31     cout << ans << endl;
  32. 32     return 0;
  33. 33 }

2B

然后就2B了…..

求2最少几个5最少几个然后min(num_two, num_five)就是答案 剩下输出路径

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int matrix[1111][1111][2];
  5.  5 int dp[1111][1111][2];
  6.  6 int step[1111][1111][2];
  7.  7 
  8.  8 void print(int nx, int ny, int k){
  9.  9     if(nx == 1 && ny == 1) return ;
  10. 10     if(step[nx][ny][k]){
  11. 11         print(nx-1, ny, k);
  12. 12         printf("D");
  13. 13     }
  14. 14     else{
  15. 15         print(nx, ny-1, k);
  16. 16         printf("R");
  17. 17     }
  18. 18 }
  19. 19 int main(){
  20. 20     int n;
  21. 21     scanf("%d", &n);
  22. 22     int zerox = 0, zeroy = 0;
  23. 23     for(int i = 1; i <= n; ++i){
  24. 24         for(int j = 1; j <= n; ++j){
  25. 25             int k;
  26. 26             scanf("%d", &k);
  27. 27             if(k == 0){
  28. 28                 zerox = i;
  29. 29                 zeroy = j;
  30. 30                 continue;
  31. 31             }
  32. 32             int numtwo = 0, numfive = 0;
  33. 33             while(!(k & 1)){
  34. 34                 ++numtwo;
  35. 35                 k >>= 1;
  36. 36             }
  37. 37             while(k % 5 == 0){
  38. 38                 ++numfive;
  39. 39                 k /= 5;
  40. 40             }
  41. 41             matrix[i][j][0] = numtwo;
  42. 42             matrix[i][j][1] = numfive;
  43. 43         }
  44. 44     }
  45. 45     memset(dp, 0x3f, sizeof(dp));
  46. 46     dp[1][1][0] = matrix[1][1][0];
  47. 47     dp[1][1][1] = matrix[1][1][1];
  48. 48     for(int i = 1; i <= n; ++i){
  49. 49         for(int j = 1; j <= n; ++j){
  50. 50             if(i == 1 && j == 1) continue;
  51. 51             for(int k = 0; k < 2; ++k){
  52. 52                 dp[i][j][k] = matrix[i][j][k] + min(dp[i-1][j][k], dp[i][j-1][k]);
  53. 53                 if(dp[i-1][j][k] < dp[i][j-1][k]) step[i][j][k] = 1;
  54. 54             }
  55. 55         }
  56. 56     }
  57. 57     int ans = min(dp[n][n][0], dp[n][n][1]);
  58. 58     if(ans == 0) puts("0");
  59. 59     else if(zerox && zeroy){
  60. 60         puts("1");
  61. 61         int nx = 1, ny = 1;
  62. 62         while(nx < zerox) ++nx, printf("D");
  63. 63         while(ny < zeroy) ++ny, printf("R");
  64. 64         while(nx < n) ++nx, printf("D");
  65. 65         while(ny < n) ++ny, printf("R");
  66. 66         return 0;
  67. 67     }
  68. 68     else printf("%d\n", ans);
  69. 69     int k = dp[n][n][0] < dp[n][n][1] ? 0 : 1;
  70. 70     print(n, n, k);
  71. 71     return 0;
  72. 72 }

2C

模拟退火 先放着

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <cmath>
  2.  2 #include <cstdio>
  3.  3 #include <cstdlib>
  4.  4 #include <cstring>
  5.  5 #include <iostream>
  6.  6 #include <algorithm>
  7.  7 using namespace std;
  8.  8 typedef long long ll;
  9.  9 #define _pow(a) ((a)*(a))
  10. 10 const double eps = 1e-6;
  11. 11 
  12. 12 struct circle{ double x, y, r; }c[3];
  13. 13 double angle[3];
  14. 14 int cx[] = {
  15.       0, 0, 1, -1}, cy[] = {
  16.       1, -1, 0, 0};
  17. 15 
  18. 16 double dis(double x1, double y1, double x2, double y2){
  19. 17     return sqrt(_pow(x1 - x2) + _pow(y1 - y2));
  20. 18 }
  21. 19 
  22. 20 double calc(double x, double y){
  23. 21     for(int i = 0; i < 3; ++i) angle[i] = dis(x, y, c[i].x, c[i].y) / c[i].r;
  24. 22     double value = 0;
  25. 23     for(int i = 0; i < 3; ++i) value += _pow(angle[i] - angle[(i + 1) % 3]);
  26. 24     return value;
  27. 25 }
  28. 26 
  29. 27 int main(){
  30. 28     double x = 0, y = 0;
  31. 29     for(int i = 0; i < 3; ++i){
  32. 30         scanf("%lf %lf %lf", &c[i].x, &c[i].y, &c[i].r);
  33. 31         x += c[i].x / 3.0;
  34. 32         y += c[i].y / 3.0;
  35. 33     }
  36. 34     double deviation = calc(x, y);
  37. 35     double step = 1;
  38. 36     for(int i = 0; i <= 1e5; ++i){
  39. 37         bool flag = false;
  40. 38         double xx, yy;
  41. 39         for(int j = 0; j < 4; ++j){
  42. 40             double nx = x + cx[j] * step, ny = y + cy[j] * step;
  43. 41             double nDeviation = calc(nx, ny);
  44. 42             if(nDeviation < deviation){
  45. 43                 deviation = nDeviation;
  46. 44                 flag = true;
  47. 45                 xx = nx;
  48. 46                 yy = ny;
  49. 47             }
  50. 48         }
  51. 49         if(flag){
  52. 50             x = xx;
  53. 51             y = yy;
  54. 52         }
  55. 53         else step /= 2.0;
  56. 54     }
  57. 55     if(deviation <= eps) printf("%.5f %.5f\n", x, y);
  58. 56     return 0;
  59. 57 }

3A

水题 但是大神的代码总是让我amazing，简单清晰直接

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int main(){
  5.  5     char s[3], t[3];
  6.  6     scanf("%s %s", s, t);
  7.  7     int a = s[0] - t[0], b = s[1] - t[1];
  8.  8     char c = a > 0 ? 'L' : (a = -a, 'R');
  9.  9     char d = b > 0 ? 'D' : (b = -b, 'U');
  10. 10     printf("%d", a > b ? a : b);
  11. 11     while(a || b){
  12. 12         puts("");
  13. 13         if(a) --a, putchar(c);
  14. 14         if(b) --b, putchar(d);
  15. 15     }
  16. 16     return 0;
  17. 17 }

3B

分开按capacity排序 再维护前缀和 再枚举space为1的船的数量

代码好丑………..

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 struct vihecle{
  5.  5     int id;
  6.  6     int cpa;
  7.  7 }p1[111111], p2[111111];
  8.  8 int presum1[111111], presum2[111111];
  9.  9 
  10. 10 bool cmp(vihecle a, vihecle b){
  11. 11     return a.cpa > b.cpa;
  12. 12 }
  13. 13 
  14. 14 int main(){
  15. 15     int n, v;
  16. 16     cin >> n >> v;
  17. 17     int i1 = 0, i2 = 0;
  18. 18     presum1[0] = presum2[0] = 0;
  19. 19     for(int i = 0; i < n; ++i){
  20. 20         int t, pp;
  21. 21         cin >> t >> pp;
  22. 22         if(t == 1){
  23. 23             p1[i1].cpa=pp;
  24. 24             p1[i1++].id=i+1;
  25. 25         }
  26. 26         else{
  27. 27             p2[i2].cpa=pp;
  28. 28             p2[i2++].id=i+1;
  29. 29         }
  30. 30     }
  31. 31     sort(p1, p1 + i1, cmp);
  32. 32     sort(p2, p2 + i2, cmp);
  33. 33     for(int i = 1; i <= i1; ++i) presum1[i] = presum1[i-1] + p1[i-1].cpa;
  34. 34     for(int i = 1; i <= i2; ++i) presum2[i] = presum2[i-1] + p2[i-1].cpa;
  35. 35     int ans = 0, ii1 = 0, ii2 = 0;
  36. 36     for(int i = 0; i <= i1; ++i){
  37. 37         if(i > v) break;
  38. 38         int tmp = presum1[i] + presum2[min((v-i)/2, i2)];
  39. 39         if(tmp > ans){
  40. 40             ans = tmp;
  41. 41             ii1 = i;
  42. 42             ii2 = min((v - i) / 2, i2);
  43. 43         }
  44. 44     }
  45. 45     cout << ans << endl;
  46. 46     for(int i = 0; i < ii1; ++i) cout << p1[i].id << " ";
  47. 47     for(int i = 0; i < ii2; ++i) cout << p2[i].id << " ";
  48. 48     return 0;
  49. 49 }

3C

恶心的模拟……….讲真……玩起来容易写起来恶心…….

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 char g[5][5];
  5.  5 int c1, c2;
  6.  6 bool f1, f2;
  7.  7 
  8.  8 int main(){
  9.  9     for(int i = 0; i < 3; ++i) scanf("%s", g[i]);
  10. 10     c1 = c2 = 0;
  11. 11     f1 = f2 = false;
  12. 12 
  13. 13     for(int i = 0; i < 3; ++i)
  14. 14         if(g[i][0] == g[i][1] && g[i][1] == g[i][2])
  15. 15             if(g[i][0] == 'X') f1 = true;
  16. 16             else if(g[i][0] == '0') f2 = true;
  17. 17     for(int i = 0; i < 3; ++i)
  18. 18         if(g[0][i] == g[1][i] && g[1][i] == g[2][i])
  19. 19             if(g[0][i] == 'X') f1 = true;
  20. 20             else if(g[0][i] == '0') f2 = true;
  21. 21     if(g[0][0] == g[1][1] && g[1][1] == g[2][2])
  22. 22         if(g[0][0] == 'X') f1 = true;
  23. 23         else if(g[0][0] == '0') f2 = true;
  24. 24     if(g[0][2] == g[1][1] && g[1][1] == g[2][0])
  25. 25         if(g[1][1] == 'X') f1 = true;
  26. 26         else if(g[1][1] == '0') f2 = true;
  27. 27 
  28. 28     for(int i = 0; i < 3; ++i)
  29. 29         for(int j = 0; j < 3; ++j)
  30. 30             if(g[i][j] == 'X') ++c1;
  31. 31             else if(g[i][j] == '0') ++c2;
  32. 32     if(c1 == c2 || c1 == c2 + 1){
  33. 33         if(f1 && f2) puts("illegal");
  34. 34         else if(f1 && !f2){
  35. 35             if(c1 == c2 + 1) puts("the first player won");
  36. 36             else puts("illegal");
  37. 37         }
  38. 38         else if(!f1 && f2){
  39. 39             if(c1 == c2) puts("the second player won");
  40. 40             else puts("illegal");
  41. 41         }
  42. 42         else{
  43. 43             if(c1 + c2 == 9) puts("draw");
  44. 44             else if(c1 + c2 < 9){
  45. 45                 if(c1 == c2) puts("first");
  46. 46                 else if(c1 == c2 + 1) puts("second");
  47. 47             }
  48. 48             else puts("illegal");
  49. 49         }
  50. 50     }
  51. 51     else puts("illegal");
  52. 52     return 0;
  53. 53 }

3D

对于处理中每一个过程都有’(‘不少于’)’，将’?’置为’)’，若’(‘少于’)’则在前面的’?’中拿出转换价值最小的进行转换

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 typedef long long ll;
  4.  4 
  5.  5 int main(){
  6.  6     string s;
  7.  7     cin >> s;
  8.  8     ll cnt = 0, ans = 0;
  9.  9     priority_queue<pair<int, int> > q;
  10. 10     for(int i = 0; i < s.size(); ++i){
  11. 11         if(s[i] == '(') ++cnt;
  12. 12         else if(s[i] == ')') --cnt;
  13. 13         else{
  14. 14             int a, b;
  15. 15             cin >> a >> b;
  16. 16             ans += b;
  17. 17             --cnt;
  18. 18             s[i] = ')';
  19. 19             q.push(make_pair(b - a, i));
  20. 20         }
  21. 21         if(cnt < 0){
  22. 22             if(q.empty()) break;
  23. 23             pair<int, int> p = q.top();
  24. 24             q.pop();
  25. 25             ans -= p.first;
  26. 26             s[p.second] = '(';
  27. 27             cnt += 2;
  28. 28         }
  29. 29     }
  30. 30     if(cnt) cout << "-1" << endl;
  31. 31     else cout << ans << endl << s << endl;
  32. 32     return 0;
  33. 33 }

4A

超级水……

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2. 2 using namespace std;
  3. 3 
  4. 4 int main(){
  5. 5     int n;
  6. 6     cin >> n;
  7. 7     cout << (((n & 1) || n == 2) ? "NO" : "YES") << endl;
  8. 8     return 0;
  9. 9 }

4B

水，随便贪一下

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 struct {
  5.  5     int mini, maxi;
  6.  6 }p[33];
  7.  7 
  8.  8 int main(){
  9.  9     int d, maxSum;
  10. 10     cin >> d >> maxSum;
  11. 11     int totalMin = 0, totalMax = 0;
  12. 12     for(int i = 0; i < d; ++i) cin >> p[i].mini >> p[i].maxi, totalMin += p[i].mini, totalMax += p[i].maxi;
  13. 13     if(totalMin > maxSum || totalMax < maxSum)
  14. 14         cout << "NO" << endl;
  15. 15     else{
  16. 16         cout << "YES" << endl;
  17. 17         int t = maxSum - totalMin;
  18. 18         for(int i = 0; i < d; ++i){
  19. 19             int ansi = p[i].mini;
  20. 20             if(t){
  21. 21                 ansi = min(p[i].maxi, ansi + t);
  22. 22                 t -= (ansi - p[i].mini);
  23. 23             }
  24. 24             cout << ansi << " \n"[i == d-1];
  25. 25         }
  26. 26     }
  27. 27     return 0;
  28. 28 }

4C

水，输入保证只有小写字母，map水过

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int main(){
  5.  5     int n;
  6.  6     cin >> n;
  7.  7     map<string, int> name;
  8.  8     while(n--){
  9.  9         string s;
  10. 10         cin >> s;
  11. 11         if(name[s] == 0) cout << "OK" << endl;
  12. 12         else cout << s << name[s] << endl;
  13. 13         ++name[s];
  14. 14     }
  15. 15     return 0;
  16. 16 }

4D

n^2的暴力dp…….

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int n;
  5.  5 struct env{
  6.  6     int w, h;
  7.  7 }p[5555];
  8.  8 int dp[5555], pre[5555];
  9.  9 
  10. 10 int dfs(int k){
  11. 11     if(dp[k]) return dp[k];
  12. 12     for(int i = 1; i <= n; ++i){
  13. 13         if(p[k].w < p[i].w && p[k].h < p[i].h){
  14. 14             if(dfs(i) + 1 > dp[k]){
  15. 15                 pre[k] = i;
  16. 16                 dp[k] = dfs(i) + 1;
  17. 17             }
  18. 18         }
  19. 19     }
  20. 20     return dp[k];
  21. 21 }
  22. 22 
  23. 23 int main(){
  24. 24     cin >> n;
  25. 25     for(int i = 0; i <= n; ++i)
  26. 26         cin >> p[i].w >> p[i].h;
  27. 27     cout << dfs(0) << endl;
  28. 28     for(int i = pre[0]; i > 0; i = pre[i]) cout << i << " ";
  29. 29     cout << endl;
  30. 30     return 0;
  31. 31 }

5A

水

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int main(){
  5.  5     string s;
  6.  6     int ans = 0, member = 0;
  7.  7     while(getline(cin, s)){
  8.  8         if(s[0] == '+') ++member;
  9.  9         else if(s[0] == '-') --member;
  10. 10         else{
  11. 11             int len = s.end() - find(s.begin(), s.end(), ':') - 1;
  12. 12             ans += member * len;
  13. 13         }
  14. 14     }
  15. 15     cout << ans << endl;
  16. 16     return 0;
  17. 17 }

5B

一眼样例明白大概但是奇数的情况要交替……..

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int main(){
  5.  5     vector<string> v;
  6.  6     string s;
  7.  7     int len = 0;
  8.  8     while(getline(cin, s)){
  9.  9         v.push_back(s);
  10. 10         len = max(len, int(s.size()));
  11. 11     }
  12. 12     cout << string(len+2, '*') << endl;
  13. 13     int k = -1;
  14. 14     for(vector<string>::iterator i = v.begin(); i != v.end(); ++i){
  15. 15         int l = len - (*i).size();
  16. 16         string fr = string(floor(double(l)/2), ' '), ba = string(ceil(double(l)/2), ' ');
  17. 17         if(l & 1){
  18. 18             if(!k) cout << "*" << ba << *i << fr << "*" << endl;
  19. 19             else cout << "*" << fr << *i << ba << "*" << endl;
  20. 20             k = ~k;
  21. 21         }
  22. 22         else cout << "*" << fr << *i << ba << "*" << endl;
  23. 23     }
  24. 24     cout << string(len+2, '*') << endl;
  25. 25     return 0;
  26. 26 }

5C

dp，让我智障好久的题……..

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 const int maxn = 1e6 + 7;
  5.  5 int dp[maxn];
  6.  6 
  7.  7 int main(){
  8.  8     ios::sync_with_stdio(false);
  9.  9     memset(dp, 0, sizeof(dp));
  10. 10     string s;
  11. 11     cin >> s;
  12. 12     stack<int> pos;
  13. 13     while(!pos.empty()) pos.pop();
  14. 14     int len = 0, sum = 1;
  15. 15     for(int i = 0; i < s.size(); ++i){
  16. 16         if(s[i] == '(') pos.push(i);
  17. 17         else if(!pos.empty()){
  18. 18             int j = pos.top();
  19. 19             pos.pop();
  20. 20             int tmpSize = i - j + 1;
  21. 21             dp[i] = tmpSize + (j ? dp[j-1] : 0);
  22. 22             if(dp[i] > len){
  23. 23                 len = dp[i];
  24. 24                 sum = 1;
  25. 25             }
  26. 26             else if(dp[i] == len) ++sum;
  27. 27         }
  28. 28     }
  29. 29     cout << len << " " << sum << endl;
  30. 30     return 0;
  31. 31 }

5D

运动学卧槽……放弃

分类还是渣的不成样子…..

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 const double eps = 1e-8;
  5.  5 double a, v, l, d, w, t1, t2, vd, vt, r;
  6.  6 
  7.  7 int fcmp(double x){
  8.  8     if(fabs(x) < eps) return 0;
  9.  9     else return x < 0 ? -1 : 1;
  10. 10 }
  11. 11 
  12. 12 int main(){
  13. 13     scanf("%lf %lf %lf %lf %lf", &a, &v, &l, &d, &w);
  14. 14     vt = sqrt(w * w / 2 + a * d);
  15. 15     r = l - d;
  16. 16     if(fcmp(d - v * v / 2 / a) <= 0 && fcmp(sqrt(2 * a * d) - w) <= 0){
  17. 17         t1 = sqrt(2 * d / a);
  18. 18         vd = sqrt(2 * a * d);
  19. 19     }
  20. 20     else if(fcmp(d - v * v / 2 / a) >= 0 && fcmp(w - v) >= 0){
  21. 21         t1 = d / v + v / 2 / a;
  22. 22         vd = v;
  23. 23     }
  24. 24     else if(fcmp(v - vt) >= 0 && fcmp(vt - w) >= 0){
  25. 25         t1 = (2 * vt - w) / a;
  26. 26         vd = w;
  27. 27     }
  28. 28     else{
  29. 29         t1 = d / v + (2 * v - w) / a - (2 * v * v - w * w) / 2 / a / v;
  30. 30         vd = w;
  31. 31     }
  32. 32     if(fcmp(r - (v * v - vd * vd) / 2 / a) >= 0)
  33. 33         t2 = r / v + (v - vd) / a - (v * v - vd * vd) / 2 / a / v;
  34. 34     else
  35. 35         t2 = (sqrt(2 * a * r + vd * vd) - vd) / a;
  36. 36     printf("%.10f\n", t1 + t2);
  37. 37     return 0;
  38. 38 }

5E

找每个点左右分别严格高于这个点的点，有点像并查集的样子

还需要找处在中间的相同高度的点

每个点与左右两个高点及相同高度的点可以互相看到

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 typedef long long ll;
  4.  4 
  5.  5 const int maxn = 1e6 + 7;
  6.  6 int height[maxn], l[maxn], r[maxn], same[maxn];
  7.  7 ll ans = 0;
  8.  8 
  9.  9 int main(){
  10. 10     int n;
  11. 11     scanf("%d", &n);
  12. 12     int maxi = -1, pos = 0;
  13. 13     for(int i = 0; i < n; ++i){
  14. 14         scanf("%d", &height[i]);
  15. 15         if(height[i] > maxi){
  16. 16             maxi = height[i];
  17. 17             pos = i;
  18. 18         }
  19. 19     }
  20. 20     rotate(height, height + pos, height + n);
  21. 21     height[n] = maxi;
  22. 22     same[n] = 0;
  23. 23     for(int i = n - 1; i >= 0; --i){
  24. 24         r[i] = i + 1;
  25. 25         while(r[i] < n && height[i] > height[r[i]]) r[i] = r[r[i]];
  26. 26         if(r[i] != n && height[i] == height[r[i]]){
  27. 27             same[i] = same[r[i]] + 1;
  28. 28             r[i] = r[r[i]];
  29. 29         }
  30. 30     }
  31. 31     for(int i = 1; i <= n; ++i){
  32. 32         l[i] = i - 1;
  33. 33         while(l[i] && height[i] >= height[l[i]]) l[i] = l[l[i]];
  34. 34     }
  35. 35     for(int i = 1; i < n; ++i){
  36. 36         ans += (2 + same[i]);
  37. 37         if(l[i] == 0 && r[i] == n) --ans;
  38. 38     }
  39. 39     printf("%I64d\n", ans);
  40. 40     return 0;
  41. 41 }

6A

水题

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int a, b, c, d;
  5.  5 
  6.  6 void init(){
  7.  7     int arr[4];
  8.  8     cin >> arr[0] >> arr[1] >> arr[2] >> arr[3];
  9.  9     sort(arr, arr + 4);
  10. 10     a = arr[0]; b= arr[1]; c = arr[2]; d = arr[3];
  11. 11 }
  12. 12 int main(){
  13. 13     init();
  14. 14     if(a + b > c || a + b > d || a + c > d || b + c > d) puts("TRIANGLE");
  15. 15     else if(a + b == c || a + b == d || a + c == d || b + c == d) puts("SEGMENT");
  16. 16     else puts("IMPOSSIBLE");
  17. 17     return 0;
  18. 18 }

6B

两层广搜过的，然而智障了……用一层广搜+set就行了

两层的辣鸡代码….:

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 const int maxsize = 111;
  5.  5 int cx[] = {
  6.       1, -1, 0, 0}, cy[] = {
  7.       0, 0, 1, -1};
  8.  6 struct pos{
  9.  7     int x, y;
  10.  8     pos(int xx = 0, int yy = 0): x(xx), y(yy){};
  11.  9 };
  12. 10 
  13. 11 char room[maxsize][maxsize];
  14. 12 bool flag[maxsize][maxsize];
  15. 13 
  16. 14 int main(){
  17. 15     int n, m;
  18. 16     char color;
  19. 17     cin >> n >> m;
  20. 18     cin.get();
  21. 19     cin >> color;
  22. 20     queue<pos> mainpos;
  23. 21     memset(flag, false, sizeof(flag));
  24. 22     for(int i = 0; i < n; ++i)
  25. 23         for(int j = 0; j < m; ++j){
  26. 24             cin >> room[i][j];
  27. 25             if(room[i][j] == color){
  28. 26                 mainpos.push(pos(i, j));
  29. 27                 flag[i][j] = true;
  30. 28             }
  31. 29         }
  32. 30     int ans = 0;
  33. 31     while(!mainpos.empty()){
  34. 32         int x = mainpos.front().x, y = mainpos.front().y;
  35. 33         mainpos.pop();
  36. 34         for(int i = 0; i < 4; ++i){
  37. 35             int nx = x + cx[i], ny = y + cy[i];
  38. 36             if(nx < 0 || n <= nx || ny < 0 || m <= ny || flag[nx][ny] || room[nx][ny] == '.') continue;
  39. 37             ++ans;
  40. 38             queue<pos> tpos;
  41. 39             tpos.push(pos(nx, ny));
  42. 40             flag[nx][ny] = true;
  43. 41             char tcolor = room[nx][ny];
  44. 42             while(!tpos.empty()){
  45. 43                 int xx = tpos.front().x, yy = tpos.front().y;
  46. 44                 tpos.pop();
  47. 45                 for(int j = 0; j < 4; ++j){
  48. 46                     int nxx = xx + cx[j], nyy = yy + cy[j];
  49. 47                     if(nxx < 0 || n <= nxx || nyy < 0 || m <= nyy || room[nxx][nyy] != tcolor || flag[nxx][nyy]) continue;
  50. 48                     flag[nxx][nyy] = true;
  51. 49                     tpos.push(pos(nxx, nyy));
  52. 50                 }
  53. 51             }
  54. 52         }
  55. 53     }
  56. 54     cout << ans << endl;
  57. 55     return 0;
  58. 56 }

一层 + set：

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 const int maxsize = 111;
  5.  5 int cx[] = {
  6.       1, -1, 0, 0}, cy[] = {
  7.       0, 0, 1, -1};
  8.  6 struct pos{
  9.  7     int x, y;
  10.  8     pos(int xx = 0, int yy = 0): x(xx), y(yy){};
  11.  9 };
  12. 10 
  13. 11 char room[maxsize][maxsize];
  14. 12 
  15. 13 int main(){
  16. 14     int n, m;
  17. 15     char color;
  18. 16     cin >> n >> m;
  19. 17     cin.get();
  20. 18     cin >> color;
  21. 19     queue<pos> mainpos;
  22. 20     for(int i = 0; i < n; ++i)
  23. 21         for(int j = 0; j < m; ++j){
  24. 22             cin >> room[i][j];
  25. 23             if(room[i][j] == color)
  26. 24                 mainpos.push(pos(i, j));
  27. 25         }
  28. 26     set<char> ans;
  29. 27     while(!mainpos.empty()){
  30. 28         int x = mainpos.front().x, y = mainpos.front().y;
  31. 29         mainpos.pop();
  32. 30         for(int i = 0; i < 4; ++i){
  33. 31             int nx = x + cx[i], ny = y + cy[i];
  34. 32             if(nx < 0 || n <= nx || ny < 0 || m <= ny || room[nx][ny] == color || room[nx][ny] == '.') continue;
  35. 33             ans.insert(room[nx][ny]);
  36. 34         }
  37. 35     }
  38. 36     cout << ans.size() << endl;
  39. 37     return 0;
  40. 38 }

6C

水题，第一次用deque

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 int main(){
  5.  5     int n;
  6.  6     cin >> n;
  7.  7     deque<int> chb;
  8.  8     for(int i = 0; i < n; ++i){
  9.  9         int tmp;
  10. 10         cin >> tmp;
  11. 11         chb.push_back(tmp);
  12. 12     }
  13. 13     int t1 = chb.front(), ans1 = 1, t2 = 0, ans2 = 0;
  14. 14     chb.pop_front();
  15. 15     while(!chb.empty()){
  16. 16         if(t1 <= t2){
  17. 17             t1 += chb.front();
  18. 18             ++ans1;
  19. 19             chb.pop_front();
  20. 20         }
  21. 21         else{
  22. 22             t2 += chb.back();
  23. 23             ++ans2;
  24. 24             chb.pop_back();
  25. 25         }
  26. 26     }
  27. 27     cout << ans1 << " " << ans2 << endl;
  28. 28     return 0;
  29. 29 }

6D

不会做…..题解看不懂……. dfs

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 typedef long long ll;
  4.  4 const int MAXN = 22;
  5.  5 int n, a, b, ans, h[MAXN], hh[MAXN];
  6.  6 
  7.  7 
  8.  8 bool dfs(int curpos, int time, int hitpos){
  9.  9     if(time == 0){
  10. 10         for(int i = 1; i <= n; ++i)
  11. 11             if(h[i] >= 0) return false;
  12. 12         return true;
  13. 13     }
  14. 14     if(h[curpos] < 0) return dfs(curpos+1, time, hitpos);
  15. 15     for(int i = min(n-1, max(hitpos, max(2, curpos))); i <= min(n-1, curpos+1); ++i){
  16. 16         h[i] -= a; h[i-1] -= b; h[i+1] -= b;
  17. 17         if(dfs(curpos, time-1, i)){
  18. 18             hh[time] = i;
  19. 19             return true;
  20. 20         }
  21. 21         h[i] += a; h[i-1] += b; h[i+1] += b;
  22. 22     }
  23. 23     return false;
  24. 24 }
  25. 25 
  26. 26 
  27. 27 int main(){
  28. 28     cin >> n >> a >> b;
  29. 29     for(int i = 1; i <= n; ++i) cin >> h[i];
  30. 30     for(int i = 1; ; ++i){
  31. 31         memset(hh, 0, sizeof(hh));
  32. 32         if(dfs(1, i, 2)){
  33. 33             cout << i << endl;
  34. 34             for(int j = 1; j <= i; ++j)
  35. 35                 cout << hh[j] << " ";
  36. 36             return 0;
  37. 37         }
  38. 38     }
  39. 39     return 0;
  40. 40 }

6E

求最大值最小值差不超过给定值的最长子串

ST表预处理区间最大值最小值，加个二分右边界…

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 const int maxn = 1e5 + 7;
  5.  5 int n, k;
  6.  6 int data[maxn];
  7.  7 int premin[maxn][20], premax[maxn][20];
  8.  8 struct tpoint{
  9.  9     int l, r;
  10. 10     tpoint(int _l, int _r): l(_l), r(_r) {};
  11. 11 };
  12. 12 
  13. 13 void init_st(){
  14. 14     for(int i = 1; i <= n; ++i)
  15. 15         premin[i][0] = premax[i][0] = data[i];
  16. 16     int k = floor(log(double(n)) / log(2.0));
  17. 17     for(int j = 1; j <= k; ++j)
  18. 18         for(int i = n; i >= 1; --i)
  19. 19             if(i + (1<<(j-1)) <= n){
  20. 20                 premin[i][j] = min(premin[i][j-1], premin[i+(1<<(j-1))][j-1]);
  21. 21                 premax[i][j] = max(premax[i][j-1], premax[i+(1<<(j-1))][j-1]);
  22. 22             }
  23. 23 }
  24. 24 
  25. 25 int query_st(int l, int r){
  26. 26     int k = floor(log(double(r-l+1)) / log(2.0));
  27. 27     return max(premax[l][k], premax[r-(1<<k)+1][k]) - min(premin[l][k], premin[r-(1<<k)+1][k]);
  28. 28 }
  29. 29 
  30. 30 int check(int i){
  31. 31     int l = i, r = n + 1;
  32. 32     while(l < r - 1){
  33. 33         int mid = (l + r) >> 1;
  34. 34         if(query_st(i, mid) <= k) l = mid;
  35. 35         else r = mid;
  36. 36     }
  37. 37     return l;
  38. 38 }
  39. 39 
  40. 40 int main(){
  41. 41     scanf("%d %d", &n, &k);
  42. 42     for(int i = 1; i <= n; ++i)
  43. 43         scanf("%d", &data[i]);
  44. 44     init_st();
  45. 45     int amount = 0;
  46. 46     vector<tpoint> vp;
  47. 47     for(int l = 1; l <= n; ++l){
  48. 48         int r = check(l);
  49. 49         int num = r - l + 1;
  50. 50         if(num > amount){
  51. 51             vp.clear();
  52. 52             vp.push_back(tpoint(l, r));
  53. 53             amount = num;
  54. 54         }
  55. 55         else if(num == amount) vp.push_back(tpoint(l, r));
  56. 56     }
  57. 57     printf("%d %d\n", amount, vp.size());
  58. 58     for(vector<tpoint>::iterator i = vp.begin(); i != vp.end(); ++i)
  59. 59         printf("%d %d\n", (*i).l, (*i).r);
  60. 60     return 0;
  61. 61 }

7A

水题但是有点意思(因为你还是个渣啊~)

记下每一行每一列多少个黑，凑齐8个答案+1，若答案是16就-8

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 char cb[10][10];
  5.  5 int cnt[10][10];
  6.  6 
  7.  7 int main(){
  8.  8     ios::sync_with_stdio(false);
  9.  9     int ans = 0;
  10. 10     for(int i = 0; i < 8; ++i)
  11. 11         for(int j = 0; j < 8; ++j){
  12. 12             cin >> cb[i][j];
  13. 13             if(cb[i][j] == 'B'){
  14. 14                 ++cnt[i][8];
  15. 15                 ++cnt[8][j];
  16. 16             }
  17. 17             if(cnt[i][8] == 8) ++ans;
  18. 18             if(cnt[8][j] == 8) ++ans;
  19. 19         }
  20. 20     if(ans == 16) ans -= 8;
  21. 21     cout << ans << endl;
  22. 22     return 0;
  23. 23 }

7B

粗暴地模拟，大概坑都是给我挖的….

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 
  4.  4 const int maxn = 111;
  5.  5 int n, k, mem[maxn];
  6.  6 
  7.  7 int main(){
  8.  8     int counter = 0;
  9.  9     scanf("%d %d", &n, &k);
  10. 10     while(n--){
  11. 11         char s[11];
  12. 12         int x;
  13. 13         scanf("%s", s);
  14. 14         if(s[0] == 'a' || s[0] == 'e'){
  15. 15             scanf("%d", &x);
  16. 16             if(s[0] == 'a'){
  17. 17                 bool flag = false;
  18. 18                 int tmp = 0;
  19. 19                 for(int i = 0; i < k; ++i){
  20. 20                     if(mem[i] == 0) ++tmp;
  21. 21                     else tmp = 0;
  22. 22                     if(tmp == x){
  23. 23                         printf("%d\n", ++counter);
  24. 24                         int index = i;
  25. 25                         while(tmp--) mem[index--] = counter;
  26. 26                         flag = true;
  27. 27                         break;
  28. 28                     }
  29. 29                 }
  30. 30                 if(!flag) puts("NULL");
  31. 31             }
  32. 32             else{
  33. 33                 bool flag = false;
  34. 34                 for(int i = 0; i < k; ++i){
  35. 35                     if(x == 0) break;
  36. 36                     if(mem[i] == x){
  37. 37                         mem[i] = 0;
  38. 38                         flag = true;
  39. 39                     }
  40. 40                 }
  41. 41                 if(!flag) puts("ILLEGAL_ERASE_ARGUMENT");
  42. 42             }
  43. 43         }
  44. 44         else{
  45. 45             for(int i = 0; i < k; ++i){
  46. 46                 if(mem[i] != 0){
  47. 47                     int j = i;
  48. 48                     while(j > 0 && mem[j-1] == 0) --j;
  49. 49                     swap(mem[i], mem[j]);
  50. 50                 }
  51. 51             }
  52. 52         }
  53. 53     }
  54. 54     return 0;
  55. 55 }

7C

扩展欧几里得解不定方程组

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 typedef long long ll;
  4.  4 
  5.  5 ll ex_gcd(ll a, ll b, ll& x, ll& y){
  6.  6     if(b == 0){
  7.  7         x = 1;
  8.  8         y = 0;
  9.  9         return a;
  10. 10     }
  11. 11     int k = ex_gcd(b, a % b, x, y);
  12. 12     int t = y;
  13. 13     y = x - (a / b) * y;
  14. 14     x = t;
  15. 15     return k;
  16. 16 }
  17. 17 
  18. 18 int main(){
  19. 19     ios::sync_with_stdio(false);
  20. 20     ll a, b, c, x, y;
  21. 21     cin >> a >> b >> c;
  22. 22     ll k = ex_gcd(a, b, x, y);
  23. 23     c = -c;
  24. 24     if(c % k) cout << "-1" << endl;
  25. 25     else cout << (c / k * x) << " " << (c / k * y) << endl;
  26. 26     return 0;
  27. 27 }

7D

字符串两个方向hash判回文+dp

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 typedef long long ll;
  4.  4 
  5.  5 const int maxn = 5e6 + 7;
  6.  6 const int mod = 1e9 + 7;
  7.  7 const int tmp = 137731735;
  8.  8 char s[maxn];
  9.  9 ll prefix[maxn], suffix[maxn], dp[maxn];
  10. 10 
  11. 11 int main(){
  12. 12     gets(s);
  13. 13     for(int i = 0; s[i]; ++i){
  14. 14         if(s[i] >= '0' && s[i] <= '9')
  15. 15             s[i] -= '0';
  16. 16         else if(s[i] >= 'a' && s[i] <= 'z')
  17. 17             s[i] -= ('a' - 10);
  18. 18         else
  19. 19             s[i] -= ('A' - 36);
  20. 20     }
  21. 21     ll len = strlen(s), base = 1;
  22. 22     for(int i = 1; i <= len; ++i){
  23. 23         prefix[i] = (prefix[i-1] + s[i-1] * base) % mod;
  24. 24         base = (base * tmp) % mod;
  25. 25         suffix[i] = (suffix[i-1] * tmp + s[i-1]) % mod;
  26. 26     }
  27. 27     ll ans = 0;
  28. 28     for(int i = 1; i <= len; ++i){
  29. 29         if(prefix[i] == suffix[i]){
  30. 30             dp[i] = dp[i>>1] + 1;
  31. 31             ans += dp[i];
  32. 32         }
  33. 33     }
  34. 34     printf("%I64d\n", ans);
  35. 35     return 0;
  36. 36 }

7E

arhgoiawhengiuehgoaijgioj……..

8A

水题，用py3写是因为…..懒……

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 s = input()
  2.  2 s1 = input()
  3.  3 s2 = input()
  4.  4 
  5.  5 forw = backw = False
  6.  6 tmp = s.find(s1)
  7.  7 if ~tmp:
  8.  8     if ~s[tmp+len(s1):].find(s2):
  9.  9         forw = True
  10. 10 s = s[::-1]
  11. 11 tmp = s.find(s1)
  12. 12 if ~tmp:
  13. 13     if ~s[tmp+len(s1):].find(s2):
  14. 14         backw = True
  15. 15 
  16. 16 if forw and backw: print('both')
  17. 17 elif forw: print('forward')
  18. 18 elif backw: print('backward')
  19. 19 else: print('fantasy')

8B

啊啊啊啊啊啊啊手贱啊啊啊啊啊啊啊 真·教育题 谢谢(微笑)

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 typedef pair<int, int> point;
  4.  4 map<point, int> check;
  5.  5 int cx[] = {
  6.       1, -1, 0, 0}, cy[] = {
  7.       0, 0, -1, 1};
  8.  6 int main(){
  9.  7     string s;
  10.  8     cin >> s;
  11.  9     int x = 0, y = 0, xx = 0, yy = 0;
  12. 10     ++check[point(x, y)];
  13. 11     bool flag = true;
  14. 12     for(int i = 0; i < s.size(); ++i){
  15. 13         if(s[i] == 'L') --x;
  16. 14         else if(s[i] == 'R') ++x;
  17. 15         else if(s[i] == 'U') ++y;
  18. 16         else --y;
  19. 17         for(int i = 0; i < 4; ++i){
  20. 18             int xxx = x + cx[i], yyy = y + cy[i];
  21. 19             if(xxx == xx && yyy == yy) continue;
  22. 20             if(check[point(xxx, yyy)]){
  23. 21                 flag = false;
  24. 22                 break;
  25. 23             }
  26. 24         }
  27. 25         if(check[point(x, y)]) flag = false;
  28. 26         if(!flag) break;
  29. 27         ++check[point(x, y)];
  30. 28         xx = x; yy = y;
  31. 29     }
  32. 30     cout << (flag ? "OK" : "BUG") << endl;
  33. 31     return 0;
  34. 32 }

8C

状压dp，不需要绝对固定的顺序，所以每次只要取最前面可取的(line34的break)，每次拿一个或两个(最里层for从 j 开始)

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 const int MAXN = 25;
  4.  4 const int INF = 0x3f3f3f3f;
  5.  5 struct point{
  6.  6     int x, y;
  7.  7     point(){}
  8.  8     point(int xx, int yy): x(xx), y(yy) {}
  9.  9 };
  10. 10 point p[MAXN];
  11. 11 int n, dp[1<<MAXN], pre[1<<MAXN], dis[MAXN][MAXN], ans[555];
  12. 12 inline int calc(point a, point b){
  13. 13     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  14. 14 }
  15. 15 int main(){
  16. 16     cin >> p[0].x >> p[0].y >> n, p[n] = p[0];
  17. 17     for(int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
  18. 18     for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) dis[i][j] = calc(p[i], p[j]);
  19. 19     memset(dp, INF, sizeof(dp));
  20. 20     dp[0] = 0;
  21. 21     for(int i = 0; i < (1<<n); ++i)
  22. 22         if(dp[i] != INF)
  23. 23             for(int j = 0; j < n; ++j)
  24. 24                 if(!(i>>j&1)){
  25. 25                     for(int k = j; k < n; ++k)
  26. 26                         if(!(i>>k&1)){
  27. 27                             int cur = i | (1<<j) | (1<<k);
  28. 28                             int tmp = dp[i] + dis[n][j] + dis[j][k] + dis[k][n];
  29. 29                             if(dp[cur] > tmp){
  30. 30                                 dp[cur] = tmp;
  31. 31                                 pre[cur] = i;
  32. 32                             }
  33. 33                         }
  34. 34                     break;
  35. 35                 }
  36. 36     cout << dp[(1<<n)-1] << endl << 0;
  37. 37     int cnt = 0;
  38. 38     for(int i = (1<<n)-1; i; i = pre[i]){
  39. 39         int tmp = pre[i] ^ i;
  40. 40         ans[cnt++] = 0;
  41. 41         for(int j = 0; j < n; ++j)
  42. 42             if((1<<j)&tmp)
  43. 43                 ans[cnt++] = j + 1;
  44. 44     }
  45. 45     for(int i = cnt-1; ~i; --i) cout << " " << ans[i];
  46. 46     return 0;
  47. 47 }

8D

转载于:https://www.cnblogs.com/book-book/p/5496344.html

发表评论

表情：
评论列表 （有 0 条评论，338人围观）

还没有评论，来说两句吧...

相关阅读