Znzryb's Blog
0%

Codeforces Round 1087 (Div. 2)——CF-2209-D. Ghostfires（奇数的构造可以先枚举多出来的东西）（怎么样凑出最多的 gb，gr，rb？求解方程组）（贪心构造的有问题？就强制多枚举前缀，我们直接给贪心暴力枚举一个长度 为 3 的前缀，这在遇到奇偶性问题的时候尤其有用）

Posted on Edited on

题目大意

题面总结

给定多组数据。每组给出三种幽火数量：红色 r、绿色 g、蓝色 b。

你需要构造一个只由 R、G、B 组成的字符串 s，表示按顺序摆放的幽火颜色，要求：

  • R、G、B 的使用次数分别不超过 r、g、b。

  • 对任意相邻位置，颜色不能相同，即 s_i != s_{i+1}。

  • 对任意间隔 2 个位置（下标差 3）的位置，颜色也不能相同，即 s_i != s_{i+3}。

  • 在满足以上条件下，|s| 要尽可能长。

如果有多个最长可行答案，输出任意一个即可。

输入输出要求

  • 输入第一行为测试组数 t。

  • 每组输入一行三个整数 r g b。

  • 对每组输出一行构造出的字符串 s。

数据范围

  • 1 <= t <= 10^4

  • 0 <= r, g, b <= 10^6

  • r + g + b > 0

  • 所有测试组的 r + g + b 总和不超过 10^6

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
5
0 0 1
1 1 1
0 3 0
2 2 2
2 7 3

输出
B
RGB
G
GBRBRG
GRGRGBGBGBG

样例配合说明

  • 第 1 组：只有 1 个蓝色，输出 B，长度为 1 且合法。

  • 第 2 组：三种颜色各 1 个，RGB 使用了全部 3 个且满足限制。

  • 第 3 组：只有绿色 3 个，但相邻不能同色，所以最多只能放 1 个，输出 G。

  • 第 4 组：GBRBRG 长度为 6，刚好把 2,2,2 全部用完，并满足相邻与间隔 2 的限制。

  • 第 5 组：GRGRGBGBGBG 在给定数量下给出一个满足条件的最长构造。

思路讲解

image

不难发现，能够凑的话，肯定是凑出足够的这个 gb，gr，rb 最好。但是怎么样凑出最多的 gb，gr，rb？其实这个就是求解一个线性方程组（如上），我们可以得到 rb 的这个数量。

但你会发现，如果采用数学式方法，去求解这个二元组的数量，然后去做，肯定是能做出来的，但是坑非常多，首先，这个元组是有可能 rb 求出来是一个负数。

这道题目怎么做？如下。

image

当然，你说为什么就强制给他安一个前缀就对了？其实也没什么神秘的，其实到最后，就是一个奇偶性问题，奇偶性问题有的时候一个的改变，就足以改变正确性了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// 强制枚举前缀
  for (int i = 0; i < pow3[3]; ++i) {
      ll opi = i;
      vector<Num_color> rgb = rgb_global;
      string ans;
      auto push_to_ans = [&](ll i) {
          ans.push_back(rgb[i].color);
          rgb[i].num--;
      };
      auto check_ans = [&]() {
          for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
              if (i - 1 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 1]) {
                  return false;
              }
          }
          for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
              if (i - 3 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 3]) {
                  return false;
              }
          }
          return true;
      };
      auto check_ans_all = [&]() {
          for (int i = SZ(ans) - 1; i >= 0; --i) {
              if (i - 1 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 1]) {
                  return false;
              }
          }
          for (int i = SZ(ans) - 1; i >= 0; --i) {
              if (i - 3 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 3]) {
                  return false;
              }
          }
          return true;
      };
      while (opi != 0) {
          push_to_ans(opi % 3);
          opi/=3;
      }
      if (!check_ans_all()) {
          continue;
      }
      sort(all(rgb), cmp);
      if (rgb[2].num < 0) {
          continue;
      }
      while (true) {
          sort(all(rgb), cmp);
          if (rgb[2].num > 0) {
              push_to_ans(0);
              push_to_ans(2);
              if (!check_ans()) {
                  swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
                  if (!check_ans()) {
                      break;
                  }
              }
              // 以后尽量不要这么写 continue，万一漏了很难 debug 出来
              continue;
          }
          if (rgb[1].num > 0) {
              push_to_ans(0);
              push_to_ans(1);
              if (!check_ans()) {
                  swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
                  if (!check_ans()) {
                      break;
                  }
              }
              continue;
          }
          if (rgb[0].num > 0) {
              push_to_ans(0);
              if (!check_ans()) {
                  ans.pop_back();
                  break;
              }
          }
          break;
      }
      // #ifdef LOCAL
      //         debug(ans);
      //         debug(ans_global);
      // #endif
      if (SZ(ans) > SZ(ans_global)) {
          swap(ans, ans_global);
      }
  }
  cout << ans_global << "\n";

AC代码

AC
https://codeforces.com/contest/2209/submission/367802322

心路历程（WA，TLE，MLE……）

写对拍器的时候，为了防止对拍写的有问题，最好写为不等于，这样子，对拍器生成的字符串过小也可以非常容易的看出来。

1
2
3
4
5
dfs(dfs, "");
if (SZ(brute) != SZ(ans)) {
    cout << "too small\n";
    cout << brute << "\n";
}