根据数据量猜解法的技巧
一个基本事实：C/C++运行时间1s，可以运行常数数量级的程序1e8次左右。所以可以根据这个事实，来猜测自己算法是否正确。
问题规模和可用算法
| n 上限 | 安全复杂度 | 典型算法 / 思路 | 备注 |
|---|---|---|---|
| ≤ 11 | O(n!) | 全排列、暴力状态压缩 | 11! ≈ 4×10⁷ |
| ≤ 22 | O(2ⁿ) | 子集枚举、状压 DP | 2²² ≈ 4×10⁶ |
| ≤ 40 | O(2^{n/2}) | Meet-in-the-middle | 2²⁰ ≈ 1×10⁶ |
| ≤ 80 | O(n⁴) | 四维 DP、Floyd 强化 | 80⁴ = 4.1×10⁷ |
| ≤ 500 | O(n³) | Floyd、高斯消元、bitset | 500³ = 1.25×10⁸ |
| ≤ 3 000 | O(n² log n) | 枚举 + 二分、FFT/NTT | 3k² log₂3k ≈ 9×10⁷ |
| ≤ 10⁴ | O(n²) | 朴素 DP、二维前缀和 | 1e4² = 1×10⁸ |
| ≤ 5×10⁴ | O(n√n) | 分块莫队、根号分治 | 5×10⁴×√(5×10⁴) ≈ 1.1×10⁸ |
| ≤ 2×10⁵ | O(n log n) | 线段树、并查集、Dijkstra | 2e5 log₂2e5 ≈ 3.7×10⁶ |
| ≤ 1×10⁶ | O(n log log n) | 欧拉筛、线性筛 | 1e6 log log 1e6 ≈ 2×10⁷ |
| ≤ 2×10⁶ | O(n) | 单调队列、线性 DP、前缀和 | 2×10⁶ |
| ≤ 1×10⁷ | 常数极小 O(n) | 递推、滑动窗口、位运算 | 卡常数 |
| ≤ 5×10⁷ | 低于 O(n) | 数学推导、公式、结论题 | 直接输出答案 |
题目1 消灭怪物
问题概述
在一款打怪游戏中，玩家拥有n个技能（1≤n≤10），每个技能具有以下属性：
- 基础伤害
x[i] - 触发双倍伤害的条件：当怪物血量小于等于
y[i]时，该技能可造成2*x[i]的伤害 - 每个技能最多使用一次
目标是使用最少数量的技能将怪物的初始血量m（1≤m≤10^6）降至0或以下。
对于每一组数据，输出一行，代表使用的最少技能数量，若无法消灭输出-1。
核心思路
由于n的取值范围较小（最大为10），可以通过全排列枚举所有可能的技能使用顺序，计算每种顺序下消灭怪物所需的最少技能数，最终选择最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void dfs(int x) {
if (x > n) {
int m0 = m;
for (int i = 1; i <= n; i++) {
if (m0 <= 0) {
ans = min(ans, i);
break;
}
int idx = arr[i];
if (m0 <= hurt[idx].y) {
m0 -= 2 * hurt[idx].x;
} else {
m0 -= hurt[idx].x;
}
if (m0 <= 0) {
ans = min(ans, i);
break;
}
}
return;
}
for (int i = 1; i <= n; i++) {
if (st[i]) {
continue;
}
st[i] = 1;
arr[x] = i;
dfs(x + 1);
st[i] = 0;
arr[x] = 0;
}
}
void solve() {
memset(st, 0, sizeof(st));
ans = 1e9;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> hurt[i].x >> hurt[i].y;
}
// dbg(n);
dfs(1);
cout << ((ans == 1e9) ? -1 : ans) << endl;
}
题目2 超级回文数
问题概述
超级回文数的定义为：
- 自身是回文数
- 同时是另一个回文数的平方
给定两个正整数L和R（以字符串形式表示，范围在[1, 10^18)），需要返回[L, R]范围内超级回文数的数目。
根据数据量猜解法的技巧应用
本题中，L和R的长度最大为18，意味着数值范围可达10^18级别。直接遍历该范围内的所有数字并判断是否为超级回文数，显然不现实（计算量过大）。
核心思路：反向构造 超级回文数是”回文数的平方”，且自身也是回文数。因此，可通过构造”作为平方根的回文数”，再计算其平方并判断是否为回文数及是否在[L, R]范围内。
通过以上方法，可在合理时间内（$O(10^5)$ 级别运算）解决问题，避免遍历 $10^{18}$ 范围的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
bool ishuiwen(long long num, long long l, long long r) {
if (l <= num && num <= r) {
} else {
return false;
}
long long num0 = num;
long long ans = 0;
while (num0 != 0) {
ans *= 10;
ans += num0 % 10;
num0 /= 10;
}
return num == ans;
}
long long gethuiwenodd(long long num) { // 奇数
long long num0 = num;
num0 /= 10;
while (num0 != 0) {
num *= 10;
num += num0 % 10;
num0 /= 10;
}
return num;
}
long long gethuiweneven(long long num) { // 偶数
long long num0 = num;
while (num0 != 0) {
num *= 10;
num += num0 % 10;
num0 /= 10;
}
return num;
}
bool safeSquare(long long num) {
return num <=static_cast<long long>(sqrt(numeric_limits<long long>::max()));
}
int superpalindromesInRange(string left, string right) {
long long l = stoll(left);
long long r = stoll(right);
long long limit = (long long)sqrt(r);
long long seed = 1;
long long num = 0;
long long ans = 0;
do {
num = gethuiweneven(seed);
if (num <= limit && safeSquare(num) && ishuiwen(num * num, l, r)) {
ans++;
}
num = gethuiwenodd(seed);
if (num <= limit && safeSquare(num) && ishuiwen(num * num, l, r)) {
ans++;
}
seed++;
} while (num < limit);
return ans;
}
