7
26
2018

恢复计划

一年多没写题了，暑假稍微恢复一下

现在大概是普及组水平

恢复一下

-------------------------------------------

bzoj 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `int` `a,b;` `int` `main(){` `freopen("1000.in","r",stdin);` `freopen("1000.out","w",stdout);` `scanf("%d %d",&a,&b);` `printf("%d\n",a+b);` `return` `0;` `}`

bzoj 1588
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26	`#include<cstdio>` `#include<set>` `#include<algorithm>` `using` `namespace` `std;` `int` `n;` `long` `long` `ans;` `set<long` `long> St;` `set<long` `long>::iterator I;` `long` `long` `Abs(long` `long` `x){return` `x>0?x:-x;}` `long` `long` `Min(long` `long` `x,long` `long` `y){return` `x<y?x:y;}` `int` `main(){` `freopen("1588.in","r",stdin);` `freopen("1588.out","w",stdout);` `scanf("%d",&n);` `while(n--){` `long` `long` `sv,tp;` `scanf("%lld",&sv);` `if(St.empty()){St.insert(sv);ans=sv;}` `else` `{I=St.lower_bound(sv);tp=Abs(sv-I);if(I!=St.begin())ans+=Min(tp,Abs(--I-sv));else` `{ans+=tp;}St.insert(sv);}` `}` `printf("%lld\n",ans);` `return` `0;` `}`

正在恢复中...

Category: OI | Tags: 弱

12
28
2016

WC2017去不了啦

有趣

Category: OI | Tags:

10
25
2016

NOIP2016考前乱写

留下一个坑

因为是NOIP，所以都是些非常简单的题呢

所以都是一句话题解

懒得放在博客里面了

看看到NOIP前能A掉多少道呢？

对了还有一个题单

都是目前没有AC的比较好的题,有些可能A掉忘了删掉了

反正都要做

-------------------------

10.25

1.[BZOJ3100] 排列

考虑选中的排列里面没有重复的数字然后和为一个定值随便扫描一下

时间复杂度 $O(n)$

bzoj 3100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=1000005;` `int` `n,m,a[N],nex[N],ne[N],ans;` `inline` `void` `Read(int` `&x){` `static` `char` `ch;` `while((ch=getchar())<'0'` `\|\| ch>'9');` `x=ch-'0';` `while((ch=getchar())>='0'` `&& ch<='9')x=(x<<3)+(x<<1)+ch-'0';` `}` `inline` `void` `Prepare(){` `memset(ne,0,sizeof(nex));` `for(register` `int` `i=n;i>=1;i--){` `if(ne[a[i]]==0)nex[i]=n+1;` `else` `nex[i]=ne[a[i]];` `ne[a[i]]=i;` `}` `}` `inline` `void` `Solve(){` `Prepare();` `m=0;` `for(register` `int` `i=1;i<=n;i++)if(a[i]==1)ne[++m]=i;` `if(m==0)return;` `else` `ans=max(ans,1);` `for(register` `int` `i=1;i<=m;i++){` `int` `mx=0,pos=ne[i],mn=nex[ne[i]];long` `long` `sum=0;` `for(register` `int` `j=ne[i]-1;j>ne[i-1];j--){` `mn=min(mn,nex[j]);` `sum+=a[j];` `if(a[j]<=mx){if(pos==j+mx+1)sum-=a[--pos];}` `else` `{mx=a[j];while(pos<mn && pos<=j+mx-1)sum+=a[pos++];}` `if(j+mx<=mn && sum==1llmx(mx+1)/2)ans=max(mx,ans);` `}` `}` `}` `int` `main(){` `freopen("3100.in","r",stdin);` `freopen("3100.out","w",stdout);` `Read(n);` `for(register` `int` `i=1;i<=n;i++)Read(a[i]);` `Solve();` `for(register` `int` `i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);` `Solve();` `printf("%d\n",ans);` `return` `0;` `}`

2.[BZOJ1195] [HNOI2006]最短母串

把互相包含的串缩一下然后状压dp,注意使用string类型来压空间

时间复杂度 $O(2^n*n^2*len)$ ,len表示比较的串的长度

bzoj 1195
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<string>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=14,M=52,INF=999999999;` `int` `n;` `char` `sr[M];` `struct` `String{` `string str;` `int` `len;` `String(){}` `String(int` `lw){len=lw;}` `friend` `inline` `bool` `operator<(const` `String &A,const` `String &B){` `int` `mn=min(A.len,B.len);` `for(register` `int` `i=1;i<=mn;i++){` `if(A.str[i-1]>B.str[i-1])return` `0;` `if(A.str[i-1]<B.str[i-1])return` `1;` `}` `return` `A.len<B.len;` `}` `friend` `inline` `String operator+(const` `String &A,const` `String &B){` `String C=String(0);` `if(A.len==INF){C.len=INF;return` `C;}` `for(register` `int` `i=min(A.len,B.len);i>=0;i--){` `int` `diff=0;` `for(register` `int` `j=1;j<=i;j++){` `if(A.str[A.len-i+j-1]!=B.str[j-1]){diff=1;break;}` `}` `if(!diff){` `C.str=A.str;` `for(register` `int` `j=i+1;j<=B.len;j++)C.str+=B.str[j-1];` `C.len=A.len+B.len-i;` `//printf("%d\n",C.len);` `return` `C;` `}` `}` `return` `C;` `}` `}str[N],dp[1<<N][M],ans;` `inline` `bool` `Cmp(const` `String &A,const` `String &B){` `return` `A.len<B.len \|\| (A.len==B.len && A<B);` `}` `int` `main(){` `freopen("1195.in","r",stdin);` `freopen("1195.out","w",stdout);` `scanf("%d",&n);` `for(register` `int` `i=1;i<=n;i++){scanf("%s",sr+1);str[i].str=sr+1;str[i].len=strlen(sr+1);}` `sort(str+1,str+n+1);` `for(register` `int` `i=1;i<n;i++){` `if(str[i].len<str[i+1].len){` `int` `diff=0;` `for(register` `int` `j=1;j<=str[i].len;j++){` `if(str[i].str[j-1]!=str[i+1].str[j-1]){diff=1;break;}` `}` `if(!diff){` `for(register` `int` `j=i;j<n;j++)str[j]=str[j+1];` `i--;n--;` `}` `}` `}` `for(register` `int` `i=1;i<=n;i++)dp[1<<(i-1)][i]=str[i];` `for(register` `int` `i=1;i<(1<<n);i++){` `for(register` `int` `j=0;j<n;j++){` `if(dp[i][j+1].len)continue;` `if(((i>>j)&1)==0)continue;` `dp[i][j+1].len=INF;` `for(register` `int` `k=0;k<n;k++){` `if(j==k \|\| ((i>>k)&1)==0)continue;` `if(Cmp(dp[i-(1<<j)][k+1]+str[j+1],dp[i][j+1]))dp[i][j+1]=dp[i-(1<<j)][k+1]+str[j+1];` `}` `}` `}` `ans=dp[(1<<n)-1][1];` `for(register` `int` `i=2;i<=n;i++)ans=min(ans,dp[(1<<n)-1][i],Cmp);` `for(register` `int` `i=0;i<ans.len;i++)putchar(ans.str[i]);` `putchar('\n');` `return` `0;` `}`

3.[BZOJ3754] Tree之最小方差树

考虑平均数一定在已经排序好的边权中间的两数之间的某个区间，这样的话树的形态是不改变的。

因为边权只有100而且是整数，所以我们每0.25枚举一下就好了，一定满足要求

时间复杂度 $O(400nlogn)$ ,其中 $nlogn$ 是排序复杂度， $400$ 是枚举复杂度。

另：我一开始搞了一个最大最小生成树的优化但是显然没搞对，其实就是确定范围而已懒得改了反正不改也能过

想改的话就是把Solve先跑两遍一个输入是0一个输入是100然后把结果当作Mn Mx跑循环而已

bzoj 3754
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<cmath>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=105,M=2005;` `struct` `Edge{` `int` `a,b,u;` `double` `v;` `friend` `bool` `inline` `operator<(const` `Edge &A,const` `Edge &B){return` `A.v<B.v;}` `}e[M];` `int` `n,m,f[N];` `double` `Mn,Mx,ans=9999999999.0;` `inline` `void` `Read(int` `&x){` `static` `char` `ch;` `while((ch=getchar())<'0'` `\|\| ch>'9');` `x=ch-'0';` `while((ch=getchar())>='0'` `&& ch<='9')x=(x<<3)+(x<<1)+ch-'0';` `}` `inline` `void` `Clear(){for(register` `int` `i=1;i<=n;i++)f[i]=i;}` `int` `Find(int` `x){return` `f[x]==x?x:f[x]=Find(f[x]);}` `inline` `void` `Union(int` `sa,int` `sb){if(sa>sb)f[sa]=sb;else` `f[sb]=sa;}` `inline` `bool` `Mi(const` `Edge &A,const` `Edge &B){return` `A.u<B.u;}` `inline` `bool` `Ma(const` `Edge &A,const` `Edge &B){return` `A.u>B.u;}` `/` `inline void Mini(){` `Clear();` `double fx=0.0,fy=0.0;` `sort(e+1,e+m+1,Mi);` `for(register int i=1;i<=m;i++){` `if(Find(e[i].a)!=Find(e[i].b)){` `Union(Find(e[i].a),Find(e[i].b));` `fx+=e[i].u;` `}` `}` `fx/=n-1;` `Clear();` `for(register int i=1;i<=m;i++){` `if(Find(e[i].a)!=Find(e[i].b)){` `Union(Find(e[i].a),Find(e[i].b));` `fy+=(e[i].u-fx)(e[i].u-fx);` `}` `}` `fy/=n-1;` `Mn=sqrt(fy);` `}` `inline void Maxi(){` `Clear();` `double fx=0.0,fy=0.0;` `sort(e+1,e+m+1,Ma);` `for(register int i=1;i<=m;i++){` `if(Find(e[i].a)!=Find(e[i].b)){` `Union(Find(e[i].a),Find(e[i].b));` `fx+=e[i].u;` `}` `}` `fx/=n-1;` `Clear();` `for(register int i=1;i<=m;i++){` `if(Find(e[i].a)!=Find(e[i].b)){` `Union(Find(e[i].a),Find(e[i].b));` `fy+=(e[i].u-fx)(e[i].u-fx);` `}` `}` `fy/=n-1;` `Mx=sqrt(fy);` `}` `/` `inline` `void` `Solve(double` `x){` `for(register` `int` `i=1;i<=m;i++)e[i].v=(x-e[i].u)(x-e[i].u);` `Clear();` `double` `fx=0.0,fy=0.0;` `sort(e+1,e+m+1);` `for(register` `int` `i=1;i<=m;i++){` `if(Find(e[i].a)!=Find(e[i].b)){` `Union(Find(e[i].a),Find(e[i].b));` `fx+=e[i].u;` `}` `}` `fx/=n-1;` `Clear();` `for(register` `int` `i=1;i<=m;i++){` `if(Find(e[i].a)!=Find(e[i].b)){` `Union(Find(e[i].a),Find(e[i].b));` `fy+=(e[i].u-fx)(e[i].u-fx);` `}` `}` `fy/=n-1;` `ans=min(ans,sqrt(fy));` `}` `int` `main(){` `freopen("3754.in","r",stdin);` `freopen("3754.out","w",stdout);` `Read(n);Read(m);` `for(register` `int` `i=1;i<=m;i++){` `Read(e[i].a);Read(e[i].b);Read(e[i].u);` `}` `//Mini();Maxi();` `//if(Mn>Mx)swap(Mn,Mx);` `Mn=0.0;Mx=100.0;` `for(double` `i=Mn;i<=Mx;i+=0.25)Solve(i);` `printf("%.4f\n",ans);` `return` `0;` `}`

4.[BZOJ3110] [Zjoi2013]K大数查询

差点忘了怎么做了……不过树套树的整体思想是清晰的

显然一个树是权值线段树，一个树是区间线段树

这题的新颖之处在于是权值套区间

以前写了爆int了没过，今天改了下unsigned int就过了

bzoj 3110
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96	`#include<cstdio>` `#include<algorithm>` `using` `namespace` `std;` `int` `n,m,cnt,root[500005];` `struct` `SegTree{` `int` `nl,nr,l,r;` `unsigned` `int` `sum,tag;` `}tree[20000005];` `void` `Pushdown(int` `rt){` `if(tree[rt].tag && tree[rt].l!=tree[rt].r){` `int` `mid=tree[rt].l+tree[rt].r>>1;` `if(!tree[rt].nl){tree[rt].nl=++cnt;tree[tree[rt].nl].l=tree[rt].l;tree[tree[rt].nl].r=mid;}` `if(!tree[rt].nr){tree[rt].nr=++cnt;tree[tree[rt].nr].l=mid+1;tree[tree[rt].nr].r=tree[rt].r;}` `tree[tree[rt].nl].tag+=tree[rt].tag;` `tree[tree[rt].nr].tag+=tree[rt].tag;` `tree[tree[rt].nl].sum+=(tree[tree[rt].nl].r-tree[tree[rt].nl].l+1)tree[rt].tag;` `tree[tree[rt].nr].sum+=(tree[tree[rt].nr].r-tree[tree[rt].nr].l+1)tree[rt].tag;` `tree[rt].tag=0;` `}` `}` `void` `Pushup(int` `rt){` `tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;` `}` `void` `Modify(int` `&rt,int` `l,int` `r,int` `L,int` `R){` `if(!rt){rt=++cnt;tree[rt].l=l;tree[rt].r=r;}` `Pushdown(rt);` `if(L<=tree[rt].l && tree[rt].r<=R){` `tree[rt].sum+=tree[rt].r-tree[rt].l+1;` `tree[rt].tag++;` `return;` `}` `int` `mid=tree[rt].l+tree[rt].r>>1;` `if(L<=mid)Modify(tree[rt].nl,l,mid,L,R);` `if(R>mid)Modify(tree[rt].nr,mid+1,r,L,R);` `Pushup(rt);` `}` `unsigned` `int` `Query(int` `rt,int` `l,int` `r){` `if(!rt)return` `0;` `Pushdown(rt);` `if(l<=tree[rt].l && tree[rt].r<=r){return` `tree[rt].sum;}` `int` `mid=tree[rt].l+tree[rt].r>>1;` `unsigned` `int` `ans=0;` `if(l<=mid)ans+=Query(tree[rt].nl,l,r);` `if(r>mid)ans+=Query(tree[rt].nr,l,r);` `Pushup(rt);` `return` `ans;` `}` `void` `Insert(int` `l,int` `r,int` `v){` `int` `L=1,R=n,rt=1;` `while(L!=R){` `int` `mid=L+R>>1;` `Modify(root[rt],1,n,l,r);` `if(v<=mid){R=mid;rt=2;}` `else` `{L=mid+1;rt=rt2+1;}` `}` `Modify(root[rt],1,n,l,r);` `}` `int` `Ask(int` `l,int` `r,int` `k){` `int` `L=1,R=n,rt=1;` `while(L!=R){` `int` `mid=L+R>>1;` `unsigned` `int` `ans=Query(root[rt2],l,r);` `if(ans>=k){R=mid;rt=2;}` `else` `{L=mid+1;rt=rt2+1;k-=ans;}` `}` `return` `L;` `}` `int` `read()` `{` `int` `x=0,f=1;char` `ch=getchar();` `while(ch<'0'\|\|ch>'9'){if(ch=='-')f=-1;ch=getchar();}` `while(ch>='0'&&ch<='9'){x=x10+ch-'0';ch=getchar();}` `return` `x*f;` `}` `int` `main(){` `freopen("3110.in","r",stdin);` `freopen("3110.out","w",stdout);` `n=read();m=read();` `for(int` `i=1;i<=m;i++){` `int` `opt,a,b,c;` `opt=read();a=read();b=read();c=read();` `if(opt==1)Insert(a,b,n-c+1);` `if(opt==2)printf("%d\n",n-Ask(a,b,c)+1);` `}` `return` `0;` `}`

小结:今天一共做了5题，修改了1题，包括一道不能放上来的题目,UER7B,和上面这4题。

1:考察了对于题目的审题能力以及观察题目性质的能力，比如我在一开始没有想到排列的和这个性质导致无从下手。

2:直接做困难的dp应考虑怎么简化状态表示和选择合适的状态表示。

3:观察题目数据范围发现问题和性质。

4:注意极限情况下的数据值可能会爆int

UER7B:考虑划分答案。~~蒟蒻我表示很难想到啊~~

不能放上来的题:考虑正负号对答案的影响或许是相同的，所以要特判。

总的来说收获还是挺多的，希望在接下来的一段时间内能够总结更多的知识，不然复赛退役可不是闹着玩的(毕竟我已经高二了)

-------------------------

10.26

考了试然后瞬间爆炸

3题只有几十分

NOIP拿不到1=咯

-------------------------

10.27

休息一天?(其实我忘了我在干啥)

-------------------------

10.28

休息一天?(其实我忘了我在干啥)

-------------------------

10.29

考了一天试只有190拿不到1=咯

-------------------------

10.30

考了一天试只有180拿不到1=咯

-------------------------

10.31

被黑了一整天于是休息一天?(其实我忘了我在干啥)

好吧还是在bzoj上交了一个题

1.[BZOJ3304] [Shoi2005]带限制的最长公共子序列

状态加一维表示匹配到z串的哪个地方直接转移即可

bzoj 3304
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=505;` `int` `dp[2][N][N],n1,n2,n3;` `char` `s1[N],s2[N],s3[N];` `int` `main(){` `freopen("3304.in","r",stdin);` `freopen("3304.out","w",stdout);` `scanf("%s",s1+1);n1=strlen(s1+1);` `scanf("%s",s2+1);n2=strlen(s2+1);` `scanf("%s",s3);n3=strlen(s3);` `for(register` `int` `i=1;i<=n1;i++){` `int` `now=i&1,pre=now^1;` `memset(dp[now],0,sizeof(dp[now]));` `for(register` `int` `j=1;j<=n2;j++){` `for(register` `int` `k=0;k<=n3;k++){` `dp[now][j][k]=max(dp[now][j][k],max(dp[pre][j][k],dp[now][j-1][k]));` `if(s1[i]==s2[j] && (k==0 \|\| dp[pre][j-1][k])){` `if(s1[i]==s3[k])dp[now][j][k+1]=max(dp[now][j][k+1],dp[pre][j-1][k]+1);` `else` `dp[now][j][k]=max(dp[now][j][k],dp[pre][j-1][k]+1);` `}` `//printf("%d\n",dp[now][j][k]);` `}` `}` `}` `if(dp[n1&1][n2][n3]==0)puts("NO SOLUTION");` `else` `printf("%d\n",dp[n1&1][n2][n3]);` `return` `0;` `}`

嗯，bzoj1009很有趣得在几天内A掉

-------------------------

11.1

睡觉睡掉了，最近需要好好休息一下

对了rky小号也上紫名了……这让大号还没紫的我情何以堪……

-------------------------

11.2

考试

爆炸

看着一个个神犇越来越强我却越来越弱的现实，却懒得去改变……难道真的要在NOIP2016直接退役吗

ZOJ挂了刷不了题目

只好做点简单题了

1.[BZOJ4326] NOIP2015 运输计划

我本来想用树链剖分，后来想了想还是看了下线性的神奇方法

好吧二分还是要二分的，只是判断线性

最近思维越来越差了

我的思路:二分答案 $ans$ ，把所有大于 $ans$ 的路径利用树链剖分实现路径加和路径取最大值

打标记实现，线段树节点保存当前最大次数和当前最大次数情况下的最大值

合并先比较次数，次数一样再取最大值

然后查询整棵树即可

但是这样单次判断是 $O(mlogn)$ 的，总时间复杂度为 $O(logmx\_len*mlogn)$

在CCF老爷机上就别想跑过去了

所以学习了一下树上前缀和

其实就是sum[u]++,sum[v]++,sum[lca]-=2;

然后dfs扫描一下就行

时间复杂度 $O(logmx\_len*(logm+m+n))$

1A,总算缓解了一下考砸后糟糕的心情

bzoj 4326
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=300005;` `int` `n,m,h[N],en,fa[N][20],sum[N],dfn[N],cnt,mx_len,dis[N][20],dep[N];` `inline` `void` `Read(int` `&x){` `static` `char` `ch;` `while((ch=getchar())<'0'` `\|\| ch>'9');` `x=ch-'0';` `while((ch=getchar())>='0'` `&& ch<='9')x=(x<<3)+(x<<1)+ch-'0';` `}` `struct` `Queries{` `int` `l,r,v,lca;` `friend` `inline` `bool` `operator<(const` `Queries &A,const` `Queries &B){return` `A.v<B.v;}` `}que[N];` `struct` `Edge{` `int` `b,v,next;` `}e[N<<1];` `inline` `void` `AddEdge(int` `sa,int` `sb,int` `sc){` `e[++en].b=sb;` `e[en].v=sc;` `e[en].next=h[sa];` `h[sa]=en;` `}` `void` `dfs(int` `u){` `dfn[u]=++cnt;` `for(int` `i=h[u];i;i=e[i].next){` `int` `v=e[i].b;` `if(v==fa[u][0])continue;` `fa[v][0]=u;` `dis[v][0]=e[i].v;` `dep[v]=dep[u]+1;` `dfs(v);` `}` `}` `inline` `void` `prepare(){` `for(register` `int` `i=1;i<=19;i++){` `for(register` `int` `j=1;j<=n;j++){` `fa[j][i]=fa[fa[j][i-1]][i-1];` `dis[j][i]=dis[j][i-1]+dis[fa[j][i-1]][i-1];` `}` `}` `}` `inline` `pair<int,int> dist(int` `u,int` `v){` `int` `ans=0;` `if(dep[u]<dep[v])swap(u,v);` `int` `deep=dep[u]-dep[v];` `for(int` `i=0;i<=19;i++)if((deep>>i)&1){ans+=dis[u][i];u=fa[u][i];}` `for(int` `i=19;i>=0;i--){` `if(fa[u][i]!=fa[v][i]){` `ans+=dis[u][i]+dis[v][i];` `u=fa[u][i];` `v=fa[v][i];` `}` `}` `return` `u==v?make_pair(u,ans):make_pair(fa[u][0],ans+dis[u][0]+dis[v][0]);` `}` `int` `update(int` `u){` `for(int` `i=h[u];i;i=e[i].next){` `int` `v=e[i].b;` `if(v==fa[u][0])continue;` `sum[u]+=update(v);` `}` `//printf("Smu:%d\n",sum[u]);` `return` `sum[u];` `}` `inline` `bool` `solve(int` `x){` `int` `l=1,r=m,mt=0,aw=0;` `while(l<=r){` `int` `mid=l+r>>1;` `if(que[mid].v>x)r=mid-1;` `else` `l=mid+1;` `}` `//printf("L:%d %d\n",l,x);` `for(register` `int` `i=1;i<=n;i++)sum[i]=0;` `for(register` `int` `i=l;i<=m;i++){` `sum[que[i].l]++;` `sum[que[i].r]++;` `sum[que[i].lca]-=2;` `mt=max(mt,que[i].v-x);` `}` `update(1);` `for(register` `int` `i=1;i<=n;i++)if(sum[i]==(m-l+1))aw=max(aw,dis[i][0]);` `//printf("mt:%d %d\n",mt,aw);` `return` `mt<=aw;` `}` `void` `div2(){` `int` `l=0,r=mx_len;` `while(l<=r){` `int` `mid=l+r>>1;` `if(solve(mid))r=mid-1;` `else` `l=mid+1;` `}` `printf("%d\n",l);` `}` `int` `main(){` `freopen("4326.in","r",stdin);` `freopen("4326.out","w",stdout);` `Read(n);Read(m);` `for(register` `int` `i=1;i<n;i++){` `static` `int` `u,v,w;` `Read(u);Read(v);Read(w);` `AddEdge(u,v,w);AddEdge(v,u,w);` `}` `for(register` `int` `i=1;i<=m;i++){Read(que[i].l);Read(que[i].r);}` `dfs(1);` `prepare();` `for(register` `int` `i=1;i<=m;i++){` `pair<int,int> Pr=dist(que[i].l,que[i].r);` `que[i].v=Pr.second;` `que[i].lca=Pr.first;` `mx_len=max(mx_len,que[i].v);` `}` `sort(que+1,que+m+1);` `div2();` `return` `0;` `}`

-------------------------

11.3

日常颓废

1.[BZOJ4066] 简单题

啊……为了调试方便把x^=lastans注释掉了……然后提交时一直忘了加上去

最后就创下了单题提交12次的记录……最后一次才发现……

本身是裸KD树

bzoj 4066
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=200005,INF=2100000000;` `int` `n,sort_tag,cnt,root;` `long` `long` `lastans;` `struct` `KDTree{` `int` `l,r,d[2],mx[2],mn[2];` `long` `long` `sum,v;` `KDTree(){l=r=d[0]=d[1]=mx[0]=mn[0]=mx[1]=mn[1]=sum=v=0;}` `friend` `inline` `bool` `operator<(const` `KDTree &A,const` `KDTree &B){return` `A.d[sort_tag]<B.d[sort_tag];}` `}tree[N];` `inline` `void` `Pushup(int` `rt){` `tree[rt].mx[0]=tree[rt].mn[0]=tree[rt].d[0];` `tree[rt].mx[1]=tree[rt].mn[1]=tree[rt].d[1];` `tree[rt].sum=tree[rt].v;` `if(tree[rt].l){` `tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);` `tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);` `tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);` `tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);` `tree[rt].sum+=tree[tree[rt].l].sum;` `}` `if(tree[rt].r){` `tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);` `tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);` `tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);` `tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);` `tree[rt].sum+=tree[tree[rt].r].sum;` `}` `}` `int` `Rebuild(int` `l,int` `r,int` `D){` `sort_tag=D;` `int` `mid=l+r>>1;` `nth_element(tree+l,tree+mid,tree+r+1);` `tree[mid].mx[0]=tree[mid].mn[0]=tree[mid].d[0];` `tree[mid].mx[1]=tree[mid].mn[1]=tree[mid].d[1];` `tree[mid].l=tree[mid].r=0;` `if(l<mid)tree[mid].l=Rebuild(l,mid-1,!D);` `if(r>mid)tree[mid].r=Rebuild(mid+1,r,!D);` `Pushup(mid);` `return` `mid;` `}` `template<typename` `T>inline` `void` `ReadO(T &x){` `static` `char` `ch;` `while((ch=getchar())<'0'` `\|\| ch>'9');` `x=ch-'0';` `while((ch=getchar())>='0'` `&& ch<='9')x=(x<<3)+(x<<1)+ch-'0';` `}` `template<typename` `T>inline` `void` `Read(T &x){` `static` `char` `ch;` `while((ch=getchar())<'0'` `\|\| ch>'9');` `x=ch-'0';` `while((ch=getchar())>='0'` `&& ch<='9')x=(x<<3)+(x<<1)+ch-'0';` `x^=lastans;` `}` `inline` `int` `AddKDNode(int` `x,int` `y,int` `z){` `tree[++cnt].d[0]=x;` `tree[cnt].d[1]=y;` `tree[cnt].v=z;` `Pushup(cnt);` `return` `cnt;` `}` `int` `Add(int` `rt,int` `d0,int` `d1,int` `val,bool` `D){` `if(!rt)return` `AddKDNode(d0,d1,val);` `if(tree[rt].d[0]==d0 && tree[rt].d[1]==d1){tree[rt].v+=val;tree[rt].sum+=val;return` `rt;}` `if(D){` `if(d1<tree[rt].d[D])tree[rt].l=Add(tree[rt].l,d0,d1,val,!D);` `else` `tree[rt].r=Add(tree[rt].r,d0,d1,val,!D);` `}` `else` `{` `if(d0<tree[rt].d[D])tree[rt].l=Add(tree[rt].l,d0,d1,val,!D);` `else` `tree[rt].r=Add(tree[rt].r,d0,d1,val,!D);` `}` `Pushup(rt);` `return` `rt;` `}` `long` `long` `Sum(int` `rt,int` `x1,int` `y1,int` `x2,int` `y2,int` `D){` `if(!rt)return` `0ll;` `long` `long` `ans=0;` `if(y1>tree[rt].mx[1] \|\| y2<tree[rt].mn[1] \|\| x1>tree[rt].mx[0] \|\| x2<tree[rt].mn[0])return` `0ll;` `if(y1<=tree[rt].mn[1] && tree[rt].mx[1]<=y2 && x1<=tree[rt].mn[0] && tree[rt].mx[0]<=x2)return` `tree[rt].sum;` `if(y1<=tree[rt].d[1] && tree[rt].d[1]<=y2 && x1<=tree[rt].d[0] && tree[rt].d[0]<=x2)ans+=tree[rt].v;` `ans+=Sum(tree[rt].l,x1,y1,x2,y2,!D)+Sum(tree[rt].r,x1,y1,x2,y2,!D);` `return` `ans;` `}` `int` `main(){` `freopen("4066.in","r",stdin);` `freopen("4066.out","w",stdout);` `ReadO(n);tree[0].d[0]=tree[0].d[1]=INF;` `while(1){` `static` `int` `opt,x1,y1,x2,y2;` `ReadO(opt);` `if(opt==1){Read(x1);Read(y1);Read(x2);root=Add(root,x1,y1,x2,0);if(cnt%10000==0)root=Rebuild(1,cnt,0);}` `if(opt==2){Read(x1);Read(y1);Read(x2);Read(y2);printf("%lld\n",lastans=Sum(root,x1,y1,x2,y2,0));}` `if(opt==3)return` `0;` `}` `return` `0;` `}`

2.[BZOJ1013] [JSOI2008]球形空间产生器sphere

画一下式子发现拆开来就是一堆方程，半径什么的都可以消掉

直接高斯消元解方程即可

bzoj 1013
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=15;` `const` `double` `eps=1e-9;` `int` `n;` `double` `px[N];` `struct` `Equa{` `double` `p[N];` `Equa(){for(register` `int` `i=0;i<N;i++)p[i]=0.0;}` `}poi[N];` `inline` `double` `Abs(const` `double` `&x){return` `x>0?x:-x;}` `inline` `void` `Gauss(){` `int` `j;` `for(register` `int` `i=1;i<=n;i++){` `for(j=i;j<=n;j++)if(Abs(poi[j].p[i])>eps)break;` `if(i!=j)for(register` `int` `k=1;k<=n+1;k++)swap(poi[i].p[k],poi[j].p[k]);` `double` `w=poi[i].p[i];` `for(register` `int` `k=1;k<=n+1;k++)poi[i].p[k]/=w;` `for(register` `int` `k=1;k<=n;k++){` `if(k==i)continue;` `w=poi[k].p[i];` `for(register` `int` `l=1;l<=n+1;l++)poi[k].p[l]-=wpoi[i].p[l];` `}` `}` `}` `int` `main(){` `freopen("1013.in","r",stdin);` `freopen("1013.out","w",stdout);` `scanf("%d",&n);` `for(register` `int` `i=1;i<=n;i++)scanf("%lf",&px[i]);` `for(register` `int` `i=1;i<=n;i++){` `for(register` `int` `j=1;j<=n;j++){` `static` `double` `x;` `scanf("%lf",&x);` `poi[i].p[j]=2.0(x-px[j]);` `poi[i].p[n+1]+=xx-px[j]px[j];` `}` `}` `Gauss();` `for(register` `int` `i=1;i<n;i++)printf("%.3lf ",poi[i].p[n+1]);` `printf("%.3lf\n",poi[n].p[n+1]);` `return` `0;` `}`

3.[BZOJ1831] [AHOI2008]逆序对

难得的看出来的题目……

总之选择的数成一个不下降序列

所以直接dp就行

bzoj 1831
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38	`#include<cstdio>` `#include<cstring>` `#include<cstdlib>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=10005,K=105;` `int` `n,k,a[N],pos[N],pcnt;` `long` `long` `dp[N][K],g[N][K],f[N][K],ans;` `int` `main(){` `freopen("1831.in","r",stdin);` `freopen("1831.out","w",stdout);` `scanf("%d %d",&n,&k);` `for(register` `int` `i=1;i<=n;i++)scanf("%d",&a[i]);` `for(register` `int` `i=1;i<=n;i++){` `if(a[i]==-1)pos[++pcnt]=i;` `else` `for(register` `int` `j=1;j<a[i];j++)g[i][j]++;` `for(register` `int` `j=1;j<=k;j++)g[i][j]+=g[i-1][j];` `if(a[i]!=-1)ans+=g[i][a[i]];` `}` `for(register` `int` `i=n;i>=1;i--){` `if(a[i]!=-1)for(register` `int` `j=a[i]+1;j<=k;j++)f[i][j]++;` `for(register` `int` `j=1;j<=k;j++)f[i][j]+=f[i+1][j];` `}` `for(register` `int` `i=1;i<=pcnt;i++){` `long` `long` `d=1ll<<62;` `for(register` `int` `j=1;j<=k;j++){` `d=min(d,dp[i-1][j]);` `dp[i][j]=d+f[pos[i]][j]+g[pos[i]][j];` `}` `}` `long` `long` `d=1ll<<62;` `for(register` `int` `i=1;i<=k;i++)d=min(d,dp[pcnt][i]);` `printf("%lld\n",d+ans);` `return` `0;` `}`

11.4-11.9

复习以及准备期中考试，暂不更新

-------------------------

Category: OI | Tags: OI

6
19
2016

简易FFT教程

这是一篇简易的FFT教程，作者水平奇低无比，这篇博文仅仅是用于分享体会

已经学会FFT的神犇们可以直接无视这篇文章

推荐几个学习FFT的很好的博客地址:Picks大神的博客 Miskcoo大神的博客 FFT算法学习笔记（对于想要进阶的来说去第一个，基础去第二个，入门去第三个）

我觉得学FFT先要去看上面三个博客，实在一点看不懂在看我的口胡……

而且我的口胡非常模糊(半夜三点在写这东西)，难免会出错，敬请指正~

嗯，蒟蒻Lvat_s开始口胡了

首先你需要知道什么是FFT

其实我也不知道是啥，但是有个专业的名字叫做Fast Fourier Transform(快速傅立叶变换)

相信看这篇博文的神犇们都具有初中数学姿势:一个二次函数可以被三个点表示出来

而小学数学告诉我们一个一次函数可以用两个点表示出来

所以，我们类比一下，一个n次多项式 $F(n)=a_n*x^n+......+a_1*x+a_0$ 可以用n+1个二维平面上的点来表示，这些点称为多项式的点值表示法

我们再来思考一下函数是怎么乘起来的

例如 $F*G=......$ (懒得写了)(总之就是对于x坐标相同的点，将两个函数的y坐标值相乘后就行了)

那么对于点值表达我们可以 $O(n)$ 的实现乘法

所以离散傅立叶变换(DFT)就是暴力的将这些点分拆与合并，时间复杂度 $O(n^2)$

为什么DFT复杂度这么高？

都是开始分拆多项式和后期合并的锅!

初中数学告诉我们由一个二次函数得到的三个点不具有唯一性，而由三个点合成的那个二次函数一定是唯一的

我们再来类比一下就知道了n次多项式 $F(n)$ 也可以这么做

所以，FFT就是找一些合适的点用 $O(nlog_2n)$ 得到点值表达，然后 $O(n)$ 计算乘法，最后用 $O(nlog_2n)$ 来重新得到这个多项式。

然而怎么降低复杂度呢？

我们选择单位复数根的倍数作为我们要找的这些点的x坐标。

看起来好像一点用没有……真的没有吗？

当然是有用的了。

~~（未完待续）~~

更新啦

我们需要知道关于复数的两个引理

设 $w_n=e^{2\pi/n}$

消去引理: $w_{dk}^{dk}=w_k^k(n>=0,k>=0,d>=0)$ 证明很简单，带进去算下就行= =

折半引理:我不太会Mathjax语法怎么办……那就弄个图片吧

还有一个求和引理就不发了= =~~懒得截图了~~

这三个引理使我们可以证明FFT的正确性。

FFT的核心就是分组(按照奇数和偶数对多项式的指数进行分组)。

如果我们可以在单次 $O(n)$ 时间内合并( $n$ 为多项式的长度)，那么多项式乘法就可以在 $O(nlogn)$ 的时间内解决。

事实是确实可以这样

具体证明在我推荐的第三个博客地址里面就有，讲的还是很清晰的。

那么我们就可以递归FFT啦！

当然这样不优美。

我们可以改成非递归版的，这样节省时间。

写的好渣啊……主要是因为当初看了好多FFT方面的博客都看不懂，所以才决定事无巨细的写这篇文章。

====================分割线=======================

多项式求逆

这玩意要用到类似倍增的东西，我还没想太清楚……

过几天更新

orz rky大爷几个月前就会了

Category: OI | Tags: OI

4
30
2016

后缀数组练习

CTSC&APIO感觉自己水平太低，完全没法做……

所以打算利用在北京的这段时间提高一下自己的OI水平

后缀数组虽然会写，但是仅限于会敲模版。。

所以我打算把罗穗骞论文里面的所有题写一遍

----------------------------------------

POJ 2774

两个串连一起搞完后缀数组然后求height最大值判断一下前后是否分别属于两个不同的串就好了

poj 2774
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63	`#include<cstdio>` `#include<cstdlib>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=200005;` `int` `n1,n2,n,rank[N],sa[N],rank2[N],wa[N],ws[N],height[N];` `char` `s1[N],s2[N],s[2N];` `int` `cmp(int` `r,int` `a,int` `b,int` `l){return` `(r[a]==r[b])&(r[a+l]==r[b+l]);}` `void` `GetSA(char` `r,int` `sa,int` `n,int` `m){` `int` `i,j,p,x=rank,y=rank2,t;` `for(i=0;i<m;i++)ws[i]=0;` `for(i=0;i<n;i++)ws[x[i]=r[i]]++;` `for(i=1;i<m;i++)ws[i]+=ws[i-1];` `for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;` `for(j=p=1;p<n;j<<=1,m=p){` `for(p=0,i=n-j;i<n;i++)y[p++]=i;` `for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;` `for(i=0;i<m;i++)ws[i]=0;` `for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;` `for(i=1;i<m;i++)ws[i]+=ws[i-1];` `for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];` `for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;` `}` `}` `void` `CalHeight(char` `r,int` `*sa,int` `n){` `int` `i,j,k=0;` `for(i=1;i<=n;i++)rank[sa[i]]=i;` `for(i=0;i<n;height[rank[i++]]=k){` `for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);` `}` `}` `bool` `Diff(int` `x){return` `(sa[x]<n1 && sa[x-1]>=n1)\|\|(sa[x]>=n1 && sa[x-1]<n1);}` `int` `Solve(){` `int` `MxHeight=0;` `for(int` `i=2;i<=n;i++){` `if(height[i]>MxHeight && Diff(i))MxHeight=height[i];` `}` `return` `MxHeight;` `}` `int` `main(){` `freopen("2774.in","r",stdin);` `freopen("2774.out","w",stdout);` `scanf("%s %s",s1,s2);` `n1=strlen(s1);` `n2=strlen(s2);` `n=n1+n2;` `for(int` `i=0;i<n1;i++)s[i]=s1[i];` `for(int` `i=n1;i<n;i++)s[i]=s2[i-n1];` `s[n]=0;` `GetSA(s,sa,n+1,128);` `CalHeight(s,sa,n);` `printf("%d\n",Solve());` `return` `0;` `}`

----------------------------------------

POJ 1743

先差分，然后二分答案k,然后对于height分组(height[i]记录的是sa[i]和sa[i-1]的LCP)，那么因为字典序相邻的后缀在sa里的顺序是连续的，那么我们对于判定答案k是否合法的方法就是找到连续的height，它们的值都不小于k(保证重复的串长大于等于k),然后如果组内最靠前和最靠后的位置差也大于等于k，那么这个方案就是合法的。

poj 1743
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77	`#include<cstdio>` `#include<cstring>` `#include<cstdlib>` `#include<algorithm>` `using` `namespace` `std;` `const` `int` `N=200005,INF=2100000000;` `int` `sa[N],rank[N],rank2[N],ws[N],s[N],wa[N],n,height[N];` `int` `Abs(int` `x){return` `x>0?x:-x;}` `int` `cmp(int` `r,int` `a,int` `b,int` `l){return` `(r[a]==r[b])&(r[a+l]==r[b+l]);}` `void` `GetSA(int` `r,int` `sa,int` `n,int` `m){` `int` `i,j,p,x=rank,y=rank2,t;` `for(i=0;i<m;i++)ws[i]=0;` `for(i=0;i<n;i++)ws[x[i]=r[i]]++;` `for(i=1;i<m;i++)ws[i]+=ws[i-1];` `for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;` `for(j=p=1;p<n;j<<=1,m=p){` `for(p=0,i=n-j;i<n;i++)y[p++]=i;` `for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;` `for(i=0;i<m;i++)ws[i]=0;` `for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;` `for(i=1;i<m;i++)ws[i]+=ws[i-1];` `for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];` `for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;` `}` `}` `void` `Calheight(int` `r,int` `sa,int` `n){` `int` `i,j,k=0;` `for(i=1;i<=n;i++)rank[sa[i]]=i;` `for(i=0;i<n;height[rank[i++]]=k){` `for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);` `}` `}` `int` `Solve(int` `k){` `int` `i=2,Mx,Mn;` `while(1){` `while(i<=n && height[i]<k)i++;` `if(i>n)break;` `Mx=sa[i-1];Mn=sa[i-1];` `while(i<=n && height[i]>=k){Mn=min(Mn,sa[i]);Mx=max(Mx,sa[i]);i++;}` `if(Mx-Mn>=k)return` `1;` `}` `return` `0;` `}` `int` `Div(){` `int` `l=4,r=n*2,ans=0;` `while(l<=r){` `int` `mid=l+r>>1;` `if(Solve(mid)){l=mid+1;ans=mid;}` `else` `r=mid-1;` `}` `ans++;` `return` `ans<5?0:ans;` `}` `int` `main(){` `freopen("1743.in","r",stdin);` `freopen("1743.out","w",stdout);` `while(scanf("%d",&n),n){` `for(int` `i=0;i<n;i++)scanf("%d",&s[i]);` `if(n<10){puts("0");continue;}` `n--;` `for(int` `i=0;i<n;i++)s[i]=s[i+1]-s[i]+89;` `s[n]=0;` `for(int` `i=0;i<N;i++)wa[i]=ws[i]=0;` `GetSA(s,sa,n+1,200);` `Calheight(s,sa,n);` `printf("%d\n",Div());` `}` `return` `0;` `}`

----------------------------------------

Category: OI | Tags: OI

11
12
2015

模版

突然觉得应该攒一些模版了……~~这样以后就可以方便的抄了~~

树链剖分(bzoj 1036)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159	`#include<cstdio>` `#include<algorithm>` `using` `namespace` `std;` `int` `en,pre[30005],segn,n,q,top[30005],id[30005],data[30005],fa[30005],son[30005],siz[30005],dep[30005],h[30005];` `char` `ask[10];` `struct` `Edge{` `int` `b,next;` `}e[60005];` `struct` `SegTree{` `int` `l,r,v,sum;` `}tree[120005];` `void` `add(int` `sa,int` `sb){` `e[++en].b=sb;` `e[en].next=h[sa];` `h[sa]=en;` `}` `void` `Build(int` `root,int` `l,int` `r){` `tree[root].l=l;` `tree[root].r=r;` `if(l==r){` `tree[root].v=data[pre[l]];` `tree[root].sum=data[pre[l]];` `return;` `}` `int` `mid=(l+r)/2;` `Build(root2,l,mid);` `Build(root2+1,mid+1,r);` `tree[root].v=max(tree[root2].v,tree[root2+1].v);` `tree[root].sum=tree[root2].sum+tree[root2+1].sum;` `}` `void` `Update(int` `root,int` `pos,int` `val){` `if(tree[root].l==tree[root].r){` `tree[root].v+=val;` `tree[root].sum+=val;` `return;` `}` `int` `mid=(tree[root].l+tree[root].r)/2;` `if(pos<=mid)Update(root2,pos,val);` `if(pos>mid)Update(root2+1,pos,val);` `tree[root].v=max(tree[root2].v,tree[root2+1].v);` `tree[root].sum=tree[root2].sum+tree[root2+1].sum;` `}` `int` `QueryMax(int` `root,int` `l,int` `r){` `if(tree[root].l>=l && tree[root].r<=r){` `return` `tree[root].v;` `}` `int` `mid=(tree[root].l+tree[root].r)/2,ans=-2147483647;` `if(l<=mid)ans=max(ans,QueryMax(root2,l,r));` `if(r>mid)ans=max(ans,QueryMax(root2+1,l,r));` `return` `ans;` `}` `int` `QuerySum(int` `root,int` `l,int` `r){` `if(tree[root].l>=l && tree[root].r<=r){` `return` `tree[root].sum;` `}` `int` `mid=(tree[root].l+tree[root].r)/2,ans=0;` `if(l<=mid)ans+=QuerySum(root2,l,r);` `if(r>mid)ans+=QuerySum(root2+1,l,r);` `return` `ans;` `}` `void` `dfs1(int` `u,int` `father,int` `deep){` `fa[u]=father;` `dep[u]=deep;` `siz[u]=1;` `son[u]=0;` `for(int` `i=h[u];i;i=e[i].next){` `int` `v=e[i].b;` `if(v==father)continue;` `dfs1(v,u,deep+1);` `siz[u]+=siz[v];` `if(siz[v]>siz[son[u]]){` `son[u]=v;` `}` `}` `}` `void` `dfs2(int` `u,int` `ux){` `top[u]=ux;` `id[u]=++segn;` `pre[segn]=u;` `if(son[u])dfs2(son[u],ux);` `else` `return;` `for(int` `i=h[u];i;i=e[i].next){` `int` `v=e[i].b;` `if(v!=son[u] && v!=fa[u]){dfs2(v,v);}` `}` `}` `int` `AskMax(int` `u,int` `v){` `int` `f1=top[u],f2=top[v],ans=-2147483647;` `while(f1!=f2){` `if(dep[f1]<dep[f2]){` `swap(u,v);` `swap(f1,f2);` `}` `ans=max(ans,QueryMax(1,id[f1],id[u]));` `u=fa[f1];` `f1=top[u];` `}` `if(dep[u]>dep[v]){` `swap(u,v);` `}` `ans=max(ans,QueryMax(1,id[u],id[v]));` `return` `ans;` `}` `int` `AskSum(int` `u,int` `v){` `int` `f1=top[u],f2=top[v],ans=0;` `while(f1!=f2){` `if(dep[f1]<dep[f2]){` `swap(u,v);` `swap(f1,f2);` `}` `ans+=QuerySum(1,id[f1],id[u]);` `u=fa[f1];` `f1=top[u];` `}` `if(dep[u]>dep[v]){` `swap(u,v);` `}` `ans+=QuerySum(1,id[u],id[v]);` `return` `ans;` `}` `int` `main(){` `freopen("1036.in","r",stdin);` `freopen("1036.out","w",stdout);` `scanf("%d",&n);` `for(int` `i=1;i<n;i++){` `int` `sa,sb;` `scanf("%d %d",&sa,&sb);` `add(sa,sb);` `add(sb,sa);` `}` `for(int` `i=1;i<=n;i++){` `scanf("%d",&data[i]);` `}` `dfs1(1,0,1);` `dfs2(1,1);` `Build(1,1,n);` `scanf("%d",&q);` `while(q--){` `int` `sa,sb;` `scanf("%s %d %d",ask,&sa,&sb);` `if(ask[0]=='C'){Update(1,id[sa],sb-data[sa]);data[sa]=sb;}` `if(ask[1]=='M'){printf("%d\n",AskMax(sa,sb));}` `if(ask[1]=='S'){printf("%d\n",AskSum(sa,sb));}` `}` `return` `0;` `}`

Aho-Corasick Automaton(hdu 2222)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80	`#include<cstdio>` `#include<cstring>` `#include<queue>` `using` `namespace` `std;` `struct` `AC_Trie{` `int` `fail,next[26],key;` `AC_Trie(){fail=0;key=0;}` `}tree[500005];` `int` `n,cnt=1;` `char` `s[1000005];` `queue<int> Q;` `void` `Ins(){` `int` `len=strlen(s),j=1;` `for(int` `i=0;i<len;i++){` `int` `p=s[i]-'a';` `if(tree[j].next[p]==0)tree[j].next[p]=++cnt;` `j=tree[j].next[p];` `}` `tree[j].key++;` `}` `void` `BFS(){` `Q.push(1);` `while(!Q.empty()){` `int` `u=Q.front();` `Q.pop();` `for(int` `i=0;i<=25;i++){` `int` `v=tree[u].next[i];` `if(v==0)continue;` `Q.push(v);` `if(u==1){` `tree[v].fail=1;` `continue;` `}` `int` `p=tree[u].fail;` `while(p){` `if(tree[p].next[i]){` `tree[v].fail=tree[p].next[i];` `break;` `}` `p=tree[p].fail;` `}` `if(!p)tree[v].fail=1;` `}` `}` `}` `int` `GetAns(){` `int` `len=strlen(s),ans=0,j=1;` `for(int` `i=0;i<len;i++){` `int` `p=s[i]-'a';` `while(tree[j].next[p]==0 && j!=1)j=tree[j].fail;` `j=tree[j].next[p];` `if(j==0)j=1;` `int` `q=j;` `while(q!=1 && tree[q].key!=-1){` `ans+=tree[q].key;` `tree[q].key=-1;` `q=tree[q].fail;` `}` `}` `return` `ans;` `}` `int` `main(){` `freopen("2222.in","r",stdin);` `freopen("2222.out","w",stdout);` `scanf("%d",&n);` `for(int` `i=1;i<=n;i++){` `scanf("%s",s);` `Ins();` `}` `BFS();` `scanf("%s",s);` `printf("%d\n",GetAns());` `return` `0;` `}`

Splay(bzoj 1500)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224	`#include<cstdio>` `#include<algorithm>` `using` `namespace` `std;` `int` `n,a[1000005],m;` `struct` `Node{` `int` `v,mx,sum,lx,rx,siz,tag,rev;` `Node ch[2],fa;` `Node(int` `val,Node fat);` `void` `Pushdown();` `void` `Pushup();` `}root,Null;` `Node::Node(int` `val=0,Node fat=Null){` `ch[0]=ch[1]=Null;` `fa=fat;` `v=sum=mx=val;` `tag=rev=0;` `siz=1;` `if(v>=0)lx=rx=v;` `else` `lx=rx=0;` `}` `void` `Node::Pushdown(){` `if(tag){` `tag=rev=0;` `if(ch[0]!=Null){ch[0]->tag=1;ch[0]->sum=ch[0]->sizv;ch[0]->v=v;}` `if(ch[1]!=Null){ch[1]->tag=1;ch[1]->sum=ch[1]->sizv;ch[1]->v=v;}` `if(v>=0){` `if(ch[0]!=Null){ch[0]->lx=ch[0]->mx=ch[0]->rx=vch[0]->siz;}` `if(ch[1]!=Null){ch[1]->lx=ch[1]->mx=ch[1]->rx=vch[1]->siz;}` `}` `else` `{` `if(ch[0]!=Null){ch[0]->mx=v;ch[0]->lx=ch[0]->rx=0;}` `if(ch[1]!=Null){ch[1]->mx=v;ch[1]->lx=ch[1]->rx=0;}` `}` `}` `if(rev){` `rev=0;` `if(ch[0]!=Null)ch[0]->rev^=1;` `if(ch[1]!=Null)ch[1]->rev^=1;` `swap(ch[0]->ch[0],ch[0]->ch[1]);` `swap(ch[1]->ch[0],ch[1]->ch[1]);` `swap(ch[0]->lx,ch[0]->rx);` `swap(ch[1]->lx,ch[1]->rx);` `}` `}` `void` `Node::Pushup(){` `siz=ch[0]->siz+ch[1]->siz+1;` `sum=ch[0]->sum+ch[1]->sum+v;` `mx=max(ch[0]->mx,ch[1]->mx);` `mx=max(mx,ch[0]->rx+v+ch[1]->lx);` `lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);` `rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);` `}` `void` `Rotate(Node x,int` `kind){` `Node y=x->fa,z=y->fa;` `y->ch[!kind]=x->ch[kind];` `if(x->ch[kind]!=Null)x->ch[kind]->fa=y;` `x->fa=z;` `if(z!=Null)z->ch[z->ch[1]==y]=x;` `y->fa=x;` `x->ch[kind]=y;` `y->Pushup();` `x->Pushup();` `}` `void` `Splay(Node x,Node place){` `while(x->fa!=place){` `Node y=x->fa,z=y->fa;` `if(z==Null \|\| z==place)Rotate(x,y->ch[0]==x);` `else` `{` `if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}` `else` `if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}` `else` `if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}` `else` `{Rotate(y,0);Rotate(x,0);}` `}` `}` `if(place==Null)root=x;` `}` `Node Find(Node splay,int` `k){` `splay->Pushdown();` `if(splay->ch[0]->siz+1==k)return` `splay;` `if(splay->ch[0]->siz>=k)return` `Find(splay->ch[0],k);` `return` `Find(splay->ch[1],k-1-splay->ch[0]->siz);` `}` `Node Split(int` `pos,int` `tot){` `Node x=Find(root,pos);` `Splay(x,Null);` `Node y=Find(root,pos+tot+1);` `Splay(y,root);` `return` `y->ch[0];` `}` `Node Build(int` `l,int` `r){` `if(l>r)return` `Null;` `int` `mid=l+r>>1;` `Node splay=new` `Node(a[mid],Null);` `splay->ch[0]=Build(l,mid-1);` `if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;` `splay->ch[1]=Build(mid+1,r);` `if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;` `splay->Pushup();` `return` `splay;` `}` `void` `Insert(int` `pos,int` `tot){` `Node x=Find(root,pos+1),y=Find(root,pos+2);` `Splay(x,Null);Splay(y,root);` `y->ch[0]=Build(1,tot);` `if(y->ch[0]!=Null)y->ch[0]->fa=y;` `y->Pushup();` `x->Pushup();` `}` `Node GetNull(){` `Node p=new` `Node(0,Null);` `p->fa=p->ch[0]=p->ch[1]=p;` `p->mx=p->v=-1000000000;` `p->rev=p->tag=p->siz=p->sum=p->lx=p->rx=0;` `return` `p;` `}` `void` `Build_First(){` `Null=GetNull();` `a[1]=-1000000000;` `a[n+2]=-1000000000;` `root=Build(1,n+2);` `}` `void` `Del_Tree(Node splay){` `if(splay==Null)return;` `splay->Pushdown();` `Del_Tree(splay->ch[0]);` `Del_Tree(splay->ch[1]);` `if(splay->ch[0]!=Null)delete` `splay->ch[0];` `if(splay->ch[1]!=Null)delete` `splay->ch[1];` `splay->ch[0]=Null;` `splay->ch[1]=Null;` `splay->Pushup();` `}` `void` `Delete(int` `pos,int` `val){` `Node seq=Split(pos,val),fat=seq->fa;` `Del_Tree(seq);` `if(seq!=Null)delete` `seq;` `fat->ch[0]=Null;` `fat->Pushup();` `fat->fa->Pushup();` `}` `void` `MakeSame(int` `pos,int` `tot,int` `val){` `Node seq=Split(pos,tot),fat=seq->fa;` `seq->tag=1;` `seq->sum=seq->sizval;` `seq->v=val;` `if(val>=0)seq->lx=seq->rx=seq->mx=seq->sizval;` `else` `seq->lx=seq->rx=0,seq->mx=val;` `fat->Pushup();` `fat->fa->Pushup();` `}` `void` `Reverse(int` `pos,int` `tot){` `Node seq=Split(pos,tot),fat=seq->fa;` `if(!seq->tag){` `seq->rev^=1;` `swap(seq->ch[0],seq->ch[1]);` `swap(seq->lx,seq->rx);` `fat->Pushup();` `fat->fa->Pushup();` `}` `}` `int` `GetSum(int` `pos,int` `tot){` `Node seq=Split(pos,tot);` `return` `seq->sum;` `}` `int` `main(){` `freopen("1500.in","r",stdin);` `freopen("1500.out","w",stdout);` `scanf("%d %d",&n,&m);` `for(int` `i=2;i<=n+1;i++)scanf("%d",&a[i]);` `Build_First();` `for(int` `i=1;i<=m;i++){` `char` `s[10];` `scanf("%s",s);` `if(s[0]=='I'){` `int` `pos,tot;` `scanf("%d %d",&pos,&tot);` `for(int` `i=1;i<=tot;i++)scanf("%d",&a[i]);` `Insert(pos,tot);` `}` `if(s[0]=='D'){` `int` `pos,tot;` `scanf("%d %d",&pos,&tot);` `Delete(pos,tot);` `}` `if(s[0]=='M'` `&& s[2]=='K'){` `int` `pos,tot,val;` `scanf("%d %d %d",&pos,&tot,&val);` `MakeSame(pos,tot,val);` `}` `if(s[0]=='M'` `&& s[2]=='X'){` `printf("%d\n",root->mx);` `}` `if(s[0]=='R'){` `int` `pos,tot;` `scanf("%d %d",&pos,&tot);` `Reverse(pos,tot);` `}` `if(s[0]=='G'){` `int` `pos,tot;` `scanf("%d %d",&pos,&tot);` `printf("%d\n",GetSum(pos,tot));` `}` `}` `return` `0;` `}`

后缀数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `char` `s[500005];` `int` `n,rank[500005],rank2[500005],height[500005],sa[500005],rmq[500005][20],ws[500005],wv[500005],er[20],log2[500005];` `int` `cmp(int` `r,int` `a,int` `b,int` `l){return` `(r[a]==r[b])&(r[a+l]==r[b+l]);}` `void` `GetSA(char` `r,int` `sa,int` `n,int` `m){` `int` `i,j,p,x=rank,y=rank2,t;` `for(i=0;i<m;i++)ws[i]=0;` `for(i=0;i<n;i++)ws[x[i]=r[i]]++;` `for(i=1;i<m;i++)ws[i]+=ws[i-1];` `for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;` `for(j=p=1;p<n;j=2,m=p){` `for(p=0,i=n-j;i<n;i++)y[p++]=i;` `for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;` `for(i=0;i<m;i++)ws[i]=0;` `for(i=0;i<n;i++)ws[wv[i]=x[y[i]]]++;` `for(i=1;i<m;i++)ws[i]+=ws[i-1];` `for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];` `for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;` `}` `}` `void` `CalHeight(char` `r,int` `*sa,int` `n){` `int` `i,j,k=0;` `for(i=1;i<=n;i++)rank[sa[i]]=i;` `for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);` `}` `void` `RMQ(){` `int` `i,j;` `er[0]=1;` `for(i=1;i<20;i++)er[i]=er[i-1]<<1;` `log2[0]=-1;` `for(i=1;i<=n;i++)log2[i]=(i&(i-1))?log2[i-1]:log2[i-1]+1;` `for(i=1;i<=n;i++)rmq[i][0]=height[i];` `for(j=1;j<20;j++)for(i=1;i+er[j-1]-1<=n;i++)rmq[i][j]=min(rmq[i][j-1],rmq[i+er[j-1]][j-1]);` `}` `int` `LCP(int` `a,int` `b){` `int` `x=rank[a],y=rank[b],t;` `if(x>y)t=x,x=y,y=t;` `x++;` `int` `k=log2[y-x+1];` `return` `min(rmq[x][k],rmq[y-er[k]+1][k]);` `}` `int` `main(){` `freopen("suffix.in","r",stdin);` `freopen("suffix.out","w",stdout);` `scanf("%s",s);` `n=strlen(s);` `s[n]=0;` `GetSA(s,sa,n+1,128);` `CalHeight(s,sa,n);` `RMQ();` `int` `q;` `scanf("%d",&q);` `for(int` `i=1;i<=q;i++){` `int` `sa,sb;` `scanf("%d %d",&sa,&sb);` `printf("%d\n",LCP(sa,sb));` `}` `return` `0;` `}`

FFT(uoj 34)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66	`#include<cstdio>` `#include<algorithm>` `#include<cstdlib>` `#include<cmath>` `#include<cstring>` `using` `namespace` `std;` `const` `double` `Pi=2asin(1);` `const` `int` `NUM_SIZE=100005;` `int` `An,Bn,Cn,Rev[NUM_SIZE3],Step,n;` `struct` `Complex{` `double` `a,b;` `Complex(double` `as=0.0,double` `bs=0.0){a=as;b=bs;}` `friend` `Complex operator+(Complex a,Complex b){return` `Complex(a.a+b.a,a.b+b.b);}` `friend` `Complex operator-(Complex a,Complex b){return` `Complex(a.a-b.a,a.b-b.b);}` `friend` `Complex operator(Complex a,Complex b){return` `Complex(a.ab.a-a.bb.b,b.aa.b+a.ab.b);}` `friend` `Complex operator/(Complex a,Complex b){return` `Complex((a.ab.a+a.bb.b)/(b.ab.a+b.bb.b),(b.aa.b-a.ab.b)/(b.ab.a+b.bb.b));}` `double` `Mod(){return` `sqrt(aa+bb);}` `}A[NUM_SIZE3],B[NUM_SIZE3],C[NUM_SIZE3];` `template<typename` `T>void` `Read(T &x){` `int` `flag=1;` `char` `ch;` `while((ch=getchar())<'0'` `\|\| ch>'9')if(ch=='-')flag=-1;` `x=ch-'0';` `while((ch=getchar())>='0'` `&& ch<='9')x=x10+ch-'0';` `x=flag;` `}` `void` `FFT(Complex x,int` `flag){` `for(int` `i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);` `for(int` `k=1;k<n;k<<=1){` `Complex wk=Complex(cos(Pi/k),flagsin(Pi/k));` `for(int` `i=0;i<n;i+=k<<1){` `Complex wkj=Complex(1.0,0.0);` `for(int` `j=0;j<k;j++){` `Complex a=x[i+j],b=x[i+j+k]wkj;` `x[i+j]=a+b;` `x[i+j+k]=a-b;` `wkj=wkjwk;` `}` `}` `}` `if(flag==-1){for(int` `i=0;i<n;i++)x[i].a/=n;}` `}` `int` `main(){` `freopen("34.in","r",stdin);` `freopen("34.out","w",stdout);` `Read(An);Read(Bn);` `An++;Bn++;` `Cn=An+Bn-1;` `for(int` `i=0;i<An;i++)Read(A[i].a);` `for(int` `i=0;i<Bn;i++)Read(B[i].a);` `for(n=1,Step=0;n<Cn;Step++,n<<=1);` `for(int` `i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)\|((i&1)<<(Step-1));` `FFT(A,1);` `FFT(B,1);` `for(int` `i=0;i<n;i++)C[i]=A[i]*B[i];` `FFT(C,-1);` `for(int` `i=0;i<Cn;i++)printf("%d ",(int)(C[i].a+0.5));` `putchar('\n');` `return` `0;` `}`

Category: OI | Tags: OI

10
25
2015

KMP+Manacher学习笔记

KMP是一种可以在最坏O(n+m)的时间内完成匹配的字符串匹配算法。学了这个也有一些时间了，也是时候写一点学习笔记了。

KMP需要处理一个next数组，也就是当匹配失败后应该跳转到的匹配位置。

算法如下~~（懒癌晚期，简直啥也没说）~~

UPD:代码里面有一个明显的错误今天才发现……我水平怎么这么低……为被坑到的同学们道个歉……555 ——2016.6.21

KMP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27	`char` `a[1000005],b[105];` `int` `next[105];` `//a表示需要匹配的串,b表示模式串` `void` `Fill() {` `next[1]=0;` `int` `n=strlen(a+1);` `for(int` `i=2,j=0;i<=n;i++) {` `while(j>0&&a[i]!=a[j+1])j=next[j];` `if(a[i]==a[j+1])j++;` `next[i]=j;` `}` `}` `//以下Find函数的mode意思是:当mode=0时,输出匹配成功的位置;mode=1时,输出出现的次数.` `int` `Find(int` `mode){` `Fill();` `int` `ans=0;` `int` `n=strlen(a+1),m=strlen(b+1);` `for(int` `i=1,j=0;i<=m;i++) {` `while(j>0&&(j==n\|\|b[i]!=a[j+1]))j=next[j];` `if(b[i]==a[j+1])j++;` `if(j==n)ans++;` `}` `return` `ans;` `}`

接下来是Manacher算法。

这是一种可以O(n)解决回文子串的算法。详见这里

~~你萌不觉得我的代码简直就是背模版么233~~

Manacher - hdu 3068
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `using` `namespace` `std;` `int` `p[240005],len;` `char` `s[240005];` `int` `main(){` `freopen("3068.in","r",stdin);` `freopen("3068.out","w",stdout);` `while(scanf("%s",s)!=EOF){` `int` `len=strlen(s),id=0,maxlen=0;` `for(int` `i=len;i>=0;i--){` `s[i2+1]='#';` `s[i2+2]=s[i];` `}` `s[0]='';` `s[len2+3]='\0';` `for(int` `i=2;i<2len+1;i++){` `if(p[id]+id>i){` `p[i]=min(p[id2-i],p[id]+id-i);` `}` `else` `p[i]=1;` `while(s[i-p[i]]==s[i+p[i]])p[i]++;` `if(id+p[id]<i+p[i])id=i;` `if(p[i]>maxlen)maxlen=p[i];` `}` `printf("%d\n",maxlen-1);` `}` `return` `0;` `}`

Category: OI | Tags: OI

10
16
2015

单调队列训练

http://hzwer.com/?s=%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97

已经做了几题：

1

Category: OI | Tags: OI

10
15
2015

多重背包单调队列优化的理解

其实我早就会写多重背包了……只不过是写成做多次01背包而已……

看着大爷秒题，我心中感到自己好弱啊。

于是我就来理解一下多重背包的单调队列做法，并记录在这里。

对于一个物品有个数限制的背包，我们考虑状态转移方程：

f[now][j]=max(f[last][j],f[last][j-w[i]*k]+c[i]*k)，其中w[i]为重量，c[i]为价值。

感觉要枚举i,j,k，然后时间复杂度就爆炸了……

怎么办？用单调队列！

因为当我们取到了最大的f[last][j-w[i]*k]+c[i]*k时，再往下取k就没有意义了（不可能大于这个值）

所以我们维护一个单调队列，使队首为最大值，每次把不符合的队首删去，同时把队尾小于我们枚举的f[last][j-w[i]*k]+c[i]*k删去。

队列中存的是k，也就是记录当前取了多少个该物品，即可。

下面是一道例题。

----------------------------------------------------------------

超市购物

Description

Bob家附近新开了一家超市。最近，超市开展了促销活动。
超市共出售N种不同的商品，编号为1…N。不同的物品对Bob来说有不同的价值，第i种物品每一个的价值为Wi。而每种商品的售价也不相同，第i种物品的单价为Ci元。同一种商品可以买多个。超市经理为了避免某些商品被一抢而光，决定每种商品每位顾客最多只能买Li个。现在，Bob共有M元，他想知道在花费不超过M元的情况下，能买到的商品价值和最大为多少？

Input

第1行两个整数N和M，分别表示商品的种数与Bob现有的钱数。
接下来N行每行为三个整数Ci,Wi,Li，分别表示第i种商品的单价，单个的价值，最多可购买的件数。

Output

输出只有一行，为Bob能买到的商品最大价值和。

Sample Input

Sample Output

42

Hint

20%的数据：N≤30，M≤10000，Li≤500；
70%的数据：N≤50，M≤500000，Li≤2000；
100%的数据：N≤50，M≤500000，Li≤500000；

----------------------------------------------------------------

Code:

单调队列优化多重背包
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28	`#include<cstdio>` `#include<algorithm>` `using` `namespace` `std;` `int` `n,m,l[55],c[55],w[55],f[2][500005],q[500005];` `int` `main(){` `scanf("%d %d",&n,&m);` `for(int` `i=1;i<=n;i++){` `scanf("%d %d %d",&c[i],&w[i],&l[i]);` `}` `for(int` `i=1;i<=n;i++){` `int` `now=i%2,last;` `last=now^1;` `for(int` `j=0;j<c[i];j++){` `int` `Rear=1,Front=1;` `q[1]=0;` `for(int` `k=0;kc[i]+j<=m;k++){` `while(Front!=Rear && k-q[Front]>l[i])Front++;` `f[now][kc[i]+j]=max(f[last][kc[i]+j],f[last][q[Front]c[i]+j]+w[i](k-q[Front]));` `while(Front<=Rear && f[last][q[Rear]c[i]+j]+w[i](k-q[Rear])<=f[last][kc[i]+j])Rear--;` `q[++Rear]=k;` `}` `}` `}` `printf("%d\n",f[n%2][m]);` `return` `0;` `}`

Category: OI | Tags: OI

Lvat_s Blog

Bless all

恢复计划

WC2017去不了啦

NOIP2016考前乱写

简易FFT教程

后缀数组练习

模版

KMP+Manacher学习笔记

单调队列训练

1

多重背包单调队列优化的理解

超市购物

Description

Input

Output

Sample Input

Sample Output

Hint

音乐播放器

分类

最新评论

最新留言

存档

链接

RSS

功能

地球

计数器