bzoj#4722-由乃【倍增,抽屉原理,bitset】
2024-08-25 23:16:23
正题
题目链接:https://darkbzoj.tk/problem/4722
题目大意
给出一个长度为\(n\)的序列值域为\([0,v)\),要求支持操作
- 询问一个区间能否找到两个没有交的非空下标集合使得这些位置的和加上集合的大小相等。
- 区间立方然后取模\(v\)。
\(1\leq n\leq 10^5,1\leq v\leq 1000\)
解题思路
考虑如果我们选出了两个有交的集合相等,那么我们把交的部分去掉就变成无交的了,所以无需考虑有没有交。
然后根据抽屉原理对于\(n\)个元素所有集合总共能表示出\(2^n\)个和,但是和最大只有\(n\times v\)所以如果\(2^n>n\times v\)时就肯定有解,那么此时会发现当\(v\)最大时\(n\)超过\(13\)就肯定有解。
如果元素个数小于或等于\(13\)时我们可以先预处理出一个倍增数组加上一个树状数组来统计每个数最终被修改了多少次就可以得到每个数的具体值了。然后考虑\(dp\),因为值域比较大可以用\(bitset\)优化就好了。
时间复杂度\(O(v\log m+m\log n+m\frac{13v}{\omega})\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define lowbit(x) (x&-x)
using namespace std;
const int N=1e5+10;
int n,m,v,f[1100][18],t[N],a[N];
bitset<13001>b;
void Change(int x,int val){
while(x<=n){
t[x]+=val;
x+=lowbit(x);
}
return;
}
int Ask(int x){
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
int Step(int x,int b){
for(int i=0;(1<<i)<=b;i++)
if((b>>i)&1)x=f[x][i];
return x;
}
int main()
{
scanf("%d%d%d",&n,&m,&v);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<v;i++)f[i][0]=i*i*i%v;
for(int j=1;(1<<j)<=n;j++)
for(int i=0;i<v;i++)
f[i][j]=f[f[i][j-1]][j-1];
while(m--){
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==2)Change(l,1),Change(r+1,-1);
else{
if(r-l+1>13){puts("Yuno");continue;}
b.reset();b[0]=1;bool flag=0;
for(int i=l;i<=r;i++){
int w=Step(a[i],Ask(i))+1;
if((b&(b<<w)).any()){flag=1;break;}
b=b|(b<<w);
}
if(flag)puts("Yuno");
else puts("Yuki");
}
}
return 0;
}
最新文章
- [Unreal]学习笔记之灯光说明
- nginx 支持laravel 5.3配置
- Spring学习进阶(四) Spring JDBC
- JS实现联想输入(一)
- jquery 获得table 行数
- KindEditor 4.1.10 (2013-11-23)首行空格不能显示在编辑器内
- 在java中高效的计数器
- Ubuntu12.4 64位 安装 arm linux gcc 4.3.2
- Windows下Mysql解压缩版配置安装与卸载
- VS2010+Visual Assist X
- C#编程建言笔记
- .net 资源
- (step8.2.7)hdu 1517(A Multiplication Game——巴什博弈变形)
- HDOJ 4248 A Famous Stone Collector DP
- 学习一之UML类图
- springmvc后台取值中文乱码问题
- Android 字体设置-Typeface讲解
- python验证码简单识别
- SQL 三范式
- BUG(1):一个关于指针的bug