主题：[原创][讨论][交流]编程高手的超级训练题解析
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个回复）
51 楼
vcacm [专家分：1500] 发布于 2007-04-16 21:35:00
[code]
续...............
int do_10_to_other (int b[], int s[], int p ,int lb)
{
int c[MAX] ;
int i,j,k,mod ;
int ls = 0, lc = 0 ;
while ( (lb >1) || (lb == 1 && b[1] > 0 ) )
{
memset(c , 0 , sizeof(c) );
lc = 0 ;
for(i= lb ; i>=1 ;i-- )
{
if( b[i] < p)
{
if ( lc >= 1)
{
c[++lc] = b[i] / p ;
}
if ( i > 1)
b[i-1] += b[i] * 10 ;
else
mod = b[i] % p ;
}
else
{
c[++lc] = b[i] / p ;
mod = b[i] % p ;
if( i> 1)
b[i-1] += mod * 10 ;
}
}
s[++ls] = mod ;
for(j= 1 ,k= lc ; j<=lc ; j++,k--)
b[k] = c[j] ;
lb = lc ;
}
return ls ;
}
int main(int argc, char *argv[])
{
int a[MAX]={0} ,s[MAX]={0} , b[MAX],st[MAX] ;
int la=0 , ls = 0 , lb = 0 ;
int i,j,k ;
int m,n,p ;
char c1,c2 ;
while ( (c1=getchar())!= '<') //&& c1 >= '0' && c1 <= '9')
{
if( c1 >= '0' && c1 <= '9' )
st[++la] = (int) (c1-'0') ;
}
scanf("%d", &n) ;
c1 = getchar() ;
scanf("%d", &p ) ;
for(i=1 , j= la ; j>=1 ; j--, i++)
a[j] = st[i] ;
if( n != 10 && p != 10 )
{
lb = change_to_10 ( a, b , n , la ) ;
ls = do_10_to_other(b, s , p ,lb ) ;
}
else if( n!= 10 && p == 10 )
{
ls = change_to_10 ( a , s, n , la ) ;
}
else if( n == 10 && p != 10 )
{
ls = do_10_to_other(a,s, p ,la) ;
}
else
{
//memory (&s[1], &a[1] , sizeof(int)* la ) ;
for(i=1 ; i<= la ; i++)
s[i] = a[i] ;
ls = la ;
}
for( i= ls ; i>=1 ; i--)
printf("%d ", s[i] );
/*#if need
for(i=1 ; i<=la ; i++)
printf("%d ",a[i]) ;
printf("%d %d",n, p );
#endif*/
return 0 ;
}
[/code]
52 楼
vcacm [专家分：1500] 发布于 2007-04-17 08:39:00
[quote]
学习计划:
一. 基础知识巩固
1. 数据结构
(1)数组,高级数组(树状数组)
(2)动态分配(指针的高级应用)
(3)链表,高级链表
(4)栈,顺序栈与链栈(表达式计算)
(5)队列,优先队列
(6)字符串操作,串匹配(KMP算法)
(7)树的高级应用(二叉树,平衡树,线段树等),表达式求值
(8)图的经典算法(DFS,BFS,MST,最短路径等), (prim,Djiskatra,kual)
(9)网络: 网络流,图的连通性问题,最小费用流,最大流等问题
(10)各种数据结构的综合应用
2.算法设计与分析
(1)递归与分治( 二分法,大数运算等)
(2)搜索算法(DFS,BFS,穷举法,回溯法,分枝限界法,以各种搜索算法的巧妙结合算法等)
(3)贪心算法(要学习证明,识别贪心选择性的正确与否)
(4)动态规划 (此法必须熟能生巧,知道什么样的问题可以用DP去解)(掌握滚动数组与DP 的 巧妙 应用)
(5)网络流算法(此法也必须撑握)
(6)线性规划
二.读经典书.
1. <<算法艺术与信息学竞赛>>
2.<<The art of compute program>>
3.<<编译原理>>
4.<<编程艺术>>
5.<<孙子兵法>>
6.<<数论>>
7.<<计算机组合学>>
8.<<程序调试技巧>>
9.<<算法设计与分析实验题解>>
三.系统全面地强化训练
1.系统强化数据结构(全部用代码实现)
2.语言技巧(充分利用C语言本身的优点,例如: 位运算, 指针等 去写出技术含量高的代码) 以及 (C语言的熟能生巧)
3.各种算法的经典运用,全部用代码去实现!
4.熟练各种算法 (算法设计与分析题解以及其它网上的有关资料)
5.针对各种问题的解决方法(做网上的题库,VIJOS,FLYIOI,以及其它OJ )
四.培养编程的感觉,和良好的考试心态
1.每周模拟训练: (时间:3小时 ; 题目: 历届竞赛题 或 其它省的选拔试题 )
2.学会怎样去发挥
3.培养考试的能力,创作出自己的一种做题技巧
4.每次训练后的小结
5.树立信心,力争400分
五.总结
1.总结平时的学习经验,吸取教训,从而避免在竞赛时出错
2.复习以前的学习笔记
3.复习C语言的各方面的知识(语法,注意事项等)
4.以一平常心去对待竞赛
5.考试技巧
[/quote]
53 楼
ttuurr [专家分：70] 发布于 2007-04-17 19:45:00
读经典书.
1. <<算法艺术与信息学竞赛>>
2.<<The art of compute program>>
3.<<编译原理>>
4.<<编程艺术>>
5.<<孙子兵法>>
6.<<数论>>
7.<<计算机组合学>>
8.<<程序调试技巧>>
9.<<算法设计与分析实验题解>>
楼上的有上面列出的电子书吗？
54 楼
vcacm [专家分：1500] 发布于 2007-04-18 09:40:00
[quote]读经典书.
1. <<算法艺术与信息学竞赛>>
2.<<The art of compute program>>
3.<<编译原理>>
4.<<编程艺术>>
5.<<孙子兵法>>
6.<<数论>>
7.<<计算机组合学>>
8.<<程序调试技巧>>
9.<<算法设计与分析实验题解>>
楼上的有上面列出的电子书吗？[/quote]
[code]
只有第九本没有,其它的都有!
你也要吗?
[/code]
55 楼
vcacm [专家分：1500] 发布于 2007-04-18 09:43:00
[code]
[color=FF00FF]
GCC-6-1 的解答:
主要有两种方法:
[/color]
/* * * =======name : gcc-6-1.c==========* * *
Input : 2
output: 1 2
4 3
* * * =================================* * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <time.h>
#define MAX 11
#define true 1
#define false 0
#define INF 10001
int f[MAX*MAX+1],flag = 0 ;
int N ,total = 0 ;
int chose = 0 , save = INF ;
int a[MAX][MAX],s[MAX][MAX] ;
int pr[INF], lp = 0 ;
void output ()
{
int i,j,sum=0 ;
//printf("\n========The %d kind way !=========\n",total) ;
sum += a[1][1] ;
for(i= 2 ; i<= N ; i++)
sum += a[1][i]+ a[i][1] ;
if ( sum < save)
{
save = sum ;
chose = total ;
for(i=1 ; i<=N ; i++)
for(j=1 ; j<=N ; j++)
s[i][j] = a[i][j] ;
}
/*for(i=1 ; i<= N ; i++)
{
for(j=1 ; j<=N ; j++)
printf("%d\t",a[i][j]) ;
printf("\n\n") ;
}
printf("\n") ;*/
}
void prime ()
{
int r,t,v ;
int h[INF] ;
v = 2 * N * N;
h[1] = false ;
for( r = 2 ; r <=v ; r++)
h[r] = true ;
for( t = 2 ; t <= v ; t++)
{
if( h[t] )
{
for(r = t+t;r <= v ; r+= t)
h[r] = false ;
}
}
for( t= 2 ; t<= v ; t++)
if(h[t])
pr[++lp] = t ;
}
[/code]
56 楼
vcacm [专家分：1500] 发布于 2007-04-18 09:43:00
[code]
int is_prime( int num )
{
int k ;
for(k=1 ; k<=lp ; k++)
if(num == pr[k])
return true ;
return false ;
}
/*int is_prime ( int num ) /if a prime or not *
{
register int k ;
if(num <= 1 )
return false ;
if(num == 2 )
return true ;
for(k = 2 ; k*k <= num ; k++)
if( num % k == 0)
return false ;
return true ;
}*/
int is_ok ( int x, int y ,int data) /* check the legal */
{
if( x== 1 && is_prime(data + a[x][y-1]) )
return true ;
if( y== 1 && is_prime(data + a[x-1][y]) )
return true ;
if( x > 1 && y > 1 && is_prime(data+a[x][y-1]) && is_prime(data + a[x-1][y] ) )
return true ;
return false ;
}
[/code]
57 楼
vcacm [专家分：1500] 发布于 2007-04-18 09:43:00
[code]
void try_do (int x, int y , int n )
{
int i,j,k ;
if ( n == N * N )
{
total ++ ;
output() ;
flag = 1 ;
//return 1 ;
}
else
{
if ( y == N +1 )
{
y = 1 ;
x = x + 1 ;
}
for(i = 2 ; i<= N*N ; i++)
if( !f[i] && is_ok(x,y,i) )
{
if(total >10)
break ;
f[i] = true ;
a[x][y] = i ;
try_do(x , y+1 , n+1 ) ;
f[i] = false ;
a[x][y] = 0 ;
}
}
/*if( flag )
return 1 ;
else
return 0 ;*/
}
int main(int argc, char *argv[])
{
int ans,p,q;
clock_t begin, end ;
scanf("%d",&N) ;
begin = clock() ;
memset(a, 0 , sizeof(a) ) ;
memset(f, 0 , sizeof(f) ) ;
memset(s, 0 , sizeof(s) ) ;
memset(pr, 0 , sizeof(pr) ) ;
prime() ;
a[1][1] = 1 ;
f[1] = 1 ;
try_do (1, 2 , 1 ) ;
if( flag == 0 )
printf("NO ANSERS!\n") ;
else
{
printf("\nThe best kind way is %d and his sum is %d \n",chose, save ) ;
for(p= 1 ; p<= N ; p++)
{
for(q= 1;q<= N ; q++)
printf("%d\t",s[p][q]);
printf("\n");
}
}
end = clock() ;
printf("\nTo compute of the num of %d should cost %f seconds!\n",N, (double)(end-begin)/1000 ) ;
return 0 ;
}
[/code]
58 楼
vcacm [专家分：1500] 发布于 2007-04-18 10:13:00
[code]
第二种方法:
/* * * =======name : gcc-6-1.c==========* * *
Input : 2
output: 1 2
4 3
* * * =================================* * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <time.h>
#define MAX 11
#define true 1
#define false 0
#define INF 1001
int f[MAX*MAX+1],flag = 0 ;
int N ,total = 0 ;
int a[MAX][MAX] ;
int pr[INF], lp = 0 ;
void prime ()
{
int r,t,v ;
int h[INF] ;
v = 2 * N * N;
h[1] = false ;
for( r = 2 ; r <=v ; r++)
h[r] = true ;
for( t = 2 ; t <= v ; t++)
{
if( h[t] )
{
for(r = t+t;r <= v ; r+= t)
h[r] = false ;
}
}
for( t= 2 ; t<= v ; t++)
if(h[t])
pr[++lp] = t ;
}
int is_prime( int num )
{
int k ;
for(k=1 ; k<=lp ; k++)
if(num == pr[k])
return true ;
return false ;
}
int is_ok ( int x, int y ,int data) /* check the legal */
{
if( x== 1 && is_prime(data + a[x][y-1]) )
return true ;
if( y== 1 && is_prime(data + a[x-1][y]) )
return true ;
if( x > 1 && y > 1 && is_prime(data+a[x][y-1]) && is_prime(data + a[x-1][y] ) )
return true ;
return false ;
}
[/code]
59 楼
vcacm [专家分：1500] 发布于 2007-04-18 10:14:00
[code]
void try_do (int x, int y , int n )
{
int i,j,k ;
if ( n == N * N )
{
flag = 1 ;
}
else
{
if ( y == N +1 && x == 1)
{
y = 1 ;
x = x + 1 ;
}
else if( x == N+1 )
{
y = y+1 ;
x = 2 ;
}
for(i = 2 ; i<= N*N ; i++)
if( !f[i] && is_ok(x,y,i) )
{
if( flag == 1 )
break ;
f[i] = true ;
a[x][y] = i ;
if( x == 1)
try_do(x , y+1 , n+1 ) ;
else
try_do(x+1,y ,n+1) ;
if( flag == 1)
break ;
f[i] = false ;
a[x][y] = 0 ;
}
}
}
int main(int argc, char *argv[])
{
int ans,p,q;
clock_t begin, end ;
scanf("%d",&N) ;
begin = clock() ;
memset(a, 0 , sizeof(a) ) ;
memset(f, 0 , sizeof(f) ) ;
prime() ;
a[1][1] = 1 ;
f[1] = 1 ;
try_do (1, 2 , 1 ) ;
if( flag == 0 )
printf("NO ANSERS!\n") ;
else
{
printf("\n=======The best kind way is=============\n") ;
for(p= 1 ; p<= N ; p++)
{
for(q= 1;q<= N ; q++)
printf("%d\t",a[p][q]);
printf("\n");
}
}
end = clock() ;
printf("\nTo compute of the num of %d should cost %f seconds!\n",N, (double)(end-begin)/1000 ) ;
return 0 ;
}
[/code]
60 楼
vcacm [专家分：1500] 发布于 2007-04-18 10:19:00
[quote]
[color=FF00FF]
测试结果如下:
[/color]
[root@localhost gcc-6]# ./gc6-1
5
=======The best kind way is=============
1 2 3 4 7
6 5 14 15 16
13 24 23 8 21
10 19 18 11 20
9 22 25 12 17
To compute of the num of 5 should cost 0.000000 seconds!
[root@localhost gcc-6]# ./gc6-1
1
=======The best kind way is=============
1
To compute of the num of 1 should cost 0.000000 seconds!
[root@localhost gcc-6]# ./gc6-1
2
=======The best kind way is=============
1 2
4 3
To compute of the num of 2 should cost 0.000000 seconds!
[root@localhost gcc-6]# ./gc6-1
4
=======The best kind way is=============
1 2 11 12
4 9 8 5
7 10 3 14
6 13 16 15
To compute of the num of 4 should cost 0.000000 seconds!
[root@localhost gcc-6]# ./gcc-6-1
4
The best kind way is 1 and his sum is 43
1 2 11 12
4 9 8 5
7 10 3 14
6 13 16 15
To compute of the num of 4 should cost 10.000000 seconds!
[/quote]
我来回复
您所在位置：