题目描述

给定一个仅由0和1组成的二进制字符串 s（至少一个 0、至少一个 1）。两人依次各执行恰好一次操作：

1. Alice（先手）：选择字符串中一个0删除；目标：最终字符串字典序尽可能大
2. Bob（后手）：在 Alice 操作后的新串中，选择一个1删除；目标：最终字符串字典序尽可能小双方均采取最优策略，求博弈结束后的最终字符串。

字典序说明：二进制串比较，从左到右第一个不同位置，1 > 0。例：101 > 100。

输入样例1

4 101 11001 0010 0101010000010100100101

输出样例1

1 101 00 01010000010100100101

样例1解释

在第 $1$ 个测试用例中，Alice必须删除唯一的 $\mathtt{0}$ 。Bob可以删除 $\mathtt{1}$ 中的任意一次，因此得到的字符串是 $\mathtt{1}$ 。

在第 $2$ 个测试用例中，Alice可以删除 $\mathtt{0}$ 中的任意一个。Bob会以最佳方式删除 $\mathtt{1}$ 的前两次出现中的一次，因此得到的字符串是 $\mathtt{101}$ 。

在第 $3$ 个测试用例中，Alice可以删除 $\mathtt{0}$ 的任何出现次数。然后，Bob删除了 $\mathtt{1}$ 的唯一一次出现，因此得到的字符串是 $\mathtt{00}$ 。

解题思路

博弈核心思想：Minimax（极小极大算法）

这道题是典型双人零和完全信息博弈，完美对应极小极大模型：

• Alice 是MAX 方：在所有可行方案里，追求结果最大；
• Bob 是MIN 方：在给定局面下，追求结果最小。

推演流程（暴力模拟思路，数据范围很小，无需数学结论）：

1. 枚举 Alice所有合法操作：遍历原串每一个下标，如果该位置字符是'0'，模拟删掉它，得到中间串 sa。
2. 针对每一个中间串 sa，模拟 Bob 的最优决策： 枚举 sa 中所有'1'，逐个删除得到候选结果；Bob 会从中挑选字典序最小的字符串，作为本轮 Alice 选择对应的最终结果。
3. Alice 预知 Bob 的最优反击，因此在所有 “Bob 反击后的结果” 中，选出字典序最大的字符串，就是全局答案。

一句话概括：Alice 预判 Bob 会怎么坑自己，再挑选对自己最有利的选择。

完整代码

#include<bits/stdc++.h> #define fr1(i,a,b) for(int (i)=(a);(i)<=(b);++(i)) #define fr2(i,a,b) for(int (i)=(a);(i)>=(b);--(i)) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pair<int,int> #define pll pair<ll,ll> #define _1st first #define _2nd second #define y1 yy1 #define elif else if #define debug cout<<endl<<"-------------------------------------------------------------"<<endl using namespace std; string del(string str,int pos){ str.erase(pos,1); return str; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int t; cin>>t; while(t--){ string s; cin>>s; string ans=""; fr1(i,0,s.size()-1){ if(s[i]!='0')continue; string sa=del(s,i); string bob_best; bool first=1; fr1(j,0,sa.size()-1){ if(sa[j]!='1')continue; string res=del(sa,j); if(first){ bob_best=res; first=0; }else{ if(res<bob_best) bob_best=res; } } if(ans.empty()||bob_best>ans){ ans=bob_best; } } cout<<ans<<'\n'; } return 0; }