Codeforces Good Bye 2013 ABCDE-蒲公英云

继续总结做过的练习赛。

链接：http://codeforces.com/contest/379

A New Year Candles

题意：初始有a根蜡烛,每根蜡烛照明1小时,每b根蜡烛的残骸可以变成一根新蜡烛,问一共可以照明多久

#include <cstdio>
int main ()
{
    int sum=0,a,b;
    scanf("%d%d",&a,&b);
    sum+=a;
    int last=a;
    while (last>=b)
    {
        sum+=last/b;
        last=last%b+last/b;
    }
    printf("%d\n",sum);
    return 0;
}

B New Year Present
题意:一个机器人要塞钱进钱袋,n个钱袋每个要塞ai个.不能连续塞两次,求任意方案
思路:让机器人从左走到右,再从右走到左,最多也只要2*300*300步

#include <cstdio>
#include <cstring>
const int N=305;
int data[N];
int n;
int main ()
{
    scanf("%d",&n);
    int i;
    for (i=1;i<=n;i++)
        scanf("%d",&data[i]);
    int cur=1,left=1,right=n;
    bool flag=true;
    while (flag)
    {
        flag=false;
        for (i=1;i<n;i++)
            if (data[i])
            {
                printf("PR");
                data[i]--;
                flag=true;
            }
            else
                printf("R");
        for (i=n;i>1;i--)
            if (data[i])
            {
                printf("PL");
                data[i]--;
                flag=true;
            }
            else
                printf("L");
    }
    printf("\n");
    return 0;
}

C New Year Ratings Change
题意:n个人，每个人最少要ai个礼物，要求每个人给礼物个数不重复，问怎么分配。
写得很逗的一题,居然fst,在case36超时了……
之后删了一个无关的变量,就795ms过了，看来以后交代码前有必要先优化一下。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=300005;
struct Node
{
    __int64 num,out;
    int id;
    void Get (int i)
    {
        id=i;
        scanf("%I64d",&num);
    }
    bool operator < (Node b) const
    {
        return num<b.num;
    }
}data[N];
bool cm (Node a,Node b)
{
    return a.id<b.id;
}
int main ()
{
    int n,i;
    scanf("%d",&n);
    for (i=0;i<n;i++)
        data[i].Get(i);
    sort(data,data+n);
    __int64 cur=0;
    for (i=0;i<n;i++)
    {
        if (cur<data[i].num)
        {
            cur=data[i].num;
            data[i].out=cur;
        }
        else
        {
            cur++;
            data[i].out=cur;
        }
    }
    sort(data,data+n,cm);
    for (i=0;i<n;i++)
        printf(i==n-1?"%I64d\n":"%I64d ",data[i].out);
    return 0;
}

D New Year Letter

当时没能做出的一题。参考了//blog.csdn.net/accelerator\_/article/details/17713303
题意:给出递推次数k,初始字符串S1、S2的长度n,m, 使用类似斐波纳契数列的字符串合并的递推操作,使得最后得到的字符串中刚好含有x个”AC”,现在要你构造出满足条件的S1和S2。
思路:暴力枚举,dp,枚举两个串的头尾字母和AC个数。每次判断进行dp递推。
f[k]=f[k-2]*a+f[k-1]*b+sum;如果头尾字母构成AC,sum=1,否则为0

#include <cstdio>
#include <cstring>
const int N=105;
int k,x,n,m;
__int64 f[N];
char ans[N],s[N],e[N];
void Out (char s, char e, int len, int num)
{
    memset(ans,'B',sizeof(ans));
    ans[0]=s;
    ans[len-1]=e;
    ans[len]=0;
    int bo = (s == 'A' ? 0 : 1); //开头是否为'A'
    for (int i=0;i<num;i++)
    {
        ans[bo + 2*i] = 'A';
        ans[bo + 2*i+1] = 'C';
    }
    printf("%s\n", ans);
}
bool OK (char s1, char e1, char s2, char e2, int xx, int yy)
{
    s[1]=s1; e[1]=e1;
    s[2]=s2; e[2]=e2;
    f[1]=xx; f[2]=yy;
    for (int i=3;i<=k;i++)
    {
        s[i] = s[i-2];
        e[i] = e[i-1];
        f[i] = f[i-1] + f[i-2] + (e[i-2]=='A' && s[i-1]=='C');
    }
    if (f[k] == x)
        return true;
    return false;
}
bool judge ()
{
    for (char s1='A'; s1<='C'; s1++) for (char e1='A'; e1<='C'; e1++)
    {
        if (n == 1 && s1 != e1) continue;   //长度为1,且首尾相同
        for (char s2='A'; s2<='C'; s2++)
            for (char e2='A'; e2<='C'; e2++)
            {
                if (m == 1 && s2 != e2) continue; //长度为1,且首尾相同
                int lx = n - (s1 != 'A') - (e1 != 'C');
                int ly = m - (s2 != 'A') - (e2 != 'C');
                lx /= 2; ly /= 2;  //各自串中可能有的AC个数上限
                for (int xx = 0; xx <= lx; xx++)
                    for (int yy = 0; yy <= ly; yy++)
                    {
                        if (n == 2 && s1 == 'A' && e1 == 'C' && xx == 0) continue;
                        if (m == 2 && s2 == 'A' && e2 == 'C' && yy == 0) continue;
                        if (OK(s1, e1, s2, e2, xx, yy))
                        {
                            Out(s1, e1, n, xx);
                            Out(s2, e2, m, yy);
                            return true;
                        }
                    }
            }
    }
    return false;
}
int main ()
{
    scanf("%d%d%d%d",&k,&x,&n,&m);
    if (judge()==false)
        printf("Happy new year!\n");
    return 0;
}

E New Year Tree Decorations
题意:n片纸,每块长都是k,求每块纸可见面积是多少
官方题解是俄语真是压力山大,参考了http://kmjp.hatenablog.jp/entry/2014/01/02/1000
果然日语还是能看懂两句的……
思路:枚举每一个区间,单独考虑，在每一个区间内对每张纸进行切割

#include <map>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define upmax(a,b) ((a)=(a)>(b)?(a):(b))
int Y[301][301];
double S[301]; //存储最终每张纸的可见面积
int main ()
{
    int i,x,n,k;
    scanf("%d%d",&n,&k);
    for (i=0;i<n;i++)
        for (x=0;x<=k;x++)
            scanf("%d",&Y[i][x]);
    for (x=0;x<k;x++)
    {//枚举每一个区间
        map<double,double> M;
        M[0]=0; M[1]=0;
        for (i=0;i<n;i++)
        {//枚举每张纸
            map<double,double> M2;
            M2[0]=M[0];
            double prex=0,prey=M[0];
            map<double,double>::iterator it;
            for (it=M.begin();it!=M.end();it++)
            {//枚举区间内所有交点,其中0和1为左右端点
                if (it->first==0) continue;
                double cx = it->first;
                double cy = it->second;
                double slope=Y[i][x+1]-Y[i][x];  //斜率
                double y1= Y[i][x]+slope*prex;   //待切割斜线的端点坐标
                double y2= Y[i][x]+slope*cx;
                //分四种情况讨论
                if (y1>=prey && y2>=cy)
                {
                    S[i] += ((y1+y2)-(cy+prey))*(cx-prex)/2.0; //梯形面积公式
                    M2[cx]=y2;
                }
                else if (y1<=prey && y2<=cy)
                    M2[cx]=cy;
                else if (y1>=prey && y2<=cy)
                {//计算交点
                    double nx = prex + (cx-prex)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
                    double ny = prey + (cy-prey)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
                    S[i] += ((y1-prey))*(nx-prex)/2.0;
                    M2[nx]=ny;  //将新交点加入容器,用于切割之后的线
                    M2[cx]=cy;
                }
                else if (y1<=prey && y2>=cy)
                {//计算交点
                    double nx = prex + (cx-prex)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
                    double ny = prey + (cy-prey)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
                    S[i] += ((y2-cy))*(cx-nx)/2.0;
                    M2[nx]=ny;
                }
                prex=cx; prey=cy;
            }
            upmax(M2[0],Y[i][x]);
            upmax(M2[1],Y[i][x+1]);
            swap(M,M2);
        }
    }
    for (i=0;i<n;i++)
        printf("%.12lf\n",S[i]);
    return 0;
}