Codeforces Round #797 (Div. 3) A—E

先放个当天打完发的吐槽：

今天cf真恶心，先卡b卡几十分钟，过完然后迅速过c后又卡d，实在想不出来于是去写了e，过完e发现e过了两千人d过了七千人，灰溜溜的继续写d，结果前缀和过了，给我恶心的，幸好看见过的那么多人没想dp，不然直接寄。

A. Print a Pedestal (Codeforces logo?)

题意题解略

#include 
using namespace std;
#define ll long long 
const int maxn=1e5+7;
int main() {
    int t;cin>>t;
    while(t--){
    	int n;
		cin>>n;
		int now=n%3;
		if(now==0){
			cout<<n/3<<" "<<n/3+1<<" "<<n/3-1<<endl;
		} 
		else if(now==1){
			cout<<n/3<<" "<<n/3+1+1<<" "<<n/3-1<<endl;
		}
		else {
			cout<<n/3+1<<" "<<n/3+1+1<<" "<<n/3-1<<endl;
		}
	}
	return 0;
}

B. Array Decrements

题意：

每次 *** 作可以使全部数字-1，如果变至0则不再减少。

题解：

除了可归0的直接求差值即可，要求所有差值全部相等，归0的差值小于等于那个需要恒等的差值。

wa：卡b不是因为思路难，是我以第一个位置做差值，忘记了第一个位置是归0的情况不可作为参考。需要特判出真正的【差值】。

#include 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
int a[maxn],b[maxn];
#define sc scanf
int main() {
    int t;cin>>t;
    while(t--){
    	int n;
		cin>>n;
		for(int i=1;i<=n;i++)sc("%d",&a[i]);
		for(int i=1;i<=n;i++)sc("%d",&b[i]);
		int c=INT_MAX;
		for(int i=1;i<=n;i++){
			if(b[i]!=0)
			{
				c=a[i]-b[i];continue;
			}
			 
		}
		
		if(c<0){
			cout<<"NO"<<endl;
			continue;
		}
		else if(c==INT_MAX){
			cout<<"YES"<<endl;
			continue;
		}
		int f=1;
		for(int i=1;i<=n;i++){
			if(b[i]==0){
				if(a[i]<=c)continue;
			}
			if(a[i]-b[i]!=c){
				f=0;break;
			}
		}
		if(f)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

C. Restoring the Duration of Tasks

题意题解略

注：根据条件知道不存在上一个还没结束但是下一个已经结束，而我考虑本情况多写了一个max，删去无影响。

#include 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
int a[maxn],b[maxn];
#define sc scanf
#define pr printf
int main() {
    int t;cin>>t;
    while(t--){
    	int n;
		cin>>n;
		for(int i=1;i<=n;i++)sc("%d",&a[i]);
		for(int i=1;i<=n;i++)sc("%d",&b[i]);
		cout<<b[1]-a[1];
		for(int i=2;i<=n;i++){
			pr(" %d",max(0,b[i]-max(a[i],b[i-1])));
		}
		pr("\n");
	}
	return 0;
}

D. Black and White Stripe

题意：
选出最少染色数目使长为k的子序列为全黑。

题解：

个人思考部分：
乍一看觉得要用一些算法，但是div3（），过的人又很多。属于是又觉得是纯思维，又害怕是dp。怎么也想不出来纯思维解法，又不愿意用算法，故卡之。

其实用一下前缀和稍微优化一下直接暴力就可以了，我们直接算出所有区间长度为k的子序列—>算出所有的染色可能，取最小即可。

#include 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
int a[maxn],b[maxn];
#define sc scanf
#define pr printf
int main() {
    int t;cin>>t;
    while(t--){
    	int n,m;cin>>n>>m;
    	string s;cin>>s;
    	if(s[0]=='W')a[0]=1;
    	else a[0]=0;
    	for(int i=0;i<n;i++){
    		if(s[i]=='W')a[i]=a[i-1]+1;
    		else a[i]=a[i-1];
		}
		int mmin=a[m-1];
		for(int i=m;i<n;i++){
			mmin=min(a[i]-a[i-m],mmin);
		}
		//cout<<"ans:";
		cout<<mmin<<endl;
	}
	return 0;
}

E. Price Maximization

题意：

第一眼：题目很长还向下取整，一定是个很难的数学题吧！（个屁）

其实感觉和D差不多难度：n个数，两两相加除以k（向下取整），如何使答案最大？

题解：

把所有的‘k’先取出来。这个是一定不会被向下取整损失掉的1，全部相加存入ans。
处理剩下的数，其实也就是余数部分了，sort拍下序。双指针遍历保证最大，此部分具见代码，当有两个数相加大于k则可以ans++。
最后的ans就是答案。

没开 ll wa了一发（）

#include 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
ll a[maxn],b[maxn];
#define sc scanf
#define pr printf
int main() {
    int t;cin>>t;
    while(t--){
    	ll n,m;cin>>n>>m;
    	ll cnt=0;
    	for(int i=1;i<=n;i++){
    		sc("%lld",&a[i]);
    		if(a[i]>=m){
    			cnt+=a[i]/m;
    			a[i]%=m;
			}
		}
		sort(a+1,a+n+1);
		ll l=1,r=n;
		while(l<r){
			if(a[l]+a[r]>=m){
				cnt++;
				l++;
				r--;
			}
			else l++;
		}
		//cout<<"ans:";
		cout<<cnt<<endl;
	}
	return 0;
}