第三届华北电力大学程序设计大赛标程及题解

淡淡的烟草味﹌ 2022-08-27 01:23 132阅读 0赞

**第一题 点蜡烛**

对第一组样例的解释：

初始4根蜡烛照明4个小时，剩余的4个残骸变为2个蜡烛，照明2小时，新出现的2个残骸变为1个蜡烛，照明1小时，一共4+2+1=7小时。

第二组样例同理

对第三组样例的解释：

初始4根蜡烛照明4个小时，剩余的4个残骸变为1个蜡烛，剩余1个残骸，照明1小时，新出现的1个残骸加上原来的共2个残骸已经变不出新蜡烛了。照明一共4+1=5小时。

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

**第二题 ASCII 码**

读入给定的字符串，每一个字母的ASCII码值相加即可。

#include <stdio.h>
    #include <string.h>
    
    int main ()
    {
        char str[30];
        int T,lenth;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%s",str);
            int sum=0;
            lenth=strlen(str);
            for (int i=0;i<lenth;i++)
                sum+=str[i];
            printf("%d\n",sum);
        }
        return 0;
    }

**第三题 找规律，画图形**

找到规律，画出图形即可。

#include <stdio.h>
    #include <iostream>
    using namespace std;
    
    int main ()
    {
    	int i,j,t;
    	int a[100][100];
    	while (scanf("%d",&t) && t!=-1)
    	{
    		for(i=0;i<t;i++)
    			for(j=0;j<t;j++)
    				a[i][j]=0;
    		for(i=0;i<t;i++)
    		{
    			if(i%2==1)
    			{
    				for(j=0;j<=i;j++)
    				{
    					a[i][j]=1;
    					a[j][i]=1;
    				}
    			}
    		}
    		for(i=0;i<t;i++)
    		{
    			for(j=0;j<t;j++)
    			{
    				if(a[i][j]==0)
    					printf("*");
    				else
    					printf("#");
    			}
    			printf("\n");
    		}
    		printf("\n");
    	}
    	return 0;
    }

**第四题 平面分割**

该问题课抽象为两两椭圆只有两个交点的情况

设椭圆数为n，分割数为S(n)

则：S(1)=2 , S(2) =4 , S(3)=8 , S(4)=14 ……

[![1][]][1 1][![2][]][2 1]

[![3][]][3 1][![4][]][4 1]

思路：当n-1个圆时，区域数为f(n-1).那么第n个圆就必须与前n-1个圆相交，则第n个圆被分为2（n-1）段线段，增加了2（n-1）个区域。  
则： f(n) = f(n-1)+2(n-1) = f(1)+2+4+……+2(n-1) = n^2-n+2

#include<cstdio>
    using namespace std;
    const int num=202;
    int data[num];
    
    void init()
    {
        int i;
        data[1]=2;
        for(i=2;i<num;i++)
            data[i]=data[i-1]+2*(i-1);
    }
    
    int main()
    {
        int n;
        init();
        while(scanf("%d",&n)!=EOF,n)
        {
            printf("%d\n",data[n]);
        }
        return 0;
    }

**第五题 Bob 在意的事**

读入字符串并存储，之后查找即可

#include <cstdio>
    #include <cstring>
    
    const int MAXN =1005;
    char a[MAXN][85];
    int p[MAXN];
    int cnt;
    int n,m;
    
    int search(char s[]) //寻找字符串是否出现过
    {
    	for (int i=0;i<cnt;i++)
            if (strcmp(s,a[i])==0) return i;
    	return -1;
    }
    int main()
    {
    	int T,i;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d%d",&n,&m);
    		cnt=0;
    		for (i=0;i<MAXN;i++)  //初始化
                p=0;
    
    		char s[85];
    		for (i=0;i<n;i++)
    		{
    			scanf("%s",s);
    			int flag=search(s);
    			if (flag==-1) //没找到
    			{
    				strcpy(a[cnt],s);
    				p[cnt++]++;
    			}
    			else //找到
    				p[flag]++;
    		}
    		int flag=0;
    		for (int i=0;i<n;i++)
    		if (p[i]==m)
    		{
    			printf("%s\n",a[i]);
    			flag=1;
    			break;
    		}
    		if (!flag)
    			printf("No Answer\n");
    	}
    	return 0;
    }

**第六题 什么时候下课啊！**

读入时间后相加，并转换为要求的格式

#include <cstdio>
    #include <cstring>
    
    int sh,sm,ss;
    int lh,lm,ls;
    
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d:%d:%d",&sh,&sm,&ss);
    		scanf("%d:%d:%d",&lh,&lm,&ls);
    		ss=ss+ls;
    		sm=sm+lm+ss/60;
    		ss=ss%60;
    		sh=sh+lh+sm/60;
    		sm=sm%60;
    		sh=sh%24;
    		printf("%d:%02d:%02d\n",sh,sm,ss);
    	}
    	return 0;
    }

**第七题 数袋鼠**

显然至少有一半是可以看见的，于是排序后从第一个和中间同时开始向后扫，如果满足多于2倍关系就同时后移，否则只有中间的后移。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    const int N=500005;
    
    int data[N];
    
    int main ()
    {
    	int n,i,j;
    	scanf("%d",&n);
    	for (i=0;i<n;i++)
    		scanf("%d",&data[i]);
    	sort(data,data+n); //升序排序函数，大家可以换为选择排序，冒泡排序等方法
    	int limit=n/2,ans=n;
    	for (i=0,j=n/2 ; i<limit && j<n;j++)
    		if (data[i]*2 <= data[j])
    		{
    			ans--;
    			i++;
    		}
    	printf("%d\n",ans);
    	return 0;
    }

**第八题 华电纪念日**

考察对日期的处理，需要考虑闰年和每个月份天数的不同

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int n;
    
    int a[2][13]={
       {0,31,28,31,30,31,30,31,31,30,31,30,31},
                  {0,31,29,31,30,31,30,31,31,30,31,30,31}};
    
    int isLeapYear(int y)
    {
        return y%400==0||y%100&&y%4==0;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            int y=1958;
            int m=9;
            int d=22;
            n--;   //注意起始时间
            while(n--)
            {
                d++;
                if(d>a[isLeapYear(y)][m])
                {
                    m++;
                    d=1;
                    if(m==13)
                    {
                        y++;
                        m=1;
                    }
                }
            }
            printf("%d-%02d-%02d\n",y,m,d);
        }
        return 0;
    }

**第九题 世界杯**

本题较复杂，只给出代码和思路，一共有2份。

以下思路对应第一份代码。

dp\[i\]\[j\] 表示第i轮比赛时j获胜的概率。

dp\[i\]\[j\] = dp\[i-1\]\[j\]\*dp\[i-1\]\[k\]\*p\[j\]\[k\]

如何判断j,k为一组

假设球队从0开始编号 000,001,010,011,100,101,110,111,共8组

第一轮 000-001,010-011,100-101,110-111

第二轮（（000,001）-（010,011））,（（100,101）-（110,111））

第三轮（（000,001,010,011）-（100,101,110,111））

(j>>(i-1))^1==k>>(i-1)

#include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    
    const int N=135;
    
    double dp[10][N];  //dp[i][j] 表示第i轮比赛时j获胜的概率。
    double p[N][N];
    
    int main ()
    {
    	int n,i,j;
    	while (scanf("%d",&n) ,~n)
    	{
    		int m=1<<n;
    		for (i=0;i<m;i++)
    			for (j=0;j<m;j++)
    				scanf("%lf",&p[i][j]);
    		memset(dp,0,sizeof(dp));
    		for (i=0;i<m;i++)
    			dp[0][i]=1;
    		for (i=1;i<=n;i++)
    			for (j=0;j<m;j++)
    				for (int k=0;k<m;k++)
    					if(((j>>(i-1))^1)==(k>>(i-1)))
    						dp[i][j] += dp[i-1][j]*dp[i-1][k]*p[j][k];
    		double maxp=0;
    		int ans;
    		for (i=0;i<m;i++)
    			if (dp[n][i]>maxp)
    			{
    				maxp=dp[n][i];
    				ans=i+1;
    			}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    double dp[8][130],map[130][130];
    int a[10];
    
    struct node
    {
       int up,down;
    }s[8][130];
    
    int find(int i,int k)
    {
         int ans;
         ans=(i-1)/a[k-1]+1;
         if(ans%2) return ans+1;
         return ans-1;
    }
    
    int main()
    {
        int i,j,k,n,index;
         int ans;
         double Max;
         a[0]=1;
         for(i=1;i<=7;i++)
             a[i]=a[i-1]*2;
         for(i=1;i<=7;i++)
         {
            ans=0;
             k=0;
             while(ans<128)
             {
                 s[i][++k].up=ans+1;
                 s[i][k].down=s[i][k].up+a[i-1]-1;
                 ans=s[i][k].down;
             }
         }
         while(scanf("%d",&n)!=EOF && n!=-1)
        {
            for(i=1;i<=a[n];i++)
                 for(j=1;j<=a[n];j++)
                     scanf("%lf",&map[i][j]);
             memset(dp,0,sizeof(dp));
             for(i=1;i<=a[n];i++)
                 dp[0][i]=1;
             for(k=1;k<=n;k++)
             {
                 for(i=1;i<=a[n];i++)
                 {
                     ans=find(i,k);
                     for(j=s[k][ans].up;j<=s[k][ans].down;j++)
                         dp[k][i]+=dp[k-1][i]*dp[k-1][j]*map[i][j];
                 }
             }
             Max=dp[n][1];
             index=1;
             for(i=2;i<=a[n];i++)
                 if(dp[n][i]>Max) {Max=dp[n][i];index=i;}
             printf("%d\n",index);
         }
         return 0;
     }

[1]: http://images.cnitblog.com/blog/579630/201401/212103173041.png
[1 1]: http://images.cnitblog.com/blog/579630/201401/212103168827.png
[2]: /images/20220824/c265aa24390c40e4a3944aaf2d2f5c5c.png
[2 1]: http://images.cnitblog.com/blog/579630/201401/212103176479.png
[3]: http://images.cnitblog.com/blog/579630/201401/212103195224.png
[3 1]: http://images.cnitblog.com/blog/579630/201401/212103189915.png
[4]: /images/20220824/d791d1b38d9d4fc4826b52965d042a78.png
[4 1]: http://images.cnitblog.com/blog/579630/201401/212103199132.png