二分+贪心+DP。跟 D1T2 思路有点类似,反正很简单。
复杂度大约是 \({\rm O}(n^22^n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll inf = 1e18;
int T, n, q[N]; ll K, w[N];
vector<int> Q;
ll dp(int o, int d, int ub) {
if (d == 0)
return q[o ^ (1 << n)] <= ub ? inf : 0;
ll left = dp(o << 1, d - 1, ub), right = dp(o << 1 | 1, d - 1, ub);
return left + min(w[o], right);
}
void solve(int o, int d, ll &k) {
if (d == 0) {
Q.push_back(q[o ^ (1 << n)]);
return;
}
int l = 1, r = 1 << n;
ll delta = 0;
while (l < r) {
int mid = l + r >> 1;
ll cost = dp(o, d, mid);
if (cost <= k) l = mid + 1, delta = cost;
else r = mid;
}
Q.push_back(l);
k -= delta;
int u = o << d;
while (q[u ^ (1 << n)] != l) u++;
for (int i = 0; i < d; i++, u >>= 1) {
ll cost = dp(u ^ 1, i, l);
if (u & 1)
k += cost;
else {
k += min(cost, w[u >> 1]);
if (k < cost) k -= w[u >> 1];
}
solve(u ^ 1, i, k);
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%lld", &n, &K);
for (int i = 1; i < 1 << n; i++)
scanf("%lld", &w[i]);
for (int i = 0; i < 1 << n; i++)
scanf("%d", &q[i]);
Q.clear();
solve(1, n, K);
for (int v : Q) printf("%d ", v);
putchar('\n');
}
return 0;
}
标签:const,省选,ll,P10220,int,cost,联考,dp
From: https://www.cnblogs.com/ac-evil/p/18051472