Codeforce-1005

codeforces round 1005(Div.2)

https://codeforces.com/contest/2064

https://codeforces.com/blog/entry/138912

A

采用模拟，a字符串从头遍历，找到第一个1，它和其后的字符串删除增加到b字符串后面；b数组从头遍历，找到第一个0；

应该使用数组比较简单；条件怎么判断

请注意，如果字符串 s 以字符 1 开头，那么在某个时刻，整个字符串 s 必须被移动到字符串 t 中。同时，如果执行操作，那么在两个字符串中，”01” 和 “10” 的出现次数最多只能减少一次。这给出了答案的上界，即 s 中 “01” 和 “10” 的出现次数，如果 s 以字符 1 开头，则在此基础上加 1。

接下来，以下构造方式使用的操作次数与上述上界相同（从而证明了这就是最小操作次数）：如果 s 以字符 1 开头，那么选择整个字符串 s 并将其移动到 t 中。然后，反复查找 s 或 t 中第一个与前一个字符不同的字符（注意在这种构造中，这样的索引一次只能存在于一个字符串中），并选择从这个字符开始的后缀，并将其移动到另一个字符串中。在这个构造过程中，s 的某个前缀将包含字符 0，而 t 的某个前缀将包含字符 1，因此每次移动后，”01” 和 “10” 的总数都会减少。

因此，这个问题的答案就是 s 中 “01” 和 “10” 的出现次数，如果 s 以字符 1 开头，则在此基础上加 1

#include<bits/stdc++.h>
using namespace std;\

void solve()
{
	int n;cin>>n;
	string s;cin>>s;
	int ans=0;
	if(s[0]=='1') ans++;
	for(int i=0;i<n-1;i++)
	{
		if(s[i]!=s[i+1])
		ans++;
	}
	cout<<ans<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;cin>>tt;
	while(tt--)
	{
		solve();
	}
	return 0;
}

B

删除子数组使得相同数字尽可能多；条件怎么设置，没有思路

只删除一个数字，个数减1而不重复数字最多减1，不会使分数增加。所以要使分数增加，删除最长的不重复数字组成的子数组。

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n;cin>>n;
	
	vector<int> a(n);//存储数组
	vector<int> cnt(n);//存储每个数字的出现次数
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		a[i]--;//因为从数组下标0开始，数组数字范围为[1,n]，所以每个数字减1
		cnt[a[i]]++;
	}
	
	int l=0,r=0;
	int len=0;
	for(int i=0;i<n;i++)
	{
		if(cnt[a[i]]>1)
		{
			len=0;//遍历数组，遇到重复就清空len
		}
		else
		{
			len++;
		}
		if(len>r-l)//如果当前子数组长度比之前找到的最大子数组长度大，更新子数组边界
		{
			r=i+1;
			l=i+1-len;
		}
	}
	
	if(l==r)
	{
		cout<<0<<'\n';
	}
	else
	{
		cout<<l+1<<' '<<r<<'\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;cin>>tt;
	while(tt--)
	{
		solve();
	}
	return 0;
}

C

ai小于0删除后缀，大于0删除前缀

如果数组左边都是大于0的数，右边都是小于0的数，很好处理

但是左边小于0，右边大于0呢

进一步，分布没有规律，分成好多子数组怎么办

首先，要注意在任何情况下，我们应该要么移除最左边的正数，要么移除最右边的负数。因为如果我们选择一个不是最左边的正数，那么我们本可以先选择最左边的正数，从而获得更高的分数。对于选择最右边的负数，也有类似的论证。

现在，如果你执行这些操作若干次，你最终总是会取走一些正数的前缀，然后是剩余的负数的后缀。因此，为了计算答案，我们只需要检查所有 n+1 种将数组分割成前缀和后缀的方式，并取其中的最大值，这可以在 O(n) 时间内轻松完成。

遍历，计算前缀和和后缀和，相加即为当前位置的分数，选出最大值。

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n;cin>>n;
	
	vector<int>a(n);//存储数组
	for(int i=0;i<n;i++) cin>>a[i];
	
	vector<long long>pre(n),suf(n);//分别存储前缀和数组，后缀和数组
	
	if(a[0]>0) pre[0]=a[0];//求前缀和数组
	for(int i=1;i<n;i++)
	{
		pre[i]=pre[i-1];
		if(a[i]>0) pre[i]+=a[i];
	}
	
	if(a[n-1]<0) suf[n-1]=-a[n-1];//求后缀和数组
	for(int i=n-2;i>=0;i--)
	{
		suf[i]=suf[i+1];
		if(a[i]<0) suf[i]-=a[i];
	}
	
	long long ans=0;
	for(int i=0;i<n;i++)//遍历寻找最大分数
	{
		ans=max(ans,pre[i]+suf[i]);
	}
	cout<<ans<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;cin>>tt;
	while(tt--)
	{
		solve();
	}
	return 0;
}

蒋大佬的代码：

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n;cin>>n;
	
	vector<int>a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	
	long long suf=0;//存储后缀和
	long long pre=0;//存储前缀和
	for(int i=0;i<n;i++)
	{
		if(a[i]<0)
		{
			suf+=a[i];//所有负数的和
		}
	}
	long long ans=-suf;//初始情况下，假设所有负数都被移除
	
	for(int i=0;i<n;i++)//动态计算前缀和 后缀和
	{
		if(a[i]<0)
		{
			suf-=a[i];//剩余负数的和
		}
		else 
		{
			pre+=a[i];//正数前缀和
		}
		ans=max(ans,pre-suf);
	}
	cout<<ans<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;cin>>tt;
	while(tt--)
	{
		solve();
	}
	return 0;
}

D

看起来很简单，只需要从后往前尝试遍历即可；忘记异或怎么操作了