欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-03 22:00:01
题目链接思路:分析可知双方每次操作一定是取连续1最多的区间消掉,贪心即可。代码:#include#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=210;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int in...

题目链接
思路:
分析可知双方每次操作一定是取连续1最多的区间消掉,贪心即可。

代码:

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=210;
const int M=2e4+5;
const double eps=1e-8;
const int mod=998244353;
const int inf=0x7fffffff;
const double pi=3.1415926;
using namespace std;
int a[100005];
signed main()
{
    IOS;
    int t;
	cin>>t;
	while (t--)
	{
		string s;
		cin>>s;
		int cnt=0,len=0;
		for (int i=0;i<s.size();i++)
		{
			if(s[i]=='1')
			{
				cnt++;
			}
			else
			{
				a[++len]=cnt;
				cnt=0;
			}
		}
		a[++len]=cnt;
		sort(a+1,a+len+1);
		int ans=0;
		for (int i=len;i>=1;i-=2)
		{
			ans+=a[i];
		}
		cout<<ans<<endl;
	}
	return 0;
}

本文地址:https://blog.csdn.net/ACkingdom/article/details/108139028

相关标签: 思维 贪心