题目大意

定义一个字符串的熵为：

$- \sum_{c} p_{c} \times \log_2 p_{c}$

其中 $p_{c}$ 为字符 $c$ 在字符串中的占比。例如 aaabb 中 $p_a = 0.6$。

给定实数 $x$，要求构造一个长度不超过 $10^3$，字符集大小不超过 $64$ 的字符串，它的熵 $y$ 满足 $\vert x - y \vert \le 5 \times 10 ^ {-3}$。

数据范围：$0 \le x \le 6$。

思路分析

我不知道标算是什么，但是我会乱搞。

首先我们规定所有串的长度都为 $10^3$ 左右。

发现字符集 $\le 4$ 的时候我们可以枚举出每一种情况。我们在本地打出表，发现这已经可以覆盖 $0 \le x \le 2$ 的所有情况。于是我们只需解决 $2 < x \le 6$ 的情况。

考虑 $6$ 的构造，是串中 $64$ 种字符的出现次数相同。我们考虑在此基础上进行偏移。先构造出一个 $64$ 个字符每个都出现了 $15$ 次的字符串（总长度为 $960$），然后每次随机两个字符，一个出现次数 $+1$，一个出现次数 $-1$。经过多轮微调后，熵会变得越来越小。发现它可以解决 $5.7 < x \le 6$（甚至更多）的情况。

现在我们还剩下 $2 < x \le 5.7$ 的情况。考虑固定字符集大小，随机每个字符的出现次数。由于我们要求出现次数的和恰好为 $10^3$，我们可以采用隔板法来随机。多次随机后取最优解输出。经过不断的尝试，有如下发现：

$2 < x \le 3$ 时，字符集大小为 $12$ 最为合适。
$3 < x \le 4$ 时，字符集大小为 $20$ 最为合适。
$4 < x \le 4.8$ 时，字符集大小为 $36$ 最为合适。
$4.8 < x \le 5.5$ 时，字符集大小为 $56$ 最为合适。
$5.5 < x \le 5.7$ 时，字符集大小为 $64$ 最为合适。

于是我们根据 $x$ 设定参数即可。至此所有情况被完全覆盖，我们已经可以解决这个问题了。

代码实现

1	#include <cmath>
2	#include <ctime>
3	#include <cstdio>
4	#include <cstdlib>
5	#include <algorithm>
6	using namespace std;
7
8	typedef double db;
9	const int n = 1000;
10	db x;
11
12	namespace part1 {
13	int cnt[205][5];
14	void get_cnt() {
15	// 此处是一张大表，在此由于篇幅原因已经省略
16	// 你可以在 https://paste.ubuntu.com/p/2JVdnFMSpR/ 处找到这张表
17	}
18	void main(db x) {
19	get_cnt();
20	int y = x * 100 + .5;
21	for (int k = 0; k < 4; k++) {
22	for (int i = 0; i < cnt[y][k]; i++) {
23	putchar('a' + k);
24	}
25	}
26	puts("");
27	}
28	}
29
30	namespace part2 {
31	const char ch[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', '.'};
32	const db t = 1. / log(2);
33	const int n = 1000;
34	int a[n + 3];
35	bool vis[n + 3];
36	db my_abs(db x) {
37	return x < 0 ? -x : x;
38	}
39	db func(db x) {
40	if (x < 1e-9) return 0;
41	return -x * log(x) * t;
42	}
43	void main(db num, int m) {
44	srand(19491001);
45	for (int i = 0; ; i++) {
46	for (int i = 2; i <= m; i++) {
47	int x = rand() % (n - 1) + 1;
48	while (vis[x]) {
49	x = rand() % (n - 1) + 1;
50	}
51	vis[x] = true;
52	a[i] = x;
53	}
54	a[1] = 0, a[m + 1] = 1000;
55	sort(a + 1, a + m + 2);
56	db sum = 0;
57	for (int i = 1; i <= m; i++) {
58	sum += func((a[i + 1] - a[i]) / 1000.);
59	vis[a[i]] = false;
60	}
61	if (my_abs(sum - num) < 0.005) {
62	for (int i = 1; i <= m; i++) {
63	for (int j = a[i]; j < a[i + 1]; j++) {
64	putchar(ch[i - 1]);
65	}
66	}
67	puts("");
68	break;
69	}
70	}
71	}
72	}
73
74	namespace part3 {
75	const char ch[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', '.'};
76	const int n = 960, m = 64;
77	const db t = 1 / log(2);
78	int c[m + 3];
79	db func(db x) {
80	if (x < 1e-9) return 0;
81	return -x * log(x) * t;
82	}
83	db my_abs(db x) {
84	return x < 0 ? -x : x;
85	}
86	void main(db x) {
87	srand(19260817);
88	for (int i = 0; i < m; i++) {
89	c[i] = 15;
90	}
91	db s = 0;
92	for (int i = 0; i < m; i++) {
93	s += func(1. * c[i] / n);
94	}
95	for (int i = 0; ; i++) {
96	if (my_abs(x - s) < 0.005) {
97	for (int i = 0; i < m; i++) {
98	for (int j = 0; j < c[i]; j++) {
99	putchar(ch[i]);
100	}
101	}
102	puts("");
103	break;
104	}
105	int x = rand() % m, y = rand() % m;
106	while (!c[y]) {
107	y = rand() % m;
108	}
109	s -= func(1. * c[x] / n);
110	s -= func(1. * c[y] / n);
111	c[x]++, c[y]--;
112	s += func(1. * c[x] / n);
113	s += func(1. * c[y] / n);
114	}
115	}
116	}
117
118	int main() {
119	scanf("%lf", &x);
120	if (x <= 2) {
121	part1::main(x);
122	} else if (x <= 3) {
123	part2::main(x, 12);
124	} else if (x <= 4) {
125	part2::main(x, 20);
126	} else if (x <= 4.8) {
127	part2::main(x, 36);
128	} else if (x <= 5.5) {
129	part2::main(x, 56);
130	} else if (x <= 5.7) {
131	part2::main(x, 64);
132	} else {
133	part3::main(x);
134	}
135	return 0;
136	}