fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. char missingChar(char a, char b) {
  8.     // 对于两个不同字符 a,b 返回第三个字符
  9.     if ((a=='L' && b=='I') || (a=='I' && b=='L')) return 'T';
  10.     if ((a=='L' && b=='T') || (a=='T' && b=='L')) return 'I';
  11.     if ((a=='I' && b=='T') || (a=='T' && b=='I')) return 'L';
  12.     return '?'; // 不会出现
  13. }
  14.  
  15. bool isBalanced(const string &s) {
  16.     int cntL=0, cntI=0, cntT=0;
  17.     for(char c : s) {
  18.         if(c=='L') cntL++;
  19.         else if(c=='I') cntI++;
  20.         else if(c=='T') cntT++;
  21.     }
  22.     return (cntL==cntI && cntI==cntT);
  23. }
  24.  
  25. // 模拟函数：给定目标 k、扫描顺序参数 order:
  26. // order = 0 表示从左到右扫描，order = 1 表示从右到左扫描。
  27. // 若能完成恰好 m = 3*k - n 次操作且最终平衡，则返回操作序列；否则返回空序列表示失败。
  28. vector<int> simulate(int k, const string &s_init, int n, int order) {
  29.     // 计算初始计数
  30.     int cntL=0, cntI=0, cntT=0;
  31.     for(char c : s_init) {
  32.         if(c=='L') cntL++;
  33.         else if(c=='I') cntI++;
  34.         else if(c=='T') cntT++;
  35.     }
  36.     int dL = k - cntL, dI = k - cntI, dT = k - cntT;
  37.     int m = 3*k - n;
  38.     string s = s_init;
  39.     vector<int> ops; // 记录操作，下标为当前状态下插入位置（1-indexed）
  40.  
  41.     // 模拟最多 m 次操作
  42.     while((int)ops.size() < m) {
  43.         bool inserted = false;
  44.         if(order==0) { // 从左到右扫描
  45.             for (int i = 0; i < (int)s.size()-1; i++) {
  46.                 if(s[i] == s[i+1]) continue;
  47.                 char x = missingChar(s[i], s[i+1]);
  48.                 // 若该字母还需要插入，则在此位置插入
  49.                 if((x=='L' && dL>0) || (x=='I' && dI>0) || (x=='T' && dT>0)) {
  50.                     ops.push_back(i+1); // 输出 1-indexed位置，即在 s[i] 与 s[i+1] 间插入
  51.                     s.insert(s.begin() + i + 1, x);
  52.                     if(x=='L') dL--;
  53.                     else if(x=='I') dI--;
  54.                     else if(x=='T') dT--;
  55.                     inserted = true;
  56.                     break; // 进行一次操作后重头扫描
  57.                 }
  58.             }
  59.         } else { // 从右到左扫描
  60.             for (int i = s.size()-2; i >= 0; i--) {
  61.                 if(s[i] == s[i+1]) continue;
  62.                 char x = missingChar(s[i], s[i+1]);
  63.                 if((x=='L' && dL>0) || (x=='I' && dI>0) || (x=='T' && dT>0)) {
  64.                     ops.push_back(i+1);
  65.                     s.insert(s.begin() + i + 1, x);
  66.                     if(x=='L') dL--;
  67.                     else if(x=='I') dI--;
  68.                     else if(x=='T') dT--;
  69.                     inserted = true;
  70.                     break;
  71.                 }
  72.             }
  73.         }
  74.         if(!inserted) break;
  75.     }
  76.     // 检查是否完成 m 次操作且最终串平衡
  77.     if((int)ops.size() == m && isBalanced(s)) return ops;
  78.     return vector<int>(); // 返回空表示失败
  79. }
  80.  
  81. int main(){
  82.     ios::sync_with_stdio(false);
  83.     cin.tie(nullptr);
  84.  
  85.     int t;
  86.     cin >> t;
  87.     while(t--){
  88.         int n;
  89.         cin >> n;
  90.         string s;
  91.         cin >> s;
  92.         // 统计初始各字母个数
  93.         int cntL=0, cntI=0, cntT=0;
  94.         for(char c: s){
  95.             if(c=='L') cntL++;
  96.             else if(c=='I') cntI++;
  97.             else if(c=='T') cntT++;
  98.         }
  99.         // 若初始串已平衡，直接输出 0
  100.         if(cntL==cntI && cntI==cntT){
  101.             cout << 0 << "\n";
  102.             continue;
  103.         }
  104.         bool solved = false;
  105.         vector<int> ansOps;
  106.         // 枚举目标 k，从 max(c_L, c_I, c_T) 到 n
  107.         int startK = max({cntL, cntI, cntT});
  108.         for (int k = startK; k <= n; k++){
  109.             int m = 3*k - n;
  110.             if(m > 2*n) continue; // 超过操作限制
  111.             // 尝试两种扫描顺序
  112.             vector<int> ops = simulate(k, s, n, 0);
  113.             if(ops.empty()) ops = simulate(k, s, n, 1);
  114.             if(!ops.empty()){
  115.                 ansOps = ops;
  116.                 solved = true;
  117.                 break;
  118.             }
  119.         }
  120.         if(!solved)
  121.             cout << -1 << "\n";
  122.         else {
  123.             cout << ansOps.size() << "\n";
  124.             for (int op : ansOps)
  125.                 cout << op << "\n";
  126.         }
  127.     }
  128.  
  129.     return 0;
  130. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
5
TILII
1
L
3
LIT
stdout
copy 
4
1
2
3
4
-1
0
https://ideone.com/0mSDnZ
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!