主题：[讨论]第八次编程比赛题目
林木
[专家分：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行 如果询问的对象亲密度比较高则输出 高 如果亲密度比较低则输出 低 如果不清楚询问对象的关系那么就输出 不知道
例：
高
高
不知道
高
回复列表 （共35个回复）
沙发
zhangmou [专家分：14200] 发布于 2005-12-23 14:42:00
占个沙发.支持..支持~
出拉四个题目啊..~~
板凳
sirfarming [专家分：1790] 发布于 2005-12-23 16:42:00
/*1*/
#include "stdio.h"
unsigned char program[2000];
void input(){
char s[200];
/* freopen("remline.in","r",stdin);*/
while(!feof(stdin) && gets(s)){
strcat(program,s);
strcat(program,"\n");
}
}
void work(){
char *p,*b;
for(p=program;*p;){
for(;*p && !(*p=='/' && p[1]=='*');p++){
if(*p=='"'){
p++;
for(;*p && *p!='"';p++){
if(*p=='\\') p++;
}
}
}
p++;p++;b=p;
for(;*p && !(*p=='*' && p[1]=='/');p++);
*p='\0';printf("%s",b);*p='*';
p++;p++;
}
}
int main(){
input();
work();
return 0;
}
/*2*/
#include <stdio.h>
typedef struct linklist{
char data;
struct linklist *child; /* 第1个孩子 */
struct linklist *next; /* 下1个兄弟 */
}LinkList;
LinkList root={'\0',NULL,NULL};
int count=1;
void print(){
printf("%d\n",count);
}
void insert(char *word){
char c;
LinkList *pThis,*pBrother,*pFather,*pNew;
pThis=&root;
for(;c=*word;word++){
pFather=pThis;
pThis=pThis->child;
pBrother=NULL;
while(pThis && pThis->data<c){
pBrother=pThis;
pThis=pThis->next;
}
if(!pThis|| pThis->data!=c){
count++;
pNew=(LinkList*)malloc(sizeof(LinkList));
pNew->data=c;
pNew->child=NULL;
pNew->next=pThis;
if(pBrother){
pBrother->next=pNew;
}else{
pFather->child=pNew;
}
pThis=pNew;
}
}
}
void work(){
char word[64];
/* freopen("trie.in","r",stdin);*/
while(!feof(stdin)){
gets(word);
if(!*word) break;
insert(word);
}
}
int main(){
work();
print();
return 0;
}
/*3*/
#include <stdio.h>
#define LIGHT 500
int n;
long m;
unsigned char data[LIGHT];
void print(){
int i;
for(i=0;i<n;i++){
printf("%d\n",data[i]);
}
}
void input(){
int i;
/* freopen("light.in","r",stdin);*/
scanf("%d %ld",&n,&m);
for(i=0;i<n;i++){
scanf("%d",data+i);
}
}
void work(){
int i;
long j;
for(j=0;j<m;j++){
data[n]=data[0];
for(i=1;i<=n;i++){
if(data[i]){
data[i-1]=!data[i-1];
}
}
}
}
int main(){
input();
work();
print();
return 0;
}
/*4*/
#include <stdio.h>
#define put(a,b,fe) data[a*n+b]=data[b*n+a]=fe
#define get(a,b) data[a*n+b]
char *data;
int n;
long m,k;
void print(){
int a,b;
long i;
for(i=0;i<k;i++){
scanf("%d %d",&a,&b);
a--;b--;
switch(get(a,b)){
case 'F':
printf("高\n");
break;
case 'E':
printf("低\n");
break;
default:
printf("不知道\n");
break;
}
}
free(data);
}
void input(){
/* freopen("qqdfn.in","r",stdin);*/
scanf("%d %ld %ld",&n,&m,&k);
data=(char*)malloc(n*n);
if(!data){
printf("no enough memory!\a");
exit(1);
}
memset(data,'.',n*n);
}
void alter(int x,int y,char fe){
int j;
char *getxj,*getyj;
getxj=data+x*n;getyj=data+y*n;
for(j=0;j<n;j++,getxj++,getyj++){
if(j==y) continue;
if((*getxj)==fe && (*getyj)!='F'){
put(j,y,'F');
alter(j,y,'F');
}
}
getxj=data+x*n;getyj=data+y*n;
for(j=0;j<n;j++,getxj++,getyj++){
if(j==x) continue;
if((*getyj)==fe && (*getxj)!='F'){
put(x,j,'F');
alter(x,j,'F');
}
}
}
void work(){
int a,b;
long i;
char fe;
for(i=0;i<m;i++){
/* read a,b,fe */
scanf("%d %d %c",&a,&b,&fe);
/* put a,b,fe */
a--;b--;
put(a,b,fe);
/* alter data */
alter(a,b,fe);
}
}
int main(){
input();
work();
print();
return 0;
}
抱歉,第3题没想到好的法子,凑个完整吧.
3 楼
bood [专家分：490] 发布于 2005-12-23 17:26:00
第一题描述不清阿
1. //类型的注释如何处理
2. 源代码有没有字符串，实际上"/*"/*abc*/中引号内的/*是不作为注释的
4 楼
eastcowboy [专家分：25370] 发布于 2005-12-23 17:43:00
是。第一题没有想象中的简单。需要考虑引号。我写了一个，不过要等全都写好了才发上来。
5 楼
boxertony [专家分：23030] 发布于 2005-12-23 18:06:00
/*1*/
#include <stdio.h>
#include <conio.h>
void OutputComments(const char *szFileName)
{
FILE *fp;
if((fp = fopen(szFileName, "rt")) == NULL)
{
printf("Cannot open %s.\n", szFileName);
return;
}
char ch1, ch2;
bool bInComment = false;
while(!feof(fp))
{
ch1 = fgetc(fp);
if(ch1 == '/')
{
ch2 = fgetc(fp);
if(ch2 == '*')
{
bInComment = true;
}
else if(bInComment == true)
{
putchar(ch1);
putchar(ch2);
}
}
else if(ch1 == '*')
{
ch2 = fgetc(fp);
if(ch2 == '/')
{
bInComment = false;
}
else if(bInComment == true)
{
putchar(ch1);
putchar(ch2);
}
}
else
{
if(bInComment == true)
{
putchar(ch1);
}
}
}
fclose(fp);
}
int main()
{
char szFileName[256];
printf("input a file name: ");
scanf("%s" , szFileName);
OutputComments(szFileName);
printf("\n");
getch();
return 0;
}
/*2*/
没时间写了。
/*3*/
#include <stdio.h>
#include <conio.h>
#include <assert.h>
void ArthurKing(const char *szInFile, const char *szOutFile)
{
FILE *fpIn, *fpOut;
if((fpIn = fopen(szInFile, "rt")) == NULL)
{
return;
}
int n, m;
char *stat; // status
fscanf(fpIn, "%d %d", &n, &m);
assert(n >= 0 && m >= 0);
stat = new char[n];
assert(stat);
for(int i=0; i<n; ++i)
{
fscanf(fpIn, "%d", stat+i);
}
fclose(fpIn);
char stat0;
for(i=0; i<m; ++i)
{
stat0 = stat[0];
for(int j=0; j<n-1; ++j)
if(stat[j+1] == 1)
stat[j] = !stat[j];
if(stat0 == 1)
stat[n-1] = !stat[n-1];
}
if((fpOut = fopen(szOutFile, "wt")) == NULL)
{
delete[] stat;
return;
}
for(i=0; i<n; ++i)
{
fprintf(fpOut, "%d\n", stat[i]);
}
fclose(fpOut);
delete []stat;
}
int main()
{
ArthurKing("in.txt", "out.txt");
getch();
return 0;
}
6 楼
boxertony [专家分：23030] 发布于 2005-12-23 18:07:00
/*4*/
#include <stdio.h>
#include <conio.h>
#include <assert.h>
#include <string.h>
#define MaxSize 200
typedef struct
{
char friendliness[MaxSize][MaxSize];
int n; // 球员数
}Relation;
void Change(Relation *rel, int v1, int v2, char relation)
{
for(int j=0; j<rel->n; ++j)
{
if(v1 != j && v2 != j)
{
if(rel->friendliness[v1][j] == relation)
{
if(rel->friendliness[v2][j] != 'F')
{
rel->friendliness[v2][j] = 'F';
rel->friendliness[j][v2] = 'F';
Change(rel, v2, j, 'F');
}
}
else if(rel->friendliness[v2][j] == relation)
{
if(rel->friendliness[v1][j] != 'F')
{
rel->friendliness[v1][j] = 'F';
rel->friendliness[j][v1] = 'F';
Change(rel, v1, j, 'F');
}
}
}
}
}
void Judge()
{
// FILE *fp;
/* if((fp = fopen("relation.txt", "rt")) == NULL)
{
return;
}*/
int n, m, k;
Relation *rel = new Relation;
memset(rel, 0, sizeof(Relation));
assert(rel);
// fscanf(fp, "%d%d%d", &n, &m, &k);
scanf("%d%d%d", &n, &m, &k);
rel->n = n;
int v1, v2;
char relation;
for(int i=0; i<m; ++i)
{
// fscanf(fp, "%d%d %c ", &v1, &v2, &relation);
scanf("%d%d %c ", &v1, &v2, &relation);
rel->friendliness[v1-1][v2-1] = relation;
rel->friendliness[v2-1][v1-1] = relation;
Change(rel, v1-1, v2-1, relation);
}
for(i=0; i<k; ++i)
{
// fscanf(fp, "%d%d", &v1, &v2);
scanf("%d%d", &v1, &v2);
if(rel->friendliness[v1-1][v2-1] == 'F')
printf("高\n");
else if(rel->friendliness[v1-1][v2-1] == 0)
printf("不知道\n");
}
// fclose(fp);
}
int main()
{
Judge();
getch();
return 0;
}
7 楼
iAkiak [专家分：8460] 发布于 2005-12-23 18:13:00
第4题，如果是这样的情况：
A-B 高
B-C 高
A-C 高
B-D 高
C-D 低
那么A-D的关系应该是什么？
8 楼
iAkiak [专家分：8460] 发布于 2005-12-23 18:16:00
//1
#include <stdio.h>
enum State
{
Begin,
Code = Begin,
Quote,
QuoteSlash,
SingleQuote,
SingleQuoteSlash,
Comment,
};
int main()
{
int c;
State s = Code;
while(!feof(stdin))
{
c = fgetc(stdin);
switch(s)
{
case Code:
if (c == '\"')
s = Quote;
else if (c == '\'')
s = SingleQuote;
else if (c == '/')
{
c = fgetc(stdin);
if (c == '*')
s = Comment;
}
break;
case Quote:
if (c == '\"')
s = Code;
else if (c == '\\')
s = QuoteSlash;
break;
case QuoteSlash:
s = Quote;
break;
case Comment:
if (c == '*')
{
c = fgetc(stdin);
if (c == '/')
{
s = Code;
break;
}
}
printf("%c", c);
break;
case SingleQuote:
if (c == '\'')
s = Code;
else if (c == '\\')
s = SingleQuoteSlash;
break;
case SingleQuoteSlash:
s = SingleQuote;
break;
}
}
return 0;
}
// 2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char buf[512][64];
char* name[512];
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;
for(i = 0; i < 512 && scanf("%s", buf[i]) == 1; i++)
name[i] = buf[i];
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;
}
9 楼
iAkiak [专家分：8460] 发布于 2005-12-23 18:17:00
//3
#include <stdio.h>
#include <string.h>
typedef unsigned char BYTE;
BYTE getCharNext(BYTE n, int left) // ¸ßλÔÚ
{
int i;
BYTE n2 = 0;
for (i=0;i<7;i++)
{
if (!!(n & (1<<i)) + !!(n & (1<<i+1)) == 1)
n2 |= 1<<i;
}
if (!!(n & 0x80) + !!left == 1)
n2 |= 0x80;
return n2;
}
int main()
{
BYTE next[2][256];
BYTE d[128] = {0};
BYTE *d1, *d2, *dt;
int i, n, m, t, j;
for (i = 0; i < 256; i++)
{
next[0][i] = getCharNext(i, 0);
next[1][i] = getCharNext(i, 1);
}
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
{
scanf("%d", &t);
if (t)
{
d[i>>3] |= 1<<(i&7);
}
}
d1 = d;
d2 = d+64;
for (i = 0; i < m; i++)
{
memset(d2, 0, 64);
for (j = 0; j < n/8; j++)
{
d2[j] = next[d1[j+1] & 1][d1[j]];
}
if (n & 7)
{
if (d1[0] & 1)
d1[j] |= 1<<(n&7);
d2[j] = next[d1[0] & 1][d1[j]] & ((1<<(n&7)) - 1);
}
dt = d1, d1 = d2, d2 = dt;
/*
for (j = 0; j < n; j++)
{
printf("%d", d1[j>>3] & (1<<(j&7)) ? 1 : 0);
}
printf("\n");
*/
}
for (i = 0; i < n; i++)
{
printf("%d\n", d1[i>>3] & (1<<(i&7)) ? 1 : 0);
}
return 0;
}
10 楼
boxertony [专家分：23030] 发布于 2005-12-23 18:19:00
呵呵，没有考虑到字符串里面的情况了。
考虑到双引号就比较麻烦了，得考虑双引号里的/*＆*/，还得考虑注释里的双引号。
我来回复
您所在位置：