当前位置: 代码迷 >> 综合 >> ACM2051
  详细解决方案

ACM2051

热度:1   发布时间:2024-01-16 14:19:48.0

题目

2043 密码

Problem Description  网上流传一句话:"常在网上飘啊,哪能不挨刀啊~"。其实要想能安安心心地上网其实也不难,学点安全知识就可以。

首先,我们就要设置一个安全的密码。那什么样的密码才叫安全的呢?一般来说一个比较安全的密码至少应该满足下面两个条件:

(1).密码长度大于等于8,且不要超过16。

(2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。

这四个字符类别分别为:

1.大写字母:A,B,C...Z;

2.小写字母:a,b,c...z;

3.数字:0,1,2...9;

4.特殊符号:~,!,@,#,$,%,^;

给你一个密码,你的任务就是判断它是不是一个安全的密码。

Input  输入数据第一行包含一个数M,接下有M行,每行一个密码(长度最大可能为50),密码仅包括上面的四类字符。

Output  对于每个测试实例,判断这个密码是不是一个安全的密码,是的话输出YES,否则输出NO。

Sample Input 

3

a1b2c3d4

Linle@ACM

^~^@^@!%

Sample Output 

NO

YES

NO

 

设计过程

这道题主要是学习了新的函数isupper()是用来判断是不是大写字母的,islower()是用来判断是不是小写字母的,isdigit()是用来判断是不是数字的,以上如果是,那么返回一个非零值,如果不是,则返回0,非常适合放在判断语句中,感觉就是为判断语句量身定做的啊!

代码

#include <ctype.h>

#include <stdio.h>

int main(void)

{

    int n, a[6];

    char c;

   scanf("%d%*c", &n);

    while (n--)

    {

        a[0] = a[1] =a[2] = a[3] = a[4] = a[5] = 0;

        while ((c =getchar()) != '\n')

        {

            if(isupper(c))

                a[0] =a[5]++;

            else if(islower(c))

                a[1] =a[5]++;

            else if(isdigit(c))

                a[2] =a[5]++;

            else

                a[3] =a[5]++;

        }

        if (a[0])a[4]++;

        if (a[1])a[4]++;

        if (a[2])a[4]++;

        if (a[3])a[4]++;

        puts(a[4] >2 && a[5] > 7 && a[5] <17 ? "YES" :"NO");

    }

    return 0;

}

题目

Problem Description

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中,蜂房的结构如下所示。

 

 

Input

输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0<a<b<50)。

 

 

Output

对于每个测试实例,请输出蜜蜂从蜂房a爬到蜂房b的可能路线数,每个实例的输出占一行。

 

 

Sample Input

2

1 2

3 6

 

 

Sample Output

1

3

设计过程

题目可以转化为从第一个数开始,+1或者是+2。一开始思路是往递归方向考虑,后来发现,每次+1或者+2后,后面的步骤有很多,换句话说第一步+1,第二步可以是+1或者+2,第三步的变化更是多样,所以运行时间上肯定相差很多。所以我先列举,然后找出规律:后一个数等于前两个数之和,那么这道题可采用预处理的方法。

调试过程

中间出现了一些错误:比如格式错误,以为是输入所有条件,再显示结果

比如范围错误,int的取值范围远远不够,要用到__int64才满足(占位符用I64d)

还比如说列举不全,我一开始i仅仅只是小于49,发现题目中是要求小于50的,所以出现WR

 

代码

#include <stdio.h>

int main()

{

         intn,i,a,c,b;

         __int64e[50],f[50];

         scanf("%d",&n);

         e[2]=1,e[3]=2;

         for(i=4;i<50;i++)

         {

                   e[i]=e[i-1]+e[i-2];

         }

   for(i=0;i<n;i++)

         {

                   scanf("%d%d",&a,&c);

                   b=c-a+1;

       f[i]=e[b];

                   printf("%I64d\n",f[i]);

         }

 

}

 

Problem Description

人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即"可乐"),经过多方打探,某资深Cole终于知道了原因,原来,LELE最近研究起了著名的RPG难题:

有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法.

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

 

 

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成,(0<n<=50)。

 

 

Output

对于每个测试实例,请输出全部的满足要求的涂法,每个实例的输出占一行。

 

 

Sample Input

1

2

 

 

Sample Output

3

6

 

设计过程

直觉告诉我这只是一道数学问题,其实就是排列组合的问题。

代码

#include <math.h>

#include <stdio.h>

int main(void)

{

   int i;

   __int64 a[51] = {0, 3, 6, 6};

   for (i = 4; i < 51; i++)

       a[i] = a[i-1] + 2*a[i-2];

   while (scanf("%d", &i) != EOF)

        printf("%I64d\n", a[i]);

   return 0;

}

 

2046 骨牌铺方格

Problem Description  在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.

例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:

Input 输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

Output 对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。

Sample Input 

1

3

2

Sample Output 

1

3

2

 

 

设计过程

和之前的题目简直是异曲同工,一个模子刻出来的

代码

 

#include <math.h>

#include <stdio.h>

int main(void)

{

   int i;

   __int64 d[51] = {1, 1, 2,};

   for (i = 3; i < 51; i++)

       d[i] = d[i-1] + d[i-2];

   while (scanf("%d", &i) != EOF)

       printf("%I64d\n", d[i]);

   return 0;

}

题目

十进制转二进制

设计思路

十进制整数转换为二进制整数采用"除2取余,逆序排列"法。具体做法是:用2整除十进制整数,可以得到一个商和余数;再用2去除商,又会得到一个商和余数,如此进行,直到商为0时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列起来。

代码

#include<stdio.h> 

void main()

{ int a; 

 chars[20];

 inti=0,rem;

 printf("请输入整数:\n");

 scanf("%d",&a); 

 do

 {  rem=a%2;   a=a/2;   s[i]=rem;  i++;  }

 while(a!=0);

 printf("输出的二进制:");

 while(i>0) 

          printf("%d",s[--i]);

 printf("\n");}

 

题目

 

Problem Description

医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.

 

 

Input

每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束.

 

 

Output

对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.

 

 

Sample Input

4

1

4

20

11

3

14

24

6

0

 

 

Sample Output

Case 1: 2

Case 2: 72

Case 3: 32

Case 4: 0

 

Case 1: 56

Case 2: 72

Case 3: 56

 

设计思路

这其实是一道递推题

把字符串的个数看成是二维数组

F[n][0]是合法字符串的个数(长度为n)

1和2表示仅AC出现的个数

可以推出F[n][0]=2*F[n-1][0]+F[n-1][1]+F[n-1][2]

构造指数级生成函数:(1+x/1!+x^2/2!+x^3/3!……)^2*(1+x^2/2!+x^4/4!+x^6/6!……)^2.

前面是B和D的情况,可以任意取,但是相同字母一样,所以要除去排列数。后者是A和C的情况,只能取偶数个情况。

根据泰勒展开,e^x在x0=0点的n阶泰勒多项式为 1+x/1!+x^2/2!+x^3/3!……

而后者也可以进行调整,需要把奇数项去掉,则e^(-x)的展开式为1-x/1!+X^2/2!-X^3/3!……

所以后者可以化简为(e^x+e^(-x))/2。则原式为 (e^x)^2   *  ((e^x*e^(-x))/2)^2

整理得到e^4x+2*e^2x。

又由上面的泰勒展开

由数学公式可以得出f[n][0]=2的2n-1次加上2的n-1次

接下来就是找规律啦

通过列举法即可

 

代码

#include <stdio.h>

int main()

{

          __int64 b[21],s1=1,s2=1;

          int c=2,d=6,i,j;

          int t,n=0;

          for(i=3;i<=24;i++)

          {

                    s1=s2=1;

                    for(j=1;j<=i;j++)

                    {

                             s1*=4; s2*=2;

                   }

                    b[i-3]=(s1+2*s2)/4%100;

          }

 

          while(scanf("%d",&t),t)

          {

                    if(t==0) break;

                    while(t--)

                    {

                             __int64 z;

                             scanf("%I64d",&z);

                             if(z<=2)

                             {

                                      if(z==1) printf("Case %d:%d\n",++n,c);

                                      else if(z==2) printf("Case %d:%d\n",++n,d);

 }

                             else printf("Case %d:%I64d\n",++n,b[(z-3)%20]);

                             if(t==0)

                             {

                                      printf("\n");

                                      n=0;

 }

 }

 }

          return 0;

 }

  相关解决方案