CSP模拟58联测20 回忆旅途的过往-Toy模板网

这篇具有很好参考价值的文章主要介绍了CSP模拟58联测20 回忆旅途的过往。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目大意

有 $n$ 个砝码，每个砝码的初始重量为 $a_i$ 。有 $q$ 次操作，每次操作分为以下两种类型：

1 l r x：表示将 $l$ 到 $r$ 之间的所有 $a_i$ 都变成 $x$
2 l r x：查询 $l$ 到 $r$ 之间的所有砝码，每个砝码可以用无限次，求是否能称出质量 $x$

$a_i$ 和所有 $x$ 都小于等于 $m$ 。

保证 $a_i$ 和所有操作一的 $x$ 总共最多不超过 $10$ 种数。

注意砝码只能放在同一侧。

$1\leq n,q\leq 10^6,1\leq m\leq 10^5$

时间限制 $2500 m s$ ，空间限制 $256 MB$ 。

题解

设砝码质量的种数为 $v$ ，依照题意， $v\leq 10$ 。我们对于每种数取或者不取，总共有 $2^v$ 种情况。对每种情况做一次背包，每种情况可以在之前的基础上再加一个砝码的贡献而得出，所以这部分的时间复杂度为 $O(m2^v)$ 。

然后，用线段树维护每一段有哪几种数。因为数的种数只有不超过 $10$ 种，所以可以将每一段有的数进行状态压缩。那么操作一就是区间修改，操作二就是在查询对应区间中有的数的状态，并将状态在背包中查询是否可以达到即可。这部分的时间复杂度为 $O(n\log n)$ 。

这样做的话，空间复杂度是 $O(m2^v+n)$ 的，数组开不下，所以背包要用 $bi t se t$ 来存。

总时间复杂度为 $O(m2^v+n\log n)$ ，空间复杂度为 $O(\dfrac{m2^v}{64}+n)$ 。文章来源地址https://www.toymoban.com/news/detail-723594.html

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=1000000,M=100000;
int n,m,q,v1=0,a[N+5],z[M+5],v[15],ct[1<<10],tr[4*N+5],ly[4*N+5];
bitset<M+5>f[1505];
struct node{
	int tp,l,r,x;
}w[N+5];
int lb(int i){
	return i&(-i);
}
void build(int k,int l,int r){
	if(l==r){
		tr[k]=1<<z[a[l]]-1;
		return;
	}
	int mid=l+r>>1;
	build(lc,l,mid);build(rc,mid+1,r);
	tr[k]=tr[lc]|tr[rc];
}
void down(int k){
	tr[lc]=tr[rc]=ly[lc]=ly[rc]=ly[k];
	ly[k]=0;
}
void ch(int k,int l,int r,int x,int y,int v){
	if(l>=x&&r<=y){
		tr[k]=ly[k]=1<<v-1;
		return;
	}
	if(ly[k]) down(k);
	int mid=l+r>>1;
	if(x<=mid) ch(lc,l,mid,x,y,v);
	if(y>mid) ch(rc,mid+1,r,x,y,v);
	tr[k]=tr[lc]|tr[rc];
}
int find(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y) return tr[k];
	if(ly[k]) down(k);
	int mid=(l+r)>>1,re=0;
	if(x<=mid) re|=find(lc,l,mid,x,y);
	if(y>mid) re|=find(rc,mid+1,r,x,y);
	return re;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=0;i<=10;i++) ct[1<<i]=i;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(!z[a[i]]){
			z[a[i]]=++v1;v[v1]=a[i];
		}
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d%d%d",&w[i].tp,&w[i].l,&w[i].r,&w[i].x);
		if(w[i].tp==1&&!z[w[i].x]){
			z[w[i].x]=++v1;v[v1]=w[i].x;
		}
	}
	f[0][0]=1;
	for(int s=1;s<1<<v1;s++){
		int t=lb(s),w=ct[t]+1;
		f[s]=f[s^t];
		for(int i=v[w];i<=m;i++){
			f[s][i]=f[s][i]|f[s][i-v[w]];
		}
	}
	build(1,1,n);
	for(int i=1;i<=q;i++){
		if(w[i].tp==1) ch(1,1,n,w[i].l,w[i].r,z[w[i].x]);
		else{
			int tmp=find(1,1,n,w[i].l,w[i].r);
			if(f[tmp][w[i].x]) printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0;
}