Educational杀我，不要在意排名和过题人数呀，还是得从问题本质上去挖掘一些性质的，从集合角度考虑问题，从无到有的构造，从有到无的构造

A. Bad Triangle

题意：
十分裸露给定n个数，问是否能找出三个数使他们组成不了三角形。

思路：
三角形性质：任意两边和大于第三边，既然组成不了那就找临界值去构造就好了
排序后看看前两个元素是否大于最大的元素即可。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int a[N];

int main()
{
	int T;
	cin>>T;
	while(T--)	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
		}
		int f=0;
		if(a[1]+a[2]>a[n]) puts("-1");
		else cout<<1<<' '<<2<<' '<<n<<'\n';
	}
	return 0;
}  

B. Substring Removal Game

题意：
很容易理解的，给定一个字符串只包含01，一次操作中，你可以选择连续相等的字符并且删掉他们，两个人交替执行，问第一个人能获得的最大一的个数是多少。

思路：
扫一遍，找出连续1的个数，排序，第一个人因为是第一次取，所以每隔奇数次更新下答案，最后输出即可。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

char s[N];
int a[N];

int main()
{
	int T;
	cin>>T;
	while(T--)	{
		scanf("%s",s+1);
		
		int len=strlen(s+1);
		
		int cnt=0;
		for(int i=1;i<=len;i++) {
			int j=i;
			while(j<=len&&s[j]=='1') {
				j++;
			}
			if(j!=i) a[++cnt]=j-i;
			i=j;
		}
		
		sort(a+1,a+1+cnt,greater<int>());
		int ans=0;
		for(int i=1;i<=cnt;i+=2) 
			ans+=a[i];
		
		cout<<ans<<'\n'; 
		
	}
	return 0;
}  

C. Good SubarraysC

题意:
很简单呀，让求有多少个区间和等于区间长度的序列。

给出了一个这样的公式:

思路：
我的思路还是经过了一些变化的，数据范围1000*1e5肯定是单层循环扫了一遍或者NlgN过的，刚开始想的难道是DP？但是定义状态的时候无法进行转移呀，区间和转移的时候也是需要O(N^2)的做法吧，然后就可能是思维题了，有大佬说对公式进行一下变形：
让每个ai-1其实这和我的理解一样，但是我的出发点不是这样考虑的

顾名思义O(N)的做法无非就是差分和前缀和了，但是差分似乎不合人意，我们考虑一件事：假设一段区间和满足题意，那么这个区间和是什么样的？没错全是由1构成的，所以我们让每个数都先减去1，然后看任意两个相等之间的数，如果这个数不是0那么这一段连续的数就相当于一个1，如果是0相当于两个1，所以十分巧妙，然后我们再看看一段连续1的能组成多少种方案数：

两个方向可以进行考虑：
从公式本身，
从最后答案的形式反向思考
将集合划分的过程，将问题划分成几段不相交的部分

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

int n;
int f[N];
int a[N];
LL s[N];

int main()
{
	int T;
	cin>>T;
	while(T--) {
		
		scanf("%d",&n);
		unordered_map<int,int>mp;
		for(int i=1;i<=n;i++)
		{
			scanf("%1d",&a[i]); 
			
			//记每个数与1的差值
			a[i]-=1;
			
			//前缀和 
			s[i]=s[i-1]+a[i];
			mp[s[i]]++;
		}
		
		LL res=0;
		
		for(auto item:mp) {
			int x=item.first;
			int y=item.second;
			if(x) y--;
			res+=1LL*y*(y+1)/2; 
		} 
		cout<<res<<'\n';
	}
	return 0;
}

**写出来这个题，实数不易，虽然出了感觉很简单，但是我感觉自己思维跳转的好慢啊，推翻了几个结论以后才发现了正解。

D. Colored Rectangles

破千刀的D题，害我呀，思索了那么长时间，刚开始就感觉是DP吧，但是定义状态时候呢没多想啊，看了数据范围200 这一定是O(N^3)的解法啊，难道求传递闭包转换成图论？可是2000多人过题，不会吧，然后我试着建图，发现不满足二分图的性质吧，也没有啥和连通块有关的性质，最后该不会是个大贪心吧，后来仔细分析下不行，贪心不能得到最优解，但是还是拿堆实现了成功WA了 ，其实贪心划分的过程很完美呀，我枚举所有可能的对数就好了，最小为1最大可以由题目算出来。好了好了进入正题吧

题意：
给定三个集合R,G,B其实是三种颜色，题目背景是每个集合里的每个元素相当于一个长度，问能组成所有长方形的面积之和最大是多少，换句话来说，每次从不同的集合选两个元素，价值为他们的乘积，问最大的成绩之和是多少。

思路：
DP很好理解。
定义状态：DP[i][j][k]代表用R中的前i大的和G中的前j大和B中的前k大能构成的最大和是多少。对吧，细品就能把问题完全划分了呀，最后的答案是可能出现在200200200这么多状态中的其中一个，考虑转移：

好迷你的dp转移过程，很简单dp[i][j-1][k-1]代表当前选了G中的第j-1个元素和B中的第k-1个元素所以更新就好了 其他同理。

最后就是注意一点：！！！
这个状态转移的时候要注意一些状态是达不到的，而也不能漏掉一些状态，比如我们的i,j,k取值要从0到各自的最大值，这样才能不漏掉一些问题的解，当然还有一些状态可能无法更新到，都需要注意

#include<bits/stdc++.h>

using namespace std;

const int N=210;

typedef long long LL;

LL dp[N][N][N];
int r[N],g[N],b[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>>r[i];
	for(int i=1;i<=G;i++) cin>>g[i];
	for(int i=1;i<=B;i++) cin>>b[i];
		
	sort(r+1,r+1+R,cmp);
	sort(g+1,g+1+G,cmp);
	sort(b+1,b+1+B,cmp);	

	LL ans=0;

	memset(dp,-1,sizeof dp);
	dp[0][0][0]=0;

	for(int i=0;i<=R;i++)
		for(int j=0;j<=G;j++) 
			for(int k=0;k<=B;k++) {
				if(i>=1&&j>=1&&dp[i-1][j-1][k]>=0) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+r[i]*g[j]);
				if(i>=1&&k>=1&&dp[i-1][j][k-1]>=0) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+r[i]*b[k]);
				if(j>=1&&k>=1&&dp[i][j-1][k-1]>=0) dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+g[j]*b[k]);
				ans=max(ans,dp[i][j][k]);	
			}
	cout<<ans<<'\n';
	return 0;
		
}