首页 > 代码库 > Codeforces Round #401 (Div. 2) E 贪心,线段树
Codeforces Round #401 (Div. 2) E 贪心,线段树
Codeforces Round #401 (Div. 2)
A 循环节
B 暴力排一下
C 标记出来，但10^5，特耿直地码了个O(n^2)的上去，最气的是在最后3分钟的时候被叉==
D 从后往前贪心暴糙一下就好。比赛时一眼瞄出来了不敢写，搞不懂这样竟然不会超时。。
E. Hanoi Factory
题意：n个环体，内径a[i]，外径b[i]，高h[i]。当 a[i+1]<b[i]<=b[i+1] 时，第 i 个环体可以堆在第 i+1个环体上。求可以堆出的最高高度。
tags：佩服那些大佬，怎么一眼就能看出用线段树呢。。
按b[i]排好序，线段树维护高度。对于第 i 个环体，找出区间[ a[i]+1, b[i] ] 上的最大高度，然后更新b[i] 上的高度。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define mid ((L+((R-L)>>1)))typedef long long ll;const int N = 1e5+10;int n, p[N<<1], cnt, tot;ll tr[N<<3], ans;struct Ring{ int a, b, h; friend bool operator < (const Ring &ca, const Ring &cb) { if(ca.b==cb.b) return ca.a<cb.a; // 坑点，这里必须要加判断 return ca.b<cb.b; }}r[N];ll query(int ro, int L, int R, int l, int r){ if(L==l && R==r) return tr[ro]; if(r<=mid) return query(ro<<1, L, mid, l, r); else if(mid<l) return query(ro<<1|1, mid+1, R, l, r); else return max(query(ro<<1, L, mid, l, mid), query(ro<<1|1, mid+1, R, mid+1, r));}void updata(int ro, int L, int R, int pos, ll v){ if(L==R && L==pos) { tr[ro]=v; return ; } if(pos<=mid) updata(ro<<1, L, mid, pos, v); else updata(ro<<1|1, mid+1, R, pos, v); tr[ro]=max(tr[ro<<1], tr[ro<<1|1]);}int getpos(int x) { return lower_bound(p+1, p+1+tot, x)-p; // -p}int main(){ scanf("%d", &n); rep(i,1,n) { scanf("%d %d %d", &r[i].a, &r[i].b, &r[i].h); p[++cnt]=r[i].a, p[++cnt]=r[i].b; //数组要记得取双倍 } sort(r+1, r+1+n); sort(p+1, p+1+cnt); tot=unique(p+1, p+1+cnt)-(p+1); // -(p+1) rep(i,1,n) { ll maxn=query(1, 1, tot, getpos(r[i].a+1), getpos(r[i].b)); updata(1, 1, tot, getpos(r[i].b), r[i].h+maxn); } printf("%lld\n", query(1, 1, tot, 1, tot)); return 0;}
Codeforces Round #401 (Div. 2) E 贪心,线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。