Codeforces Good Bye 2013 ABCDE

我会带着你远行 2022-08-24 14:15 39阅读 0赞

继续总结做过的练习赛。

链接：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**

当时没能做出的一题。参考了:http://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;
    }

**F New Year Tree**  
貌似与树的直径有关,以后学习了这部分再回来看。