CF-1073-C. Sorting Game（考虑和终态不一样的点） · znzryb
## 题目大意
Alice 和 Bob 在长度为 n 的二进制字符串 s(仅包含字符 0 和 1)上进行博弈游戏。Alice 先手,双方轮流操作。
**游戏规则:**
- 每回合,玩家选择一个索引序列 i₁, i₂, ..., iₘ(严格递增),使得这些位置的字符形成**非增序列**(s[i₁] ≥ s[i₂] ≥ ... ≥ s[iₘ])
- 然后将这些位置的字符重新排列为**非减序列**(先放所有 0,再放所有 1)
- 有效移动必须**严格改变**字符串(即选中的字符中至少有一个 0 和一个 1)
- 无法进行有效移动的玩家输掉游戏
**任务:**
- 假设双方都采用最优策略,判断谁会获胜
- 如果 Alice 获胜,输出她的一个获胜首步移动(索引序列)
**输入格式:**
- 多组测试数据,第一行包含测试数据组数 t(1 ≤ t ≤ 10⁴)
- 每组数据:第一行为字符串长度 n(1 ≤ n ≤ 2×10⁵),第二行为二进制字符串 s
- 保证所有测试用例的 n 之和不超过 2×10⁵
**输出格式:**
- 如果 Bob 获胜,输出 "Bob"
- 如果 Alice 获胜,输出三行:第一行 "Alice",第二行整数 m(选中的索引数量),第三行 m 个递增的索引
**样例说明:**
- 样例 1(000):字符串已经有序,无法进行任何有效移动,Bob 直接获胜
- 样例 3(10):Alice 可以选择位置 [1,2],将字符串变为 01,之后 Bob 无法移动,Alice 获胜
## 思路讲解
其实我们会发现，**只需要一次操作即可解决这个问题**。
<!-- Notion block type: column_list -->
## AC代码
AC
[https://codeforces.com/contest/2191/submission/358351618](https://codeforces.com/contest/2191/submission/358351618)
::: 源代码
```cpp
/**
* Problem: C. Sorting Game
* Contest: Codeforces Round 1073 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2191/problem/C#
* Created: 2026-01-18 00:37:57
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
void Solve() {
ll N;
cin >> N;
string s;
cin>>s;
string sorted_str=s;
sort(all(sorted_str));
vector<ll> op_ls;
for (int i=0;i<N;++i) {
if (sorted_str[i]!=s[i]) {
op_ls.push_back(i);
}
}
if (op_ls.empty()) {
cout<<"Bob\n";
return;
}
cout<<"Alice\n";
cout<<SZ(op_ls)<<"\n";
for (auto pos:op_ls) {
cout<<pos+1<<" ";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）