答题说明
以下共有13道题共68个空 程序要求输入题号 并输出对应答案。
注：每个空至多填入一行代码！
答案请不要输入多余的空格！
样例代码
请将68个空的答案按顺序填入S数组后提交至OJ。
#include <iostream>
#include <string>
using namespace std;
string S[100]={
"A", // 第1空
"666", // 第2空
"666", // 第3空
... // 第4~67空，按照一行一空填入(注意双引号和逗号)
"A" , // 第68空
};
int main(){
int a;
cin >> a;
cout << S[a-1];
return 0;
}
题目
1.（2007）第 27 题
完善程序:
（求字符的逆序）下面的程序的功能是输入若干行字符串 每输入一行 就按逆序输出该行 最后键入-1终止程序 请将程序补充完整
#include <iostream.h>
#include <string.h>
int maxline = 200, kz;
int reverse( char s[] )
{
int i, j, t;
for ( i = 0, j = strlen( s ) - 1; i < j; 【①】 , 【②】 )
{
t = s[i]; s[i] = s[j]; s[j] = t;
}
return(0);
}
void main()
{
char line[100];
cout << "continue? -1 for end." <<endl;
cin>>kz;
while(【③】)
{
cin >> line;
【④】;
cout << line << endl;
cout << "continue ? -1 for end." << endl;
cin >> kz;
}
}
(1)._______________________________
(2). _______________________________
(3). _______________________________
(4). _______________________________
2.（2007）第 28 题
完善程序：
（棋盘覆盖问题）在一个2k×2k个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为-1的方格）称之为特殊方格 现用L型（占3个小方格）纸片覆盖棋盘上除特殊方格的所有部分 各纸片不得重叠 于是，用到的纸片数恰好是(4k-1)/3 在下表给出的一个覆盖方案中 k=2 相同的3个数字构成一个纸片 下面给出的程序使用分治法设计的 将棋盘一分为四 依次处理左上角 右上角 左下角 右下角，递归进行 请将程序补充完整
2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5
#include <iostream.h>
#include <iomanip.h>
int board[65][65], tile; /* tile为纸片编号 */
void chessboard( int tr, int tc, int dr, int dc, int size )
/* dr,dc依次为特殊方格的行、列号 */
{
int t, s;
if ( size == 1 )
⑤ ；
t = tile++;
s = size / 2;
if ( ⑥ )
chessboard( tr, tc, dr, dc, s );
else{
board[tr + s -1][tc + s -1] = t;
[⑦];
}
if ( dr < tr + s && dc >= tc + s )
chessboard( tr, tc + s, dr, dc, s );
else{
board[tr + s -1][tc + s] = t;
⑧;
}
if ( dr >= tr + s && dc < tc + s )
chessboard( tr + s, tc, dr, dc, s );
else{
board[tr + s][tc + s -1] = t;
[⑨];
}
if ( dr >= tr + s && dc >= tc + s )
chessboard( tr + s, tc + s, dr, dc, s );
else{ board[tr + s][tc + s] = t;
[⑩]; }
}
void prtl( int b[][65], int n )
{
int i, j;
for ( i =1; i <= n; i++ )
{
for ( j =1; j <= n; j++ )
cout << setw( 3 ) << b[i][j];
cout << endl;
}
}
void main()
{
int size, dr, dc;
cout << "input size(4/8/16/64):" << endl;
cin >> size;
cout << "input the position of special block(x,y):" << endl;
cin >> dr >> dc;
board[dr][dc] = -1;
tile++;
chessboard( 1, 1, dr, dc, size );
prtl( board, size );
}
(5)_______________________________
(6). _______________________________
(7). _______________________________
(8). _______________________________
(9). _______________________________
(10). _______________________________
3.（2008）第 27 题
完善程序：
（字符串替换）给定一个字符串S（S仅包含大小写字母） 下面的程序将S中的每个字母用规定的字母替换 并输出S经过替换后的结果 程序的输入是两个字符串 第一个字符串是给定的字符串S 第二个字符串S’由26个字母组成 它是a-z的任一排列 大小写不定 S’规定了每个字母对应的替换字母 S’中的第一个字母是字母A和a的替换字母 即S中的A用该字母的大写替换 S中的a用该字母的小写替换 S’中的第二个字母是字母B和b的替换字母 即S中的B用该字母的大写替换 S中的b用该字母的小写替换 以此类推
#include <iostream>
#include <string.h>
char change[26], str[5000];
using namespace std;
void CheckChangeRule()
{
int i;
for (i = 0;i < 26;i ++)
{
if ( [ ① ] )
change[i] -= 'A' - 'a';
}
}
void ChangeString()
{
int i;
for (i = 0;i <strlen(str);i ++)
{
if ( [ ② ] )
str[i] = change[str[i] - 'A'] -'a' + 'A';
else
[ ③ ]
}
}
int main()
{
int i;
cin >> str ;
cin >> change;
CheckChangeRule();
[ ④ ]
cout << str << endl;
return 0;
}
(11). _______________________________
(12). _______________________________
(13). _______________________________
(14). _______________________________
4.（2008）第 28 题
完善程序：
(找第k大的数) 给定一个长度为1000000的无序正整数序列 以及另一个数n (1<=n<=1000000) 然后以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1 2 3 4 5 6}中第3大的数是4）
#include <iostream>
using namespace std;
int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
int c;
c = a;
a = b;
b = c;
}
int FindKth(int left, int right, int n)
{
int tmp,value,i,j;
if (left == right) return left;
tmp = rand()% (right - left) + left;
swap(a[tmp],a[left]);
value =[ ① ];
i = left;
j = right;
while (i < j)
{
while (i < j && [ ② ]) j --;
if (i < j) {a[i] = a[j]; i ++;} else break;
while (i < j && [ ③ ]) i ++;
if (i < j) {a[j] = a[i]; j - -;} else break;
}
[ ④ ]
if (i < n) return FindKth([ ⑤ ] );
if (i > n) return [ ⑥ ]
return i;
}
int main()
{
int i;
int m = 1000000;
for (i = 1;i <= m;i ++)
cin >> a[i];
cin >> n;
ans = FindKth(1,m,n);
cout << a[ans];
return 0;
}
(15). _______________________________
(16). _______________________________
(17). _______________________________
(18). _______________________________
(19). _______________________________
(20). _______________________________
5.（2009）第 27 题
完善程序：
（最大连续子段和）给出一个数列（元素个数不多于100） 数列元素均为负整数 正整数 0 请找出数列中的一个连续子数列 使得这个子数列中包含的所有元素之和最大 在和最大的前提下还要求该子数列包含的元素个数最多 并输出这个最大和以及该连续子数列中元素的个数 例如数列为4 -5 3 2 4时 输出9和3 数列为1 2 3 -5 0 7 8时 输出16和7
#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg;
int main(){
cin >> n;
for (i=1;i<=n;i++)
cin >> a[i];
tmp=0;
ans=0;
len=0;
beg= [ ① ] ;
for (i=1;i<=n;i++){
if (tmp+a[i]>ans){
ans=tmp+a[i];
len=i-beg;
}
else if ( [ ② ] &&i-beg>len)
len=i-beg;
if (tmp+a[i] [ ③ ] ){
beg= [ ④ ] ;
tmp=0;
}
else
[ ⑤ ];
}
cout << ans << " " << len << endl;
return 0;
}
(21). _______________________________
(22). _______________________________
(23). _______________________________
(24). _______________________________
(25). _______________________________
6.（2009）第 28 题
完善程序：
(国王放置) 在n*m的棋盘上放置k个国王 要求k个国王互相不攻击 有多少种不同的放置方法 假设国王放置在第(x,y)格 国王的攻击的区域是:(x-1,y-1) (x-1,y) (x-1,y+1) (x,y-1) (x,y+1) (x+1,y-1) (x+1,y) (x+1,y+1) 读入三个数n m k 输出答案 题目利用回溯法求解 棋盘行标号为0n-1 列标号为0m-1
#include <iostream>
using namespace std;
int n,m,k,ans;
int hash[5][5];
void work(int x,int y,int tot){
int i,j;
if (tot==k){
ans++;
return;
}
do{
while (hash[x][y]){
y++;
if (y==m){
x++;
y=[ ① ];
}
if (x==n)
return;
}
for (i=x-1;i<=x+1;i++)
if (i>=0&&i<n)
for (j=y-1;j<=y+1;j++)
if (j>=0&&j<m)
[ ② ];
[ ③ ];
for (i=x-1;i<=x+1;i++)
if (i>=0&&i<n)
for (j=y-1;j<=y+1;j++)
if (j>=0&&j<m)
[ ④ ];
y++;
if (y==m){
x++;
y=0;
}
if (x==n)
return;
}
while (1);
}
int main(){
cin >> n >> m >> k;
ans=0;
memset(hash,0,sizeof(hash));
[ ⑤ ] ;
cout << ans << endl;
return 0;
}
(26). _______________________________
(27). _______________________________
(28). _______________________________
(29). _______________________________
(30). _______________________________
7.（2010）第 27 题
完善程序：
（哥德巴赫猜想）哥德巴赫猜想是指 任一大于2的偶数都可写成两个质数之和 迄今为止 这仍然是一个著名的世界难题 被誉为数学王冠上的明珠 试编写程序 验证任一大于2且不超过n的偶数都能写成两个质数之和
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 1000;
int n, r, p[SIZE], i, j, k, ans;
bool tmp;
cin>>n;
r = 1;
p[1] = 2;
for (i = 3; i <= n; i++) {
[ ① ];
for (j = 1; j <= r; j++)
if (i % [ ② ] == 0) {
tmp = false;
break;
}
if (tmp) {
r++;
[ ③ ] ;
}
}
ans = 0;
for (i = 2; i <= n / 2; i++) {
tmp = false;
for (j = 1; j <= r; j++)
for (k = j; k <= r; k++)
if (i + i == [ ④ ] ) {
tmp = true;
break;
}
if (tmp)
ans++;
}
cout<<ans<<endl;
return 0;
}
若输入n为2010 则输出[ ⑤ ]时表示验证成功 即大于2且不超过2010的偶数都满足哥德巴赫猜想
(31). _______________________________
(32). _______________________________
(33). _______________________________
(34). _______________________________
(35). _______________________________
8.（2010）第 28 题
完善程序：
(过河问题）在一个月黑风高的夜晚 有一群人在河的右岸 想通过唯一的一根独木桥走到河的左岸 在这伸手不见五指的黑夜里 过桥时必须借助灯光来照明 很不幸的是 他们只有一盏灯 另外 独木桥上最多承受两个人同时经过 否则将会坍塌 每个人单独过桥都需要一定的时间 不同的人需要的时间可能不同 两个人一起过桥时 由于只有一盏灯 所以需要的时间是较慢的那个人单独过桥时所花的时间 现输入n（2≤n<100）和这n个人单独过桥时需要的时间 请计算总共最少需要多少时间 他们才能全部到达河的左岸
#include <iostream>
using namespace std;
const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
int n, hour[SIZE];
bool pos[SIZE];
int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
int go(bool stage)
{
int i, j, num, tmp, ans;
if (stage == RIGHT_TO_LEFT) {
num = 0;
ans = 0;
for (i = 1; i <= n; i++)
if (pos[i] == RIGHT) {
num++;
if (hour[i] > ans)
ans = hour[i];
}
if ([ ① ])
return ans;
ans = INFINITY;
for (i = 1; i <= n - 1; i++)
if (pos[i] == RIGHT)
for (j = i + 1; j <= n; j++)
if (pos[j] == RIGHT) {
pos[i] = LEFT;
pos[j] = LEFT;
tmp = max(hour[i], hour[j]) +[ ② ];
if (tmp < ans)
ans = tmp;
pos[i] = RIGHT;
pos[j] = RIGHT;
}
return ans;
}
if (stage == LEFT_TO_RIGHT) {
ans = INFINITY;
for (i = 1; i <= n; i++)
if ([ ③ ]) {
pos[i] = RIGHT;
tmp =[ ④ ];
if (tmp < ans)
ans = tmp;
[ ⑤ ];
}
return ans;
}
return 0;
}
int main()
{
int i;
cin>>n;
for (i = 1; i <=n; i++) {
cin>>hour[i];
pos[i] = RIGHT;
}
cout<<go(RIGHT_TO_LEFT)<<endl;
return 0;
}
(36). _______________________________
(37). _______________________________
(38). _______________________________
(39). _______________________________
(40). _______________________________
9.（2011）第 27 题
完善程序
（子矩阵）给输入一个n1m1的矩阵a 和n2m2的矩阵b 问a中是否存在子矩阵和b相等 若存在 输出所有子矩阵左上角的坐标 若不存在输出“There is no answer”
#include<iostream>
using namespace std;
const int SIZE = 50;
int n1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];
int main()
{
int i,j,k1,k2;
bool good ,haveAns;
cin>>n1>>m1;
for(i=1;i<=n1;i++)
for(j=1;j<=m1;j++)
cin>>a[i][j];
cin>>n2>>m2;
for(i=1;i<=n2;i++)
for(j=1;j<=m2;j++)
[ ① ];
haveAns=false;
for(i=1;i<=n1-n2+1;i++)
for(j=1;j<= [ ② ];j++){
[ ③ ];
for(k1=1;k1<=n2;k1++)
for(k2=1;k2<=[ ④ ] ;k2++){
if(a[i+k1-1][j+k2-1]!=b[k1][k2])
good=false;
}
if(good){
cout<<i<<' '<<j<<endl;
[ ⑤ ];
}
}
if(!haveAns)
cout<<"There is no answer"<<endl;
return 0;
}
(41). _______________________________
(42). _______________________________
(43). _______________________________
(44). _______________________________
(45). _______________________________
10.（2011）第 28 题
完善程序
(大整数开方) 输入一个正整数n（1≤n≤10^100） 试用二分法计算它的平方根的整数部分
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推
hugeint times(hugeint a,hugeint b)
// 计算大整数a和b的乘积
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)1
for(j=1;j<=b.len;j++)
[ ① ] +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
[ ② ];
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeint a,hugeint b)
//计算大整数a和b 的和
{
int i;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= [ ③ ] ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeint a,hugeint b)
//计算大整数a和b的平均数的整数部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=([ ④ ])*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
// 计算大整数a加2之后的结果
{
int i;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
[ ⑤ ];
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数a>b则返回true，否则返回false
{
int i;
if([ ⑥ ])
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]-[ ⑦ ];
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over([ ⑧ ]))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推
hugeint times(hugeint a,hugeint b)
// 计算大整数a和b的乘积
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)1
for(j=1;j<=b.len;j++)
[ ① ] +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
[ ② ];
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeint a,hugeint b)
//计算大整数a和b 的和
{
int i;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= [ ③ ] ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeint a,hugeint b)
//计算大整数a和b的平均数的整数部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=([ ④ ])*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
// 计算大整数a加2之后的结果
{
int i;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
[ ⑤ ];
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数a>b则返回true，否则返回false
{
int i;
if([ ⑥ ])
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]-[ ⑦ ];
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over([ ⑧ ]))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}
(46). _______________________________
(47). _______________________________
(48). _______________________________
(49). _______________________________
(50). _______________________________
(51). _______________________________
(52). _______________________________
(53). _______________________________
11.（2012）第 27 题
完善程序
（坐标统计）输入n个整点在平面上的坐标 对于每个点 可以控制所有位于它左下方的点（即x、y坐标都比它小） 它可以控制的点的数目称为“战斗力” 依次输出每个点的战斗力 最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高 输出其中最大的编号）
#include <iostream>
using namespace std;
const int SIZE =100;
int x[SIZE],y[SIZE],f[SIZE];
int n,i,j,max_f,ans;
int main()
{
cin>>n;
for(i=1;i<=n;i++) cin>>x[i]>>y[i];
max_f=0;
for(i=1;i<=n;i++)
{
f[i]= [ ① ];
for(j=1;j<=n;j++)
{
if(x[j]<x[i] && [ ② ])
[ ③ ] ;
}
if( [ ④ ])
{
max_f=f[i];
[ ⑤ ];
}
}
for(i=1;i<=n;i++) cout<<f[i]<<endl;
cout<<ans<<endl;
return 0;
}
(54). _______________________________
(55). _______________________________
(56). _______________________________
(57). _______________________________
(58). _______________________________
12.（2012）第 28 题
完善程序
（排列数）输入两个正整数n m（1<n<20,1<m<n） 在1~n中任取m个数 按字典序从小到大输出所有这样的排列
例如：
输入:
3 2
输出：
1 2
1 3
2 1
2 3
3 1
3 2
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE =25;
bool used[SIZE];
int data[SIZE];
int n,m,i,j,k;
bool flag;
int main()
{
cin>>n>>m;
memset(used,false,sizeof(used));
for(i=1;i<=m;i++)
{
data[i]=i;
used[i]=true;
}
flag=true;
while(flag)
{
for(i=1;i<=m-1;i++) cout<<data[i]<<" ";
cout<<data[m]<<endl;
flag= [ ① ] ;
for(i=m;i>=1;i--)
{
[ ② ];
for(j=data[i]+1;j<=n;j++)
if(!used[j])
{
used[j]=true;
data[i]=[ ③ ] ;
flag=true;
break;
}
if(flag)
{
for(k=i+1;k<=m;k++)
for(j=1;j<= [ ④ ];j++)
if(!used[j])
{
data[k]=j;
used[j]=true;
break;
}
[ ⑤ ];
}
}
}
return 0;
}
(59). _______________________________
(60). _______________________________
(61). _______________________________
(62). _______________________________
(63). _______________________________
13.（2013）第 27 题
完善程序： （序列重排）
全局数组变量 a 定义如下：
const int SIZE = 100;
int a[SIZE], n;const int SIZE = 100;
int a[SIZE], n;
它记录着一个长度为n 的序列 a[1] a[2] ⋯ a[n]。
现在需要一个函数 以整数p (1 ≤p ≤n) 为参数 实现如下功能 将序列a 的前 p个数与后 n –p 个数对调 且不改变这p 个数（或n –p 个数）之间的相对位置
有一种朴素的算法可以实现这一需求 其时间复杂度为O( n) 空间复杂度为 O(n)：
void swap1( int p )
{
int i, j, b[SIZE];
for ( i = 1; i <= p; i++ )
b[①] = a[i];
for ( i = p + 1; i <= n; i++ )
b[i - p] = ②;
for ( i = 1; i <= ③; i++ )
a[i] = b[i];
}
我们也可以用时间换空间 使用时间复杂度为O(n2) 空间复杂度为O(1) 的算法：
void swap2( int p )
{
int i, j, temp;
for ( i = p + 1; i <= n; i++ )
{
temp = a[i];
for ( j = i; j >= ④; j-- )
a[j] = a[j - 1];
⑤ = temp;
}
}
(64). _______________________________
(65). _______________________________
(66). _______________________________
(67). _______________________________
(68). _______________________________
