meet in the middle，适用于输入数据较小，但也没小到可以直接用暴力搜索通过的情况。
主要的思想就是讲整个搜索过程分成两半进行，最后在将这两半的结果进行合并，对于搜索复杂度为 \(O(a^b)\) 的情况，meet in the middle 可以将它优化为 \(O(a^{\frac{b}{2}})\)。
题目
P5691 [NOI2001] 方程的解数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
原来的暴力搜索复杂度是 \(150^{6}\)，折半后是 \(2 \times 150^{3}\)。
//The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 10;
int n, m;
int k[N], p[N];
vector<int> sum[3];
ll qpow(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1) {
ans = ans * x;
}
y >>= 1;
x = x * x;
}
return ans;
}
void dfs(int u, ll tot, int tp) {
if (u > n) {
sum[tp].emplace_back(tot);
return ;
}
rep (i, 1, m, 1) {
dfs(u + 2, tot + 1ll * k[u] * qpow(i, p[u]), tp);
}
}
int main() {
n = read<int>(), m = read<int>();
rep (i, 1, n, 1) {
k[i] = read<ll>(), p[i] = read<ll>();
}
dfs(1, 0, 1);
dfs(2, 0, 2);
sort(sum[1].begin(), sum[1].end());
sort(sum[2].begin(), sum[2].end());
int siz1 = sum[1].size() - 1, r = sum[2].size() - 1, ans = 0;
rep (l, 0, siz1, 1) {
while (sum[2][r] + sum[1][l] > 0 && r > 0) {
-- r;
}
per (j, r, 0, 1) {
if (sum[2][j] + sum[1][l] == 0) {
++ ans;
} else {
break ;
}
}
}
cout << ans << '\n';
return 0;
}
P9234 [蓝桥杯 2023 省 A] 买瓜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
卡常题，meet in the middle 是其中优化的一部分。
然而我并没有卡过去
//The code was written by yifan, and yifan is neutral!!!
// 并不是 AC 代码，只是提供 meet in the middle 的应用
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
typedef long double db;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 40;
const int mod = 1e7 + 7;
using tli = tuple<ll, int>;
int n;
ll m;
ll a[N];
vector<ll> res[3];
cc_hash_table <ll, int> mp[3];
void dfs(int u, ll tot, int tp, int cnt) {
if (tot > m) return ;
if (mp[tp][tot] != 0 && cnt > mp[tp][tot]) {
return ;
}
if (u > n) {
if (mp[tp][tot] == 0) {
res[tp].emplace_back(tot);
mp[tp][tot] = cnt;
} else if (mp[tp][tot] > cnt) {
mp[tp][tot] = cnt;
}
return ;
}
dfs(u + 2, tot, tp, cnt);
dfs(u + 2, tot + a[u], tp, cnt);
dfs(u + 2, tot + a[u] / 2, tp, cnt + 1);
}
int main() {
n = read<int>(), m = read<ll>();
m <<= 1;
rep (i, 1, n, 1) {
a[i] = read<ll>();
a[i] <<= 1;
}
sort(a + 1, a + n + 1);
dfs(1, 0, 1, 0);
dfs(2, 0, 2, 0);
sort(res[1].begin(), res[1].end());
sort(res[2].begin(), res[2].end());
int siz1 = res[1].size(), siz2 = res[2].size(), r = siz2 - 1, ans = n + 1;
rep (l, 0, siz1 - 1, 1) {
while (res[1][l] + res[2][r] > m && r > 0) {
-- r;
}
if (res[1][l] + res[2][r] == m) {
ans = min(ans, mp[1][res[1][l]] + mp[2][res[2][r]]);
}
}
if (ans == n + 1) {
puts("-1");
return 0;
}
cout << ans << '\n';
return 0;
}
Wavy numbers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题剧毒瘤！！！
十进制下最多是 \(14\) 位数，折半，前 \(7\) 位搜一搜，后 \(7\) 位搜一搜，处理出相接地方是浪顶和浪底的情况，然后二分查找位置求情况数量。
//The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const ll seven = 1e7;
const ll six = 1e6;
const ll five = 1e5;
const int UP = 2;
const int DN = 1;
using tll = pair<ll, ll>;
ll n, k;
vector<ll> base;
vector<tll> up, down;
void dfs(ll v, int pos, int res) {
if (res == 1) {
if (v % n == 0) {
-- k;
if (!k) {
cout << v << '\n';
exit(0);
}
}
base.emplace_back(v);
if (v >= six) {
if (pos == UP) {
down.emplace_back(v % n, v);
} else {
up.emplace_back(v % n, v);
}
} else if (v >= five) {
if (pos == DN) {
up.emplace_back(v % n, v);
}
}
return ;
}
if (pos != DN) {
int lim = v % 10;
rep (i, 0, lim - 1, 1) {
dfs(v * 10 + i, DN, res - 1);
}
}
if (pos != UP) {
int start = v % 10 + 1;
rep (i, start, 9, 1) {
dfs(v * 10 + i, UP, res - 1);
}
}
}
int main() {
n = read<ll>(), k = read<ll>();
rep (i, 1, 7, 1) {
rep (st, 1, 9, 1) {
dfs(st, 0, i);
}
}
sort(down.begin(), down.end());
sort(up.begin(), up.end());
for (ll it : base) {
ll need = (n - it * seven % n) % n;
if (it < 10) {
int num = lower_bound(up.begin(), up.end(), tll(need, it * six))
- lower_bound(up.begin(), up.end(), tll(need, 0ll));
if (num >= k) {
tll g = *(lower_bound(up.begin(), up.end(), tll(need, 0LL)) + k - 1);
cout << it * seven + get<1>(g) << '\n';
return 0;
}
k -= num;
int num2 = lower_bound(down.begin(), down.end(), tll(need + 1, 0LL))
- lower_bound(down.begin(), down.end(), tll(need, (it + 1) * six));
if (num2 >= k) {
cout << it * seven + get<1>(*(lower_bound(down.begin(), down.end(), tll(need, (it + 1) * six)) + k - 1)) << '\n';
return 0;
}
k -= num2;
} else {
int num = 0;
if (it / 10 % 10 < it % 10) {
num = lower_bound(up.begin(), up.end(), tll(need, it % 10 * six))
- lower_bound(up.begin(), up.end(), tll(need, 0ll));
if (num >= k) {
cout << it * seven + get<1>(*(lower_bound(up.begin(), up.end(), tll(need, 0ll)) + k - 1)) << '\n';
return 0;
}
} else {
num = lower_bound(down.begin(), down.end(), tll(need + 1, 0ll))
- lower_bound(down.begin(), down.end(), tll(need, (it % 10 + 1) * six));
if (num >= k) {
cout << it * seven + get<1>(*(lower_bound(down.begin(), down.end(), tll(need, (it % 10 + 1) * six)) + k - 1)) << '\n';
return 0;
}
}
k -= num;
}
}
puts("-1");
return 0;
}