2021年CCF非专业级别软件能力认证第一轮CSP_S/提高级
2021
第一轮
2023-09-01 18:39:28
70次
一、单选题
a, b, c 均为 1～9 之间的整数，若以 a、 b、 c 作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 n 有（ ）个。
和 
的和为（ ）。
二、判断题
三、组合题
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。
提示：考虑优化朴素的动态规划算法，将前
位和后位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
③处应填（）
| A． -INF |
B． Max[y] [x] |
| C． 0 |
D． Max[x][yJ |
②处应填（）
| A． (a & MS) « B |
B． a>>B |
| C． a&(1<<B) |
D． a&(MS<<B) |
⑤处应填()
| A． to_max(Max[y][z],v + w(a ^(z << B))) |
B． to_max(Max[z][y],v + w((x ^ z) << B)) |
| C． to_max(Max[zJ[y],v + w(a ^ (z << B))) |
D． to_max(Max[x][z],v + w(y ^ z)) |
④处应填（）
| A． Max[x] [z]+w（y^z） |
B． Max[x][z] + w(a ^ z) |
| C． Max[x] [z]+w（x^(z<<B）) |
D． Max[x][z] + w(x ^ z) |
①处应填（）
| A． X >>= 1 |
B． X ^=X & (x ^ (x + 1)) |
| C． X -= X | -X |
D． X ^= X & (X ^ (x - 1)) |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为：1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n，B， w[maxn]， v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v， u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”％d\n”， w);
else
printf(”％d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("％d %d", &n， &B);
for(int i = 1; i <= n; i ++) {
scanf(”％d%d，&w[i]， &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1])；
swap(v[j]，v[j + 1])；
}
int curV, curW;
if（②） {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④)；
return 0;
}
print (⑤)；
return 0;
}
③处应填()
| A． print(v[1]w[1]); return 0; |
B． curV = 0; curW = 0; |
| C． print(w[1] v[1]); return 0; |
D． curV = v[1]; curW = w[1]; |
⑤处应填（）
| A． curW, curV |
B． curW，1 |
| C． curV, curW |
D． curV，1 |
④处应填（）
| A． curW * v[i] + curV * w[i], v[i] |
B． (curW - w[i]) * v[i] + (B - curV) * w[i], v[i] |
| C． curW + v[i], w[i] |
D． curW * v[i] * (B - curV) * w[i], v[i] |
②处应填（）
| A． w[1] <= B |
B． v[1] <= B |
| C． w[1] >= B |
D． v[1] >= B |
①处应填()
| A． W[j] / v[j] < w[j+1]/v[j+1] |
B． W[j] / v[j]> w[j+1]/v[j+1] |
| C． v[j] * w[j+1]< v[j+1]*w[j] |
D． w[j] * v[j+1]< w[j+1]*v[j] |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <iostream>
#include <cmath>
using namespace std;
const double r = acos(0.5);
int a1, b1, c1, d1;
int a2, b2, c2, d2;
inline int sq(const int x) { return x * x; }
inline int cu(const int x) { return x * x * x; }
int main()
{
cout.flags(ios::fixed);
cout.precision(4);
cin >> a1 >> b1 >> c1 >> d1;
cin >> a2 >> b2 >> c2 >> d2;
int t = sq(a1 - a2) + sq(b1 - b2) + sq(c1 - c2);
if (t <= sq(d2 - d1)) cout << cu(min(d1, d2)) * r * 4;
else if (t >= sq(d2 + d1)) cout << 0;
else {
double x = d1 - (sq(d1) - sq(d2) + t) / sqrt(t) / 2;
double y = d2 - (sq(d2) - sq(d1) + t) / sqrt(t) / 2;
cout << (x * x * (3 * d1 - x) + y * y * (3 * d2 - y)) * r;
}
cout << endl;
return 0;
}
假设输入的所有数的绝对值都不超过 1000，完成下面的判断题和单选题：
(1)．（2 分）当输入为“0 0 0 1 1 0 0 1”时，输出为“1.3090”。（ ）
| A．正确 | B．错误 |
将第 28 行中的“x * x”改成“sq(x)”、“y * y”改成“sq(y)” ，不会影响程序运行的结果。（ ）
| A．正确 | B．错误 |
将第 26、27 行中的“/ sqrt(t) / 2”替换为“/ 2 / sqrt(t)”，不会影响程序运行的结果。（ ）
| A．正确 | B．错误 |
（2.5 分）这段代码的含义为（ ）。
| A． 求圆的面积并 |
B． 求球的体积并 |
| C． 求球的体积交 |
D． 求椭球的体积并 |
将第 21 行中 t 的类型声明从 int 改为 double，不会影响程序运行的结果。（ ）
| A．正确 | B．错误 |
当输入为“1 1 1 1 1 1 1 2”时，输出为（ ）。
| A． “3.1416” |
B． “6.2832” |
| C． “4.7124” |
D． “4.1888” |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <iostream>
#include <string>
using namespace std;
char base[64];
char table[256];
void init()
{
for (int i = 0; i < 26; i++) base[i] = 'A' + i;
for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
base[62] = '+', base[63] = '/';
for (int i = 0; i < 256; i++) table[i] = 0xff;
for (int i = 0; i < 64; i++) table[base[i]] = i;
table['='] = 0;
}
string encode(string str)
{
string ret;
int i;
for (i = 0; i + 3 <= str.size(); i += 3) {
ret += base[str[i] >> 2];
ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
ret += base[(str[i + 1] & 0x0f) << 2 | str[i + 2] >> 6];
ret += base[str[i + 2] & 0x3f];
}
if (i < str.size()) {
ret += base[str[i] >> 2];
if (i + 1 == str.size()) {
ret += base[(str[i] & 0x03) << 4];
ret += "==";
}
else {
ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
ret += base[(str[i + 1] & 0x0f) << 2];
ret += "=";
}
}
return ret;
}
string decode(string str)
{
string ret;
int i;
for (i = 0; i < str.size(); i += 4) {
ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
if (str[i + 2] != '=')
ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
if (str[i + 3] != '=')
ret += table[str[i + 2]] << 6 | table[str[i + 3]];
}
return ret;
}
int main()
{
init();
cout << int(table[0]) << endl;
int opt;
string str;
cin >> opt >> str;
cout << (opt ? decode(str) : encode(str)) << endl;
return 0;
}
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
(1)．对于任意不含空白字符的字符串 str1，先执行程序输入“0 str1”，得到输出的第
二行记为 str2；再执行程序输入“1 str2”，输出的第二行必为 str1。（ ）
| A．正确 | B．错误 |
（4 分）当输入为“0 CSP2021csp”时，输出的第二行为（ ）。
| A． “Q1NQMjAyMWNzcAv=” |
B． “Q1NQMjAyMGNzcA==” |
| C． “Q1NQMjAyMGNzcAv=” |
D． “Q1NQMjAyMWNzcA==” |
设输入字符串长度为 n，encode 函数的时间复杂度为（ ）。
| A． Θ,√n |
B． Θ(n) |
| C． Θ(n log n) |
D． Θ(n^2 ) |
输出的第一行为（ ）。
| A． “0xff” |
B． “255” |
| C． “0xFF” |
D． “-1” |
当输入为“1 SGVsbG93b3JsZA==”时，输出的第二行为“HelloWorld”。（ ）
| A．正确 | B．错误 |
程序总是先输出一行一个整数，再输出一行一个字符串。（ ）
| A．正确 | B．错误 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <algorithm>
#include <iostream>
using namespace std;
int n, a[1005];
struct Node
{
int h, j, m, w;
Node(const int _h, const int _j, const int _m, const int _w):
h(_h), j(_j), m(_m), w(_w)
{ }
Node operator+(const Node &o) const
{
return Node(
max(h, w + o.h),
max(max(j, o.j), m + o.h),
max(m + o.w, o.m),
w + o.w);
}
};
Node solve1(int h, int m)
{
if (h > m)
return Node(-1, -1, -1, -1);
if (h == m)
return Node(max(a[h], 0), max(a[h], 0), max(a[h], 0), a[h]);
int j = (h + m) >> 1;
return solve1(h, j) + solve1(j + 1, m);
}
int solve2(int h, int m)
{
if (h > m)
return -1;
if (h == m)
return max(a[h], 0);
int j = (h + m) >> 1;
int wh = 0, wm = 0;
int wht = 0, wmt = 0;
for (int i = j; i >= h; i--) {
wht += a[i];
wh = max(wh, wht);
}
for (int i = j + 1; i <= m; i++) {
wmt += a[i];
wm = max(wm, wmt);
}
return max(max(solve2(h, j), solve2(j + 1, m)), wh + wm);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << solve1(1, n).j << endl;
cout << solve2(1, n) << endl;
return 0;
}
假设输入的所有数的绝对值都不超过 1000，完成下面的判断题和单选题：
(1)．solve1(1, n) 的时间复杂度为（ ）。
| A． Θ(log n) |
B． Θ(n) |
| C． Θ(n log n) |
D． Θ(n^2) |
当输入为“5 -10 11 -9 5 -7”时，输出的第二行为“7”。（ ）
| A．正确 | B．错误 |
solve2(1, n) 的时间复杂度为（ ）。
| A． Θ(log n) |
B． Θ(n) |
| C． Θ(n log n) |
D． Θ(n^2) |
程序总是会正常执行并输出两行两个相等的数。（ ）
| A．正确 | B．错误 |
当输入为“10 -3 2 10 0 -8 9 -4 -5 9 4”时，输出的第一行为（ ）。
| A． “13” |
B． “17” |
| C． “24” |
D． “12” |
第 28 行与第 38 行分别有可能执行两次及以上。（ ）
| A．正确 | B．错误 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
