首页 > 其他分享 >题解 P5527 [Ynoi2012] NOIP2016 人生巅峰

题解 P5527 [Ynoi2012] NOIP2016 人生巅峰

时间:2022-10-21 11:46:35浏览次数:82  
标签:NOIP2016 P5527 cup int 题解 times 集合 有解 dp

人生第一道 Ynoi,同时也是 1k 通过。不卡常不难写,小清新 Ynoi 真的不多见了。

前置知识:抽屉原理,树状数组,bitset,动态规划基础。

首先考虑一个事实,当这个区间够长是必然有解的。

对于一个区间 \((l,r)\),它会产生 \(v\times(r-l+1)\) 种不同的贡献。而它只有 \(2^{r-l+1}-1\) 个不同的子集。所以当 \(v\times(r-l+1)<2^{r-l+1}-1\) 时必然有解。

我们来做一个类比,假设现在有两种颜色的小球,你要在这些小球中选三个,那么必然会有两个小球的颜色是一样的。同理,我们现在有 \(v\times(r-l+1)\) 种和,我们要在这些和中选 \(2^{r-l+1}-1\) 个,那么当 \(v\times(r-l+1) < 2^{r-l+1}-1\) 时一定会有至少一种和重复了一次。

我们把 \(v\) 的最大值带进去,解一个不等式就可以得到当 \(r-l+1>13\) 时必然有解。

现在区间长度小了,我们就可以直接背包做了。

具体地,令 \(dp_{i,j}\) 表示前 \(i\) 个数能不能凑出 \(j\) 。

转移方程显然为 \(dp_{i,j}=dp_{i-1,j-a_i-1}\),这里要减 \(1\) 是因为贡献是 \(a_i+1\) 。

那么重点来了,如何判断有解?

先下结论,如果有一个 \(j\) 使得 \(dp_{i-1,j}=dp_{i-1,j-a_i-1}\) 有解。

考虑每一个状态其实都表示一个集合,那么我们设 \(dp_{i-1,j}\) 为集合 \(S\),\(dp_{i-1,j-a_i-1}\) 为集合 \(T\),那么 \(S\) 和 \(T\cup \{i\}\) 都是贡献为 \(j\) 的集合。

而我们同时删除一些相同的元素,两个集合的贡献显然还是相等的。这个时候假设 \(S\cap(T\cup\{i\})=S\cap T=P\) 那么 \((S\setminus P)\cap((T\cup\{i\})\setminus P)=\varnothing\)。

所以当 \(dp_{i-1,j}=dp_{i-1,j-a_i-1}\) 时必然有解。

最后如何处理区间修改操作?当然可以欧拉定理降幂,但没有这个必要。

我们考虑先用树状数组记录每个位置被立方了多少次,修改的时候区间修改,假设我们用到了这个位置的数,单点查询一下,然后倍增处理即可。

具体地,令 \(t_{i,j}\) 表示 \(i\) 被立方了 \(2^j\) 后的值。用到的时候二进制分解算一下就好了。

代码:

int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int k)
{
	while(x<=n)
	{
		t[x]+=k;
		x+=lowbit(x);
	}
	return ;
}
int query(int x)
{
	int ret=0;
	while(x)
	{
		ret+=t[x];
		x-=lowbit(x);
	}
	return ret;
}
void clear()
{
	vis.reset();
	vis.set(0,1);
}
int main()
{
	read(n);read(m);read(v);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int j=0;j<v;j++)
	{
		tot[j][0]=j*j*j%v;
	}
	for(int i=1;i<=21;i++)
	{
		for(int j=0;j<v;j++)
		{
			tot[j][i]=tot[tot[j][i-1]][i-1];
		}
	}
	while(m--)
	{
		int opt,l,r;
		read(opt);
		read(l);
		read(r);
		flag=0;
		if(opt==2)
		{
			add(l,1);
			add(r+1,-1);
		}
		if(opt==1)
		{
			if(r-l+1>13)
			{
				puts("Yuno");
			}
			else
			{
				clear();
				for(int i=l;i<=r;i++)
				{
					int k=query(i);
					int x=a[i];
					for(int j=21;j>=0;j--)
					{
						if(k&(1<<j))
						{
							x=tot[x][j];
						}
					}//倍增查询x的值
					if((vis&(vis<<(x+1))).any())//这个就相当于 dp[i-1][j]=dp[i-1][j-a[i]-1]
					{
						puts("Yuno");
						flag=1;
						break;
					}
					vis=vis|(vis<<(x+1));//更新 dp 值
				}
				if(flag==0) puts("Yuki");
			}
		}
		
	}
	return 0;
}

标签:NOIP2016,P5527,cup,int,题解,times,集合,有解,dp
From: https://www.cnblogs.com/zplqwq/p/16812913.html

相关文章