基数排序发表时间:2022-10-27 20:31 基数排序 时间限制:10 sec 空间限制:1 GB 问题描述 给定 n 个 [0,2^k) 之间的整数,请你将它们升序排序。 由于 n 可能很大,为了避免过大的输入、输出规模,我们会在程序内部生成数据,并要求你输出排序后序列的哈希值。具体方法如下(用 c++代码展示): 输入将会给定 n,k,seed。 你可以调用 initData(a,n,k,seed) 来获得需要排序的 a 数组。 排序后,你可以调用函数 hashArr(a,n) 来获得我们希望你输出的哈希值。 输入格式 一行 3 个用空格隔开的整数 n,k,seed,意义见题目描述。 输格式 一行一个整数,表示我们希望你输出的哈希值。 样例输入 样例输 样例解释 生成的序列应为 4 10 13 9 4,排序后的结果应为 4 4 9 10 13。 数据范围 本题共设置 4 组数据。 对于第 1 组数据,保证 n=1000,k=16。对于第 2 组数据,保证 n=5*10^6,k=32。对于第 3 组数据,保证 n=10^8,k=16。对于第 4 组数据,保证 n=10^8,k=32。 保证给定的 seed 在 32 位无符号整数的范围内。 提示 [对于 k=16 的数据,使用基数排序即可。] [对于 k=32 的数据,不妨考虑两次基数排序哦!(即先排二进制下后 16 位,再排二进制下前 16 位)] 代码 #include <bits/stdc++.h> using namespace std; #include <bits/stdc++.h> using namespace std; // ================= 代码实现开始 ================= typedef unsigned int u32; // 以下代码不需要解释,你只需要知道这是用于生成数据的就行了 u32 nextInt(u32 x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } void initData(u32* a, int n, int k, u32 seed) { for (int i = 0; i < n; ++i) { seed = nextInt(seed); a[i] = seed >> (32 - k); } } u32 hashArr(u32* a, int n) { u32 x = 998244353, ret = 0; for (int i = 0; i < n; ++i) { ret ^= (a[i] + x); x = nextInt(x); } return ret; } // 以上代码不需要解释,你只需要知道这是用于生成数据的就行了const int N = 100000000; u32 a[N + 1]; u32 _a[N + 1]; const int m = 16; const int B = 1 << m; const int b = B - 1; int sum[B + 1]; // 这是你的排序函数,你需要将全局变量中的 a 数组进行排序 // n, k:意义与题目描述相符 // 返回值:本函数需不要返回值(你只需要确保 a 被排序即可) void sorting(int n, int k) { memset(sum, 0, sizeof(sum)); for (int i = 0; i < n; ++i) ++sum[a[i] & b]; for (int i = 1; i < B; ++i) sum[i] += sum[i - 1]; for (int i = n - 1; i >= 0; --i) _a[--sum[a[i] & b]] = a[i]; memset(sum, 0, sizeof(sum)); for (int i = 0; i < n; ++i) ++sum[(_a[i] >> m) & b]; for (int i = 1; i < B; ++i) sum[i] += sum[i - 1]; for (int i = n - 1; i >= 0; --i) a[--sum[(_a[i] >> m) & b]] = _a[i]; } // ================= 代码实现结束 =================
int main() { int n, k; u32 seed; scanf("%d%d%u", &n, &k, &seed); initData(a, n, k, seed);
sorting(n, k);
u32 ans = hashArr(a, n); printf("%u\n", ans); return 0; } |