LYD说过，只要看完课件上的例题，都做一做，NOIP就能提高不少的分。
于是我开了这个大坑，打算把课件上的例题都做了。
其实并不是很容易啊。。。有好多内容都没听懂的。。。
好吧，一定要克服困难！
密码箱 bzoj 1406
求x^2=1 (mod p)的所有解
这题这么做：
x^2=1 mod p
(x+1)(x-1) = p*k
p|(x+1)(x-1)
令a*b=p 则
a|(x+1) && b|(x-1) || a|(x-1) && b|(x+1)
枚举p的约数带入验证
这道题告诉我们 对于约数的暴力是可行的
一定要注意的一点是 枚举的时候要枚举大的约数 这样保证了复杂度
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=1000000; long long p; int s[N],cnt; int main() { scanf("%lld",&p); for(long long i=1;i*i<=p;i++) if(p%i==0) { long long a=i,b=p/i;//需要保证p/i是较大的约数 否则会TLE for(int j=1;j<=p;j+=b)//枚举x 保证 x-1是b的约数 if((j+1)%a==0)s[++cnt]=j; for(int j=b-1;j<=p;j+=b)//枚举 x 保证 x+1是b的约数 if((j-1)%a==0)s[++cnt]=j; } sort(s+1,s+cnt+1); for(int i=1;i<=cnt;i++) if(s[i]==s[i-1])continue; else printf("%lld\n",s[i]); }
樱花 bzoj 2721
给定n，求1/x+1/y=1/(n!)的整数解的数量，结果对1e9+7取模
一开始以为是神题。。。
后来发现很巧妙
首先说一个定理
如果一个数可以被拆成 a1^b1*a2^b2*a3^b3…ak*bk 其中ai为素数 bi>0
则这个数的约数有(b1+1)*(b2+1)*(b3+1)..(bk+1)个
这个很好证明
每个素数有bi+1种选法(选有bi种 不选有一种) 乘法原理即可
那么 n!显然是可以表示为这种形式的
n!= a1^b1*a2^b2*a3^b3…ak*bk
这样显然不太好看。。
我们以n=10为栗子吧
10!=1*2*3*4*5*6*7*8*9*10
其中 表示成n!= a1^b1*a2^b2*a3^b3…ak*bk形式下 2的指数为
10/2^1+10/2^2+10/2^3
这个很容易理解
第一次我们除掉一个2
其中 2 4 8 10 可以被除掉 变成 1 2 4 5
为了凑成这4个2 我们需要2^4
第二次由于我们之前已经除掉了一个2 所以多除一个2
其中 4 8可以被除掉 我们需要2^2
以此类推
我们发现这个2的指数还可以写成这样：
while(n)
ans+=n/2,n/=2;
其实都一样啦
现在我们来看这个题
1/x+1/y=1/(n!)的整数解的数量
我们首先把他难度降低一些
1/x+1/y=1/n的整数解数量
进行一些变形 这式子散着没法搞
把x放到一边 其他的放到另一边
x=yn/(y-n)
分离常量 得
x=n(1-(n/y-n))
乘进去
x=n+(n^2)/(y-n)
然后喜闻乐见的发现答案就是n^2约数的数量
把n^2换成(n!)^2就行了
(n!)^2大概长这样：
1*1*2*2*3*3
把每个的指数算出来*2就行了
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=1000005; const long long mod=1000000007; int n; bool no[N]; int p[N],cnt; void init() { for(int i=2;i<=n;i++) { if(!no[i])p[++cnt]=i; for(int j=1;p[j]*i<=n;j++) { no[p[j]*i]=1; if(p[j]%i==0)break; } } } int main() { scanf("%d",&n); init(); long long ans=1; for(int i=1;i<=cnt;i++) { long long now=p[i],t=0; for(int j=1;now<=n;j++) { t=(t+n/now)%mod; now=now*p[i]; } t=(t*2+1)%mod; ans=(ans*t)%mod; } printf("%lld\n",ans); }
GCD统计相关：
仪仗队 bzoj 2721
这题实际上让求gcd(a,b)=1的个数 即n以下的欧拉函数之和
然而我们发现gcd(a,b)=1时gcd(b,a)也等于1，所以*2
根据题意 算上了0,0 0,1 1,0这三个点 所以*2+3即可
gcd bzoj 2818
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对
这个猛一看起来很吓人 是素数 好可怕
然而把素数筛出来，用n/p[i] 最后求和 就变成了上一题。。。
但是这题好像认为1不是素数 所以*2-1就行 减去(1,1)
沙【傻】拉【叉】公主的困惑
bzoj 2186
史上第一卡常题
这题是让求求1..n!中与m!互质的数的数量 mod r r为质数
首先 我们注意一个定理：
1 到 x*y 中和x互质的数的数量是phi(x)*y
这个画画图就知道了。。。并不会证
然后套用上面的公式
则变形为1 到 n!中与m!互质的数量为 phi(m!)*(n!/m!)
这样看上去能直接做了啊
phi(m!)=m!*π(1-1/pi)
然后可知素数pi<=m 且pi为m的素因子
有个定理 m!的素因子为m以下的所有素数
然后在m范围内筛出来就行啦！！
开开心心的敲完代码 默默地看了一眼数据范围。。。
询问<=10000
你在逗我 这是要O(1)出解。。。而n!/m!还要算一会。。。
只好继续化简 原式等价于
n!*π（1-1/pi) pi为m的素因子
继续化简成 n!*π(pi-1/pi) 这样出现了一个除法 需要逆元
现在 我们需要三个东西 阶乘 素数 逆元 统统在O(N)算出
逆元比较麻烦 需要递推或线性筛 不过线性筛好像特别慢
于是就递推了
然而交上去就TLE了 简直fucker
找到YJZ【常数优化小天使】 把long long全换成int 我自己加了小优化
就这样才A了。。。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const long long N=10000005; int p[N]; int jie[N],a[N]; int rev[N]; bool no[N]; int cnt; int r,n,t; void init() { for(int i=2;i<=n;i++) { if(!no[i])p[++cnt]=i; for(int j=1;(long long)p[j]*i<=n&&j<=cnt;j++) { no[p[j]*i]=1; if(i%p[j]==0)break; } } rev[1]=1; for(int i=2;i<=n;i++)//递推%r下逆元 if(i>=r)break; else rev[i]=((long long)(r-r/i)*rev[r%i])%r; jie[1]=1; for(int i=2;i<=n;i++) if(jie[i-1]==0)break; else jie[i]=((long long)(jie[i-1])*(i%r))%r; a[0]=a[1]=1; for(int i=2;i<=n;i++) { a[i]=a[i-1]; if(!no[i])a[i]=(long long)a[i]*(i-1)%r*rev[i%r]%r; } } int main() { scanf("%d%d",&t,&r); n=10000000; init(); while(t--) { int n,m; scanf("%d%d",&n,&m); printf("%d\n",((long long)jie[n]*a[m])%r); } }
tyvj1107或codevs1172
Hankson的趣味题
这题我的方法和网上题解都不一样哦
根据题意
可以推出
lcm(x,b0)=x*b0/gcd(x,b0)=b1
=> b1*gcd(x,b0)=x*b0
=> gcd(x,b0)=x*b0/b1
=> gcd(b1/b0,b1/x)=1
快算死我了==
然后你惊奇的发现 x是b1的约数！！！
然后有TM的约数暴力了。。
枚举约数sqrt(n) 验证logn 这应该可以卡过。。。
tyvj是官方数据（每个点数据不超过100组） 全过了
拿到codevs惊奇的发现有个2000组的数据 TLE了。。。
然后考虑两个小优化：
1 当x%a1!=0时 即a1不是x的约数时，显然不对
2 可以考虑将gcd(x,a0)=a1化简为gcd(x/a1,a0/a1)=1 再配上 gcd(b1/b0,b1/x)=1 这个验证 应该会快很多
最终结果是 加上这两个小优化后 程序跑的飞快。。貌似5000组数据都可以过。。。
论约数暴力的重要性
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int cnt,tot; int a0,a1,b0,b1; int gcd(int a,int b) {return b==0?a:gcd(b,a%b);} bool calc(long long x) { if(x%a1!=0)return 0; return gcd(x/a1,a0/a1)==1&&gcd(b1/b0,b1/x)==1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&a0,&a1,&b0,&b1); long long ans=0; for(int i=1;i*i<=b1;i++) { if(b1%i==0) { ans+=calc(i); if(b1/i!=i) ans+=calc(b1/i); } } printf("%lld\n",ans); } }
等差子序列
bzoj 2124
神奇的维护hash
从左到右扫描序列
设我们现在算到了当前数 now
首先我们设某个数如果在某个数的左边 则将其标为1 否则为0
然后你会发现 如果从小到大排列这个序列 会出现这样的形状：
1 0 0 1 0 1 0 1
如果这个数左右两边的串不相等 那么肯定就是有等差存在啦
所以用hash比较两边是否相等。。
然而需要修改 所以使用线段树维护hash
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=10005; int n,a[N]; unsigned long long power[N],base=131; struct segtree { int l,r; unsigned long long hash[2]; }tr[N*6]; void up(int p) { int len1=tr[p*2].r-tr[p*2].l+1,len2=tr[p*2+1].r-tr[p*2+1].l+1; tr[p].hash[0]=tr[p*2].hash[0]*power[len2]+tr[p*2+1].hash[0]; tr[p].hash[1]=tr[p*2+1].hash[1]*power[len1]+tr[p*2].hash[1]; } void build(int p,int l,int r) { tr[p].l=l,tr[p].r=r; if(l==r){tr[p].hash[1]=tr[p].hash[0]=0;return;} int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); } void change(int p,int l,int r,int x) { if(tr[p].l==l&&tr[p].r==r) { tr[p].hash[0]=tr[p].hash[1]=x;return; } int mid=(tr[p].l+tr[p].r)/2; if(l<=mid)change(p*2,l,r,x); if(r>mid)change(p*2+1,l,r,x); up(p); } unsigned long long get1(int p,int l,int r) { if(tr[p].l==l&&tr[p].r==r)return tr[p].hash[0]; unsigned long long ret1,ret2; int mid=(tr[p].l+tr[p].r)/2; if(r<=mid)return get1(p*2,l,r); else if(l>mid)return get1(p*2+1,l,r); else { ret1=get1(p*2,l,mid); ret2=get1(p*2+1,mid+1,r); return ret1*power[r-mid]+ret2; } } unsigned long long get2(int p,int l,int r) { if(tr[p].l==l&&tr[p].r==r)return tr[p].hash[1]; unsigned long long ret1,ret2; int mid=(tr[p].l+tr[p].r)/2; if(r<=mid)return get2(p*2,l,r); else if(l>mid)return get2(p*2+1,l,r); else { ret1=get2(p*2,l,mid); ret2=get2(p*2+1,mid+1,r); return ret2*power[mid-l+1]+ret1; } } int main() { int t;scanf("%d",&t); while(t--) { memset(&tr,0,sizeof tr); memset(a,0,sizeof a); memset(power,0,sizeof power); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); power[0]=1; for(int i=1;i<=n;i++)power[i]=power[i-1]*base; build(1,1,n);bool flag=0; for(int i=1;i<=n;i++) { int now=a[i]; if(now!=1&&now!=n) { int len=min(now-1,n-now); if(get1(1,now-len,now-1)!=get2(1,now+1,now+len)) {flag=1,puts("Y");break;} } change(1,now,now,1); } if(!flag)puts("N"); } }
秦腾与教学评估
二分+智商题。。。
bzoj 1271
据dyf神犇介绍，此题具有悠久的历史，不过还是个智商题。
由于题中给出了一个重要的性质，奇数个的点只有一个。
我们设人数前缀为奇数的点为1，其他的为2 整个序列变成了这样
0000001111111 显然满足单调性
于是我们二分查找第一个1的位置即可 判定时计算前缀有多少人就行
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=210005; long long max(long long a,long long b) {return a>b?a:b;} long long min(long long a,long long b) {return a<b?a:b;} struct dat { long long l,r,d; }s[N]; int n; long long calc(int p) { long long sum=0; for(int i=1;i<=n;i++) { if(s[i].l>p)continue; long long ed=min(p,s[i].r); long long now=ceil((double)(ed-s[i].l+1)/(double)s[i].d); sum+=now; } return sum; } bool judge(int p) { return calc(p)%2;//如果是奇数则说明大了 } long long mn,mx; void work() { long long l=mn,r=mx,ans=-1; while(l<=r) { long long mid=(l+r)/2; if(judge(mid))ans=mid,r=mid-1; else l=mid+1; } if(ans!=-1) printf("%lld %lld\n",ans,(long long)calc(ans)-calc(ans-1)); else puts("Poor QIN Teng:("); } int main() { int t; scanf("%d",&t); while(t--) { mx=0,mn=0x3f3f3f3f; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",&s[i].l,&s[i].r,&s[i].d); mx=max(s[i].r,mx); mn=min(s[i].l,mn); } work(); } }
永无乡
bzoj 2733
启发式合并平衡树 treap真是好写好用
所谓启发式合并平衡树。。就是把大的往小的里面合并。。
对于这个题可以证明每个点只会被合并1次？
总之只是多个log而已
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=200005; int fa[N];//并查集 //独一无二的重要度。。。。 int find(int x){if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];} int cnt,root[N]; int f[N]; int n,m; struct treap {int l,r,v,rank,w,size;}tr[N*5],z; void up(int p) {tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;} void rturn(int &p) { int t=tr[p].l;tr[p].l=tr[t].r;tr[t].r=p; tr[t].size=tr[p].size;up(p);p=t; } void lturn(int &p) { int t=tr[p].r;tr[p].r=tr[t].l;tr[t].l=p; tr[t].size=tr[p].size;up(p);p=t; } void insert(int &p,int x,int id) { if(p==0) { p=++cnt; tr[p].size=1; tr[p].w=id; tr[p].v=x; tr[p].rank=rand(); return; } tr[p].size++; if(tr[p].v>x) { insert(tr[p].l,x,id); if(tr[tr[p].l].rank<tr[p].rank)rturn(p); } else { insert(tr[p].r,x,id); if(tr[tr[p].r].rank<tr[p].rank)lturn(p); } } int ask_kth(int &p,int x) { if(p==0)return 0; if(x<=tr[tr[p].l].size)return ask_kth(tr[p].l,x); if(x>tr[tr[p].l].size+1)return ask_kth(tr[p].r,x-tr[tr[p].l].size-1); return tr[p].w; } void join(int a,int b) { a=find(a),b=find(b); if(a==b)return; if(tr[root[a]].size>tr[root[b]].size)swap(a,b);//保证a的小 fa[a]=b;//将a并到b上 queue<int>q; q.push(root[a]); while(!q.empty()) { int p=q.front();q.pop(); insert(root[b],tr[p].v,tr[p].w); if(tr[p].l)q.push(tr[p].l); if(tr[p].r)q.push(tr[p].r); } } void init() { for(int i=1;i<=n;i++)fa[i]=i; } char s[10]; int main() { scanf("%d%d",&n,&m); init(); for(int i=1;i<=n;i++)scanf("%d",&f[i]),insert(root[i],f[i],i); for(int i=1;i<=m;i++) { int a,b;scanf("%d%d",&a,&b); join(a,b); } int t;scanf("%d",&t); while(t--) { scanf("%s",s); if(s[0]=='Q') { int a,k;scanf("%d%d",&a,&k); int x=find(a); if(tr[root[x]].size<k)puts("-1"); else printf("%d\n",ask_kth(root[x],k)); } else { int a,b; scanf("%d%d",&a,&b); join(a,b); } } }
dispatching
bzoj 2809
左偏树。。好写好用的可合并堆。。
核心操作merge logn的时间将两棵树合并 原理有点像一层一层的插
插节点-》合并单个节点 删堆顶-》合并左右子树
比较神奇
对于这个题 每个点建立一个左偏树 自底向上合并 如果超了限制就删堆顶，贪心思想取最值
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=100005*10,M=N*3; int list[M],next[M],head[N],tot; long long val[N],lead[N]; long long max(long long a,long long b) {return a>b?a:b;} void add(int a,int b) {tot++;list[tot]=b;next[tot]=head[a];head[a]=tot;} struct ltree { int l,r,h; long long v,sum,size; }tr[N]; int cnt; void up(int x) { tr[x].sum=tr[tr[x].l].sum+tr[tr[x].r].sum+tr[x].v; tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+1; } int merge(int x,int y) { if(!x||!y)return x+y; if(tr[x].v<tr[y].v)swap(x,y); tr[x].r=merge(tr[x].r,y);up(x); if(tr[tr[x].l].h<tr[tr[x].r].h)swap(tr[x].l,tr[x].r); tr[x].h=tr[x].r?tr[tr[x].r].h+1:0; return x; } void push(int &root,long long x) { tr[++cnt].v=tr[cnt].sum=x; tr[cnt].size=1; root=merge(root,cnt); } void pop(int &root) {root=merge(tr[root].l,tr[root].r);} bool empty(int &root) {return tr[root].size==0;} int n,m; long long ans=0; void calc(int &root,int v) { while(!empty(root)) if(tr[root].sum>m)pop(root); else break; ans=max(ans,lead[v]*tr[root].size); } void dfs(int &root,int v)//当前到达节点v { for(int i=head[v];i;i=next[i]) { int u=list[i]; int ro=0; dfs(ro,u); root=merge(ro,root); } push(root,val[v]); calc(root,v); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int x; scanf("%lld%lld%lld",&x,&val[i],&lead[i]); if(x)add(x,i); } int c=0;dfs(c,1); printf("%lld\n",ans); } }
字符串折叠
bzoj 1090
然而水题我也写挂了
明显的区间DP。。但是需要枚举折叠的循环节。。
总感觉暴力循环节会死 但是最终证明不会。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=105; int n,f[N][N];char s[N]; void dp() { memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++)f[i][i]=1; for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=n;i++) { int j=i+len-1; for(int k=1;k<=len/2;k++)//枚举位置 { if(len%k)continue; int p=1; for(int a=i+k,b=i;a<=j;a++) { if(s[a]!=s[b]){p=0;break;} b++; if(b==i+k)b=i; } if(p) f[i][j]=min(f[i][j],f[i][i+k-1]+3+(len/k>9)+(len/k>99)); } for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); } } printf("%d\n",f[1][n]); } int main() { scanf("%s",s+1); n=strlen(s+1); dp(); }
zap
bzoj 1101
莫比乌斯反演【我才不懂什么莫比乌斯反演呢】
我只知道一个公式 e(n)=Σd|n μ(d)
然后这题可以这么变形
gcd(a,b)=d 的数量可以看成
Σa<=n/d Σb<=m/d gcd(a,b) 【x<=N/d y<=M/d 互质的x y的对数】
然后套用神公式 变为
Σa<=n Σb<=m e(gcd(a/d,b/d))
Σa<=n Σb<=m Σd|gcd(a,b) μ(d)
Σa<=n Σb<=m Σd|a && d|b μ(d)
然后我们发现 Σd|a && d|b 的数量为
Σd<=n n/d*m/d
最后转化为
Σd<=n n/d*m/d*μ(d)
然后筛出μ n/d m/d 可以分块做。。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=51005; bool no[N]; int p[N],cnt,mu[N]; int sm[N]; int n,m,d; void init() { mu[1]=1; for(int i=2;i<=n;i++) { if(!no[i])p[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt&&i*p[j]<=n;j++) { no[i*p[j]]=1; mu[i*p[j]]=-mu[i];//多乘了个质数 取反 if(i%p[j]==0) {//之前这个数已经被乘了一个了 mu[i*p[j]]=0;//乘了两个 为0 break; } } } for(int i=1;i<=n;i++) sm[i]=sm[i-1]+mu[i]; } void work() { long long ans=0; int now=0; for(int i=1;i<=n;i=now+1) { now=min(n/(n/i),m/(m/i));//n/(n/i)为下块的前一个位置 n/(i+1)为前一块的最后一个位置 ans+=1LL*(sm[now]-sm[i-1])*(n/i)*(m/i); } printf("%lld\n",ans); } int main() { int t;n=50005; init(); scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&d); n/=d,m/=d; if(n>m)swap(n,m); work(); } }
奶牛的滑雪
bzoj 1744
这题是物理题？
可以发现 到每个点的速度可以预处理出来 根据能量守恒定律。。
就是不管你前面怎么变 到最后的速度一定是 v[1,1]*2^(h[1,1]-h[i,j])
然后算出速度 建图 跑spfa就行了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int N=105,M=N*N; const double eps=1e-8; int map[N][N]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int list[M*100],head[M],next[M*100],tot; double len[M*100]; int n,m; double vsta; void add(int a,int b,double c) { tot++; //cout<<"add "<<a<<" "<<b<<" "<<c<<endl; list[tot]=b,len[tot]=c; next[tot]=head[a]; head[a]=tot; } double power(long long a,int b) { long long ret=1; bool flag=b<0; while(b) { if(b%2)ret=ret*a; b/=2; a=a*a; } double c=ret; if(flag)c=1.0/c; return c; } int p(int i,int j) {return (i-1)*m+j;} void build() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { double v=vsta*power(2,map[1][1]-map[i][j]); for(int k=0;k<4;k++) { int x=i+dx[k]; int y=j+dy[k]; if(x>=1&&y>=1&&x<=n&&y<=m) add(p(i,j),p(x,y),1/v); } } } double dist[M]; bool vis[M]; void spfa() { memset(dist,67,sizeof dist); queue<int>q; q.push(p(1,1));dist[p(1,1)]=0;vis[p(1,1)]=1; while(!q.empty()) { int v=q.front();q.pop(); vis[v]=0; //cout<<v<<endl; for(int i=head[v];i;i=next[i]) { int u=list[i]; if(dist[u]>dist[v]+len[i]) { //cout<<"songchi "<<u<<endl; dist[u]=dist[v]+len[i]; if(!vis[u]) { vis[u]=1; q.push(u); } } } } printf("%.2f\n",dist[p(n,m)]); } int main() { scanf("%lf%d%d",&vsta,&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); build(); spfa(); }
神之KMP：
牛的模式匹配
bzoj 1729
这题名字出的太裸了吧 让人一下子就想到KMP了
这题说匹配的必要条件是两个数在两个串的排名相同。。
那么可以转化成小于两个串的数的数量相同，等于两个串的数的数量相同
于是因为这题字符集只有25 我们暴力统计前缀和
如果字符集大小不限 我们可以使用树状数组统计1的数量来做
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100005,M=25005; int s1[N],s2[M]; int p1[N][30],p2[N][30]; int n,m,s; void init() { for(int i=1;i<=n;i++) { for(int j=1;j<=s;j++) p1[i][j]=p1[i-1][j]; p1[i][s1[i]]++; } for(int i=1;i<=m;i++) { for(int j=1;j<=s;j++) p2[i][j]=p2[i-1][j]; p2[i][s2[i]]++; } } bool cmp1(int i,int j) { int sum1=0,sum2=0,sx=0,sy=0; for(int k=1;k<s2[i];k++) sum1+=p2[i][k]-p2[i-j][k]; for(int k=1;k<s2[j];k++) sum2+=p2[j][k]; sx=p2[i][s2[i]]-p2[i-j][s2[i]]; sy=p2[j][s2[j]]; return sum1==sum2&&sx==sy; } bool cmp2(int i,int j) { int sum1=0,sum2=0,sx=0,sy=0; for(int k=1;k<s1[i];k++) sum1+=p1[i][k]-p1[i-j][k]; for(int k=1;k<s2[j];k++) sum2+=p2[j][k]; sx=p1[i][s1[i]]-p1[i-j][s1[i]]; sy=p2[j][s2[j]]; return sum1==sum2&&sx==sy; } int next[N]; void getnext() { for(int i=2,j=0;i<=m;i++) { while(j&&!cmp1(i,j+1))j=next[j]; if(cmp1(i,j+1))j++; next[i]=j; } } int ans[N],cnt; void kmp() { for(int i=1,j=0;i<=n;i++) { while(j&&!cmp2(i,j+1))j=next[j]; if(cmp2(i,j+1))j++; if(j==m){ans[++cnt]=i-j+1;j=next[j];} } } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) scanf("%d",&s1[i]); for(int i=1;i<=m;i++) scanf("%d",&s2[i]); init(); getnext(); kmp(); printf("%d\n",cnt); for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]); }
之前写过忘了整理了。。。
基本分块：
[Violet 6]蒲公英
bzoj 2724
区间众数 强制在线
分成sqrt块 预处理从第i块起到j位置的区间众数数量和答案
然后块内暴力 块外多出去的一块使用另一个数组二分处理
预处理一个有序结构体数组 结构体中存每个数的位置和数值 按照数值第一关键字 位置第二关键字排序
然后每次询问多出去的一块时 对于里面的每一个数 二分其在有序数组的第一次出现位置和最后一次出现位置
在这两个位置之间二分左区间端点和右区间端点 即可求出[l,r]之间其出现次数 更新答案
好多细节需要注意
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> using namespace std; const int N=50005,M=500; int block,p,a[N],aa[N],q[N],b[N],c1[M][M],c2[M][M],s[M],ss[M],t[N],sta[M],le[N],ri[N],n,m,fhash[N]; struct num {int x,pos;}f[N]; bool cmp(num a,num b) {if(a.x==b.x)return a.pos<b.pos;return a.x<b.x;} void build() { block=(int)(sqrt(n)); for(int i=1;i<=n;i++)q[i]=a[i]; sort(q+1,q+n+1); for(int i=1;i<=n;i++)aa[i]=lower_bound(q+1,q+n+1,a[i])-q,fhash[aa[i]]=a[i]; p=1,sta[p]=1; for(int i=1,j=1;i<=n;i++,j++){if(j>block)p++,j=1,sta[p]=i;b[i]=p;} for(int i=1;i<=p;i++) { memset(t,0,sizeof t); for(int j=sta[i];j<=sta[i]+block-1;j++) { t[aa[j]]++; if(ss[i]<t[aa[j]])s[i]=fhash[aa[j]],ss[i]=t[aa[j]]; else if(ss[i]==t[aa[j]])s[i]=min(s[i],fhash[aa[j]]); } } for(int i=1;i<=p;i++) { int t1=0,t2=0;memset(t,0,sizeof t); for(int j=sta[i],k=i;j<=n;j++) { t[aa[j]]++; if(t2<t[aa[j]])t2=t[aa[j]],t1=fhash[aa[j]]; else if(t2==t[aa[j]])t1=min(t1,fhash[aa[j]]); if(b[j]!=b[j+1])c1[i][k]=t1,c2[i][k]=t2,k++; } } for(int i=1;i<=n;i++)f[i].x=aa[i],f[i].pos=i;sort(f+1,f+n+1,cmp); for(int i=1;i<=n;i++) { if(le[f[i].x]==0)le[f[i].x]=i; ri[f[i].x]=max(ri[f[i].x],i); } } int getr(int l,int r,int x) { int ans=0; while(l<=r) { int mid=(l+r)/2; if(f[mid].pos>x)r=mid-1; else ans=mid,l=mid+1; } return ans; } int getl(int l,int r,int x) { int ans=0x3f3f3f3f; while(l<=r) { int mid=(l+r)/2; if(f[mid].pos<x)l=mid+1; else ans=mid,r=mid-1; } return ans; } int find(int l,int r,int x) {return getr(le[x],ri[x],r)-getl(le[x],ri[x],l)+1;} int work(int l,int r) { if(b[l]==b[r]||b[l]+1==b[r]) { int t1=0,t2=0; for(int i=l;i<=r;i++) { int k=find(l,r,aa[i]); if(k>t2)t1=fhash[aa[i]],t2=k; else if(k==t2)t1=min(t1,fhash[aa[i]]); } return t1; } else { int lx=sta[b[l]+1],rx=sta[b[r]-1]+block; int t1=c1[b[l]+1][b[r]-1],t2=c2[b[l]+1][b[r]-1]; for(int i=l;i<=lx;i++) { int k=find(l,r,aa[i]); if(k>t2)t1=fhash[aa[i]],t2=k; else if(k==t2)t1=min(t1,fhash[aa[i]]); } for(int i=rx;i<=r;i++) { int k=find(l,r,aa[i]); if(k>t2)t1=fhash[aa[i]],t2=k; else if(k==t2)t1=min(t1,fhash[aa[i]]); } return t1; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); build();int lst=0; while(m--) { int x,y;scanf("%d%d",&x,&y); x=(x+lst-1)%(n)+1,y=(y+lst-1)%(n)+1; if(x>y)swap(x,y); lst=work(x,y); printf("%d\n",lst); } return 0; }
只要看完课件上的例题，都做一做，NOI
P就能提高不少的分拿满分了。惊奇的发现我之前的评论怎么被你D了- –
然而评论的重点不在这里，
快把我友链后面的神犇去掉！（求不要这么黑我！）
ha ya ku!
惊奇的发现我之前的评论怎么被你D了- –
然而评论的重点是什么！
把我友链后面的神犇去掉;
顺便我的id似乎也不是wfy吧
这个评论的排版好奇怪