2012NCEPU训练赛3

A、The 3n + 1 problem

题意：输入两个数据分别是上下限，
根据：

if n = 1 then STOP
if n is odd then   n <-- 3n+1
else   n <-- n/2

循环数字，求上下限间循环次数最多的

思路：

使用循环结构，在两数之间找最大的循环次数，1结束

注意：

输入两数间没有确定的大小关系。

#include <stdio.h>
void main()
{
    int i,j,n1,n2=0,a,b,t;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        if(a>b)
        {
            {
            t=a;a=b;b=t;
            }
        n1=0;n2=0;
         for(i=a;i<=b;i++)
         {
             n1=0;
             j=i;
             while(j!=1)
             {
     if(j%2==0)
             {
                 j=j/2;
                 n1++;
             }
             else
             {
                 j=3*j+1;
                 n1++;
             }
             }
             n1++;
             if(n2<=n1)
                 n2=n1;
         }
         printf("%d %d %d\n",b,a,n2);
        }
        else
        {
            n1=0;n2=0;
         for(i=a;i<=b;i++)
         {
             n1=0;
             j=i;
             while(j!=1)
             {
     if(j%2==0)
             {
                 j=j/2;
                 n1++;
             }
             else
             {
                 j=3*j+1;
                 n1++;
             }
             }
             n1++;
             if(n2<=n1)
                 n2=n1;
         }
         printf("%d %d %d\n",a,b,n2);
        }
    }
}

B、THE DRUNK JAILER
题意：n个牢房循环n遍，起初都开着，循环过程中将某些牢房开的关了，关的开了，某些牢房跟循环次数有关，是次数的整数倍

思路：输入n，先将数组都赋值为0，表示开，当k次循环时，将整除k的牢房的值变化，以前是0的变为1，以前是1的变为0，最后统计数组中1的个数

#include <stdio.h>
int main()
{
    int n,a[200],i,j,k,count=0,b[10000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&b[i]);
    for(k=0;k<n;k++)
    {
        count=0;
     for(i=1;i<=b[k];i++)
        a[i]=0;
     for(i=1;i<=b[k];i++)
     {
        for(j=1;j<=b[k];j++)
        {
            if(j%i==0)
            {
                if(a[j]==0)
                    a[j]=1;
                else if(a[j]==1)
                    a[j]=0;
            }
        }
     }
     for(i=1;i<=b[k];i++)
     {
        if(a[i]==1)
            count++;
     }
     printf("%d\n",count);
     }

    return 0;
}

C - Quicksum

题意：输入字符串，以回车结束，其quicksum为各个字符的位置乘以它对应的的值之和。

思路：用两个数组，一个记录字符串内容，另一个整型数组记录对应位置字符的大小，将大小*位置加起来即可。

#include <stdio.h>
#include <string.h>
int main()
{
    char a[300],*p;
    int s=0,i,cnt[300],n;
    while(gets(a) && a[0]!='#')
    {
        s=0;n=0;
        p=a;
        n=strlen(a);
     for(i=0;i<n;i++)
     {
         if(a[i]==' ')
             cnt[i+1]=0;
         else
             cnt[i+1]=a[i]-'A'+1;
     }
     for(i=1;i<=n;i++)
     {
        s=s+i*cnt[i];
     }
     printf("%d\n",s);
     }
    return 0;
}

D - Above Average

题意：求平均值以上数字的百分比

思路：用数组记录各个数据，求和，再求平均值，数组值一一与平均值比较，记录比平均值大的数据个数，除以总数即可。

注意：%号的输出方式是%%。

#include <stdio.h>
int a[2000][2000];
int main()
{
    int n,i,no,j;
    float avg,precent;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        avg=0;
        no=0;
        scanf("%d",&a[i][0]);
        for(j=1;j<=a[i][0];j++)
        {
            scanf("%d",&a[i][j]);
         avg=avg+a[i][j];
        }
        avg=avg/a[i][0];
        for(j=1;j<=a[i][0];j++)
        {
            if(a[i][j]>avg)
                no++;
        }
        precent=(float)no/a[i][0]*100;
        printf("%.3f%%\n",precent);
    }
    return 0;
}

E - 排列

题目描述：
大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。

任务描述：
给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。
比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。

思路：使用数组记录数值，全排列函数排序输出。

注意：函数的使用方法，用c++编程

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct node
{
    int n;
    int k;
    int a[2000];
}node[2000];
int main()
{
    int m,i,j;
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&node[i].n,&node[i].k);
        for(j=0;j<node[i].n;j++)
        {
            scanf("%d",&node[i].a[j]);
        }
        for(j=0;j<node[i].k;j++)
        next_permutation(node[i].a,node[i].a+node[i].n);
        for(j=0;j<node[i].n;j++)
               printf("%d ",node[i].a[j]);
        printf("\n");
    }
    return 0;
}

F - Soundex

题意：翻译问题，将字符按一定规律翻译成数字，输出无连续重复数字

思路：逐个翻译，使用if判断，翻译后存储在数字数组中，判断输出。

注意：循环结束条件。

#include <stdio.h>
int main()
{
    char a[21],*p;
    int b[21],n=0,i;
    while(scanf("%s",a)!=EOF)
    {
        n=0;
        p=a;
        while(*p!='\0')
        {
            if(*p=='B' || *p=='F'||*p=='P'||*p=='V')
                b[n]=1;
            else if(*p=='C'|| *p=='G'||*p=='J'||*p=='K'||*p=='Q'|| *p=='S'||*p=='X'||*p=='Z')
                b[n]=2;
            else if(*p=='D'|| *p=='T')
                b[n]=3;
            else if(*p=='L')
                b[n]=4;
            else if(*p=='M' || *p=='N')
                b[n]=5;
            else if(*p=='R')
                b[n]=6;
            else b[n]=0;
            n++;
            p++;
        }
        for(i=0;i<n;i++)
        {
            if(b[i]!=0 && b[i]!=b[i-1])
                printf("%d",b[i]);
        }
        printf("\n");
    }
    return 0;
}