\(noip模拟23\;solutions\)

怎么说呢？？这个考试考得是非常的惨烈，一共拿了70分，为啥呢

因为我第一题和第三题爆零了，然后第二题拿到了70分，还是贪心的分数

第一题和第二题我调了好久，hhhh

害，害，害，害

\(T1\;联\)

据出题人说，这是个线段树裸题，啊啊啊，我看到1e5的时候也觉得这是个简单的线段树

后来看到1e18我就溜走了，后来回来看，发现这个可以\(O(n^2)\)链表做

打对了1，2操作，忘记换行了0分，应该是30分

这个题说白了就是利用线段树维护值，不过你发现他的范围极其大

但是，这里面有用的值吧，只有这些区间的端点和这些区间右端点的右边那一位

所以我们要做的就是一个离散化，然后就很容易找到了这第一个0

再看看操作，1，2直接下放，3的话就追上1，2的时候给他的laz标记异或一下

代码实现极其简单，我因为pushdown没有改当前值WA了好长时间

注意离散化要把1也弄进去，离散化数组开打一点

AC_code


#include<bits/stdc++.h>

using namespace std;

#define re register int

#define ll long long

const int N=1e5+5;

int m;

int typ[N];

ll a[N],b[N];

ll lsh[N*10],lh;

map<long long,int> ys;

struct TREE{

	#define ls x<<1

	#define rs x<<1|1

	int laz[N*16],now[N*16],mn[N*16];

	TREE(){}

	void pushup(int x){

		mn[x]=min(mn[ls],mn[rs]);

		return ;

	}

	void build(int x,int l,int r){

		mn[x]=l;

		if(l==r){

			return ;

		}

		now[x]=-1;

		int mid=l+r>>1;

		build(ls,l,mid);

		build(rs,mid+1,r);

		return ;

	}

	void pushdown(int x,int l,int r){

		if(now[x]==-1)return ;

		int mid=l+r>>1;

		now[ls]=now[rs]=now[x];

		if(now[x]==0){

			mn[ls]=l;mn[rs]=mid+1;

		}

		else if(now[x]==1)mn[ls]=mn[rs]=0x3f3f3f3f;

		now[x]=-1;

		return ;

	}

	void ins(int x,int l,int r,int ql,int qr,int v){

		//if(v==1)cout<<x<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<now[x]<<" "<<mn[x]<<endl;

		if((ql<=l&&r<=qr)&&(v!=3||now[x]!=-1)){

			if(v==1)now[x]=1;

			if(v==2)now[x]=0;

			if(v==3){

				now[x]^=1;

			}

			if(now[x]==0)mn[x]=l;

			if(now[x]==1)mn[x]=0x3f3f3f3f;

			return ;

		}

		pushdown(x,l,r);

		int mid=l+r>>1;

		if(ql<=mid)ins(ls,l,mid,ql,qr,v);

		if(qr>mid)ins(rs,mid+1,r,ql,qr,v);

		pushup(x);

		//if(v==1)cout<<x<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<now[x]<<" "<<mn[x]<<endl;

		return ;

	}

}xds;

signed main(){

	scanf("%d",&m);

	lsh[++lh]=1;

	for(re i=1;i<=m;i++){

		scanf("%d%lld%lld",&typ[i],&a[i],&b[i]);

		lsh[++lh]=a[i];

		lsh[++lh]=b[i];

		lsh[++lh]=b[i]+1;

	}

	sort(lsh+1,lsh+lh+1);

	lh=unique(lsh+1,lsh+lh+1)-lsh-1;

	for(re i=1;i<=lh;i++)ys[lsh[i]]=i;//cout<<i<<" "<<lsh[i]<<endl;

	xds.build(1,1,lh);

	for(re i=1;i<=m;i++){

		a[i]=ys[a[i]];

		b[i]=ys[b[i]];

		//cout<<a[i]<<" "<<b[i]<<endl;

		xds.ins(1,1,lh,a[i],b[i],typ[i]);

		//cout<<xds.now[64]<<" ";

		printf("%lld\n",lsh[xds.mn[1]]);

	}

}

\(T2\;赛\)

这个题考场上我只会打贪心，拿到了70pts

最后我发现，这个贪心正确性果然保证不了，因为你无法枚举完所有的情况

并且你根本不知道要选多少共同喜欢的物品才能达到最有解

所以我们就枚举，先枚举一个共同喜欢的个数，再枚举在各自喜欢的中选多少

最后在剩余的中寻找前几个，最后的这个用线段树，要不然复杂度就炸了

这里有一堆边界之要维护，诸如，是否有足够m个共同喜欢的。。。。

AC_code


#include<bits/stdc++.h>

using namespace std;

#define re register int

#define ll long long

const int N=2e5+5;

int n,m,k,a[N],b[N];

bool via[N],vib[N],vis[N];

int val[N];

int cc[N],ac[N],bc[N];

ll ans,res;

struct node{

	int ls[N*40],rs[N*40];

	ll sum[N*40],siz[N*40];

	int seg;

	void pushup(int x){

		sum[x]=sum[ls[x]]+sum[rs[x]];

		siz[x]=siz[ls[x]]+siz[rs[x]];

	}

	void ins(int &x,int l,int r,int pos){

		if(!x)x=++seg;

		if(l==r){

			siz[x]+=1;

			sum[x]+=pos;

			return ;

		}

		int mid=l+r>>1;

		if(pos<=mid)ins(ls[x],l,mid,pos);

		else ins(rs[x],mid+1,r,pos);

		pushup(x);return ;

	}

	void del(int x,int l,int r,int pos){

		if(l==r){

			siz[x]-=1;

			sum[x]-=pos;

			return ;

		}

		int mid=l+r>>1;

		if(pos<=mid)del(ls[x],l,mid,pos);

		else del(rs[x],mid+1,r,pos);

		pushup(x);return ;

	}

	ll query(int x,int l,int r,int rak){

		if(!rak)return 0;

		if(!x)return 0;

		if(!siz[x])return 0;

		if(rak==siz[x])return sum[x];

		int mid=l+r>>1;ll ret=0;

		if(rak>siz[ls[x]]){

			ret+=query(ls[x],l,r,siz[ls[x]]);

			ret+=query(rs[x],l,r,rak-siz[ls[x]]);

		}

		else ret+=query(ls[x],l,r,rak);

		return ret;

	}

}xds;

int R,rt;

bool cmp(int x,int y){

	return val[x]<val[y];

}

signed main(){

	ans=0x3f3f3f3f3f3f3f3f;

	scanf("%d%d%d",&n,&m,&k);

	for(re i=1;i<=n;i++)scanf("%d",&val[i]),R=max(R,val[i]);

	scanf("%d",&a[0]);

	for(re i=1;i<=a[0];i++)scanf("%d",&a[i]);

	scanf("%d",&b[0]);

	for(re i=1;i<=b[0];i++)scanf("%d",&b[i]);

	for(re i=1;i<=a[0];i++)via[a[i]]=true;

	for(re i=1;i<=b[0];i++)vib[b[i]]=true;

	for(re i=1;i<=a[0];i++)if(vib[a[i]])cc[++cc[0]]=a[i];

	for(re i=1;i<=a[0];i++)if(!vib[a[i]])ac[++ac[0]]=a[i];

	for(re i=1;i<=b[0];i++)if(!via[b[i]])bc[++bc[0]]=b[i];

	int nc=m,na;

	while(nc>cc[0])nc--;

	if(k-nc>ac[0]||k-nc>bc[0]||nc<2*k-m){

		printf("-1");

		return 0;

	}

	//cout<<"sb"<<endl;

	sort(cc+1,cc+cc[0]+1,cmp);

	sort(ac+1,ac+ac[0]+1,cmp);

	sort(bc+1,bc+bc[0]+1,cmp);

	for(re i=1;i<=nc;i++)vis[cc[i]]=true,res+=val[cc[i]];

	for(re i=1;i<=k-nc;i++)vis[ac[i]]=true,res+=val[ac[i]];

	for(re i=1;i<=k-nc;i++)vis[bc[i]]=true,res+=val[bc[i]];

	for(re i=1;i<=n;i++)if(!vis[i])xds.ins(rt,1,R,val[i]);

	na=max(k-nc,0);

	//cout<<"sb"<<endl;

	//cout<<res<<" "<<na<<" "<<nc<<" "<<xds.query(rt,1,R,m-2*na-nc)<<endl;

	ans=min(ans,res+xds.query(rt,1,R,m-na*2-nc));

	for(re i=nc;i>=max(1,2*k-m);i--){

		if(na>ac[0]||na>bc[0])break;

		res-=val[cc[i]];vis[cc[i]]=false;

		xds.ins(rt,1,R,val[cc[i]]);

		if(k-i+1>0){

			res+=val[ac[k-i+1]];vis[ac[k-i+1]]=true;

			xds.del(rt,1,R,val[ac[k-i+1]]);

			res+=val[bc[k-i+1]];vis[bc[k-i+1]]=true;

			xds.del(rt,1,R,val[bc[k-i+1]]);

			na++;

		}

		if(na*2+i-1>m)break;

		//cout<<ans<<" "<<na<<" "<<i<<endl;

		ans=min(ans,res+xds.query(rt,1,R,m-2*na-i+1));

		//cout<<ans<<" "<<res<<" "<<cc[i]<<" "<<ac[k-i+1]<<" "<<bc[k-i+1]<<endl;

	}

	printf("%lld",ans);

}

调的时候千万不要着急，得耐心的调，要不然肯定调不出来

\(T3\;题\)

这个我第一眼看上去就是一个图论，然后没有想到怎么做

最后dfs也没有打对，就直接0分了，其实就是一个大枚举。。。。

维护一个\(bool\)数组\(f[i][j]\)，

1表示，如果想让i存在，那么必须删掉j，0就不用了呗

那么偶们就有了一个转移，每次枚举u，v

如果\(f[i][u]和f[i][v]\)都为1，那么这个苹果就不可能存在了，注意uv是从m到1的

因为你后面必须要删掉u，v，而你现在就要删掉一个，那后面的条件就不能满足了

如果只有其中一个为1，那就把另一个也标记成1

最后我们美剧可能存在的点，如果他们必须删掉的点集中没有交集，那就合法

AC_code


#include<bits/stdc++.h>

using namespace std;

#define re register int

const int N=405;

const int M=5e4+5;

int n,m;

int f[N][N],g[N];

int u[M],v[M];

int ans;

signed main(){

	scanf("%d%d",&n,&m);

	for(re i=1;i<=m;i++)scanf("%d%d",&u[i],&v[i]);

	for(re i=1;i<=n;i++)f[i][i]=1,g[i]=1;

	for(re i=1;i<=n;i++){

		for(re j=m;j>=1;j--){

			if(f[i][u[j]]&&f[i][v[j]])g[i]=0;

			else if(f[i][u[j]])f[i][v[j]]=1;

			else if(f[i][v[j]])f[i][u[j]]=1;

		}

	}

	for(re i=1;i<=n;i++){

		for(re j=1;j<=n;j++){

			int flag=0;

			if(!g[i]||!g[j])continue;

			for(re k=1;k<=n;k++){

				if(f[i][k]&&f[j][k])

					flag=1;

			}

			if(flag==0)ans++;

		}

	}

	printf("%d",ans/2);

}

巴特西

noip模拟23[联·赛·题]

\(noip模拟23\;solutions\)

\(T1\;联\)

\(T2\;赛\)

\(T3\;题\)

最新文章

热门文章