Educational Codeforces Round 93 (Rated for Div. 2) B. Substring Removal Game

「爱情、让人受尽委屈。」 2024-04-01 16:53 67阅读 0赞

[Problem - B - Codeforces][]

题意：

给定一个01串，Alice和Bob玩游戏，对于每一个玩家，都能取走连续的数值相同的串，贡献为取走的串的1的个数，问赢家最多的贡献是多少

思路：

基于贪心的博弈，把它当作贪心做就好了

贪心的话考虑贡献，贡献为取走的串的1的个数，极端地考虑：对于每个玩家，取走1个数最多的串。事实上就是这么做的

如果取走0串，则贡献为0，取走1串后也只是给两端的0合并，对贡献无影响，因此策略成立

写的时候双指针模拟一下就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e5+10,mnf=0x3f3f3f3f,inf=0xc0c0c0c0;
    string s;
    vector<int> v;
    int n;
    bool cmp(int x,int y){
    	return x>y;
    }
    void solve(){
    	v.clear();
    	s.clear();
    	cin>>s;
    	n=s.size();
    	s=" "+s;
    	int l=1,r=1;
    	int ans=inf;
    	while(1){
    		if(l>n||r>n) break;
    		while(l<=n&&s[l]=='0') l++;
    		r=l;
    		while(r<=n&&s[r]=='1') r++;
    		r--;
    		v.push_back(r-l+1);
    		l=r+1;
    	}
    	sort(v.begin(),v.end(),cmp);
    	int res=0;
    	for(int i=0;i<v.size();i+=2) res+=v[i];
    	cout<<res<<'\n';
    }
    int main(){
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int T;
    	cin>>T;
    	while(T--)solve();
    	return 0;
    }

**总结：**

**基于贪心的博弈，把它当作贪心做**

[Problem - B - Codeforces]: https://codeforces.com/contest/1398/problem/B