大数据分析网站,代理公司注册变更,湛江网站建设咨询,什么是网络营销产生的基础文章目录Running MedianSequenceBuy Low Sell High[APIO/CTSC 2007] 数据备份[NOI2010] 超级钢琴「LibreOJ β Round」ZQC 的手办Running Median
source
对顶栈
用大根堆和小根堆一起维护
若元素小于等于大根堆栈顶#xff0c;放入大根堆否则放入小根堆
大根堆维护的就是…
文章目录Running MedianSequenceBuy Low Sell High[APIO/CTSC 2007] 数据备份[NOI2010] 超级钢琴「LibreOJ β Round」ZQC 的手办Running Median
source
对顶栈
用大根堆和小根堆一起维护
若元素小于等于大根堆栈顶放入大根堆否则放入小根堆
大根堆维护的就是前一半较小的树小根堆维护的就是后一半较大的树
最后调整两个堆的大小大根堆比小根堆多一
答案就是大根堆的栈顶
#include cstdio
#include queue
using namespace std;
#define maxn 10000
priority_queue int MS;
priority_queue int, vector int , greater int IS;
int x[maxn];int main() {int T, Case, n;scanf( %d, T );while( T -- ) {while( ! MS.empty() ) MS.pop();while( ! IS.empty() ) IS.pop();scanf( %d %d, Case, n );for( int i 1;i n;i )scanf( %d, x[i] );int cnt 0;printf( %d %d\n, Case, ( n 1 ) 1 );for( int i 1;i n;i ) {if( MS.empty() || x[i] MS.top() ) MS.push( x[i] );else IS.push( x[i] );if( i 1 ) {while( IS.size() ( i 1 ) )IS.push( MS.top() ), MS.pop();while( MS.size() ( ( i 1 ) 1 ) )MS.push( IS.top() ), IS.pop();cnt , printf( %d , MS.top() );if( cnt 10 ) printf( \n), cnt 0;}}printf( \n );}return 0;
} Sequence
source
先把每行的mmm个元素排序
一层一层的往下叠加仅保留前mmm小即可
#include queue
#include cstdio
#include cstring
#include algorithm
using namespace std;
#define maxn 2005
priority_queue int q;
int T, n, m;
int now[maxn], nxt[maxn];int main() {scanf( %d, T );while( T -- ) {scanf( %d %d, n, m );for( int i 1;i m;i )scanf( %d, now[i] );sort( now 1, now m 1 );for( int k 1;k n;k ) {for( int i 1;i m;i )scanf( %d, nxt[i] );sort( nxt 1, nxt m 1 );for( int i 1;i m;i )for( int j 1;j m;j ) {int val now[i] nxt[j];if( q.size() m ! q.empty() val q.top() ) break;else {q.push( val );while( q.size() m ) q.pop();}}for( int i 1;i m;i )now[m - i 1] q.top(), q.pop();}for( int i 1;i m;i )printf( %d , now[i] );printf( \n );}return 0;
}Buy Low Sell High
source
反悔贪心
如果第iii天的收益更好那么弹出栈顶选择第iii天
e.g.
k→j→ik\rightarrow j\rightarrow ik→j→i最优选择为k→ik\rightarrow ik→i
在当前最优解的jjj时选择k→jk\rightarrow jk→j先记录临时答案然后把jjj的股票价放进栈
在iii的时候进行pi−pjp_i-p_jpi−pj刚好抵消 pj−pkpi−pjpi−pkp_j-p_kp_i-p_jp_i-p_kpj−pkpi−pjpi−pk
#include cstdio
#include queue
using namespace std;
#define int long long
#define maxn 300005
priority_queue int, vector int , greater int q;
int n, ans;
int p[maxn];signed main() {scanf( %lld, n );for( int i 1;i n;i )scanf( %lld, p[i] );for( int i 1;i n;i ) {if( ! q.empty() q.top() p[i] )ans p[i] - q.top(), q.pop(), q.push( p[i] );q.push( p[i] );}printf( %lld\n, ans );return 0;
}[APIO/CTSC 2007] 数据备份
source
反悔贪心
选了iii就不能选i−1,i1i-1,i1i−1,i1
弥补的代价为di−1di1−did_{i-1}d_{i1}-d_idi−1di1−di
双向链表维护
#include queue
#include cstdio
#include iostream
using namespace std;
#define maxn 100005
#define int long long
struct node {int id, l, r, val;node(){}node( int ID, int L, int R, int Val ) {id ID, l L, r R, val Val;}
}it[maxn];
struct Node {int id, val;Node(){}Node( int ID, int Val ) {id ID, val Val;}bool operator ( Node t ) const {return val t.val;}
};
priority_queue Node q;
int n, k, ans;
bool vis[maxn];void Delete( int x ) {it[x].l it[it[x].l].l;it[x].r it[it[x].r].r;it[it[x].l].r x;it[it[x].r].l x;
}signed main() {int last;scanf( %lld %lld %lld, n, k, last );for( int i 1, d;i n;i ) {scanf( %lld, d );it[i] node( i, i - 1, i 1, d - last );q.push( Node( i, d - last ) );last d;}it[0].val it[n].val 1e15;for( int i 1;i k;i ) {while( vis[q.top().id] ) q.pop(); int val q.top().val, x q.top().id;q.pop(), ans val;vis[it[x].l] vis[it[x].r] 1;it[x].val it[it[x].l].val it[it[x].r].val - it[x].val;q.push( Node( x, it[x].val ) );Delete( x );}printf( %lld\n, ans );return 0;
} [NOI2010] 超级钢琴
source
对于每个iii将其符合要求的区间扔进队列确定最大值的位置pospospos
可以使用ststst表预处理最大值位置
然后大根堆开始选择
一段区间最大值知晓了次大值一定是在最大值的左边或者右边刨除最大值位置
所以直接将区间划成两部分扔进大根堆要保证区间存在
#include iostream
#include cstdio
#include queue
#include cmath
using namespace std;
#define maxn 500005
int n, k, L, R;
int sum[maxn];
int st[maxn][20];void init() {for( int i 1;i n;i ) st[i][0] i;for( int j 1;j 20;j )for( int i 1;i ( 1 j ) - 1 n;i )if( sum[st[i ( 1 j - 1 )][j - 1]] sum[st[i][j - 1]] )st[i][j] st[i ( 1 j - 1 )][j - 1];elsest[i][j] st[i][j - 1];
}int query( int l, int r ) {int i log2( r - l 1 );if( sum[st[l][i]] sum[st[r - ( 1 i ) 1][i]] )return st[l][i];elsereturn st[r - ( 1 i ) 1][i];
}struct node {int s, l, r, t;node( int S, int L, int R ) { s S, l L, r R, t query( l, r ); }bool operator ( node MS ) const { return sum[t] - sum[s - 1] sum[MS.t] - sum[MS.s - 1]; }
};
priority_queue node q;int main() {scanf( %d %d %d %d, n, k, L, R );for( int i 1;i n;i ) {scanf( %d, sum[i] );sum[i] sum[i - 1];}init();for( int i 1;i n - L 1;i )q.push( node( i, i L - 1, min( i R - 1, n ) ) );long long ans 0;while( k -- ) {node now q.top(); q.pop();ans sum[now.t] - sum[now.s - 1];if( now.t ! now.l ) q.push( node( now.s, now.l, now.t - 1 ) );if( now.t ! now.r ) q.push( node( now.s, now.t 1, now.r ) );}printf( %lld\n, ans );return 0;
}「LibreOJ β Round」ZQC 的手办
source
超级钢琴的父版
操作111直接线段树标记维护
操作222因为保证xxx总和不会很大那么类似超级钢琴一样将区间切成两部分那种
用线段树查区间最小值以及最小值位置
#include queue
#include cstdio
#include iostream
using namespace std;
#define maxn 500005
#define inf 0x7f7f7f7f
#define lson num 1
#define rson num 1 | 1
#define Pair pair int, int
void read(int x) {x 0;char s getchar();while (s 0 || s 9)s getchar();while (0 s s 9) {x (x 1) (x 3) (s ^ 48);s getchar();}
}
struct node {int l, r;Pair ret;node() {}node(int L, int R, Pair p) {l L, r R, ret p;}bool operator (const node t) const {return ret.first t.ret.first;}
};
priority_queue node q;
int a[maxn], ans[maxn];
int t[maxn 2], pos[maxn 2], tag[maxn 2];void pushup(int num) {if (t[lson] t[rson])t[num] t[lson], pos[num] pos[lson];elset[num] t[rson], pos[num] pos[rson];
}void build(int num, int l, int r) {if (l r) {t[num] a[l];pos[num] l;return;}int mid (l r) 1;build(lson, l, mid);build(rson, mid 1, r);pushup(num);
}void pushdown(int num) {t[lson] max(t[lson], tag[num]);t[rson] max(t[rson], tag[num]);tag[lson] max(tag[lson], tag[num]);tag[rson] max(tag[rson], tag[num]);tag[num] 0;
}void modify(int num, int l, int r, int L, int R, int k) {if (t[num] k)return;if (R l || r L)return;if (L l r R) {t[num] max(t[num], k);tag[num] max(tag[num], k);return;}pushdown(num);int mid (l r) 1;modify(lson, l, mid, L, R, k);modify(rson, mid 1, r, L, R, k);pushup(num);
}Pair query(int num, int l, int r, int L, int R) {if (r L || R l)return make_pair(inf, inf);if (L l r R)return make_pair(t[num], pos[num]);pushdown(num);int mid (l r) 1;Pair ans1 query(lson, l, mid, L, R);Pair ans2 query(rson, mid 1, r, L, R);if (ans1.first ans2.first)return ans1;elsereturn ans2;
}int main() {int n, m;read(n);for (int i 1; i n; i )read(a[i]);build(1, 1, n);read(m);for (int i 1, opt, a, b, k, x; i m; i ) {read(opt), read(a), read(b), read(k);if (opt 1)modify(1, 1, n, a, b, k);else {read(x);while (! q.empty())q.pop();int cnt 0;q.push(node(a, b, query(1, 1, n, a, b)));while (! q.empty() cnt x) {node now q.top();q.pop();int val now.ret.first, pos now.ret.second;if (val k)break;elseans[ cnt] val;if (pos ! now.l)q.push(node(now.l, pos - 1, query(1, 1, n, now.l, pos - 1)));if (pos ! now.r)q.push(node(pos 1, now.r, query(1, 1, n, pos 1, now.r)));}if (cnt x)printf(-1\n);else {for (int i 1; i x; i )printf(%d , ans[i]);printf(\n);}}}return 0;
}
