题解：P17857 立秋 / autumnascit

xxxxxzy · 2026-11-08 18:19:23 · 题解

一个比较蠢的做法。

考虑把一些字符放在一起产生贡献，称为匹配。我们称一个数达到绝对众数为 2x \ge n。这个时候其他所有字符只能插空这个字符。

很容易发现一些匹配：

尝试贪心，首先尽可能匹配类型一，记更新后的为 a',b'：

• + 如果 $a'$ 比较大：考虑一直进行第四类匹配，直到让 $a'$ 称为绝对众数。之后的贡献是一直进行五类匹配的次数。算一下得到答案为 $c+d+2e-a'+1+\max(0,\min(c,d)-(c+d+e-a'+1))+[a>b][c>d]+[a<b][c<d]$。 + 如果 $c$ 比较大（不妨设 $c \ge d$）：考虑一直进行第四类匹配或者第五类匹配，直到让 $c'$ 成为绝对众数，之后的贡献为 $0$。算一下，贡献为 $\min(a+d+e+1-c,a+c+e+1-d)$。 + 如果 $e$ 比较大，那么 $a'$ 一定可以全部产生贡献。贡献为 $a'$。 + 如果 $a',c,e$ 没有明显的大小关系，那么此时上界为 $\min(a',\min(c,d)+e+[a>b][c>d]+[a<b][c<d])$。 + 综合起来，对四类贡献取 $\min$，再加上 $2(a-a')$ 即可得到答案。
• 否则，在 c,d,e 中出现了绝对众数，贡献固定了，为 \min(a'+b'+d+e-c+1,a'+b'+c+e-d+1,a+b)。

答案为以下所有项取 \min 后加上 2 \min(a,b)：

• 记 a'=a-\min(a,b),b'=b-\min(a,b)。
• 如果 (a',b',c,d,e) 不存在任意解（也就是 2 \max \le n + 1）：
• 否则的话，记 s = a'+b'：

随便写一点证明：

• 我们观察到，c+d+2*e-s+1+\max(0,\min(c,d)-(c+d+e-s+1))+[a>b][c>d]+[a<b][c<d] \ge c+d+2*e-s+1+\min(c,d)-(c+d+e-s+1)+[a>b][c>d]+[a<b][c<d] = \min(c,d)+e+[a>b][c>d]+[a<b][c<d]，也就是说这个上界实际上是无效的。
• 后面的上界分析应该是平凡的，此处略去。

写的不是很具体，放个代码：

::::info[代码]

#include <bits/stdc++.h>
#define Debug(fmt, args...) fprintf(stderr, "(func %s, line #%d): " fmt, __func__, __LINE__, ##args), fflush(stderr)
#define debug(fmt, args...) fprintf(stderr, fmt, ##args), fflush(stderr)
#define ll long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<ll, ll>
#define mp make_pair
#define pb push_back 
#define eb emplace_back
#define ld lower_bound
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define drep(i, a, b) for (int i = (a); i >= (b); i--)
#define U(i, a, b) for (int i = (a); i < (b); i++)
#define ud upper_bound
#define mem(s, k) memset(s, k, sizeof(s))
#define fi first
#define se second
#define ull unsigned long long
#define vi vector <ll>
#define fv inline void
#define fn inline static
#define sz(x) (i32)(x.size())
#define bp(x) __builtin_popcount(x)
using u8 = unsigned char; using u16 = unsigned short; using u32 = unsigned; using u64 = unsigned ll; using u128 = __uint128_t;
using i16 = short; using i32 = ll; using i64 = ll; using i128 = __int128_t; using db = long double;
using namespace std;
const i32 N = 1e5 + 5;
bool vis[N];
fn bool check(i32 a, i32 b, i32 c, i32 d, i32 e) {
  if (a < 0 || b < 0 || c < 0 || d < 0 || e < 0) return 0;
  i32 t = max({a, b, c, d, e}), n = a + b + c + d + e;
  if (t > n - t + 1) return 0;
  return 1;
}
i32 Ans;
bool type = 0;
i32 _[10] = {};
i32 to[512], revflg;
char c[] = {'.', 'L', 'R', 'l', 'r', 'M'};
fn i32 count(string s) {
//  cerr << s << ":\n";
  if (revflg) {
    reverse(s.begin(), s.end());
    for (char &c : s) {
      if (c == 'L') c = 'R';
      else if (c == 'R') c = 'L';
      else if (c == 'l') c = 'r';
      else if (c == 'r') c = 'l';
    }
  }
//  cerr << s << " :\n";
  i32 m = s.size(); s = " " + s;
  rep (i, 1, m) vis[i] = 0;
  rep (i, 1, m) _[to[s[i]]]--;
//  cerr << "\n";
//  rep (i, 1, 5) cerr << _[i] << " ";
//  cerr << "\n";
  rep (i, 1, 5) if (_[i] != 0) assert(0);
  rep (i, 1, m) {
    assert(s[i] != s[i + 1]);
    if (s[i + 1] == 'l' || s[i - 1] == 'r') continue;
    if (s[i] == 'R') vis[i + 1] = 1;
    if (s[i] == 'L') vis[i - 1] = 1;
  }
  i32 cnt = 0;
  rep (i, 1, m) cnt += vis[i];
//  cerr << Ans << " - " << cnt << " - " << s << "\n";
  assert(Ans == -1 || cnt == Ans);
  cout << cnt << "\n";
  if (type) {
    rep (i, 1, m) cout << s[i];
    cout << "\n";
  }
  return cnt;
}
fn string get(i32 lst, i32* s) {
//  cerr << "get " << lst << " " << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << s[5] << "\n";
  string S;
  if (s[1] + s[2] + s[3] + s[4] + s[5] == 0) return "";
  s[0] = -1;
  while (1) {
    i32 p = 0;
    rep (i, 1, 5) if (i != lst && s[i] > s[p]) p = i;
    s[p]--;
    if (!check(s[1], s[2], s[3], s[4], s[5])) assert(0);
    S += c[p], lst = p;
//    cerr << lst << " -\n";
    if (s[1] + s[2] + s[3] + s[4] + s[5] == 0) break;
  }
  return S;
}
i32 s[10];
fn string get1(i32 *s) { 
  i32 p = 0, pre = -1; string S;
  i32 cnt = 0;
  rep (i, 1, 5) cnt += (s[i] > 0);
  rep (i, 1, 5) if (s[i] > s[p]) p = i;
  if ((p == 1 || p == 2) && cnt > 2) {
    //R: (r R l R), L : (l R r R)
    if (p == 2) {
//      cerr << "+++\n";
      S = "R"; bool flg = 0;
      if (s[4]) s[2]--, s[4]--, flg = 1;
      while (s[3] && s[4]) s[3]--, s[4]--, S += "rRlR";
      drep (i, 5, 1) {
        if (i == p) continue;
        while (s[i]) s[i]--, S += c[i], S += "R";
      }
      if (flg) S += "rR";
    } else {
      S = "L";
      while (s[3] && s[4]) s[3]--, s[4]--, S += "rLlL";
      rep (i, 1, 5) {
        if (i == p) continue;
        while (s[i]) s[i]--, S += c[i], S += "L";
      }
    }
  } else {
    S += c[p];
    rep (i, 1, s[p] - 1) {
      rep (j, 1, 5) if (j != p && s[j]) {
        S += c[j], s[j]--; break; 
      }
      S += c[p];
    }
    s[p] = 0;
  } 
//  cerr << S << "\n";
  return S;
}
fn i32 query(i32 a, i32 b, i32 c, i32 d, i32 e) {
  if (!check(a, b, c, d, e)) return -1;
  i32 t = abs(a - b);
  i32 aa = a, bb = b;
  i32 L = 0, R = min(a, b), Ans = 0;
  while (L <= R) {
    i32 mid = (L + R) >> 1;
    if (check(a - mid, b - mid, c, d, e)) Ans = mid, L = mid + 1;
    else R = mid - 1;
  }
  aa = a - Ans, bb = b - Ans;
  i32 w = 1e16, res = (a - aa) * 2;
  if (!aa || !bb) {
    i32 a = aa + bb;
    w = min({w, a, min(c, d) + e + (aa > bb) * (c > d) + (aa < bb) * (c < d), c + d + 2 * e - a + 1 + max(0ll, min(c, d) - (c + d + e - a + 1)) + (aa > bb) * (c > d) + (aa < bb) * (c < d)});
    w = min({w, a + d + e + 1 - c, a + c + e + 1 - d});
  } else {
    w = min({aa + bb, aa + bb + d + e - c + 1, aa + bb + c + e - d + 1});
  }
  w += res;
  return w;
}
fv sol() {
  Ans = -1;
  to['L'] = 1, to['R'] = 2, to['l'] = 3, to['r'] = 4, to['M'] = 5;
  revflg = 0;
  rep (i, 1, 5) s[i] = 0;
  cin >> type >> s[1] >> s[2] >> s[3] >> s[4] >> s[5];
  if (type == 0) return cout << query(s[1], s[2], s[3], s[4], s[5]) << "\n", void();
  rep (i, 1, 5) _[i] = s[i];
  if (s[1] > s[2]) {
    swap(s[1], s[2]), swap(s[3], s[4]);
    revflg = 1;
  }
//  cerr << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << s[5] << "\n";
  i32 mx = max({s[1], s[2], s[3], s[4], s[5]}), n = s[1] + s[2] + s[3] + s[4] + s[5];
//  cerr << mx << " - " << n << "\n";
  if (mx * 2 - 1 > n) return cout << "-1\n", void();
  if (mx * 2 - 1 == n) return count(get1(s)), void();

  string S;
  while (check(s[1] - 1, s[2] - 1, s[3], s[4], s[5])) s[1]--, s[2]--, S += "RL";
//  cerr << s[1] << " + " << s[2] << " + " << s[3] << " + " << s[4] << " + " << s[5] << "\n";
  if (!s[1] || !s[2]) {
    if (!s[1]) {
      i32 mx = max({s[1], s[2], s[3], s[4], s[5]}), n = s[1] + s[2] + s[3] + s[4] + s[5];
      if (mx * 2 == n + 1 && (mx == s[2] || mx == s[5])) return count(S + get1(s)), void();
      i32 w1 = s[2];
      i32 w2 = min(s[3], s[4]) + s[5] + (_[1] < _[2]) * (_[3] < _[4]) + (_[1] > _[2]) * (_[3] > _[4]);
      i32 w3 = s[3] + s[4] + s[5] * 2 - s[2] + 1 + max(0ll, min(s[3], s[4]) - (s[3] + s[4] + s[5] - s[2] + 1)) + (_[1] < _[2]) * (_[3] < _[4]) + (_[1] > _[2]) * (_[3] > _[4]);
      i32 w4 = s[2] + s[4] + s[5] + 1 - s[3], w5 = s[2] + s[3] + s[5] + 1 - s[4];
      i32 ans = min({w1, w2, w3, w4, w5});
//        cerr << w1 << " - " << w2 << " - " << w3 << " - " << w4 << " - " << w5 << "\n";
      Ans = ans + (!revflg ? (_[1] - s[1]) * 2 : (_[1] - s[2]) * 2);
      if (ans == w4) { // l is numerous
        string _S = "";
//          S = "l" + S, s[3]--;
        while (check(s[1], s[2] - 1, s[3] - 1, s[4] - 1, s[5])) _S += "lRr", s[2]--, s[3]--, s[4]--;
        while (check(s[1], s[2] - 1, s[3] - 1, s[4], s[5] - 1)) _S += "lRM", s[2]--, s[3]--, s[5]--;
//          S = _S + S;
        return count(_S + get(to[_S.back()], s) + S), void();
      } else if (ans == w5) { // r is numerous
        string _S = "";
//          S = "l" + S, s[3]--;
        while (check(s[1], s[2] - 1, s[3] - 1, s[4] - 1, s[5])) S += "Rrl", s[2]--, s[3]--, s[4]--;
        while (check(s[1], s[2] - 1, s[3], s[4] - 1, s[5] - 1)) S += "RrM", s[2]--, s[4]--, s[5]--;
//          cerr << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << s[5] << "\n";
        return count(S + get(to[S.back()], s)), void();
      } else if (ans == w3) { // b >= max(c, d) + e + 1
//        if (s[3] > s[4]) S += "l", s[3]--;
        while (1) {
          if (check(s[1], s[2] - 1, s[3], s[4], s[5] - 1)) S += "RM", s[2]--, s[5]--;
          else if (check(s[1], s[2] - 1, s[3] - 1, s[4] - 1, s[5])) S += "Rrl", s[2]--, s[3]--, s[4]--;
          else break;
        }
//        cerr << s[1] << " - " << s[2] << " - " << s[3] << " - " << s[4] << " - " << s[5] << "\n";
        return count(S + get1(s)), void();
//        RlRr
//        return ;
      } else if (ans == w2) {
        if (s[3] > s[4]) S = "l" + S, s[3]--;
        while (1) {
          if (check(s[1], s[2] - 1, s[3] - 1, s[4], s[5] - 1) || check(s[1], s[2] - 1, s[3], s[4] - 1, s[5] - 1)) {
            if (s[2] > s[3] && s[2] > s[4]) S += "RM", s[2]--, s[5]--;
            else if (s[3] > s[4]) S += "RMl", s[2]--, s[3]--, s[5]--;
            else S += "RrM", s[2]--, s[4]--, s[5]--;
          } else if (check(s[1], s[2] - 1, s[3] - 1, s[4] - 1, s[5])) S += "Rrl", s[2]--, s[3]--, s[4]--;
          else break;
        }
//        cerr << S << " --\n";
//        if ((S.back() == 'L' || S.back() == 'R') && s[5] && check(s[1], s[2], s[3], s[4], s[5] - 1)) S = S + "M", s[5]--;
        return count(S + get(to[S.back()], s)), void();
//        assert(0);
        return ;
      } else if (ans == w1) {
        while (s[2]) {
//            cerr << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << s[5] << "---\n";
          i32 mx = max({s[2], s[3], s[4], s[5]});
          if (mx == s[2]) {
            if (s[5]) S += "RM", s[2]--, s[5]--;
            else if (s[3] && s[4]) S += "Rrl", s[2]--, s[3]--, s[4]--;
            else S += "Rr", s[2]--, s[4]--;
          }
          else if (mx == s[5]) S += "RM", s[2]--, s[5]--;
          else if (mx == s[3]) {
            if (s[4]) S += "Rrl", s[2]--, s[3]--, s[4]--;
            else S += "RMl", s[2]--, s[3]--, s[5]--;
          } else if (mx == s[4]) {
            if (s[3]) S += "Rrl", s[2]--, s[3]--, s[4]--;
            else S += "RrM", s[2]--, s[4]--, s[5]--;
          }
//          cerr << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << s[5] << "---\n";
        }
//        cerr << S << "\n";
        if (S.back() == 'L' && s[4] && check(s[1], s[2], s[3], s[4] - 1, s[5])) S = S + "r", s[4]--;
        else if (S.back() == 'L' && check(s[1], s[2], s[3], s[4], s[5] - 1)) S = S + "M", s[5]--;
        if (S.back() == 'l' && s[3] && check(s[1], s[2], s[3] - 1, s[4], s[5])) S = "l" + S, s[3]--;
//        cerr << S << " --\n";
        return count(S + get(to[S.back()], s)), void();
      } else assert(0);
    } else assert(0);
  } else {
//    cerr << " +++\n";
    Ans = (!revflg ? (_[1] - s[1]) * 2 : (_[1] - s[2]) * 2);
//    cerr << s[1] << " - " << s[2] << " - " << s[3] << " - " << s[4] << " - " << s[5] << " " << S << "\n"; 
    Ans += min({s[1] + s[2], s[1] + s[2] + s[3] + s[5] - s[4] + 1, s[1] + s[2] + s[5] + s[4] - s[3] + 1});
//    cerr << Ans << "\n";
//    cerr << s[1] + s[2] << " " << s[1] + s[2] + s[3] + s[5] - s[4] + 1 << " " << s[1] + s[2] + s[3] + s[4] - s[5] + 1 << "\n";
    i32 mx = max({s[1], s[2], s[3], s[4], s[5]}), n = s[1] + s[2] + s[3] + s[4] + s[5];
    assert(mx * 2 >= n);
    if (mx * 2 == n + 1) {
      if (mx == s[3]) return count(get1(s) + S), void();
      if (mx == s[4]) return count(S + get1(s)), void();
      return count(S + get1(s)), void();
    } else {
//      cerr << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << s[5] << "\n";
      if (mx == s[3] || mx == s[4]) {
        if (mx == s[3]) { // l
          s[1]--;
          return count(get1(s) + "L" + S), void(); 
        }
        if (mx == s[4]) { // r
          s[2]--;
          return count(S + "R" + get1(s)), void();
        }
      } else {
        if (!s[3] && !s[4]) {
          S += "M", s[5]--;
          while (s[2] > 1) s[2]--, s[5]--, S += "RM";
          S += "RLM", s[5]--, s[1]--, s[2]--;
          while (s[1] > 1) s[1]--, s[5]--, S += "LM";
        }
        while (s[2]) s[2]--, s[5]--, S += "RM";
        while (s[3]) s[3]--, s[5]--, S += "lM";
        while (s[4]) s[4]--, s[5]--, S += "rM";
        while (s[1]) s[1]--, s[5]--, S += "LM";
//        cerr << S << "\n";
        return count(S), void();
      }
    }
  }
} 
/*
1
1 2 10 2 4 1
*/
int main() {
//  freopen("3-1.in", "r", stdin);
//  freopen("test.out", "w", stdout);
  IOS;
  i32 T; cin >> T;
  while (T--) sol();
}

::::