【Codeforces398A】Cards – 徐亦轲的博客

题目大意：给出两个非负整数a,b (a+b>=1)，你需要构造一个由a个o和b个x构成的序列。对于任何一个序列，我们可以算出一个分数：

初始分数为 0；

对于每一块o，设其长度为x，则分数加上x^2；

对于每一块x，设其长度为y，分数减去y^2。

要求构造出一个最大的序列。

那么我们可以发现，若把a个o分成k块，则最大的分数为1+1+1+…+(a-k+1)^2（不会证，想想就知道了）

那么要把b个x分成(k+1)块，分别插进k块o中，则要使减去的分数最小，就要使每一块的个数尽量平均。也就是每一块先有⌊b/(a-1)⌋个数，然后每一块加1直到分完。

枚举一下k，取分数最大值即可。

// <cards.cpp> - 01/02/16 08:12:15
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}

int main(){
	freopen("cards.in","r",stdin);
	freopen("cards.out","w",stdout);
	lol x=getint(),y=getint();
	if(!x){cout<<-y*y<<endl;for(int i=0;i<y;i++)cout<<'x';return 0;}
	if(!y){cout<<x*x<<endl;for(int i=0;i<x;i++)cout<<'o';return 0;}
	lol M=min(x,y),dd=0,ans=-2147483647ll;
	for(int d=1;d<=M;d++){
		lol now=0;
		now+=(d-1)+(x-d+1)*(x-d+1);
		lol l=y/(d+1),b=y%(d+1);
		now-=l*l*(d+1-b)+(l+1)*(l+1)*b;
		if(now>ans){ans=now;dd=d;}
	}
	cout<<ans<<endl;
	lol l=y/(dd+1),b=y%(dd+1);
	lol xiao=dd+1-b;bool big=0;
	for(int i=1;i<=dd;i++){
		if(xiao){xiao--;for(int i=0;i<l;i++)cout<<'x';}
		else for(int i=0;i<=l;i++)cout<<'x';
		if(!big){big=1;for(int i=0;i<x-dd+1;i++)cout<<'o';}
		else cout<<'o';
	}
	if(xiao){xiao--;for(int i=0;i<l;i++)cout<<'x';}
	else for(int i=0;i<=l;i++)cout<<'x';
	return 0;
}

// <cards.cpp> - 01/02/16 08:12:15

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

int main(){

freopen("cards.in","r",stdin);

freopen("cards.out","w",stdout);

lol x=getint(),y=getint();

if(!x){cout<<-y*y<<endl;for(int i=0;i<y;i++)cout<<'x';return 0;}

if(!y){cout<<x*x<<endl;for(int i=0;i<x;i++)cout<<'o';return 0;}

lol M=min(x,y),dd=0,ans=-2147483647ll;

for(int d=1;d<=M;d++){

lol now=0;

now+=(d-1)+(x-d+1)*(x-d+1);

lol l=y/(d+1),b=y%(d+1);

now-=l*l*(d+1-b)+(l+1)*(l+1)*b;

if(now>ans){ans=now;dd=d;}

}

cout<<ans<<endl;

lol l=y/(dd+1),b=y%(dd+1);

lol xiao=dd+1-b;bool big=0;

for(int i=1;i<=dd;i++){

if(xiao){xiao--;for(int i=0;i<l;i++)cout<<'x';}

else for(int i=0;i<=l;i++)cout<<'x';

if(!big){big=1;for(int i=0;i<x-dd+1;i++)cout<<'o';}

else cout<<'o';

}

if(xiao){xiao--;for(int i=0;i<l;i++)cout<<'x';}

else for(int i=0;i<=l;i++)cout<<'x';

return 0;

}

说点什么