1 条题解
-
1
赛后的做法。
首先,我们发现若区间存在两个相同元素,那么一定有解。
根据鸽笼原理,当区间长度大于等于时一定有解。
此时,我们需要解决的的区间满足元素互不相同。
我们注意到,一个集合非常容易有解,很难构造出很大的无解集合。
打表发现,当时,最大的无解集合大小为。
所以考虑相对暴力的做法。我们使用bitset来维护一些元素经过添加正负号(或弃用)之后,能够组成的数。这相当于一个可行性背包。
对于某个数,若前面的数能组成或则有解。
对于修改,用分块维护,扩展欧拉定理降幂。可能有更好的做法。
复杂度。其中是最大不合法集合大小。
代码:
#include<bits/stdc++.h> using namespace std; #define int long long #define lb(x) (x&(-x)) #define _Y "Yuno\n" #define _N "Yuki\n" int n,m,V; const int N=1e5+1000,B=400; int a[N]; int tms[N],tk[N]; inline int K(int x){ return (x-1)/B+1; } int phi; int pw[1010][2010]; int f3[N]; int hve[1010]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>V; for(int i=1;i<=V;i++){ if(__gcd(i,V)==1) phi++; }for(int i=1;i<V;i++){ pw[i][0]=1; for(int j=1;j<=2*phi;j++){ pw[i][j]=pw[i][j-1]*i%V; } }f3[0]=1; for(int i=1;i<=100000;i++){ f3[i]=f3[i-1]*3; if(f3[i]>=phi){ f3[i]=f3[i]%phi+phi; } } for(int i=1;i<=n;i++){ cin>>a[i]; } int cnt=0; for(int t=1;t<=m;t++){ int op,l,r; cin>>op>>l>>r; if(op==1){ cnt++; if(r-l+1>V){ cout<<_Y; continue; }for(int i=1;i<=V;i++) hve[i]=0; int flag=0; for(int i=l;i<=r;i++){ int val=pw[a[i]][f3[tms[i]+tk[K(i)]]]+1; if(hve[val]){ flag=1;break; }hve[val]=1; }if(flag){ cout<<_Y; continue; } const int D=5000;//5000过了,想保守一点可以开大一些 bitset<D*2+100>vis; vis[D]=1; for(int i=1;i<=V;i++){ if(hve[i]==0) continue; if(vis[D+i]==1||vis[D-i]==1){ flag=1;break; }vis=((vis|(vis<<i))|(vis>>i)); } if(flag==1){ cout<<_Y;continue; }cout<<_N; }else{ if(K(l)==K(r)){ for(int i=l;i<=r;i++) tms[i]=tms[i]+1; }else{ for(int i=l;i<=K(l)*B;i++) tms[i]=tms[i]+1; for(int i=K(r)*B-B+1;i<=r;i++) tms[i]=tms[i]+1; for(int i=K(l)+1;i<K(r);i++) tk[i]=tk[i]+1; } } } return 0; }
题外话:
在调试这道题时,我在SYOJ上看到了如下的错误信息:
Wrong Answer 0读取到 Yes,应为 Yuno。所以我合理推测,赛时的挂零是因为题面与数据不符导致的
- 1
信息
- ID
- 887
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 41
- 已通过
- 3
- 上传者