全国入门组 CSP-J 初赛模拟试题 (10)
一、单项选择题
（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
15) 定义一种字符申操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将“A”移到“B”之前，变字符串“ABC”，如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要( )次操作。
二、阅读程序
（程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题4分，共计40分）
#include <bits/stdc++.h>
using namespace std;
const int maxn=50;
void getnext(char str[]) {
int l= strlen(str), i,j,k, temp;
k=l-2;
while(k-1>=0&&str[k]>str[k+1])k--;
i=k+1;
while(i<1&& str[i]> str[k])i++;
temp = str[k] ;
str[k]= str[i-1];
str[i-1] =temp;
for(i= l-1; i>k; i--)
for(j = k+1; j<i; j++)
if(str[j]>str[j+1]) {
temp = str[i];
str[i]= str[j+1];
str[j + 1] = temp;
}
return;
}
int main() {
char a[maxn];
int n;
cin>>a>>n;
while(n>0) {
getnext(a);
n --;
}
cout << a << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int w[35000],d[35000],dp[35000];
int main()
{
int n,m;
scanf("%d%d",&n, &m);
for(int i=1; i<=n; ++i)
scanf("%d%d" ,&w[i],&d[i]);
for(int i=1; i<=n; ++i)
{
for(int j=m; j>=w[i]; --j)
dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
}
printf("%d\n" ,dp[m]);
return 0;
}#include <iostream>
using namespace std;
const int NUM= 5;
int r(int n) {
int i;
if(n<=NUM) return n;
for(int i= 1; i<=NUM; ++i)
if(r(n-i)<0) return i;
return -1;
}
int main() {
int n;
cin>>n;
cout<<r(n)<< endl;
return 0;
}三、完善程序
（单选题，每题3分，共计30分）
(过河问题)在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在伸手不见五指的黑夜里，过桥时必须借照灯光来照明，不幸的是，他们只有一盏灯。另外，独木桥上最多能承受两个人同时经过，否则将会坍塌。每个人单独过独木桥都需要一定的时间，不同的人用的时间可能不同。两个人一起过独木桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥所花费的时间。现在输入N(2<= N <=1000)和这N个人单独过桥需要的时间，请计算总共最少需要多少时间，他们才能全部到达河左岸。
例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是:甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙在一起过桥到河的左岸，总时间为2+1+4=7。
例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是:甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙在一起过桥到河的左岸，总时间为2+1+4=7。
#include<iostream>
#include<cstring>
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(___(1)___)
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])+___(2)___;
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(___(3)___)
{
pos[i] = RIGHT;
tmp=___(4)___;
if(tmp < ans)
ans = tmp;
___(5)___;
}
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;
}(国王放置)在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，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1,列标号为0~m-1。
试补全程序。
试补全程序。
#include <cstdio>
#include <cstring>
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=___(1)___;
}
if(x == n)
return;
}
for(i=x=x-1; i<=x+1; i++)
if(i>=&&i<n)
for(j=y-1; j<=y+1; j++)
if(j>=0 && j<m)
___(2)___;
___(3)___;
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)
hash[i][i]--;
___(4)___;
if(y== m) {
x++;
y=0;
}
if(x==n)
return;
} while(1);
}
int main() {
scanf("%d%d%d", &n, &m, &k);
ans = 0;
memset(hash, 0, sizeof(hash));
___(5)___;
printf("%d\n", ans);
return 0;
}