[toggle hide="yes" title="题目" color=""][ttl2v]081017[/ttl2v][/toggle]
T1 Blue
这道题结论性非常强,考试的时候想到一种可行的贪心策略是每次选择最远的石头跳,但是没去仔细想就去搞后面了,结果最后打了个暴力查找,50分。正解可以使用多种数据结构来找下一个位置,将O(n)变成O(logn),比如用set然后每次删除,或者是二分右端点+线段树(单点修改+区间最小值查询),于是这样就可过了(虽然用set还得卡(强)卡(开)常(O)数(3))。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#pragma GCC optimize("-O3") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; #define mxn 1000005 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<<1)+(s<<3)+ch-'0',ch=getchar(); return s*f; } int s[mxn]; set<int> st; set<int>::iterator it; inline void work(){ int n=read(),m=read(),d=read(),l=read(); for(int i=1;i<=n;++i) s[i]=read(); int ans=0,js=0,cur,x,ok; st.clear(),st.insert(0); for(int i=1;i<=n;++i) st.insert(s[i]); for(int i=1;i<=m;++i){ int cur=0,lst=0,ok=1; while(cur+d<l){ it=st.upper_bound(cur+d),it--,x=*it; if(x<=cur) {ok=0;break;} st.erase(x),cur=x; } ans+=ok; if(!ok) break; } if(ans<m) printf("%d\n",ans); else puts("Excited"); } int main(){ // freopen("blue.in","r",stdin); int cas=read(); while(cas--) work(); } |
T2 Weed
其实今天写博客主要是为了这道题。考试的时候没读明白题意,一直以为是不真正修改,然后调了快一个小时暴力(中间电脑关机一次),感觉自己好蠢。。。
实际上,每个加数和删除的操作可以看作是入栈和弹栈操作,之后可以用线段树维护多个操作间的关系。线段树上维护四个信息:
s:区间内加数总和(仅考虑区间内部影响);
nd:当前区间向前删除数字的数量;
na:当前区间内“净”加的元素数。
sd:当前区间被右兄弟删除后的总和。 ※仅对左儿子维护此信息。
我们通过维护以上四个标记,就可以得到答案(root->s)。现在我们考虑如何维护。
首先,在建树或修改时,只需要将叶子节点的前三个标记维护好即可;在递归返回时,再计算最后一个。如果左儿子不够右儿子删,那么非常简单,直接利用这几个标记计算即可,l->sd=0。比较麻烦的是左儿子不被删光的情况。我们先实现一个函数cal(x),利用sd标记计算在当前区间中删去x个元素后的和。
考虑cal(x)的实现(当前节点为o):
1.若r->na>x,那么返回l->sd+r->cal(x)。
2.若r->na<x,那么右儿子不够删,返回l->cal(x-r->na+r->nd)
※这里非常重要,一定要再删掉右儿子要删的
3.若r->na==x,直接返回l->sd。
有了这个函数,我们就可以非常方便地计算左儿子的sd,维护其他标记了,不再赘述。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define mxn 200005 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<<1)+(s<<3)+ch-'0',ch=getchar(); return s*f; } int scur,n,m,qk[mxn],qv[mxn]; struct node{ node *l,*r; int s,na,nd,sd; inline int cal(int x){ if(r->na==x) return l->sd; if(r->na>x) return l->sd+r->cal(x); else return l->cal(x-r->na+r->nd); } inline void mnt(){ if(l->na<=r->nd) { s=r->s,nd=l->nd+r->nd-l->na,na=r->na; l->sd=0; } else{ nd=l->nd; na=l->na+r->na-r->nd; if(r->nd) l->sd=l->cal(r->nd); else l->sd=l->s; s=l->sd+r->s; } } }*root,pool[mxn<<2]; inline void build(node *&o,int l,int r){ o=&pool[++scur]; if(l==r){ o->sd=0; if(!qk[l]) o->s=qv[l],o->na=1; else o->nd=qv[l]; } else{ int m=l+r>>1; build(o->l,l,m),build(o->r,m+1,r); o->mnt(); } } inline void update(node *o,int l,int r,int p,int k,int v){ if(l==r){ if(!k) o->s=v,o->na=1,o->nd=0; else o->s=0,o->na=0,o->nd=v; } else{ int m=l+r>>1; if(p<=m) update(o->l,l,m,p,k,v); else update(o->r,m+1,r,p,k,v); o->mnt(); } } int main(){ n=read(),m=read(); for(int i=1;i<=n;++i) qk[i]=read(),qv[i]=read(); build(root,1,n); while(m--){ int p=read(),k=read(),v=read(); update(root,1,n,p,k,v); printf("%d\n",root->s); } } |
T3 Drink
算算时间复杂度,大(强)力(开)卡(O)常(3)+用char减少耗时居然卡过去了(其实本来以为过不去的),跑得比标程还快,但是正解貌似只有wq会大模拟做法,据说5k...但是出题人非常不良心,数据上的范围比标注的大很多,好像有2000。。。
叨叨几句... 1 条评论
即使犯错也是为成功铺路!不怕错误,唯有信心和坚持!!!