题解：Codeforces Round 1113 CF2248 A - You Delete, I Delete
题目描述
给定一个仅由0和1组成的二进制字符串 s（至少一个 0、至少一个 1）。两人依次各执行恰好一次操作：
- Alice（先手）：选择字符串中一个
0删除；目标：最终字符串字典序尽可能大 - 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 方：在给定局面下，追求结果最小。
推演流程（暴力模拟思路，数据范围很小，无需数学结论）：
- 枚举 Alice所有合法操作：遍历原串每一个下标，如果该位置字符是
'0'，模拟删掉它，得到中间串 sa。 - 针对每一个中间串 sa，模拟 Bob 的最优决策： 枚举 sa 中所有
'1'，逐个删除得到候选结果；Bob 会从中挑选字典序最小的字符串，作为本轮 Alice 选择对应的最终结果。 - 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; }