原题是可以用暴力过的，当然加强版过不了。
首先我们最朴素的做法就是对 和 分类，把所有合法的最大值 丢到堆里面，然后就是一个简单的贪心。显然这个做法是十分暴力的，考虑优化。
我们发现每次弹出的时候都要把次大值放回堆里，这个枚举次大值时间复杂度是非常高的，然后总的伪光滑数的个数其实是不多的，我们考虑预处理出来，就可以把枚举时间复杂度优化到 。
令 表示第 小的质数，首先能想出一个显然的转移方案： 表示 且 的伪光滑数堆，转移方程即为 ，令 ，可以前缀和优化 。
然后这还是时间空间爆炸，但是看到堆合并，可以用启发式合并 / 左偏树优化时间复杂度；而空间可以可持久化，于是我们对于每一个状态建立可持久化左偏树，并下传标记即可。
然后因为实现不同，此思路可能在加强版获得 0 分的好成绩，仔细观察发现合并左偏树所需的时间和空间都是极大的，都是 级别。对于删除最大值不一定要真的删除堆顶，只要把左儿子和右儿子放入堆中即可，。时间复杂度？不知道，反正能过。
代码轻微压行，此是加强版代码，普通版改改参数就过了。
#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll, int>
using namespace std;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (! isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
return x * f;
}
const int maxn = 5e6 + 10, lg_max = 40;
int k, tot, l, pr[105], f[105][105], g[105][105]; bool vis[105][105];
int lc[maxn], rc[maxn], dis[maxn]; priority_queue<PII> q; ll ans, n, lz[maxn], a[maxn];
void cpy(int x, int y) { tie(dis[y], lc[y], rc[y], lz[y], a[y]) = make_tuple(dis[x], lc[x], rc[x], lz[x], a[x]); }
int mul(int x, ll v) { int p = ++ tot; cpy(x, p), lz[p] *= v, a[p] *= v; return p; }
void trans(int &x, ll v) { if (!x) return ; int p = x; x = ++ tot; cpy(p, x), lz[x] *= v, a[x] *= v; }
void pushd(int x) { if (lz[x] - 1) trans(lc[x], lz[x]), trans(rc[x], lz[x]), lz[x] = 1; }
int merg(int x, int y) {
if (!x || !y) return x | y; if (a[x] < a[y]) swap(x, y);
int p = ++ tot; cpy(x, p), pushd(p), rc[p] = merg(rc[p], y);
if (dis[lc[p]] < dis[rc[p]]) swap(lc[p], rc[p]);
dis[p] = dis[rc[p]] + 1; return p;
}
signed main() {
n = read(), k = read(); bool fl = 1;
for (int i = 2; i <= 397; i ++) { fl = 1; for (int j = 2; j * j <= i; j ++) fl &= bool(i % j); if (fl) pr[++ l] = i; }
for (int j = 1; j <= l; j ++) { ll s = pr[j]; int p = 1; while (s <= n) s *= pr[j], vis[p ++][j] = 1; }
for (int i = 1; vis[1][i]; i ++) {
lz[++ tot] = 1, a[tot] = pr[i], f[1][i] = g[1][i] = tot;
q.push({pr[i], tot}), g[1][i] = merg(g[1][i - 1], g[1][i]);
}
for (int i = 2; i <= lg_max; i ++) for (int j = 1; vis[i][j]; j ++)
g[i][j] = merg(f[i][j] = mul(g[i - 1][j], pr[j]), g[i][j - 1]), q.push({a[f[i][j]], f[i][j]});
while (k --) {
PII t = q.top(); q.pop();
int T; tie(ans, T) = t, pushd(T);
if (lc[T]) q.push({a[lc[T]], lc[T]});
if (rc[T]) q.push({a[rc[T]], rc[T]});
}
printf("%lld", ans);
return 0;
}
共 1 条回复
主要就是数集 dp 用可持久化数据结构优化，知道这个点其实整题的思路就很丝滑了。