人生第一道 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