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;
}