081017模拟

[toggle hide="yes" title="题目" color=""][ttl2v]081017[/ttl2v][/toggle]

T1 Blue

这道题结论性非常强，考试的时候想到一种可行的贪心策略是每次选择最远的石头跳，但是没去仔细想就去搞后面了，结果最后打了个暴力查找，50分。正解可以使用多种数据结构来找下一个位置，将O(n)变成O(logn)，比如用set然后每次删除，或者是二分右端点+线段树（单点修改+区间最小值查询），于是这样就可过了（虽然用set还得卡(强)卡(开)常(O)数(3)）。

#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();
}

#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，维护其他标记了，不再赘述。

#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);
	}
}

#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。。。

Narcissus' Blog

T1 Blue

T2 Weed

T3 Drink

071017模拟

101017模拟

Scott

叨叨几句... 1 条评论

liuliu 博主

取消回复

Narcissus' Blog