1 #include <algorithm> 2 #include <iostream> 3 using namespace std; 4 5 int n; 6 int d[50][2]; 7 int ans; 8 9 void dfs(int n, int sum) { 10 if (n == 1) { 11 ans = max(sum, ans); 12 return; 13 } 14 for (int i = 1; i < n; ++i) { 15 int a = d[i - 1][0], b = d[i - 1][1]; 16 int x = d[i][0], y = d[i][1]; 17 d[i - 1][0] = a + x; 18 d[i - 1][1] = b + y; 19 for (int j = i; j < n - 1; ++j) 20 d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1]; 21 int s = a + x + abs(b - y); 22 dfs(n - 1, sum + s); 23 for (int j = n - 1; j > i; --j) 24 d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1]; 25 d[i - 1][0] = a, d[i - 1][1] = b; 26 d[i][0] = x, d[i][1] = y; 27 } 28 } 29 30 int main() { 31 cin >> n; 32 for (int i = 0; i < n; ++i) 33 cin >> d[i][0]; 34 for (int i = 0; i < n; ++i) 35 cin >> d[i][1]; 36 ans = 0; 37 dfs(n, 0); 38 cout << ans << endl; 39 return 0; 40 }
假设输入的 是不超过 的正整数，d[i][0]、d[i][1] 都是不超过 的正整数，完成下面的判断题和单选题。
若输入 为 ，此程序可能会死循环或发生运行错误。（ ）
（1.5 分）若输入 为 ，接下来的输入全为 ，则输出为 。（ ）
（1.5 分）输出的数一定不小于输入的 d[i][0] 和 d[i][1] 的任意一个。（ ）
若输入的 为 ，接下来的输入是 个 和 个 ，则输出为（ ）。
（3 分）若输入的 为 ，接下来的输入是 个 和 个 ，则输出为（ ）。
（3 分）若输入的 为 ，接下来的输入是 到 ，以及 到 ，则输出为（ ）。
（4 分）1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 unsigned short x, y; 8 cin >> x >> y; 9 x = (x | x << 2) & 0x33; 10 x = (x | x << 1) & 0x55; 11 y = (y | y << 2) & 0x33; 12 y = (y | y << 1) & 0x55; 13 unsigned short z = x | y << 1; 14 cout << z << endl; 15 return 0; 16 }
删去第 行与第 行的 unsigned，程序行为不变。（ ）
将第 行与第 行的 short 均改为 char，程序行为不变。（ ）
程序总是输出一个整数 0。（ ）
当输入为 2 2 时，输出为 10。（ ）
当输入为 2 2 时，输出为 59。（ ）
当输入为 13 8 时，输出为（ ）。
1 #include <iostream> 2 3 using namespace std; 4 5 int n, k; 6 7 int solve1() 8 { 9 int l = 0, r = n; 10 while (l <= r) { 11 int mid = (l + r) / 2; 12 if (mid * mid <= n) l = mid + 1; 13 else r = mid - 1; 14 } 15 return l - 1; 16 } 17 18 double solve2(double x) 19 { 20 if (x == 0) return x; 21 for (int i = 0; i < k; i++) 22 x = (x + n / x) / 2; 23 return x; 24 } 25 26 int main() 27 { 28 cin >> n >> k; 29 double ans = solve2(solve1()); 30 cout << ans << ' ' << (ans * ans == n) << endl; 31 return 0; 32 }
假设 int 为 位有符号整数类型，输入的 n 是不超过 的自然数、k 是不超过 int 表示范围的自然数，
该算法最准确的时间复杂度分析结果为 。（ ）
（1.5 分）当输入为 9801 1 时，输出的第一个数为 99。（ ）
对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成 1。（ ）
该程序有存在缺陷。当输入的 n 过大时，第 行的乘法有可能溢出，因此应当将 mid 强制转换为 位整数再计算。（ ）
当输入为 2 1 时，输出的第一个数最接近（ ）。
当输入为 3 10 时，输出的第一个数最接近（ ）。
当输入为 256 11 时，输出的第一个数（ ）。
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 6 int f(string x, string y) { 7 int m = x.size(); 8 int n = y.size(); 9 vector<vector<int>> v(m+1, vector<int>(n+1, 0)); 10 for (int i = 1; i <= m; i++) { 11 for (int j = 1; j <= n; j++) { 12 if (x[i-1] == y[j-1]) { 13 v[i][j] = v[i-1][j-1] + 1; 14 } else { 15 v[i][j] = max(v[i-1][j], v[i][j-1]); 16 } 17 } 18 } 19 return v[m][n]; 20 } 21 22 bool g(string x, string y) { 23 if (x.size() != y.size()) { 24 return false; 25 } 26 return f(x + x, y) == y.size(); 27 } 28 29 int main() { 30 string x, y; 31 cin >> x >> y; 32 cout << g(x, y) << endl; 33 return 0; 34 }
f 函数的返回值小于等于 min(n,m)。（ ）
f 函数的返回值等于两个输入字符串的最长公共子串的长度。（ ）
（1.5 分）当输入两个完全相同的字符串时，g 函数的返回值总是 true。（ ）
将第 行中的 v[m][n] 替换为 v[n][m]，那么该程序（ ）。
当输入为 csp-j p-jcs 时，输出为（ ）。
当输入为 csppsc spsccp 时，输出为（ ）。
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 int solve1(int n) { 6 return n * n; 7 } 8 9 int solve2(int n) { 10 int sum = 0; 11 for (int i = 1; i <= sqrt(n); i++) { 12 if (n % i == 0) { 13 if (n/i == i) { 14 sum += i*i; 15 } else { 16 sum += i*i + (n/i)*(n/i); 17 } 18 } 19 } 20 return sum; 21 } 22 23 int main() { 24 int n; 25 cin >> n; 26 cout << solve2(solve1(n)) << " " << solve1(solve2(n)) << endl; 27 return 0; 28 }
如果输入的 n 为正整数，solve2 函数的作用是计算 n 所有的因子的平方和。（ ）
第 - 行的作用是避免 n 的平方根因子 i（或 n/i）进入第 行而被计算两次。（ ）
如果输入的 n 为质数，solve2(n) 的返回值为 。（ ）
如果输入的 n 为质数 的平方，那么 solve2(n) 的返回值为（ ）。
当输入为正整数时，第一项减去第二项的差值一定（ ）。
（3 分）当输入为 5 时，输出为（ ）。
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 int compute(vector<int>& cost) { 6 int n = cost.size(); 7 vector<int> dp(n+1, 0); 8 dp[1] = cost[0]; 9 for (int i = 2; i <= n; i++) { 10 dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]; 11 } 12 return min(dp[n], dp[n-1]); 13 } 14 15 int main() { 16 int n; 17 cin >> n; 18 vector<int> cost(n); 19 for (int i = 0; i < n; i++) { 20 cin >> cost[i]; 21 } 22 cout << compute(cost) << endl; 23 return 0; 24 }
当输入的 cost 数组为 {10, 15, 20} 时，程序的输出为 15。（ ）
如果将 dp[i-1] 改为 dp[i-3]，程序可能会产生编译错误。（ ）
程序总是输出 cost 数组中最小的元素。（ ）
当输入的 cost 数组为 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1} 时，程序的输出为（ ）。
如果输入的 cost 数组为 {10, 15, 30, 5, 5, 10, 20}，程序的输出为（ ）。
若将代码中的 min(dp[i-1], dp[i-2]) + cost[i-1] 修改为 dp[i-1] + cost[i-2]，输入 cost 数组为 {5, 10, 15} 时，程序的输出为（ ）。
1 #include <algorithm> 2 #include <cstdio> 3 #include <cstring> 4 #define ll long long 5 6 int n, k; 7 int a[200007]; 8 int ans[200007]; 9 10 int main() { 11 scanf("%d%d", &n, &k); 12 for (int i = 1; i <= n; ++i) { 13 scanf("%d", &a[i]); 14 } 15 std::sort(a + 1, a + n + 1); 16 n = std::unique(a + 1, a + n + 1) - a - 1; 17 for (int i = 1, j = 0; i <= n; ++i) { 18 for (; j < i && a[i] - a[j + 1] > k; ++j) 19 ; 20 ans[i] = ans[j] + 1; 21 } 22 printf("%d\n", ans[n]); 23 return 0; 24 }
当输入为 3 1 3 2 1 时，输出结果为 。（ ）
假设输入的 n 为正整数，输出的答案一定满足 且 。（ ）
将第 行的：
1 n = std::unique(a + 1, a + n + 1) - a - 1;
删除后，有可能出现与原本代码不同的输出结果。（ ）
（1.5 分）假设输入的 a 数组和 k 均为正整数，执行第 行代码时，一定满足的条件 不包括（ ）。
当输入为：n = 100, k = 2, a = {1, 2, ..., 100} 时，输出为（ ）。
假设输入的 a 数组和 k 均为正整数，但 a 数组不一定有序，则若误删去第 行的：
std::sort(a + 1, a + n + 1);
程序有可能出现的问题有（ ）。
（3 分）1 #include <algorithm> 2 #include <cstdio> 3 #include <cstring> 4 #define ll long long 5 int f[5007][5007]; 6 int a[5007], b[5007]; 7 int n; 8 int main(){ 9 scanf("%d", &n); 10 for (int i = 1; i <= n; ++i) { 11 scanf("%d", &a[i]); 12 } 13 for (int i = 1; i <= n; ++i) { 14 scanf("%d", &b[i]); 15 } 16 for (int i = 1; i <= n; ++i) { 17 for (int j = 1; j <= n; ++j) { 18 f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1])); 19 if (a[i] == b[j]) { 20 f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1); 21 } 22 } 23 } 24 printf("%d\n", f[n][n]); 25 return 0; 26 }
当输入为 4 1 2 3 4 1 3 2 2 时，输出为 。（ ）
当程序运行完毕后，对于所有的 ，都一定有 。（ ）
（1.5 分）将第 行的 f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1])); 删去后，并不影响程序运行结果。（ ）
输出的答案满足的性质有（ ）。
（3 分）如果在第 行的循环前加上以下两行：
1 std::sort(a + 1, a + n + 1); 2 std::sort(b + 1, b + n + 1);
则答案会（ ）。
（3 分）如果输入的 a = {1, 2, ..., n}，而且 b 数组中数字均为 中的正整数，则上述代码等价于下面哪个问题？（ ）
1 #include <iostream> 2 using namespace std; 3 4 const int n = 100000; 5 const int N = n + 1; 6 7 int m; 8 int a[N], b[N], c[N], d[N]; 9 int f[N], g[N]; 10 11 void init() 12 { 13 f[1] = g[1] = 1; 14 for (int i = 2; i <= n; i++) { 15 if (!a[i]) { 16 b[m++] = i; 17 c[i] = 1, f[i] = 2; 18 d[i] = 1, g[i] = i + 1; 19 } 20 for (int j = 0; j < m && b[j] * i <= n; j++) { 21 int k = b[j]; 22 a[i * k] = 1; 23 if (i % k == 0) { 24 c[i * k] = c[i] + 1; 25 f[i * k] = f[i] / c[i * k] * (c[i * k] + 1); 26 d[i * k] = d[i]; 27 g[i * k] = g[i] * k + d[i]; 28 break; 29 } 30 else { 31 c[i * k] = 1; 32 f[i * k] = 2 * f[i]; 33 d[i * k] = g[i]; 34 g[i * k] = g[i] * (k + 1); 35 } 36 } 37 } 38 } 39 40 int main() 41 { 42 init(); 43 44 int x; 45 cin >> x; 46 cout << f[x] << ' ' << g[x] << endl; 47 return 0; 48 }
假设输入的 x 是不超过 的自然数，完成下面的判断题和单选题：
若输入不为 1，把第 行删去不会影响输出的结果。（ ）
第 行的 f[i] / c[i * k] 可能存在无法整除而向下取整的情况。（ ）
在执行完 init() 后，f 数组不是单调递增的，但 g 数组是单调递增的。（ ）
init 函数的时间复杂度为（ ）。
在执行完 init() 后，f[1]、f[2]、f[3] …… f[100] 中有（ ）个等于 。
当输入为 1000 时，输出为（ ）。
1 #include <algorithm> 2 #include <iostream> 3 #include <limits> 4 5 using namespace std; 6 7 const int MAXN = 105; 8 const int MAXK = 105; 9 10 int h[MAXN][MAXK]; 11 12 int f(int n, int m) 13 { 14 if (m == 1) return n; 15 if (n == 0) return 0; 16 17 int ret = numeric_limits<int>::max(); 18 for (int i = 1; i <= n; i++) 19 ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1); 20 return ret; 21 } 22 23 int g(int n, int m) 24 { 25 for (int i = 1; i <= n; i++) 26 h[i][1] = i; 27 for (int j = 1; j <= m; j++) 28 h[0][j] = 0; 29 30 for (int i = 1; i <= n; i++) { 31 for (int j = 2; j <= m; j++) { 32 h[i][j] = numeric_limits<int>::max(); 33 for (int k = 1; k <= i; k++) 34 h[i][j] = min( 35 h[i][j], 36 max(h[i - k][j], h[k - 1][j - 1]) + 1); 37 } 38 } 39 40 return h[n][m]; 41 } 42 43 int main() 44 { 45 int n, m; 46 cin >> n >> m; 47 cout << f(n, m) << endl << g(n, m) << endl; 48 return 0; 49 }
当输入为 7 3 时，第 行用来取最小值的 min 函数执行了 次。（ ）
输出的两行整数总是相同的。（ ）
（1.5 分）当 m 为 时，输出的第一行总为 n。（ ）
算法 g(n,m) 最为准确的时间复杂度分析结果为（ ）。
当输入为 20 2 时，输出的第一行为（ ）。
当输入为 100 100 时，输出的第一行为（ ）。