主题：[原创][讨论][交流]编程高手的超级训练题解析
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
回复列表 （共83个回复）
61 楼
vcacm [专家分：1500] 发布于 2007-04-18 10:23:00
[quote]
[root@localhost gcc-6]# ./gc6-1
10
=======The best kind way is=============
1 2 3 4 7 6 5 8 9 10
12 29 38 33 40 67 42 65 62 69
11 30 41 56 57 70 97 84 95 98
18 23 48 53 50 81 100 79 72 59
13 24 19 54 47 32 51 88 85 78
16 37 34 49 60 71 80 93 64 73
15 22 25 58 43 96 77 86 87 76
14 39 28 31 36 35 74 63 94 55
17 44 45 52 61 66 83 68 99 82
20 27 26 21 46 91 90 89 92 75
To compute of the num of 10 should cost 770.000000 seconds!
[root@localhost gcc-6]# ./gc6-1
9
=======The best kind way is=============
1 2 3 4 7 6 5 8 9
10 21 38 75 52 61 42 65 74
13 40 63 64 37 46 55 48 23
16 27 34 19 24 43 54 53 56
15 26 45 22 49 30 59 44 57
14 33 28 25 78 71 68 69 80
17 20 39 58 73 66 35 62 47
12 41 32 51 76 31 36 77 60
11 18 29 50 81 70 67 72 79
To compute of the num of 9 should cost 69710.000000 seconds!
[root@localhost gcc-6]#
[/quote]
62 楼
vcacm [专家分：1500] 发布于 2007-04-18 10:26:00
[code]
我的程序无法在[color=FF00FF]1秒以内[/color]通过所有测试数据,哪位高手可以做到在
1秒以内通过1<=N<=10 这十个测试数据!
[color=FF00FF]
麻烦把程序贴出来,并说说你的解法!
-----------THANKS!
[/color]
[/code]
63 楼
vcacm [专家分：1500] 发布于 2007-04-19 12:11:00
[color=FF00FF]<gcc-24-3 :>麻烦各位帮我看一下,这个程序错在哪 ?
[/color]
[code]
/* * * =========================* * *
Input Sample:
2 3
1 1 2 3 3 2
1 2
1 2
------------- 2 1
3 2
2 5
2 4
Output Sample:
10
* * * =========================* * */
#include <stdio.h>
#include <stdlib.h>
#define MAX 21
#define false 0
#define true 1
typedef struct node
{
int fg;
int med ;
int tie ;
int over;
}Node ;
struct save
{
Node sa[MAX] ;
}op[MAX] ;
struct time
{
int begin ;
int mid ;
int end ;
}time[MAX] ;
int a[MAX] ;
int flag[MAX] ;
int m,n ;
int main (int argc, char *argv[])
{
int i,j,k ;
int su[MAX] ;
int t1,t2,t3,t4,t5,fa ;
int max_time = 0 ;
memset( a, 0 ,sizeof(a) );
memset( time,0 , sizeof(time) ) ;
memset(op , 0 , sizeof(op) ) ;
memset(flag , 0 , sizeof(flag) ) ;
scanf("%d %d",&m, &n) ;
for(i= 1 ; i<= m * n ;i++)
scanf("%d",&a[i]) ;
for(i= 1 ; i<= n; i++)
{
for(j=1 ; j<= m ; j++)
scanf("%d",&op[i].sa[j].med) ;
}
for(i= 1 ; i<=n ; i++)
{
for(j=1 ; j<= m ; j++)
scanf("%d",&op[i].sa[j].tie) ;
}
for(i= 1 ; i<= n ; i++)
{
for(j=1 ; j<=m ; j++)
op[i].sa[j].fg = false ;
}
[/code]
64 楼
vcacm [专家分：1500] 发布于 2007-04-19 12:14:00
[code]
/* Beging to Compute */
for(k = 1 ; k <= m*n ; k++ )
//if ( flag[a[k]] == 0 || (op[a[k]].sa[flag[a[k]]-1].fg &&
{
flag[a[k]]++ ;
op[a[k]].sa[flag[a[k]]].fg = true ;
if(flag[a[k]]== 1 )
{
t1 = time[op[a[k]].sa[1].med].begin ;
t2 = time[op[a[k]].sa[1].med].mid ;
t3 = time[op[a[k]].sa[1].med].end ;
t4 = op[a[k]].sa[1].tie ;
if ( t2 - t1 > t4)
{
t1 += t4 ;
op[a[k]].sa[1].over = t1 ;
time[op[a[k]].sa[1].med].begin = t1 ;
}
[/code]
65 楼
vcacm [专家分：1500] 发布于 2007-04-19 12:14:00
[code]
else if ( t1 == t2 )
{
t3 += t4 ;
time[op[a[k]].sa[1].med].begin = t3 ;
time[op[a[k]].sa[1].med].mid = t3 ;
time[op[a[k]].sa[1].med].end = t3 ;
op[a[k]].sa[1].over = t3 ;
}
else
{
t3 += t4 ;
op[a[k]].sa[1].over = t3 ;
time[op[a[k]].sa[1].med].end = t3 ;
}
}
[/code]
66 楼
vcacm [专家分：1500] 发布于 2007-04-19 12:15:00
[code]
else
{
fa = flag[a[k]] ;
t1 = time[op[a[k]].sa[fa].med].begin ;
t2 = time[op[a[k]].sa[fa].med].mid ;
t3 = time[op[a[k]].sa[fa].med].end ;
t4 = op[a[k]].sa[fa].tie ;
t5 = op[a[k]].sa[fa-1].over ;
if ( t1 >= t5 && t2-t1 >= t4)
{
t1 += t4 ;
op[a[k]].sa[fa].over = t1 ;
time[op[a[k]].sa[fa].med].begin = t1 ;
}
else if( t3 >= t5 )
{
t3 += t4 ;
op[a[k]].sa[fa].over = t3 ;
if( t2 - t1 == 0 )
{
time[op[a[k]].sa[fa].med].begin = t3 ;
time[op[a[k]].sa[fa].med].mid = t3 ;
}
time[op[a[k]].sa[fa].med].end = t3 ;
}
else if ( t3 < t5 )
{
time[op[a[k]].sa[fa].med].mid = t3 ;
t3 = t5 + t4 ;
op[a[k]].sa[fa].over = t3 ;
time[op[a[k]].sa[fa].med].begin = t2 ;
time[op[a[k]].sa[fa].med].end = t3 ;
}
}
}
for(i=1 ; i<= m ; i++)
if (time[i].end > max_time )
max_time = time[i].end ;
printf("\n ======the best time is %d =======\n",max_time ) ;
return 0 ;
}
[/code]
67 楼
vcacm [专家分：1500] 发布于 2007-04-20 16:14:00
[color=FF00FF]
gcc-24-3 参考答案: 终于被我AC了!
前面我写得那个程序太复杂了!
我现在换了一种技巧来"摸拟"!
用"0"来表示空闲时间, 用"1"来表示不可用时间!
虽然此时的时间复杂度为: O(m * n * max_time) !
但由于题目中的数据较小!
全0.0000sAC!
从总体分析!
[/color]
[code]
#include <stdio.h>
#define MAX 21
#define MAX_NUM 501
struct node
{
int time[MAX] ;
int mede[MAX] ;
}op[MAX] ; // op save the message of time and medicine
int mt[MAX][MAX_NUM] ;// the medecine
int m , n ;
int a[MAX*MAX+1] ; // the opeator order !
int num[MAX] ; // save the thing
int save[MAX][MAX] ; //the save of the last time !
int max_time = 0 ;
int main(int argc, char *argv[])
{
int i, j , k , q , h ;
int pa,pt,pk, t,t1,t2,t3,place ;
/* Init the array */
memset ( save , 0 , sizeof(save) ) ;
memset (num , 0 ,sizeof(num ) ) ;
memset (a , 0 , sizeof(a) ) ;
memset (op , 0 , sizeof(op) ) ;
memset (mt , 0 , sizeof(mt) ) ;
/* Output the message !*/
scanf("%d %d",&m ,&n ) ;
for(i= 1 ; i<= m*n ; i++)
scanf("%d",&a[i]) ;
for(i = 1; i<=n ; i++)
for(j = 1; j<=m ; j++)
scanf("%d",&op[i].mede[j]) ;
for(i = 1; i<=n ; i++)
for(j=1 ; j<= m ; j++)
scanf("%d",&op[i].time[j]) ;
/* Begin to compute */
for(k = 1 ; k<= m *n ; k++)
{
num[a[k]]++ ;
pt = num[a[k]] ;
pk = op[a[k]].mede[pt] ;
t = op[a[k]].time[pt] ;
place = 0 ;
for( i= save[a[k]][pt-1]+1 ; ;i++ )
{
for(h = i ; h<= i+t-1; h++)
if(mt[pk][h] == 1)
break ;
if( h > i+t-1 )
{
place = i ;
break ;
}
}
for( j = place ; j<= place+t-1 ; j++)
mt[pk][j] = 1 ;
save[a[k]][pt] = place+t-1 ;
}
max_time = 0 ;
for( i=1 ; i<= n ; i++ )
if( save[i][m] > max_time )
max_time = save[i][m] ;
printf("%d\n",max_time ) ;
/*for(i=1; i<=n ; i++)
{
for(j=1; j<= m ; j++)
printf("%d ", op[i].mede[j]) ;
printf("\n") ;
}*/
return 0 ;
}
[/code]
68 楼
vcacm [专家分：1500] 发布于 2007-04-23 17:36:00
[code]
[color=FF00FF]怎么啦!
[/color]
[color=FFF00]
PFAN最近好像不景气[/color][color=FF00FF]^--^[/color]
[/code]
69 楼
freeeerf [专家分：5440] 发布于 2007-05-02 18:40:00
楼主可否把修改签名弄短点,看得有点辛苦.
70 楼
vcacm [专家分：1500] 发布于 2007-05-02 21:13:00
[quote]楼主可否把修改签名弄短点,看得有点辛苦.[/quote]
好的....
我来回复
您所在位置：