[原创][讨论][交流]编程高手的超级训练题解析

主题：[原创][讨论][交流]编程高手的超级训练题解析

vcacm [专家分：1500] 发布于 2007-04-11 17:29:00

[code]
        [[color=FF0000]注意：这儿绝大部分的题目来源于信息学竞赛！
        这些题目都是非常好的！如果大家能把这些题目做出来，那么可以说你
        的编程能力达到了一定的水平！
        关于这些题目的答案在GOOGLE/BAIDU上都能搜出来，但我：希望大家积极参与讨论，如果你把当中的题目做出来了可以贴出来，不过最好是要讲清自己的解题思路！
我也会把自己做出来了的题目以及解题思路发上来和大家一起交流！
         如果你想学好编程，那么实践是很重要的！
         我也是一个编程爱好者！[/color]
  [color=FF00FF]            My dream is to
       develop a better than Linux, Windows more popular than the OS! [/color]
          有啥问题，可以联系本人：见我的签名档！
         ]

第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
             （高中组  竞赛用时：3小时）
             [color=FF00FF] 编号为： gcc_1[/color]
[/code]
[quote]

1．比赛安排（20分）
    设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n ? 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n ? 1天内每个队都与不同的对手比赛。
例如n=2时的比赛安排：
    队         1  2            3  4
    比赛       1==2            3==4             一天
               1==3            2==4             二天
               1==4          2==3             三天

2．数制转换（20分）
    设有一个字符串A$的结构为：  A$=’m<n>p’
    其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。
    程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。
    例如：A$=’48<10>8’
          其意义为：将10进制数48，转换成8进制数输出。
          输出结果为：48<10>=60<8>

3．挖地雷（30分）
    在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。

V1               V 2             V3                       V4                         V5

例如：
[题目要求]
当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
    输入格式： N：                       （表示地窖的个数）
         　　　Ｗ1，W2，W3，……WN     （表示每个地窖中埋藏的地雷数量）
                    A12…………… .     A1N
                        A23…………..A2N
                        ……..
                               AN-1  N

    输出格式：
      K1--K2--……….KV                  （挖地雷的顺序）
      MAX                            （挖地雷的数量）
例如：

　　　   　⑩--------⑧    ④-----⑦-------⑥

其输入格式为：                   输出：
               5                        1  ?3  -4  -5
10，8，4，7，6            max=27
    1  1  1  0
       0  0  0
          1  1
             1

4．砝码称重（30分）
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），
要求：
    输入方式：a1  a2  a3  a4  a5  a6
             （表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
    输出方式：Total=N
             （N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
如输入：1_1_0_0_0_0   （注：下划线表示空格）
  输出：TOTAL=3  表示可以称出1g，2g，3g三种不同的重量。

[/quote]

最后更新于：2007-04-17 06:46:00

本帖地址： http://bbs.pfan.cn/post/226056.html

回复列表（共83个回复）

71 楼

vcacm [专家分：1500] 发布于 2007-05-02 21:17:00

LZ现在应该可以了吧...

72 楼

vcacm [专家分：1500] 发布于 2007-05-03 11:33:00

[color=FF00FF]GCC-13 : ( 3-4) 题目参考答案：
[/color]
[code]

===============gcc-13-3:求先序排列===================
/* ***********************************
    A B C
    B C A
    A C B
*************************************/
#include <stdio.h>
#include <string.h>

#define MAX 101

int search (int le1,int le2, char *e , int lm1,int lm2,char *m)
{
        int i,d1,d2;

        if(le1 > le2)
        return 0;

        printf("%c",e[le2]);

        if(le1==le2 || le2==0 || lm1==lm2)
        return 0;
       for(i =lm1; i<=lm2; i++)
       if(m[i]==e[le2])
       break;

      d1 = le1+i-lm1-1;
      d2 = d1+1;

     if(d1 >= 0 )

     search (le1, d1, e, lm1, i-1 , m);

     if(d2 >= 0)

     search (d2, le2-1, e, i+1, lm2 , m);

}

int main(int argc, char *argv )
{
       char m[MAX],e[MAX];
       int len=0;

       scanf("%s %s", m , e);
       len = strlen(m);
       search (0,len-1,e, 0, len-1, m);
       return 0;
}

===============gcc-13-4:装箱问题 ====================

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

    #define MAX 20001
    #define MIN 50

    int main (int argc,char *argv)

    {
        long data[MIN];
        int a[MAX];
        long i,j,k,v,n;

        scanf("%ld %ld",&v, &n);

        for(i=1; i<=n ; i++)
        scanf("%ld",&data[i]);

        memset(a,0,sizeof(a));

        a[0] = 1;

        for(i=1 ; i<=n ; i++)
            for(j=v; j>=data[i] ; j--)
            {
                if(a[j-data[i]] == 1)
                a[j] = 1 ;
            }

        for(k=v; a[k] != 1;)
        k--;

        printf("%ld\n",v-k);

        return 0;
    }


[/code]

73 楼

vcacm [专家分：1500] 发布于 2007-05-03 11:38:00

[color=FF00FF]GCC-17: 部分题目答案

[/color]

   =============gcc-17-1: 乒乓球=======================
[code]
/* * *         the score count of pingpang         * * */

    /* * *         write by zhxdong! 30th,March, 2007    * * */

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

    #define MAXV 100001

    int main()
    {

        FILE *in = fopen("/home/gcc/table/table6.in","r");
        //FILE *out = fopen("/home/gcc/table5.out","w");

        char a[MAXV],c ;
        int len=0;
        int i,j,k;
        int w=0,l=0;
        /*scanf("%c",&c);
        while (c != 'E')
        {
            if(c != ' ')
            a[++len] = c;
            scanf("%c",&c);
        }*/

        //for(; (c=getchar())!='E' ; )
        fscanf(in,"%c", &c);

        for(; c != 'E' ; )

        {
            if(c !=' ' && c != '\n')
            {
            a[++len] = c ;
            if(a[len]=='W')
            w ++;
            if(a[len]=='L')
            l++;
            if( ( ((w == 11 && l<=11)||(w <= 11 && l == 11) ) && abs(w-l) >= 2  )
|| ((w > 11 || l > 11 ) && abs(w-l) == 2) )
            {
            printf("%d:%d\n",w, l);
            w = 0;
            l = 0;
            }
            }

            fscanf(in, "%c" , &c);

        }


        printf("%d:%d\n",w,l);
        printf("\n");


        w=0;
        l=0;

        for(j=1 ; j<= len ; )
        {
            if(a[j] == 'W')
            w++;
            if(a[j] == 'L')
            l++;

            if (  ( ((w==21 && l <= 21) || (w <= 21&& l == 21))
&& abs(w-l) >= 2 ) || (( w > 21 || l >21 ) && abs(w-l) == 2 ) )

            {
            printf("%d:%d\n",w,l);
            w=0;
            l=0;
            }
            j ++;
        }

        printf("%d:%d\n",w,l);

        fclose(in);

        return 0;
    }
[/code]

74 楼

vcacm [专家分：1500] 发布于 2007-05-04 01:24:00

[color=FF00FF]
GCC-11: 部分答案！
[/color]

===================gcc-11-1 : 计算器的改良=====================
[code]
/* * * ***********************************
     * * *
         * * *     Date : 2007 / 5 / 3 11:03.pm
     * * *     Program name : jisuanji.c
     * * *   Input : -5x + 9 = 8x + 1
     * * *   Output: 0.478
     * * *
     * * * ***********************************/

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

     #define MAX 101

     int pow_10 (int n)
     {
        int i,ok=1 ;
        if ( n == 0 )
        return 1 ;

        for (i=1 ;i <= n ; i++)
        ok *= 10 ;
        return ok ;
    }

     void slove (char * , int ,int * ,int * ) ;
     int main(void)
     {
        FILE *in = fopen("data.in","r") ;
        FILE *out = fopen("data.out","w") ;

        int left=0 ,right = 0 ;
        int i,j,k,x1,x2;
        char le[MAX]={'\0'}, ri[MAX] = {'\0'} ;
        char c1 ;
        int l = 0 , r= 0 ;
        float x0=0,y0=0,sum;

        while ( (c1 = fgetc(in) )!= '=')
        {
            le[++l] = c1 ;
        }

        while ( (c1 = fgetc(in) )!= '\n')
        {
            ri[++r] = c1 ;
        }

        slove(le , l , &x1 , &left) ;
        slove(ri , r , &x2 , &right) ;

        /*printf("x1 = %d\n x2= %d \nleft= %d \n right = %d\n",x1,x2,left,right) ;        */

        x0 = right - left ;
        y0 = x1 - x2 ;
        sum = x0 / y0 ;

        fprintf(out,"%0.3f\n",sum) ;
        fclose(in) ;
                fclose(out) ;
        return 0 ;
    }

    [/code]

75 楼

vcacm [专家分：1500] 发布于 2007-05-04 01:25:00

同上...
[code]
void slove ( char st[MAX],int len ,int *x , int *su)
    {

        int save,num,sum,i,j,k ;

        *x = 0 ;
        *su= 0 ;

        for(i=1 ; i<= len ; ) /*solve  the left data*/
        {
                save = i ;
                num = 0 ;
                sum = 0 ;
                j = i+1 ;
                while(st[j] != '+' && st[j] != '-'&& st[j]!='\0')
                {
                    j ++ ;
                    num ++ ;
                }

                j -- ;

                if( '0' <= st[j] && st[j] <= '9' )
                {



                    if ( !(st[i] >= '0' && st[i]<='9' ))

                    i ++ ;

                    else

                    num ++ ;
                    for(k= i ; k<= j ; k++,num--)
                    sum += (st[k]-'0')*pow_10(num-1) ;

                    if ( st[save] == '-' )
                    *su -= sum ;
                    else
                    *su += sum ;
                }

                else
                {
                    if ( st[j-1] >= '0' && st[j-1] <= '9' )
                    {
                        if( !(st[i]>= '0' && st[i]<='9') )
                         {
                        i ++ ;
                        num -- ;
                         }



                        for(k=i ; k<= j-1 ; k++,num--)
                        sum += (st[k]-'0') * pow_10(num-1) ;
                    }
                    else
                    sum = 1 ;

                    if ( st[save] == '-' )
                    *x -= sum ;
                    else
                    *x += sum ;
                }

            i = j+1 ;
          }
    }

[/code]

76 楼

duckping [专家分：50] 发布于 2007-05-06 15:27:00

弄得很好的
还是对于初学者有很大的帮助

77 楼

chuangjun [专家分：220] 发布于 2007-05-06 16:49:00

貌似这些提挺有趣的，有生之年一定搞定他了！

78 楼

chwen822 [专家分：1540] 发布于 2007-05-06 23:26:00

[quote]弄得很好的
还是对于初学者有很大的帮助
[/quote]

79 楼

oopos [专家分：0] 发布于 2007-10-08 12:14:00

不错。。。呵呵。。。。我也来做做。。。

80 楼

lxianw163 [专家分：0] 发布于 2008-09-25 12:26:00

编号为： gcc_3的第二题和第三题的算法能告诉我么？谢谢！~

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创][讨论][交流]编程高手的超级训练题解析

回复列表（共83个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创][讨论][交流]编程高手的超级训练题解析

回复列表 （共83个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共83个回复）