1724: CSP-S20阅读程序
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Special Judger
Creator：
Submit：5
Solved：0
Description
第 1 题（12分）
#include <iostream>
using namespace std;
int n;
int d[1000];
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i];
int ans = -1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (d[i] < d[j])
ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
cout << ans;
return 0;
}
假设输入的 n 和 d[i] 都是不超过 10000 的正整数，完成下面的判断题和单选题：
判断题
1. n 必须小于 1000,否则程序可能会发生运行错误。（ ）
A. 正确
B. 错误
2. 输出一定大于等于 0。（ ）
A. 正确
B. 错误
3. 若将第 13 行的 j=0 改为 j = i + 1 程序输出可能会改变。 （ ）
A. 正确
B. 错误
4. 将第 14 行的 d[i] < d[j] 改为 d[i] != d[j]，程序输出不会改变。（ ）
A. 正确
B. 错误
单选题
5. 若输入 n 为 100，且输出为 127，则输入的 d[i] 中不可能有（ ）。
A. 127
B. 126
C. 128
D. 125
6. 若输出的数大于 0，则下面说法正确的是( ）。
A. 若输出为偶数，则输入的 d[i] 中最多有两个偶数
B. 若输出为奇数，则输入的 d[i] 中至少有两个奇数
C. 若输出为偶数，则输入的 d[i] 中至少有两个偶数
D. 若输出为奇数，则输入的 d[i] 中最多有两个奇数
第 2 题（13分）
#include <iostream>
#include <cstdlib>
using namespace std;
int n;
int d[10000];
int find(int L, int R, int k) {
int x = rand() % (R - L + 1) + L;
swap(d[L], d[x]);
int a = L + 1, b = R;
while (a < b) {
while (a < b && d[a] < d[L])
++a;
while (a < b && d >= d[L])
--b;
swap(d[a], d);
}
if (d[a] < d[L])
++a;
if (a - L == k)
return d[L];
if (a - L < k)
return find(a, R, k - (a - L));
return find(L + 1, a - 1, k);
}
int main() {
int k;
cin >> n;
cin >> k;
for (int i = 0; i < n; ++i)
cin >> d[i];
cout << find(0, n - 1, k);
return 0;
}
假设输入的 n,k 和 d[i] 都是不超过 10000 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：
判断题
7. 第 9 行的 x 的数值范围是 L+1 到 R，即 [L+1,R]。（ ）
A. 正确
B. 错误
8. 将第 19 行的 d[a] 改为 d，程序不会发生运行错误。（ ）
A. 正确
B. 错误
单选题
9.当输入的 d[i] 是严格单调递增序列时，第 17 行的 swap 平均执行次数是( )。【A】（2.5 分）
A. O(nlogn)
B. O(n)
C. O(logn)
D. O(n^2)
10.当输入的 d[i] 是严格单调递减序列时，第 17 行的 swap 平均执行次数是( )。（2.5 分）
A. O(n^2)
B. O(n)
C. O(nlogn)
D. O(logn)
11.若输入的 d[i] 为 ii，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。（2.5 分）
A. O(n),O(n^2)
B. O(n),O(nlogn)
C. O(nlogn),O(n2)
D. O(nlogn),O(nlogn)
12.若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( )。（2.5 分）
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n2)
第 3 题（15分）
#include <iostream>
#include <queue>
using namespace std;
const int maxl = 20000000;
class Map {
struct item {
string key; int value;
} d[maxl];
int cnt;
public:
int find(string x) {
for (int i = 0; i < cnt; ++i)
if (d[i].key == x)
return d[i].value;
return -1;
}
static int end() { return -1; }
void insert(string k, int v) {
d[cnt].key = k; d[cnt++].value = v;
}
} s[2];
class Queue {
string q[maxl];
int head, tail;
public:
void pop() { ++head; }
string front() { return q[head + 1]; }
bool empty() { return head == tail; }
void push(string x) { q[++tail] = x; }
} q[2];
string st0, st1;
int m;
string LtoR(string s, int L, int R) {
string t = s;
char tmp = t[L];
for (int i = L; i < R; ++i)
t[i] = t[i + 1];
t[R] = tmp;
return t;
}
string RtoL(string s, int L, int R) {
string t = s;
char tmp = t[R];
for (int i = R; i > L; --i)
t[i] = t[i - 1];
t[L] = tmp;
return t;
}
bool check(string st , int p, int step) {
if (s[p].find(st) != s[p].end())
return false;
++step;
if (s[p ^ 1].find(st) == s[p].end()) {
s[p].insert(st, step);
q[p].push(st);
return false;
}
cout << s[p ^ 1].find(st) + step << endl;
return true;
}
int main() {
cin >> st0 >> st1;
int len = st0.length();
if (len != st1.length()) {
cout << -1 << endl;
return 0;
}
if (st0 == st1) {
cout << 0 << endl;
return 0;
}
cin >> m;
s[0].insert(st0, 0); s[1].insert(st1, 0);
q[0].push(st0); q[1].push(st1);
for (int p = 0;
!(q[0].empty() && q[1].empty());
p ^= 1) {
string st = q[p].front(); q[p].pop();
int step = s[p].find(st);
if ((p == 0 &&
(check(LtoR(st, m, len - 1), p, step) ||
check(RtoL(st, 0, m), p, step)))
||
(p == 1 &&
(check(LtoR(st, 0, m), p, step) ||
check(RtoL(st, m, len - 1), p, step))))
return 0;
}
cout << -1 << endl;
return 0;
}
判断题
13. 输出可能为 0。（ ）
A. 正确
B. 错误
14. 若输入的两个字符串长度均为 101 时，则 m=0 时的输出与 m=100 时的输出是一样的。（ ）
A. 正确
B. 错误
15. 若两个字符串的长度均为 n，则最坏情况下，此程序的时间复杂度为 O(n!)。（ ）
A. 正确
B. 错误
单选题
16. 若输入的第一个字符串长度由 100 个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的 m 为 0，则输出为（ ）。（2.5 分）
A. 49
B. 50
C. 100
D. -1
17. 己知当输入为 0123\n3210\n1 时输出为 4，当输入为 012345\n543210\n1 时输出为 14，当输入为 01234567\n76543210\n1 时输出为 28，则当输入为0123456789ab\nba9876543210\nl 输出为
( ）。其中 \n 为换行符。（4 分）
A. 56
B. 84
C. 102
D. 68
18. 若两个字符串的长度均为 n，且 0<m<n−1，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（ ）。提示：考虑输入与输出有多少对字符前后顺序不一样。（4 分）
A. 若 n,m 均为奇数，则输出可能小于 0。
B. 若 n,m 均为偶数，则输出可能小于 0。
C. 若 n 为奇数、m 为偶数，则输出可能小于 0。
D. 若 n 为偶数、m 为奇数，则输出可能小于 0。
#include <iostream>
using namespace std;
int n;
int d[1000];
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i];
int ans = -1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (d[i] < d[j])
ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
cout << ans;
return 0;
}
假设输入的 n 和 d[i] 都是不超过 10000 的正整数，完成下面的判断题和单选题：
判断题
1. n 必须小于 1000,否则程序可能会发生运行错误。（ ）
A. 正确
B. 错误
2. 输出一定大于等于 0。（ ）
A. 正确
B. 错误
3. 若将第 13 行的 j=0 改为 j = i + 1 程序输出可能会改变。 （ ）
A. 正确
B. 错误
4. 将第 14 行的 d[i] < d[j] 改为 d[i] != d[j]，程序输出不会改变。（ ）
A. 正确
B. 错误
单选题
5. 若输入 n 为 100，且输出为 127，则输入的 d[i] 中不可能有（ ）。
A. 127
B. 126
C. 128
D. 125
6. 若输出的数大于 0，则下面说法正确的是( ）。
A. 若输出为偶数，则输入的 d[i] 中最多有两个偶数
B. 若输出为奇数，则输入的 d[i] 中至少有两个奇数
C. 若输出为偶数，则输入的 d[i] 中至少有两个偶数
D. 若输出为奇数，则输入的 d[i] 中最多有两个奇数
第 2 题（13分）
#include <iostream>
#include <cstdlib>
using namespace std;
int n;
int d[10000];
int find(int L, int R, int k) {
int x = rand() % (R - L + 1) + L;
swap(d[L], d[x]);
int a = L + 1, b = R;
while (a < b) {
while (a < b && d[a] < d[L])
++a;
while (a < b && d >= d[L])
--b;
swap(d[a], d);
}
if (d[a] < d[L])
++a;
if (a - L == k)
return d[L];
if (a - L < k)
return find(a, R, k - (a - L));
return find(L + 1, a - 1, k);
}
int main() {
int k;
cin >> n;
cin >> k;
for (int i = 0; i < n; ++i)
cin >> d[i];
cout << find(0, n - 1, k);
return 0;
}
假设输入的 n,k 和 d[i] 都是不超过 10000 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：
判断题
7. 第 9 行的 x 的数值范围是 L+1 到 R，即 [L+1,R]。（ ）
A. 正确
B. 错误
8. 将第 19 行的 d[a] 改为 d，程序不会发生运行错误。（ ）
A. 正确
B. 错误
单选题
9.当输入的 d[i] 是严格单调递增序列时，第 17 行的 swap 平均执行次数是( )。【A】（2.5 分）
A. O(nlogn)
B. O(n)
C. O(logn)
D. O(n^2)
10.当输入的 d[i] 是严格单调递减序列时，第 17 行的 swap 平均执行次数是( )。（2.5 分）
A. O(n^2)
B. O(n)
C. O(nlogn)
D. O(logn)
11.若输入的 d[i] 为 ii，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。（2.5 分）
A. O(n),O(n^2)
B. O(n),O(nlogn)
C. O(nlogn),O(n2)
D. O(nlogn),O(nlogn)
12.若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( )。（2.5 分）
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n2)
第 3 题（15分）
#include <iostream>
#include <queue>
using namespace std;
const int maxl = 20000000;
class Map {
struct item {
string key; int value;
} d[maxl];
int cnt;
public:
int find(string x) {
for (int i = 0; i < cnt; ++i)
if (d[i].key == x)
return d[i].value;
return -1;
}
static int end() { return -1; }
void insert(string k, int v) {
d[cnt].key = k; d[cnt++].value = v;
}
} s[2];
class Queue {
string q[maxl];
int head, tail;
public:
void pop() { ++head; }
string front() { return q[head + 1]; }
bool empty() { return head == tail; }
void push(string x) { q[++tail] = x; }
} q[2];
string st0, st1;
int m;
string LtoR(string s, int L, int R) {
string t = s;
char tmp = t[L];
for (int i = L; i < R; ++i)
t[i] = t[i + 1];
t[R] = tmp;
return t;
}
string RtoL(string s, int L, int R) {
string t = s;
char tmp = t[R];
for (int i = R; i > L; --i)
t[i] = t[i - 1];
t[L] = tmp;
return t;
}
bool check(string st , int p, int step) {
if (s[p].find(st) != s[p].end())
return false;
++step;
if (s[p ^ 1].find(st) == s[p].end()) {
s[p].insert(st, step);
q[p].push(st);
return false;
}
cout << s[p ^ 1].find(st) + step << endl;
return true;
}
int main() {
cin >> st0 >> st1;
int len = st0.length();
if (len != st1.length()) {
cout << -1 << endl;
return 0;
}
if (st0 == st1) {
cout << 0 << endl;
return 0;
}
cin >> m;
s[0].insert(st0, 0); s[1].insert(st1, 0);
q[0].push(st0); q[1].push(st1);
for (int p = 0;
!(q[0].empty() && q[1].empty());
p ^= 1) {
string st = q[p].front(); q[p].pop();
int step = s[p].find(st);
if ((p == 0 &&
(check(LtoR(st, m, len - 1), p, step) ||
check(RtoL(st, 0, m), p, step)))
||
(p == 1 &&
(check(LtoR(st, 0, m), p, step) ||
check(RtoL(st, m, len - 1), p, step))))
return 0;
}
cout << -1 << endl;
return 0;
}
判断题
13. 输出可能为 0。（ ）
A. 正确
B. 错误
14. 若输入的两个字符串长度均为 101 时，则 m=0 时的输出与 m=100 时的输出是一样的。（ ）
A. 正确
B. 错误
15. 若两个字符串的长度均为 n，则最坏情况下，此程序的时间复杂度为 O(n!)。（ ）
A. 正确
B. 错误
单选题
16. 若输入的第一个字符串长度由 100 个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的 m 为 0，则输出为（ ）。（2.5 分）
A. 49
B. 50
C. 100
D. -1
17. 己知当输入为 0123\n3210\n1 时输出为 4，当输入为 012345\n543210\n1 时输出为 14，当输入为 01234567\n76543210\n1 时输出为 28，则当输入为0123456789ab\nba9876543210\nl 输出为
( ）。其中 \n 为换行符。（4 分）
A. 56
B. 84
C. 102
D. 68
18. 若两个字符串的长度均为 n，且 0<m<n−1，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（ ）。提示：考虑输入与输出有多少对字符前后顺序不一样。（4 分）
A. 若 n,m 均为奇数，则输出可能小于 0。
B. 若 n,m 均为偶数，则输出可能小于 0。
C. 若 n 为奇数、m 为偶数，则输出可能小于 0。
D. 若 n 为偶数、m 为奇数，则输出可能小于 0。