ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

2248A　You Delete, I Delete

来源：Codeforces ★ 800

本题活力0.23按难度、完成结果与训练证据估算

算法如山行则将至

查看原题王梓豪 的主页

题目描述

Alice and Bob are given a binary string∗
s
of length n
. It contains at least one 0
and at least one 1
.

They each perform exactly one operation in the following order:

First, Alice chooses an occurrence of 0
in s
and deletes it.
Then, Bob chooses an occurrence of 1
in the resulting string and deletes it.
Alice wants the final string to be lexicographically†
as large as possible, while Bob wants it to be lexicographically as small as possible. Determine the final string if both players act optimally.

代码

#include <bits/stdc++.h>
using namespace std;
void solve(string s)
{
for(int i=0;i<s.size();i++)
{
    if(s[i]=='0'){s.erase(s.begin()+i);break;}
}
for(int i=0;i<s.size();i++)
{
    if(s[i]=='1'){s.erase(s.begin()+i);break;}
}
cout<<s<<endl;
}
int main() {
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        solve(s);
    }
}