[POI2016]Korale 堆+st表

xiaoxiao2021-03-01  7

Desription 给你n个数。现在你可以选择若干个数(也可以一个都不选),选择的价值为所有数的价值和。现在给所有可能的选择,先按权值从小到大排序,对于权值相同的,根据所用数字集合的标号的字典序从小到大排序。请输出第k小的选择的价值,以及所用的选择集合。


Sample Input 4 10 3 7 4 3


Sample Output 10 1 3 4


这题卡长卡了我一上午。。。 首先我们如果按照DFS的思想,每一次对于一个数,我们要么选,要么不选,但这样是肯定会T的,我们需要一些想法。 如果我希望使序列长度加1,那我肯定是选择前面一个最小的数。 如果我们使序列长度增长,那我们肯定就使选择一个当前的次小值将他替换当前队尾的值,这里你可以用超级钢琴的思想来做,然后用个堆维护。 然后关于字典序之类的,你可以用他pre的rank来瞎搞搞。 (关于卡长,有一个小技巧:把数组维数换一换就能快。。。 我本来st表是这么开的:int f[1000010][21] 给成这样就快了:int f[21][1000010] 至于能快多少,这道题里面,差不多有6,7s这样子。。。 )


#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; inline int read() { int s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * f; } struct node { LL sum; int l, r, x, pre, rank; } p[3000010]; int o, heap[3000010]; LL a[1000010]; int Log[1000010], f[21][1000010], bin[21]; inline int _min(int x, int y) {return a[x] <= a[y] ? x : y;} inline bool pd(int x, int y) { if(p[x].sum == p[y].sum) { if(p[x].x == p[y].x) return p[p[x].pre].rank < p[p[y].pre].rank; return p[x].x < p[y].x; } return p[x].sum < p[y].sum; } inline void up(int x) { while(x) { if(x / 2 && pd(heap[x], heap[x / 2])) swap(heap[x], heap[x / 2]), x /= 2; else break; } } inline void down(int x) { int s = x * 2; while(s <= o) { if(s < o && pd(heap[s + 1], heap[s])) s++; if(pd(heap[s], heap[x])) swap(heap[x], heap[s]), x = s, s *= 2; else break; } } inline int query(int l, int r) { register int hh = Log[r - l + 1]; return _min(f[hh][l], f[hh][r - bin[hh] + 1]); } inline void print(int x) { printf("%d ", p[x].x); if(p[x].pre) print(p[x].pre); } int main() { int n = read(), k = read(); k--; if(k == 0) { printf("0\n"); return 0; } a[0] = 999999999; register int i, j; for(i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1; for(i = 1; i <= n; ++i) a[i] = read(), f[0][i] = i; bin[0]=1; for(i = 1; i <= 20; ++i) bin[i] = bin[i - 1] << 1; for(i = 1; bin[i] <= n; ++i) for(j = 1; j + bin[i - 1] <= n; ++j) f[i][j] = _min(f[i - 1][j], f[i - 1][j + bin[i - 1]]); int tp = 1; p[1].l = 1, p[1].r = n, p[1].x = query(1, n), p[1].sum = a[p[1].x], p[1].pre = 0; heap[o = 1] = 1; LL last = -1, hh = 0; while(k--) { int g = heap[1]; swap(heap[1], heap[o--]); down(1); node now = p[g]; if(!k) {printf("%lld\n", now.sum); print(g); return 0;} if(now.sum > last) last = now.sum, hh = 1; else hh++; p[g].rank = hh; if(now.x > 1) { int j = ++tp; p[j].l = 1, p[j].r = now.x - 1, p[j].x = query(1, now.x - 1); p[j].sum = now.sum + a[p[j].x], p[j].pre = g; heap[++o] = j; up(o); } if(now.l < now.x) { int j = ++tp; p[j].l = now.l, p[j].r = now.x - 1, p[j].x = query(now.l, now.x - 1); p[j].sum = now.sum + a[p[j].x] - a[now.x], p[j].pre = now.pre; heap[++o] = j; up(o); } if(now.x < now.r) { int j = ++tp; p[j].l = now.x + 1, p[j].r = now.r, p[j].x = query(now.x + 1, now.r); p[j].sum = now.sum + a[p[j].x] - a[now.x], p[j].pre = now.pre; heap[++o] = j; up(o); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-3350253.html

最新回复(0)