Educational Codeforces Round 93 (Rated for Div. 2) A~D

A - Bad Triangle

 因为序列是非单调递减的，那么只需要判断序列的前两个数(最小的两个数)和序列的最后一个数(最大的一个数)能否构成三角形即可；

#include <bits/stdc++.h>
using namespace std;
int a[50005];
int main()
{
	int t;
	cin >>t;
	while(t--)
	{
		int n;
		cin >>n;
		for(int i=1;i<=n;i++) cin >>a[i];
		if(a[1]+a[2]<=a[n]) printf("1 2 %d\n",n);
		else puts("-1");
	}
}

B - Substring Removal Game

简单模拟下流程， 统计每个连续子段“1” 的长度并且记录下来，然后从大到小排序，Alice先手，每次中间隔一个子段取即可；

#include <bits/stdc++.h>
using namespace std;
int a[50005];
int main()
{
	int t;
	cin >>t;
	while(t--)
	{
		string s;
		cin >>s;
		int len=s.size();
		vector<int> p;
		for(int i=0;i<len;)
		{
			int cnt=0;
			while(s[i]=='1') cnt++,i++; 
			if(!cnt) i++;
			else p.push_back(cnt);
		}
		sort(p.begin(),p.end());
		reverse(p.begin(),p.end());
		int ans=0;
		for(int i=0;i<p.size();i++)
		{
			if(i%2==0) ans+=p[i];
		}
		cout <<ans<<endl;
	}
}

C - Good Subarrays

非常巧妙的思路： 暴力统计区间和等于区间长度肯定超时，可以把区间的每个数减一，那么区间和就变成了0；然后对序列求前缀和，并且统计每个前缀和出现多少次，如果一个前缀和出现了两次，那么说明中间出现了区间和为0的情况，也就是满足题意的情况；统计过程中记录即可；

假设一个前缀和出现了三次，那么可以构造出来两个满足题意的区间；如下图：

假设  BC  和   DE  都是区间为0的，那么BD，CE也是区间为0的，不算区间BC，一共对答案贡献了三个区间；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<int,int> mp;
int main()
{
	int t;
	cin >>t;
	while(t--)
	{
		mp.clear();
		int n;
		cin >>n;
		char c;
		ll res=0,ans=0;
		mp[0]=1;
		while(n--)
		{
			cin >>c;
			res+=c-'0'-1;
			if(mp.count(res)) ans+=(ll)mp[res];
			mp[res]++;
		}
		cout <<ans<<endl;
	}
}

 D - Colored Rectangles

这道题贪心wa到我哭了；举个反例吧：

红 ：4 4        蓝：  5       绿 ： 6 

贪心结果：5x6=30           正确结果：    4x5+4x6=44

所以可以在贪心的思想上DP枚举每一步选哪两个能获得最大值；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<int,int> mp;
const int N=220;
int rr[N],gg[N],bb[N];
int dp[N][N][N];
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	int r,g,b;
	cin >>r>>g>>b;
	for(int i=1;i<=r;i++) cin >>rr[i];
	for(int i=1;i<=g;i++) cin >>gg[i];
	for(int i=1;i<=b;i++) cin >>bb[i];
	sort(rr+1,rr+1+r,cmp); 
	sort(gg+1,gg+1+g,cmp); 
	sort(bb+1,bb+1+b,cmp); 
	int ans=0;
	for(int i=0;i<=r;i++)
	{
		for(int j=0;j<=g;j++)
		{
			for(int k=0;k<=b;k++)
			{
				int maxx=0;
				if(i&&j) maxx=max(maxx,dp[i-1][j-1][k]+rr[i]*gg[j]);
				if(i&&k) maxx=max(maxx,dp[i-1][j][k-1]+rr[i]*bb[k]);
				if(j&&k) maxx=max(maxx,dp[i][j-1][k-1]+gg[j]*bb[k]);
				dp[i][j][k]=max(maxx,dp[i][j][k]);
				ans=max(ans,dp[i][j][k]);
			}
			
		}
	}
	cout <<ans<<endl;
}