[讨论]第八次编程比赛题目 — 编程爱好者社区

主题：[讨论]第八次编程比赛题目

林木 [专家分：130] 发布于 2005-12-24 07:56:00

严重道歉,各位,我来晚了.比赛时间延长150分钟.

/////////////////////////////////////////////////////////////////////////////////
[color=FF0000]注意:不得不再提醒大家一下,你们的排名不仅将同你的正确率有关,另一个重要因素是效率,所以请在保证正确的情况下,尽量提高你的时空效率.[/color]
/////////////////////////////////////////////////////////////////////////////////

1.注释提取器
[题目描述]
  给出一个程序源代码
  要求输出其注释部分内容.即/* 与 */中的内容

[输入样例]
  #include <stdio.h>/*  Hello world*/
  int main(){
    printf("example.");/* 世界,你好. */
    return 0;
  }
[输出样例]:
    Hello world 世界,你好.
  提示:包括空格.

2.单词查找树(TRIE)
[题目描述]
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
在满足上述条件下，该单词查找树的节点数最少。
例：
对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）

[输入样例]
注:为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符。文件总长度不超过32K，至少有一行数据.

A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

[输出样例]
注:该文件中仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。
13

4.墙上的灯
[题目描述]：
Arthur King的城堡有一个圆形的大厅。大厅的墙壁上有N盏灯，分别按顺序从1到N编号。每盏灯都可以每打开或关上。在每一秒钟，如果第I+1盏灯是亮的，那么第I盏灯在下一秒会变化它的状态；特别的，如果第1盏灯是亮的，那么第N盏灯在下一秒会变化它的状态。
Arthur King给你某一时刻所有灯的状态，希望你能求出它们在M秒之后的状态。你正好想加入圆桌骑士的行列，赶快抓住这个机会，向Arthur King证明你的实力吧。

[输入描述]：
输入文件有N+1行。第一行有两个数N,M。此后N行，每行是一个数，不是0就是1。第I+1行的数描述初始时第I盏灯的状态。如果这个数为0，表示第I盏灯是灭的；如果这个数为1，表示第I盏灯是亮的。
20<N<500,2<M<200000

[输出描述]：
输出文件有N行，每行一个数，不是0就是1。第I行的数描述M秒后第I盏灯的状态。如果这个数为0，表示第I盏灯是灭的；如果这个数为1，表示第I盏灯是亮的。

[输入范例]：
3 1
0
0
1

[输出范例]：
0
1
1

4.强强的烦恼
[题目描述]:
新的赛季即将来临，强强将派出自己的球队---强强队去参加这来之不易的比赛，由于这场比赛非常重要，强强不光要考虑队员的体力和技术还必须考虑到整个球队队员的亲密程度，如果球队中出现一些亲密度较差的队员那么一定会影响这个比赛的成绩，这个问题使强强很伤脑筋，因为他训练的队员太多了，无法完全掌握所有队员之间的亲密度~~。再这样下去强强精神就要崩溃了，看来我们还是要想个办法帮帮他。
你设计了一个程序，由程序存入各个球员之间的信息，用来方便强强查询。

输入数据：第一行3个数N，M，K 表示有N个队员M个关系以及K次询问(1<N<=2000,1<=M<=500000,1<=K<=500000)
接下来M+K行，前M行给出A，B(A<>B   A B分别表示不同的两个队员的球衣编号A<=2000 B<=2000)两队员的关系（F表示亲密度较高 E表示亲密度较低）后K行为强强的询问
值得注意的是：如果A与B亲密度比较低 B与C亲密度也比较低那么A与C的亲密度就算为比较高咯
如果A与B亲密度比较高 B与C亲密度也比较高那么A与C的亲密度就算为比较高咯

[输入样例]:
5 4 4
1 2 F
2 3 F
1 4 E
4 5 E
1 5
1 3
2 4
2 5
[输出样例]注：输出K行如果询问的对象亲密度比较高则输出高如果亲密度比较低则输出低如果不清楚询问对象的关系那么就输出不知道
例：
高
高
不知道
高

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

回复列表（共35个回复）

11 楼

iAkiak [专家分：8460] 发布于 2005-12-23 18:26:00

哦，我明白了。只有高高和低低可以推导

12 楼

林木 [专家分：130] 发布于 2005-12-23 19:40:00

@3,bood
双斜杠里面的不算.

会有字符串出现

13 楼

林木 [专家分：130] 发布于 2005-12-23 19:45:00

@4,IakIAK
答案是不知道.

14 楼

dglllq [专家分：0] 发布于 2005-12-23 20:28:00

这四题都不容易,而且题目也不好理解!!!

15 楼

kmjim [专家分：90] 发布于 2005-12-23 21:19:00

#include<stdio.h>
int main()
{
    int flag=0;
    char pre,p;
    FILE *fin;
    fin=fopen("1.cpp","rt+");
    if(!fin)
    {
        printf("conn't open file 1.cpp\n");
        return 1;
    }

    p=fgetc(fin);
    if(flag==0 && p=='\"')  flag=1;
        else if(p=='\"')    flag=1;


    while(!feof(fin))
    {
        pre=p;
        p=fgetc(fin);

        switch(flag)
        {
            case 0:/* 一般情况 */
                if(p=='\"'){flag=1;break;}/* 进入“ 1 */
                if(pre=='/' &&p=='*') /*开始 2 */
                    {flag=2;break;}
            case 1:/* 离开“  0 */
                if(p=='\"')    flag=0;
                break;
            case 2:/*  */
                if(p=='*')/* 单独* 4 */
                    flag=3;
                else    putchar(p);
                break;
            case 3: /* 内部单独* */
                if(p=='/')  /* 结束 0 */
                {flag=0;break;}
                else if(p=='*') {putchar(pre);flag=3;break;}
                    else
                    {putchar(pre); flag=2;break;}

        }
    }
    fclose(fin);
    printf("\n");
    return 0;
}

16 楼

eastcowboy [专家分：25370] 发布于 2005-12-23 21:35:00

这次的程序加起来好长……

第一个：
特色：考虑了引号里面的情况，并且诸如
printf("abc\"abcd");
也能正确判断。
另外写了一个带缓存的GetChar函数。

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

#define GetChar My_GetChar
//#define GetChar getchar

/*标准的getchar效率可能比这个My_GetChar低下*/
int My_GetChar() /*带有缓冲区的getchar函数*/
{
    static char buf[1024] = {'\0'};
    static char *pc = buf;
    if( *pc=='\0' || pc>=(buf+sizeof(buf)/sizeof(*buf)) ) /*缓冲区空*/
    {   if( fgets( buf, sizeof(buf), stdin ) == NULL )
            return EOF;
        pc = buf;
    }
    return *pc++;
}

int main()
{
    int in_quote = 0;    /*开始时在引号外面*/
    int in_remark = 0;   /*开始时在注释外面*/
    int need_skip = 0;
    int c = ' ';
    int lastchar;
    while( 1 )
    {
        lastchar = c;
        if( (c=GetChar()) == EOF )
            break;
        switch( c )
        {
            case '\"':
                if( lastchar != '\\' )
                {   in_quote = !in_quote;   /*设置引号状态*/
                }
                break;
            case '/':
                if( !in_quote && GetChar()=='*' )
                {   in_remark = 1;
                    need_skip = 1;
                }
                break;
            case '*':
                if( !in_quote && GetChar()=='/' )
                {   in_remark = 0;
                    need_skip = 1;
                }
                break;
        }
        if( need_skip )
            need_skip = 0;
        else
            if( in_remark )
                putchar(c);  /* 如果在注释中，并且不需要跳过，把所得字符输出 */
    }
    system("pause");
    return 0;
}

17 楼

eastcowboy [专家分：25370] 发布于 2005-12-23 21:37:00

第二题：
#include<stdio.h>
#include<stdlib.h>

#define nCharactor 26

typedef struct node
{
    char data;
    struct node *children[nCharactor];
}NODE;

NODE *root = NULL;

NODE *CreateNewNode(char data) /*根据给定的data构造一个新的结点*/
{
    NODE *node;
    int i;
    node = malloc(sizeof(NODE));
    /*C++的话就写node = (NODE *)malloc(sizeof(NODE))*/
    node -> data = data;
    for(i=0;i<nCharactor;++i)
        node->children[i] = NULL;
    return node;
}

void AddToTree(char *s)
{
    NODE *p = root;
    NODE *temp;
    char c;
    while( (c=*s) != '\0' )
    {
        temp = p->children[ c-'A' ];
        if( temp != NULL )
            p = temp;
        else
        {   p->children[ c-'A' ] = CreateNewNode( c );
            p = p->children[ c-'A' ];
        }
        ++s;
    }
}

int CountTreeNodes(NODE *p)
{
    int ret = 0;
    int i;
    if( !p )
        return 0;
    for( i=0; i<nCharactor; ++i )
        ret += CountTreeNodes( p->children[i] );
    return ++ret;
}

int main()
{
    char word[64];
    root = CreateNewNode( '\0' );
    while( gets(word) != NULL )
        AddToTree( word );
    printf("%d\n",CountTreeNodes(root));
    system("pause");
    exit(0);    /*释放所有内存并退出*/
}

18 楼

eastcowboy [专家分：25370] 发布于 2005-12-23 21:38:00

第三个短一点，其实就是一个异或逻辑运算吧。不过可能有更快的算法，需要数学化简。
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int m,n;
    int i,j,tempstate;
    int state[500];
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)
        scanf("%d",state+i);
    --n;
    for(i=0;i<m;++i)
    {
        tempstate = state[0];
        for(j=0;j<n;++j)
            state[j] ^= state[j+1];
        state[n] ^= tempstate;
    }
    for(i=0;i<=n;++i)
        printf("%d\n",state[i]);
    system("pause");
    return 0;
}

19 楼

eastcowboy [专家分：25370] 发布于 2005-12-23 21:39:00

第四个，写得有点郁闷，看看错没有。（测试数据倒是通过了。以上几个也通过）
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>

int state[2001][2001] = {0};
int m,n,k;

int Check(int a,int b)
{
    int state_ab,state_ac,state_bc;
    int c;
    if( (state_ab=state[a][b]) != 0 )
        return state_ab;
    if( a>b )
    {   register t;
        t = a;  a = b;  b = t;
    }
    /*现在state[a][b] == 0*/
    state[a][b] = state[b][a] = -1; /*标记state[a][b]为“暂时不能计算”，避免死递归*/
    for(c=1;c<=n;++c)
    {
        if( c==a || c==b )
            continue;
        if( (state_ac=Check(a,c)) == -1 )
            continue;
        if( (state_bc=Check(b,c)) == -1 )
            continue;
        if( state_ac=='F' && state_bc=='F' )
            return state[a][b] = state[b][a] = 'F';
        if( state_ac=='E' && state_bc=='E' )
            return state[a][b] = state[b][a] = 'F';
    }
    /*还原state[a][b]的值*/
    state[a][b] = state[b][a] = 0;
    return -1;
}

int main()
{
    int i;
    int a,b;
    char ch;
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<m;++i)
    {   scanf("%d%d",&a,&b);
        while( isspace(ch=getchar()) )
            ;
        state[a][b] = state[b][a] = ch;
    }
    for(a=1;a<=n;++a)
        for(b=a+1;b<=n;++b)
            Check(a,b);
    for(i=0;i<k;++i)
    {   scanf("%d%d",&a,&b);
        switch(state[a][b])
        {
            case 'F':
                printf("高\n");
                break;
            case 'E':
                printf("低\n");
                break;
            default:
                printf("不知道\n");
                break;
        }
    }
    system("pause");
    return 0;
}

20 楼

iAkiak [专家分：8460] 发布于 2005-12-23 22:46:00

第2题eastcowboy提示我说单词数量不一定是512，确实有道理。我改改：
// 2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char buf[32768];
char* name[16384];
int cover(char *a, char *b)
{
    int i = 0;
    for (; *a && *b; a++, b++, i++)
        if (*a < *b)
            break;
    return i;
}
typedef char * String;
int cmp(const void*a, const void*b)
{
    return strcmp(*(const String*)a,*(const String*)b);
}
int main()
{
    int i, count, sum, lastlen, len;
    char *pBuf = buf;
    for(i = 0; i < 16384 && scanf("%s", pBuf) == 1; i++)
        name[i] = pBuf, pBuf += strlen(pBuf) + 1;
    count = i;
    if (count == 0)
    {
        printf("1\n");
        return 0;
    }
    qsort(name, count, sizeof(char *), cmp);
    sum = lastlen = strlen(name[0]);
    for (i = 1; i < count; i++)
    {
        len = cover(name[i-1], name[i]);
        lastlen = len;
        sum += strlen(name[i]) - len;
    }
    printf("%d\n", sum + 1);
    return 0;
}

我来回复

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

主题：[讨论]第八次编程比赛题目

回复列表（共35个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[讨论]第八次编程比赛题目

回复列表 （共35个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共35个回复）