Codeforces 398A Cards 暴力

题目大意：

就是现在对于一个只含有字符‘x'和字符’o'的串, 其和为连续的‘o'的个数的平方的和减去连续的’x'的平方和

例如"ooxoooxo"的和是2*2 - 1*1 + 3*3 - 1*1 + 1*1 = 9

现在给出a, b (0 <= a, b <= 10 ^5, a + b >= 1) 表示一个串中含有a个‘o'和b个’x', 要使得和最大问需要如何排列使得和最大, 输出最大的和以及对应的排列

大致思路：

首先注意到如果一个串中含有p个连续的‘o'串和q个连续的’x'串, 那么|p - q| <= 1, 由于a和b是给定的, 把a分成p份(x1 + x2 + ... + xp == a)使得平方和最大当然是x1 = a - (p - 1)且x2 = x3 = ...= xp = 1, 同时对于b个'x'分成q份(y1 + y2 + .. + yq == b)使得平方和最小当然是尽量平分, 对于yi (1 <= i <= b % q) yi = b/q + 1, 对于yi(b % q < i <= q) yi = b / q，即可

所以只需要枚举将a和b分成p和q份即可

代码如下：

Result  :  Accepted     Memory  :  8 KB     Time  :  46 ms

/*
 * Author: Gatevin
 * Created Time:  2015/2/28 20:46:44
 * File Name: Shana.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

lint O, X;

int main()
{
    cin>>O>>X;
    if(O == 0)
    {
        cout<<-X*X<<endl;
        for(int i = 0; i < X; i++)
            printf("x");
        return 0;
    }
    if(X == 0)
    {
        cout<<O*O<<endl;
        for(int i = 0; i < O; i++)
            printf("o");
        return 0;
    }
    lint ans = -99999999999999999LL;
    lint ans_tmp;
    lint ans_p, ans_q;
    for(lint p = 1; p <= O; p++)
    {
        lint q = p + 1;
        if(q <= X && q >= 1)
        {
            ans_tmp = 0;
            ans_tmp += (O - (p - 1))*(O - (p - 1)) + p - 1;
            ans_tmp -= X % q * (X / q + 1)*(X / q + 1) + (X/q)*(X/q)*(q - X % q);
            if(ans_tmp > ans)
            {
                ans = ans_tmp;
                ans_p = p;
                ans_q = q;
            }
        }
        q = p - 1;
        if(q >= 1 && q <= X)
        {
            ans_tmp = 0;
            ans_tmp += (O - (p - 1))*(O - (p - 1)) + p - 1;
            ans_tmp -= X % q * (X / q + 1)*(X / q + 1) + (X/q)*(X/q)*(q - X % q);
            if(ans_tmp > ans)
            {
                ans = ans_tmp;
                ans_p = p;
                ans_q = q;
            }
        }
        q = p;
        if(q >= 1 && q <= X)
        {
            ans_tmp = 0;
            ans_tmp += (O - (p - 1))*(O - (p - 1)) + p - 1;
            ans_tmp -= X % q * (X / q + 1)*(X / q + 1) + (X/q)*(X/q)*(q - X % q);
            if(ans_tmp > ans)
            {
                ans = ans_tmp;
                ans_p = p;
                ans_q = q;
            }
        }
    }
    cout<<ans<<endl;
    lint p = ans_p, q = ans_q;
    //cout<<p<<" "<<q<<endl;
    if(p > q)
    {
        for(int i = 1, j = 1; i <= p && j <= q; i++, j++)
        {
            if(i == 1)
                for(int k = 1; k <= O - q + 1; k++)
                    printf("o");
            else
                printf("o");
            if(j <= X % q)
                for(int k = 1; k <= X / q + 1; k++)
                    printf("x");
            else
                for(int k = 1; k <= X / q; k++)
                    printf("x");
        }
        printf("o\n");
    }
    else
    {
        for(int i = 1, j = 1; i <= p && j <= q; i++, j++)
        {
            if(i <= X % q)
                for(int k = 1; k <= X / q + 1; k++)
                    printf("x");
            else
                for(int k = 1; k <= X / q; k++)
                    printf("x");
            if(i == 1)
                for(int k = 1; k <= O - p + 1; k++)
                    printf("o");
            else
                printf("o");
        }
        if(p != q)
            for(int k = 1; k <= X / q; k++)
                printf("x");
        printf("\n");
    }
    return 0;
}