题目大意:给出两个非负整数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,取分数最大值即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// <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; } |