本文共 3231 字，大约阅读时间需要 10 分钟。

3分钟过A

然后莫名其妙开了C，RE了一发，T了一发

回头做B，40分钟搞定

再看CD，毫无进展，一直在T。。。

挂了

A. Red and Blue Beans

题意：

有一堆红蓝豆，分成一些堆，让每一堆内数量差不超过d，问可不可行（数据int范围）

思路：

1. 如果两种颜色剩余数量一样，无论d大小，显然可以
2. 显然数量少的豆子（记为A）要“照顾”数量多的颜色（记为B）

即：每A的每个豆子最多配d+1个B类豆子

所以，B≤(d+1)*A即为可行

记得开longlong

时间复杂度：

O(T)

参考代码：

#include<bits/stdc++.h>using namespace std;int t,n,m;int main(){	scanf("%d",&t);	while(t--){		int a,b,c;		scanf("%d%d%d",&a,&b,&c);		int minn=min(a,b),maxx=max(a,b);		if((long long)minn*(c+1)<maxx) printf("No\n");		else printf("Yes\n");	}}

题意：

从(x,y)走到(x,y+1)需要花费x，走到(x+1,y)需要花费y，从(1,1)走到(n,m)能否花费恰好为k(n,m≤100,k≤10000)

思路：

• 开始手算一波，最后打表走一波，发现不管怎么走，代价都是一样的（上表为最大值，下表为最小值）

• 下证结论，如图所示，从左上开始，由于只能向右下方向走，所以每一步的成本都相同，或者现在，或者将来，都会体现

例如(1,1)->(1,2)->(1,3)->(2,3)，花费1+1+3

(1,1)->(1,2)->(2,2)->(2,3)，花费1+2+2，都是5

所以先进行预处理，计算到达每一点的代价，直接判断即可

时间复杂度：

O(10000+T)

参考代码：

#include<bits/stdc++.h>using namespace std;int t,n,m,k,f[110][110]; void ini(){	for(int i=1;i<=100;i++) {		for(int j=1;j<=100;j++){			if(i!=1)f[i][j]=f[i-1][j]+j;			else if(j!=1)f[i][j]=f[i][j-1]+i;		} 	}} int main(){	scanf("%d",&t);	ini();	while(t--){		scanf("%d%d%d",&n,&m,&k);		printf("%s\n",(k==f[n][m])?"Yes":"No");	}}

C. Berland Regional

题意：

有n位学生参加比赛，每位学生有属于的大学，和实力值，对于每个i≤n，求出如果i人才能一队，总实力值最大值

思路：

• 每所学校都要派出实力最强的成员参赛，做完前缀和暴力统计即可（数据可能卡常，比赛T了）
• 如果有x人的学校y人一队，实力值就是即可

时间复杂度：

O(T*n*logn)

参考代码：

#pragma GCC optimize(3)#pragma GCC optimize(2)#pragma GCC optimize("Ofast")#pragma GCC target("avx,avx2,fma")#pragma GCC optimization("unroll-loops")#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>#include<cmath>#include<map>#include<vector>#include<queue>#include<stack>#define max(a,b) (a>b?a:b)using namespace std;int t,n,id[200010],sz[200010];vector<long long> v[200010];bool cmp(int a,int b){	return a>b;} int main(){	scanf("%d",&t)	while(t--){		int mx=0;		scanf("%d",&n)		for(register int i=1;i<=n;i++) id[i]=read(),mx=max(mx,id[i]);		for(register int i=1;i<=n;i++){			int x;scanf("%d",&x);			v[id[i]].push_back(x);		}		for(register int i=1;i<=mx;i++) sz[i]=v[i].size();		long long ans[n+10]={0};		for(register int i=1;i<=mx;i++){			if(v[i].size()==0) continue;			sort(v[i].begin(),v[i].end(),cmp);			for(register int j=1,z=sz[i];j<z;j++) v[i][j]+=v[i][j-1]; 			for(int j=1;j<=sz[i];j++){				ans[j]+=v[i][sz[i]/j*j-1];			}		} 		for(int i=1;i<=n;i++) printf("%lld ",ans[i]);		printf("\n");		for(int i=1;i<=mx;i++) v[i].clear();	}}

D. Maximum Sum of Products

题意

长度为n的序列A和B，翻转任意一段连续区间，最大化

思路

• 不妨假设翻转[l,r]区间，那么和是
• 考虑求出f[l][r]，显然对于长度为1或2，直接求出，否则为

时间复杂度

O()

参考代码

#include<bits/stdc++.h>using namespace std;int n,a[5010],b[5010];long long pre[5010],dp[5010][5010];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d",a+i);    for(int i=1;i<=n;i++)scanf("%d",b+i);    for(int i=1;i<=n;i++)pre[i]=(long long)a[i]*b[i]+pre[i-1];    for(int len=1;len<=n;len++)    	for(int l=1;len+l-1<=n;l++){    		int r=len+l-1;    		if(len==1){    			dp[l][l]=(long long)a[l]*b[l];    		}    		else if(len==2){    			dp[l][r]=(long long)a[l]*b[r]+(long long)a[r]*b[l];    		}    		else{    			dp[l][r]=(long long)a[l]*b[r]+(long long)a[r]*b[l]+dp[l+1][r-1];    		}    	}    long long ans=pre[n];    for(int i=1;i<=n;i++)    	for(int j=1;j<i;j++)    		ans=max(ans,pre[n]-pre[i]+pre[j-1]+dp[j][i]);    printf("%lld",ans);}