Educational Codeforces Round 108 (Rated for Div. 2) ABCD題解

A. Red and Blue Beans
思路：不妨假設r<b ,當b-r足夠小時，一定是輸出YES的，
只有當b-r 足夠大時，才會無解， 極端情況就是 對于每一個口袋（packet） ，只放1個red bean 和d+1個blue bean，因此當r*(d+1)<b時無解，
代碼：（注意相乘會爆int）

#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 10010;
int a[N];
int main()
{
	int T;cin>>T;
	ll n;
	ll r,b,d;
	while(T--)
	{
		cin>>r>>b>>d;
		ll mi = min(r,b),ma = max(r,b);
		if(mi*(d+1)<ma) puts("NO");
		else puts("YES");
	} 
    return 0;
}

B. The Cake Is a Lie
觀察知，無論怎么走，從(1,1) 到(n,m) 所需的花費相同，
代碼：

#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 10010;
int a[N];
int main()
{
	int T;cin>>T;
	ll n,m,k;
	ll d;
	while(T--)
	{
		cin>>n>>m>>k;
		d = n-1+(m-1)*n;
		if(d==k)
			puts("YES");
		else puts("NO");
	} 
    return 0;
}

C. Berland Regional

思路：其實暴力就可以解決，給每個隊的人按照能力排序（降序），然后記錄前綴和， 列舉k，找到每只隊伍大小距離k的倍數最近的值(例如隊伍大小是 d 使得d-=d%k 即可，這樣就滿足了d是k的倍數)，累加即可， 但是這樣的復雜度是O(n^2) 容易超時，注意到當隊伍大小d<k時就退出，因此我們可以對隊伍大小進行排序(用pair記錄隊伍人數和隊伍號) ，對隊伍人數降序排列，當d<k時直接break即可

#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 200010;
typedef pair<int,int> PII;
struct stu{
	int u,s;
}a[N];
vector<ll> re[N];
PII op[N];
int cnt[N];
int cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int T;cin>>T;
	int n,m,k;
	ll d;
	while(T--)
	{
		ll res = 0;
		scanf("%d",&n);
		memset(cnt,0,sizeof cnt);
		memset(op,0,sizeof op);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i].u);
			re[i].clear();
			cnt[a[i].u]++;
		}
		
		int now = 0;
		for(int i=1;i<=n;i++)
			 if(cnt[i]) op[++now] = {cnt[i],i};
		sort(op+1,op+1+now);
		reverse(op+1,op+1+now);
		
		
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i].s);
		
		for(int i=1;i<=n;i++)
		{
			re[a[i].u].push_back(a[i].s);
		}
		for(int i=1;i<=n;i++)
			sort(re[i].begin(),re[i].end(),cmp);
		for(int i=1;i<=n;i++)
		{
			int t = re[i].size();
			for(int j=1;j<t;j++)
				re[i][j] = re[i][j-1]+re[i][j];
		}
		//cout<<"de:"<<sum[1][2]<<endl;
		for(int k=1;k<=n;k++)
		{
			ll res = 0;
			for(int s=1;s<=now;s++)
			{
				int i = op[s].second;
				int t = re[i].size();
				if(t<k) break;
				t-=t%k;
				res+=re[i][t-1];
			}
			printf("%lld ",res);
		}
		puts("");
	} 
    return 0;
}

D. Maximum Sum of Products
裸裸的區間dp，假設f[l][r] 代表反轉l~r之間的值所形成的值 則有f[l][r] = f[l+1][r-1] - a[l]*b[l] - a[r]*b[r] + a[l]*b[r] + a[r]*b[l]

代碼

#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5010;
ll a[N],b[N];
ll f[N][N];
int main()
{
	int n;cin>>n;
	ll res = 0;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]),res+=a[i]*b[i];
	for(int i=1;i<=n;i++)
		f[i][i] = f[i][i-1] = res;
	int r;
	for(int len = 2;len<=n;len++)
	{
		for(int l = 1;l+len-1<=n;l++)
		{
			r = l+len-1;
			f[l][r] = f[l+1][r-1] - a[l]*b[l] - a[r]*b[r] + a[l]*b[r] + a[r]*b[l];
			res = max(res,f[l][r]);
		}
	}
	cout<<res;
    return 0;
}

記憶化搜索寫法

#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5010;
ll a[N],b[N];
ll f[N][N];
ll d;
ll dp(int l,int r)
{
	if(f[l][r]) return f[l][r];
	return f[l][r] = dp(l+1,r-1) - a[l]*b[l] - a[r]*b[r] + a[l]*b[r] + a[r]*b[l];
}
int main()
{
	int n;cin>>n;
	ll res = 0;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]),res += a[i]*b[i];
	for(int i=1;i<=n;i++)
		f[i][i] = f[i][i-1] = res;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			res = max(res,dp(i,j));
	cout<<res;
    return 0;
}