CSP第一轮模测六

您的姓名：

有n名同学参加学校组织的郊游活动，已知学校给这 n 名同学的郊游总经费为 A 元，与此同时第 i 位同学自己携带
了 Mi 元。为了方便郊游，活动地点提供 B(≥n)辆自行车供人租用，租用第 j 辆自行车的价格为 Cj元，每位同学可以使用
自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想
知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间[l, r]，我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心
算法实现的。
#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn){
int count = 0, i, j;
i = ___1___;
j = 1;
while (i <= n){
if (___2___) count += C[j] - M[i];
i++;
j++;
}
return ___3___;
}
void sort(int a[], int l, int r){
int i = l, j = r, x = a[(l + r) / 2], y;
while (i <= j){
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j) {
y = a[i];
a[i] = a[j];
a[j] = y;
i++;
j--;
}
}
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}
int main(){
int i;
cin >> n >> B >> A;
for (i = 1; i <= n; i++) cin >> M[i];
for (i = 1; i <= B; i++) cin >> C[i];
sort(M, 1, n);
sort(C, 1, B);
l = 0;
r = n;
while (l <= r){
mid = (l + r) / 2;
if (___4___){ans = mid; l = mid + 1;}
else r = ( 5 );
}
cout << ans << endl;
return 0;
}
（1）处应填写：

（2）处应填写

（3）处应填写

（4）处应填写

（5）处应填写

给定一个字符串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(void){
int i;
for (i = 0; i < 26; i++){
if (___1___) change[i] -= 'A' - 'a';
}
}
void ChangeString(void){
int i;
for (i = 0; i < strlen(str); i++){
if (___2___) str[i] = change[str[i] - 'A'] - 'a' + 'A';
else ___3___;
}
}
int main(){
int i;
cin >> str;
cin >> change;
CheckChangeRule();
___4___;
cout << str << endl;
return 0;
}
（1）处应填写

（2）处应填写

（3）处应填写

（4）处应填写

给出一个不超过10000的正整数，判断这个数是否是质数。
#include <stdio.h>
int main() {
int ___1___;
scanf("%d", &n);
if (n == 2) puts(___2___);
else if (___3___ || n % 2 == 0) puts("NO");
else {
i = 3;
while (i * i <= n){
if (___4___){
puts("NO");
return 0;
}
i = i + 2;
}
puts("YES");
}
return 0;
}
（1）处应填写

（2）处应填写

（3）处应填写

（4）处应填写

有n条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子
中切割出m条长度相同的绳段，求绳段的最大长度是多少。
输入：第一行是一个不超过100的正整数n，第二行是n个不超过10^6 的正整数，表示每条绳子的长度，第三行是一个
不超过10^8 的正整数m。
输出：绳段的最大长度，若无法切割，输出 Failed。
#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main(){
cin >> n;
count = 0;
for (i = 0; i < n; i++){cin >> len[i]; ___1___;}
cin >> m;
if (___2___){ cout << "Failed" << endl; return 0;}
lbound = 1;
ubound = 1000000;
while (___3___){
mid = ___4___;
count = 0;
for (i = 0; i < n; i++) ___5___;
if (count < m) ubound = mid - 1;
else lbound = mid;
}
cout << lbound << endl;
return 0;
}
（1）处应填写

（2）处应填写

（3）处应填写

（4）处应填写

（5）处应填写

给定一个长度为 n（3 ≤ n ≤ 1000）的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和
最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。
要求：每个连续子序列长度至少为1，且两个连续子序列之间至少间隔1个数
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, ans, sum;
int x[MAXN];
int lmax[MAXN]; //lmax[i]为仅含x[i]及x[i]左侧整数的连续子序列的序列和中，最大的序列和
int rmax[MAXN]; //rmax[i]为仅含x[i]及x[i]右侧整数的连续子序列的序列和中，最大的序列和
int main(){
cin >> n;
for (i = 0; i < n; i++) cin >> x[i];
lmax[0] = x[0];
for (i = 1; i < n; i++)
if (lmax[i - 1] <= 0) lmax[i] = x[i];
else lmax[i] = lmax[i - 1] + x[i];
for (i = 1; i < n; i++)
if (lmax[i] < lmax[i - 1]) lmax[i] = lmax[i - 1];
___1___;
for (i = n - 2; i >= 0; i--)
if (rmax[i + 1] <= 0) ___2___;
else ___3___;
for (i = n - 2; i >= 0; i--)
if (rmax[i] < rmax[i + 1]) ___4___;
ans = x[0] + x[2];
for (i = 1; i < n - 1; i++){
sum = ___5___;
if (sum > ans) ans = sum;
}
cout << ans << endl;
return 0;
}
（1）处应填写

（2）处应填写

（3）处应填写

（4）处应填写

（5）处应填写