2012级第三次训练题解

POJ 1207 The 3n + 1 problem

题意：著名的3n+1问题就是说任何一个数字N经过如下操作后一定能到达1.

如果N是偶数，则N=N/2，否则N为奇数就N=N*3+1。如此下去得到一组数，我们可以求得给定的N的这组数的长度。如N=22，则22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 所求序列，长度为16。

现在给你两个数X，Y，求在X和Y之间（包括X和Y)的所有数中上述序列最长的长度并输出。

思路：直接对N模拟执行上述操作，求出序列长度L。要注意的是有可能存在X>Y的情况。

#include <stdio.h>
int cal(int x)
{
    int ans=1;
    while(x!=1)
    {
        if(x%2) x=3*x+1;
        else x/=2;
        ans++;
    }
    return ans;
}
int main()
{
    int x,y,t,i,ans;
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        printf("%d %d ",x,y);
        if(x>y) t=x,x=y,y=t;
        ans=0;
        for(i=x;i<=y;i++) if((t=cal(i))>ans)
            ans=t;
        printf("%d\n",ans);
    }
    return 0;
}

POJ 1218 THE DRUNK JAILER

题意：有N个锁着的房间（编号为1~N），每次对房间的操作都是和房间当前状态相反的操作，即原来锁着的就打开，原来开着的就锁上。现在有N轮操作，第X轮操作就是把X倍数的房间进行操作。问最后开着的房间共有几个？

思路1：简单模拟上述过程。其中用到了内存清空函数memset和取反操作！

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int a[120];
int main()
{
    int t,n,i,j,ans;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(i=1;i<=n;i++) for(j=1;i*j<=n;j++)
            a[i*j]=!a[i*j];
        for(i=1;i<=n;i++) if(a[i])
            ans++;
        printf("%d\n",ans);
    }
    return 0;
}

思路2：考虑每个房间最后的状态，比如房间4，它在第1、2、4轮分别被执行操作，所以最后是开着的。那对于房间F，就是在F的约数时被执行操作，并且最后如果F有奇数个约数则房间最后是开着的。设F=p1^k1*p2^k2...，则F的约数个数为(k1+1)*(k2+1)...，可以看出k1,k2...必须全部为偶数才能满足约数个数为奇数个，其实也就是F必须为平方数时才满足。所以最后开着的房间数就是有多少个小于等于N的平方数。ans=(int)sqrt(n); 

#include <stdio.h>
#include <math.h>
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",(int)sqrt(1.0*n));
    }
    return 0;
}

POJ 3094 Quicksum

题意：计算每个字符串的值。计算方法如下：ACM: 1*1 + 2*3 + 3*13 = 46

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

POJ 2350 Above Average

题意：求出一个数组中比平均数大的数所占的比例。

#include <stdio.h>
int a[1200];
int main()
{
    int T,n,i,ans;
    double s;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        s=0.0; ans=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            s+=a[i];
        }
        s/=n;
        for(i=0;i<n;i++) if(a[i]>s)
            ans++;
        printf("%.3lf%%\n",ans*100.0/n);
    }
    return 0;
}

POJ 1833 排列

题意：求一个数列的下K个排列。用next_permutation()。

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[1028];
int main()
{
    int T,n,k,i;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(i=0;i<n;i++) scanf("%d",&a[i]);
        while(k--) next_permutation(a,a+n);
        for(i=0;i<n-1;i++) printf("%d ",a[i]);
        printf("%d\n",a[i]);
    }
    return 0;
}

POJ 2608 Soundex

题意：每个字母都有一个映射码，给你一个字符串让你输出映射码。但有些字母没有映射码则不输出，且相邻两个字母如果映射码相同则只输出一个。

#include <stdio.h>
char s[25];
char map[27]="01230120022455012623010202";
int main()
{
    int i;
    while(scanf("%s",s)!=EOF)
    {
        for(i=0;s[i];i++) if(map[s[i]-'A']!='0' && map[s[i]-'A']!=map[s[i-1]-'A'])
            printf("%c",map[s[i]-'A']);
        printf("\n");
    }
    return 0;
}