10
25
2015
0

KMP+Manacher学习笔记

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

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

算法如下(懒癌晚期,简直啥也没说)

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

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

#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[i*2+1]='#';
        s[i*2+2]=s[i];
    }
    s[0]='*';
    s[len*2+3]='\0';
    for(int i=2;i<2*len+1;i++){
        if(p[id]+id>i){
            p[i]=min(p[id*2-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
25
2015
0

[BZOJ1625] [Usaco2007 Dec] 宝石手镯

水题大法好!

有几天没写blog了呢。因为这几天颓废了。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,w[3500],c[3500],f[25000];

int main(){
freopen("1625.in","r",stdin);
freopen("1625.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d %d",&w[i],&c[i]);
}
for(int i=1;i<=n;i++){
    for(int j=m;j>=w[i];j--){
        f[j]=max(f[j],f[j-w[i]]+c[i]);
    }
}
printf("%d\n",f[m]);
return 0;
}
Category: BZOJ | Tags: bzoj
10
22
2015
0

[BZOJ1801] [Ahoi2009] chess 中国象棋

有几天没写题解了啊……

这几天在复习以前写过的题目。以后隔一阵子也要去看一看。

记忆化搜索大法好!

#include<cstdio>
#include<cstring>

const long long MOD=9999973;
long long n,m,f[105][105][105],c[105][105];

long long C(long long i,long long j){
	if(j==0)return 1;
	if(i==0)return 0;
	if(i==1)return j==1?1:0;
	if(j==1)return i;
	if(c[i][j]!=-1)return c[i][j];
	return c[i][j]=(C(i-1,j-1)%MOD+C(i-1,j)%MOD)%MOD;
}

long long dfs(long long a,long long b,long long c){
	if(a>n)return 1;
	if(f[a][b][c]!=-1)return f[a][b][c];
	f[a][b][c]=dfs(a+1,b,c)%MOD;
	if(c>=1){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b+1,c-1)%MOD*c%MOD)%MOD;
	}
	if(m-b-c>=1){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b,c+1)%MOD*(m-b-c)%MOD)%MOD;
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b+1,c)%MOD*(m-b-c)%MOD*c%MOD)%MOD;
	}
	if(c>=2){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b+2,c-2)%MOD*C(c,2)%MOD)%MOD;
	}
	if(m-b-c>=2){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b,c+2)%MOD*C(m-b-c,2)%MOD)%MOD;
	}
	return f[a][b][c];
}

int main(){
	freopen("1801.in","r",stdin);
	freopen("1801.out","w",stdout)
	scanf("%lld %lld",&n,&m);
	memset(f,-1,sizeof(f));
	memset(c,-1,sizeof(c));
	printf("%lld\n",dfs(1,0,0));
	return 0;
}
Category: BZOJ | Tags: bzoj
10
18
2015
0

[BZOJ1618] [Usaco2008 Nov] Buying Hay 购买干草

最近感觉颓废指数直线上升。所以为了每日一以上题解,我又来做大水题了。

这题是一个完全背包,令初始的价格为负然后按照正常完全背包处理即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,v,c[5005],f[500005],w[5005];

int main(){
freopen("1618.in","r",stdin);
freopen("1618.out","w",stdout);
scanf("%d %d",&n,&v);
for(int i=1;i<=n;i++){scanf("%d %d",&w[i],&c[i]);c[i]=-c[i];}
memset(f,-127,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){
    for(int j=w[i];j<=v+5000;j++){
        f[j]=max(f[j],f[j-w[i]]+c[i]);
        //printf("%d %d %d",f[j],j,f[j-w[i]]+c[i]);
    }
}
for(int i=v+1;i<=v+5000;i++)f[v]=max(f[v],f[i]);
printf("%d\n",-f[v]);
return 0;
}
Category: BZOJ | Tags: bzoj
10
16
2015
0

[BZOJ1603] [Usaco2008 Oct] 打谷机

一开始不知道什么意思,看了hzwer的博客才知道:什么奇怪的题。

我都有些不好意思传代码了。

#include<cstdio>

int n,x,y=0;

int main(){
freopen("1603.in","r",stdin);
freopen("1603.out","w",stdout);
scanf("%d",&n);
n--;
while(n--){
    scanf("%d",&x);
    scanf("%d",&x);
    scanf("%d",&x);
    y^=x;
}
printf("%d\n",y);
return 0;
}
Category: BZOJ | Tags: bzoj
10
16
2015
1

单调队列训练

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

已经做了几题:

1

Category: OI | Tags: OI
10
15
2015
1

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

其实我早就会写多重背包了……只不过是写成做多次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

5 30
3 1 3
1 4 1
8 10 3
4 7 2
2 2 4

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:
#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;k*c[i]+j<=m;k++){
            while(Front!=Rear && k-q[Front]>l[i])Front++;
            f[now][k*c[i]+j]=max(f[last][k*c[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][k*c[i]+j])Rear--;
            q[++Rear]=k;
        }
    }
}
printf("%d\n",f[n%2][m]);
return 0;
}

 

Category: OI | Tags: OI
10
15
2015
0

[BZOJ1602] [Usaco2008 Oct] 牧场行走

这是一个很裸的LCA。

觉得hzwer的LCA模版更加优美,于是膜拜了一下。

#include<cstdio>
#include<algorithm>
using namespace std;

int fa[1005][12],f[1005],n,q,en,h[1005],deep[1005],flg[1005];

struct Edge{
int b,v,next;
}e[2005];

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void Yuchuli(int u){
flg[u]=1;
for(int i=1;i<=10;i++){
    if(deep[u]<(1<<i))break;
    fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(flg[v])continue;
    f[v]=f[u]+e[i].v;
    fa[v][0]=u;
    deep[v]=deep[u]+1;
    Yuchuli(v);
}
}

int LCA(int u,int v){
if(deep[u]<deep[v])swap(u,v);
int dep=deep[u]-deep[v];
for(int i=0;i<=10;i++)if((1<<i)&dep)u=fa[u][i];
for(int i=10;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){
        u=fa[u][i];
        v=fa[v][i];
    }
}
return u==v?u:fa[u][0];
}

int main(){
freopen("1602.in","r",stdin);
freopen("1602.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    add(sa,sb,sc);
    add(sb,sa,sc);
}
Yuchuli(1);
while(q--){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    printf("%d\n",f[sa]+f[sb]-2*f[LCA(sa,sb)]);
}
return 0;
}
Category: BZOJ | Tags: bzoj
10
15
2015
0

[BZOJ1600] [Usaco2008 Oct] 建造栅栏

这题是一个打表找规律。

据说这题可以dp,但是我并不想写。(懒癌晚期)

具体的找规律方式:点击这里

dp:点击这里

#include<cstdio>

int n,f[2505];

int main(){
freopen("1600.in","r",stdin);
freopen("1600.out","w",stdout);
scanf("%d",&n);
f[4]=1;
for(int i=5;i<=n;i++){
    if(i&1)f[i]=f[i-1]+(i-2)*(i/2-1);
    else f[i]=f[i-1]+i/2-1;
}
printf("%d\n",f[n]);
return 0;
}
Category: BZOJ | Tags: bzoj
10
15
2015
0

[BZOJ1607] [Usaco2008 Dec] Patting Heads 轻拍牛头

这是一个筛法。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000005],s[1000005],c[1000005],mx;

int main(){
freopen("1607.in","r",stdin);
freopen("1607.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    c[a[i]]++;
    mx=max(a[i],mx);
}
for(int i=1;i<=mx;i++){
    if(c[i]){
        for(int j=i;j<=mx;j+=i)s[j]+=c[i];
    }
}
for(int i=1;i<=n;i++)printf("%d\n",s[a[i]]-1);
return 0;
}
Category: BZOJ | Tags: bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com