1.
#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++;j--;
}
}
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] << " ";
}
判断题
1) 当1000>=d>=b 时，输出的序列是有序的（ ）
2) 当输入“5 5 1”时，输出为“1 1 5 5 5”（ ）
3) 假设数组c 长度无限制，该程序所实现的算法的时间复杂度是O(b)的（ ）
选择题
4) 函数int logic(int x,int y)的功能是（ ）
5) （4 分）当输入为“10 100 100”时，输出的第100 个数是（ ）
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 ll;
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;
elsereturn 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;
}
判断题
1) 假设程序运行前能自动将maxn 改为n+1，所实现的算法的时间复杂度是O(nlogn)。( )
2) 时间开销的瓶颈是init()函数（ ）
3) 若修改常数B1 或K1 的值，该程序可能会输出不同呢的结果（ ）
选择题
4) 在solve()函数种，h[]的合并顺序可以看作是：（ ）
5) 输入“10”，输出的第一行是？（ ）
6) (4 分)输入“16”，输出的第二行是？（ ）