2012级第二次训练题解

POJ 1002 487-3279

题意:

输入N个电话号码字符串,你需要对字符串进行变换得到标准格式xxx-xxxxx,然后你要对标准电话号码进行统计,得出每个电话号码出现的次数.最后你要输出的就是按照电话号码的字典序输出那些出现次数超过1次的电话号码,如果没有的话就输出"No duplicates. ".

思路:

这一题有两个难点:1.处理字符串,将电话号码转换成标准格式.2.统计每个电话号码的次数并按字典序输出.

对于第一个难点,我的处理方式是:给出每个字母对应数字的数组,然后将电话号码按照整数处理,比如310-1010就是整数3101010,F101010也是整数3101010.这样的好处就是不用管其他非字母字符了.

对于第二个难点,就是把电话号码(我已经处理成整数了)从小到大排序,然后统计输出.我在统计的时候在最后添加了一个哨兵(a[n]=-1),因为所有的电话号码都不会是-1.

使用qsort()的时间复杂度是O(NlgN).将电话号码处理成整数的空间复杂度是O(N).

include <stdio.h>
#include <memory.h>
#include <stdlib.h>

const int maxn=100005;
int a[maxn],map[128];
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
void init()
{
    memset(map,-1,sizeof(map));
    map['A']=map['B']=map['C']=2;
    map['D']=map['E']=map['F']=3;
    map['G']=map['H']=map['I']=4;
    map['J']=map['K']=map['L']=5;
    map['M']=map['N']=map['O']=6;
    map['P']=map['R']=map['S']=7;
    map['T']=map['U']=map['V']=8;
    map['W']=map['X']=map['Y']=9;
    for(int i='0';i<='9';i++) map[i]=i-'0';
}
int trans(char s[])
{
    int ans=0,i;
    for(i=0;s[i];i++) if(map[s[i]]!=-1)
        ans=ans*10+map[s[i]];
    return ans;
}
int main()
{
    int n,i,ans=0,p,cnt;
    char s[125];
    init();
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%s",s);
        a[i]=trans(s);
    }
    qsort(a,n,sizeof(a[0]),cmp);
    a[n]=-1;
    p=a[0]; cnt=1;
    for(i=1;i<=n;i++) if(p==a[i])
        cnt++;
    else
    {
        if(cnt>1) { ans=1; printf("%03d-%04d %d\n",p/10000,p%10000,cnt); }
        cnt=1;
        p=a[i];
    }
    if(!ans) printf("No duplicates.\n");
    return 0;
}

POJ 2388 Who's in the Middle

题意:

给你N个(N一定为奇数)数,求这些数的中位数.

思路:

对N个数进行排序,A[N/2]就是中位数.

#include <stdio.h>
#include <stdlib.h>
int a[10004];
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    qsort(a,n,sizeof(a[0]),cmp);
    printf("%d\n",a[n/2]);
    return 0;
}

POJ 2390 Bank Interest

题意:

给出年利率R,本金M,年数Y,求Y年后本息和.

思路:

使用公式ans=M*(1+R/100)^Y.使用库函数pow().

#include <stdio.h>
#include <math.h>
int main()
{
    int a,b,n;
    while(scanf("%d%d%d",&a,&b,&n)!=EOF)
    {
        printf("%d\n",(int)(pow(1.0+a/100.0,n)*b));
    }
    return 0;
}

POJ 1035 Spell Checker

题意:

给出一个字典包含若干单词,然后给你若干单词,让你判断该单词是否在字典中出现过,若出现过则该单词正确,若未出现过则查找字典中是否有单词可以通过删除/替换/插入一个字母而得到该单词.

思路:

主要就是对删除/替换/插入这三种操作的处理.详细参见代码.

#include <stdio.h>
#include <string.h>
#include <math.h>

const int maxn=10005;
char dic[maxn][18],s[18];
int v[maxn];
int like(char s[],char t[])
{
    int x=strlen(s),y=strlen(t),i;
    if(abs(x-y)>1) return 0;
    if(x==y)
    {
        int cnt=0;
        for(i=0;i<x;i++) if(s[i]!=t[i])
        {
            cnt++;
            if(cnt>1) return 0;
        }
        return 1;
    }
    if(x-y==1)
    {
        i=0;
        while(s[i]==t[i]) i++;
        for(;i<y;i++) if(s[i+1]!=t[i]) return 0;
        return 1;
    }
    i=0;
    while(s[i]==t[i]) i++;
    for(;i<x;i++) if(s[i]!=t[i+1]) return 0;
    return 1;
}
int main()
{
    int cnt=0,i;
    while(scanf("%s",dic[cnt]) && dic[cnt][0]!='#')
        cnt++;
    while(scanf("%s",s) && s[0]!='#')
    {
        int ans=0,f=0;
        for(i=0;i<cnt;i++)
        {
            if(strcmp(s,dic[i])==0){ f=1; break;}
            else if(like(s,dic[i])) v[ans++]=i;
        }
        if(f) printf("%s is correct\n",s);
        else
        {
            printf("%s:",s);
            for(i=0;i<ans;i++) printf(" %s",dic[v[i]]);
            printf("\n");
        }
    }
    return 0;
}

UVA 488 Triangle Wave

题意:

输出一个波形,简单控制一下就行了.

思路:

主要就是注意一下最后一个的最后一行后面是没有空行的.

#include <stdio.h>
int main()
{
    int T,h,f,i,j,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&h,&f);
        for(i=0;i<f;i++)
        {
            for(j=1;j<=h;j++,putchar('\n'))
                for(k=0;k<j;k++)
                    printf("%d",j);
            for(j=h-1;j>0;j--,putchar('\n'))
                for(k=0;k<j;k++)
                    printf("%d",j);
            if(!(T==0 && i==f-1))
                putchar('\n');
        }
    }
    return 0;
}