阅读程序

#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;
}