选择题 共15道
阅读程序 共17道
完善程序 共10道
阅读程序
#include <iostream> using namespace std; const int N = 1000; int c[N]; int logic(int x, int y) { return (x & y) ^ ((x ^ y) | (x & y)); } void generate(int a, int b, int *c) { for (int i = 0; i < b; i++) { c[i] = logic(a, i) % (b + 1); } } void recursion(int depth, int *arr, int size) { if (depth <= 0 || size <= 1) return; int pivot = arr[0]; int i = 0, j = size - 1; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; } } recursion(depth - 1, arr, j + 1); recursion(depth - 1, arr + i, size - i); } int main() { int a, b, d; cin >> a >> b >> d; generate(a, b, c); recursion(d, c, b); for (int i = 0; i < b; i++) cout << c[i] << " "; }
阅读程序2
#include #include using namespace std; const int P = 998244353, N = 1e4 + 10, M = 20; int n, m; string s; int dp[1 << M]; int solve() { dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = (1 << (m - 1)) - 1; j >= 0; j--) { int k = (j << 1) | (s[i] - '0'); if (j != 0 || s[j] == '1') dp[k] = (dp[k] + dp[j]) % P; } } int ans = 0; for (int i = 0; i < (1 << m); i++) { ans = (ans + 1ll * i * dp[i]) % P; } return ans; } int solve2() { int ans = 0; for (int i = 0; i < (1 << n); i++) { int cnt = 0; int num = 0; for (int j = 0; j < n; j++) { if (i & (1 << j)) { num = num * 2 + (s[j] - '0'); cnt++; } } if (cnt <= m) (ans += num) %= P; } return ans; } int main() { cin >> n >> m; cin >> s; if (n <= 20) { cout << solve2() << endl; } cout << solve() << endl; return 0; }
假设输入的 s 是包含 n 个字符的 01 串，函数 solve() 所实现的算法时间复杂度是 O(n*2^m)。
阅读程序3
#include < iostream > #include < cstring > #include < algorithm > using namespace std; const int maxn = 1000000 + 5; const int P1 = 998244353, P2 = 1000000007; const int B1 = 2, B2 = 31; const int K1 = 0, K2 = 13; typedef long long II; int n; bool p[maxn]; int p1[maxn], p2[maxn]; struct H { int h1, h2, l; H(bool b = false) { h1 = b + K1; h2 = b + K2; l = 1; } H operator + (const H &h)const { H hh; hh.l = l + h.l; hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1; hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2; return hh; } bool operator == (const H &h)const { return l == h.l && h1 == h.h1 && h2 == h.h2; } bool operator <(const H &h)const { if (l != h.l) return l < h.l; else if (h1 != h.h1) return h1 < h.h1; else return h2 < h.h2; } } h[maxn]; void init() { memset(p, 1, sizeof(p)); p[0] = p[1] = false; p1[0] = p2[0] = 1; for (int i = 1; i <= n; i++) { p1[i] = (1ll * B1 * p1[i - 1]) % P1; p2[i] = (1ll * B2 * p2[i - 1]) % P2; if (!p[i])continue; for (int j = 2 * i; j <= n; j += i) { p[j] = false; } } } int solve() { for (int i = n; i; i--) { h[i] = H(p[i]); if (2 * i + 1 <= n) { h[i] = h[2 * i] + h[i] + h[2 * i + 1]; } else if (2 * i <= n) { h[i] = h[2 * i] + h[i]; } } cout << h[1].h1 << endl; sort(h + 1, h + n + 1); int m = unique(h + 1, h + n + 1) - (h + 1); return m; } int main() { cin >> n; init(); cout << solve() << endl; }
假设程序运行前能自动将 maxn 改为 n+1，所实现的算法的时间复杂度是 O(nlogn)。
完善程序（单选题，每小题 3 分，共计 30 分）
合并序列，有两个长度为 N 的单调不降序列 A 和 B，序列的每个元素都是小于 10^9 的非负整数。在 A 和 B 中各取一个数相加可以得到 N^2 个和，求其中第 k 小的和。上述参 数满足 N<=10^5 和 1<=K<=N^2
#include < iostream > using namespace std; const int maxn = 100005; int n; long long k; int a[maxn], b[maxn]; int *upper_bound(int *a, int *an, int ai) { int l = 0, r = ______(1)______; while (l < r) { int mid = (l + r) >> 1; if (______(2)______) { r = mid; } else { l = mid + 1; } } return ______(3)______; } long long get_rank(int sum) { long long rank = 0; for (int i = 0; i < n; i++) { rank += upper_bound(b, b + n, sum - a[i]) - b; } return rank; } int solve() { int i = 0, r = ______(4)______; while (i < r) { int mid = ((long long)! + r) >> 1; if (______(5)______) { i = mid + 1; } else { r = mid; } } return i; } int main() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; cout << solve() << endl; return 0; }
（次短路）已知有一个 n 个点 m 条边的有向图 G，并且给定图中的两个点 s 和 t，求次 短路（长度严格大于最短路的最短路径）。如果不存在，输出一行“-1”。如果存在，输出两 行，第一行表示此段路经的长度，第二行表示此段路的一个方案
#include < cstdio > #include < queue > #include < utility > #include < cstring > using namespace std; const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279; int n, m, s, t; int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1; int dis[maxn << 1], *dis2; int pre[maxn << 1], *pre2; bool vis[maxn << 1]; void add(int a, int b, int c) { ++tot; nxt[tot] = head[a]; to[tot] = b; w[tot] = c; head[a] = tot; } bool upd(int a, int b, int d, priority_queue>& q) { if (d >= dis[b]) return false; if (b < n) ______(1)______; q.push(______(2)______); dis[b] = d; pre[b] = a; return true; } void solve() { priority_queue> q; q.push(make_pair(0, s)); memset(dis, ______(3)______, sizeof(dis)); memset(pre, -1, sizeof(pre)); dis2 = dis + n; pre2 = pre + n; dis[s] = 0; while (!q.empty()) { int aa = q.top().second; q.pop(); if (vis[aa]) continue; vis[aa] = true; int a = aa % n; for (int e = head[a]; e; e = nxt[e]) { int b = to[e], c = w[e]; if (aa < n) { if (upd(a, b, dis[a] + c, q)) ______(4)______; } else { upd(n + a, n + b, dis2[a] + c, q); } } } } void out(int a) { if (a != s) { if (a < n) out(pre[a]); else out(______(5)______); } printf("%d%s", a % n + 1, (a == n + t) ? "\n" : " "); } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); s--, t--; for (int i = 0; i < m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a - 1, b - 1, c); } solve(); if (dis2[t] == inf) puts("-1"); else { printf("%d\n", dis2[t]); out(n + t); } return 0; }