作者存档：edward_mj

[POJ 2752]KMP**

【题目大意】

求所有对于同一字符串的前缀和后缀相等的位置。

【算法分析】

KMP，然后一直从n一直next回去，路上的都是。

为什么呢？

首先从在n的第一次next是找最长的S[1,K]=S[n-K+1,n]

这个容易理解。

然后接下来的next是求最长的S[1,K]=S[J-K+1,J]

注意了，这个S[J-K+1,J]必然与S[n-K+1,n]相等。（可以用数学归纳法证明一下）

于是对应下一个前缀等于后缀的位置。

所以，这样一直下去就会找到所有的前缀等于后缀的位置。

【其它】1A

http://hi.baidu.com/aekdycoin/blog/item/fbe5a03233bd1648ad4b5f1c.html

紧紧跟随师傅的脚步。

【CODE】

#include #include #include

int next[500000],n,ans[500000],ansl;
char s[500000];

int main(){
    int i,j;
    while (scanf("%sn",&s[1])!=EOF){
          n=strlen(s+1);
          next[1]=0;
          j=0;
          for (i=2;i<=n;i++){
              while (j && s[j+1]!=s[i]) j=next[j];
              if (s[j+1]==s[i]) j++;
              next[i]=j;
          }
          ansl=1; ans[1]=n;
          j=n;
          while (1){
                if (next[j]==0) break;
                j=next[j];
                ans[++ansl]=j;
          }
          for (i=ansl;i>=1;i–){
              printf("%d",ans[i]);
              if (i!=1) printf(" ");
          }
          printf("n");
    }
}

HDU月赛——2010.3.6

这次月赛终于不是一个人单挑了。

CWJ&&FHN&&CZM组成了一队。

然后说说比赛经历：

一开始12点开始，FHN和CZM都没在。。。于是我开了第一题。

写了一会儿，好像很繁琐，然后FHN和CZM陆续回来了。

然后FHN一下就把最后一题秒了，YM。。。

然后我碌碌无为，第一题没搞定，跳过。

看第2题，一看出题人，AekdyCoin，是师傅那题防AK的题目，于是再次跳过。

第三题，看着是个最大独立集问题。但是好像是任意图的。百度一下，发现MS是NP问题？跳过。。

然后CZM大概浏览了题目，告诉我第四题是字符串，让我去做。于是我一看，KMP，1A。

然后CZM和FHN看后面的题目，发现都挺神，于是他们把目光聚焦在那题比较多人AC的题目上，然后CZM一个犀利的背包把它搞定了。

然后FHN出去买电脑

剩下我和CZM，然后我表示第一题突然有了想法，线段树，因为long long WA了两次，终于AC。期间肥闽各种看题目，不过MS没什么结果。

然后我回看第三题，推了一些性质，然后交了个贪心，WA。。。CZM犀利地给了我一个反例。。。

最后我推出一个重要性质：

∵出题人戴牛

∴必然可以网络流

于是尝试了各种二分图构图，终于WA了2次以后AC。

然后FHN回来了，和CZM一起在那里猜数字。。。

我去搞1009，发现应该是在AC自动机上的DP。但是空间好像卡着卡着。。。

纠结到剩下半小时，放弃，和他们一起猜数字。。。

然后得到的结论：

1、没有billion，million….and so on…

2、字符串长度14

然后我说：直接枚举吧，大不了(26+10+1)*14。。。

然后CZM就先去搞那个字符集，为我们枚举作为前提，后来很可惜，没有搞完，结束了。

一共就出了5题。。。。

其实和第一名的差距就是1009——AC自动机上的DP 以及 1005——猜数字。

猜数字其实想通了不难，但是一开始没有意识到是单case。。。

RANK：18

围观地址：http://acm.hdu.edu.cn/vip/contest_ranklist.php?cid=237&page=1

这次的猜数字，绝对NB，赞一个，不过在OI的话没法出。

GDKOI之旅

这次GDKOI总的来说比较遗憾，但是也不算太差。。。

给AekdyCoin师傅丢脸了。。。

首先说下题目类型（后面的是题目分值）：

Day1

1：Floyed——30分

2：基于连通性的状态压缩动态规划——40分

3：找循环节，然后比较繁琐的处理——40分

4：IMBA的压轴题，构造简单割处理，转化比较牛B，很可惜居然这题是上一年winter camp上的原题，而且当时的出题人也在参加比赛。。。无语——40分

Day2

1：直接积分 or 利用导数求出单调性，发现是单峰函数，可以二分 or 直接推导出答案O(1)，总的来说是数学题——30分

2：简单的DP——40分

3：双向BFS——40分

4：平衡树连边再处理。主要是这题我推不出那个边数必然为O（N）规模的这一结论。

我的情况：

Day1：

1：AC

2：暴力DFS拿了90%的分数。。。

3：悲剧，怎么拍都有BUG，于是只拿30%分数。

4：被秒杀。。。55555555，被虐了，用了个状态压缩DP，拿了30%分数。

Day2：

1：AC

2：居然10分钟敲的DP写错了。。。我无语，直接丢32分。。。。

3：双向BFS写出来了，不过操作步数为0的情况没有特判，WA1个点。拿到36分。

4：居然暴力都写错，12分就这样没了。

假设是当前水平下，最好状态：

Day1第3题过掉。+28分

Day2第2题DP写对。+32分

Day2第3题那个点拿掉。+4分

Day2第4题写对。+12分。

总共可以+76分，但是毕竟比赛不能说都能做出来，也算是这样了。。

最后并列第10，前面有两个是高三拿了NOI金牌回来FUN的。。。

总的来说比较遗憾，下次要减少这些SB失误唉。。。

[ZOJ 3297 Cookie Choice II]头尾指针维护

【题目大意】

就是找一个最短连续子序列，使得对于每个i,min[i]<=sum(i)<=max[i]

【算法分析】

很简单的头尾指针维护。

不过要注意题目有负数等无关数字，无视即可（只增加长度）。

然后由于满足单调性我们维护一个最短的区间使得其满足所有的min

然后判断这时候符不符合max即可。

【其它】比赛时1A

【CODE】

#include #include int n,kind,ans;
int hash[3000],a[401111],min[3000],max[3000];

void work(){
    ans=0x7FFFFFFF;
    int i,j=0,que=0,more=0;
    for (i=1;i<=kind;i++){
      if (min[i]>0) que++;
      if (max[i]<0) more++;
    }   
    for (i=1;i<=n;i++){
        while (j            j++;
            if (a[j]>=1 && a[j]<=kind){
              hash[a[j]]++;
              if (hash[a[j]]==max[a[j]]+1) more++;
              if (hash[a[j]]==min[a[j]]) que–;
            }   
        }
        if (!que && !more && j-i+1        if (a[i]>=1 && a[i]<=kind){
            hash[a[i]]–;
            if (hash[a[i]]==min[a[i]]-1) que++;
            if (hash[a[i]]==max[a[i]]) more–;
        }   
    }   
}   

int main(){
    while (scanf("%d%d",&n,&kind)!=EOF){
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        for (int i=1;i<=kind;i++){
            scanf("%d%d",&min[i],&max[i]);
        }   
        memset(hash,0,sizeof(hash));
        work();
        if (ans==0x7FFFFFFF) printf("-1n");
        else printf("%dn",ans);
    }   
}   

[ZOJ 3304 Prison Break]BFS、模拟、种子染色法

【题目大意】

如果把P视作不能去的区域，哪个人不能通过上下左右走到达牢房边缘的话，直接就变成Ghost

然后在剩下的人里，找最大的上下左右对角线连通的连通块。

【算法分析】

一开始处理Ghost的话，从牢房边缘bfs进来，如果不能到达某个P，他就死了。

然后剩下的就是种子染色法了。

【CODE】

#include #include int m,n,lx[1111111],ly[1111111],ans,head,tail;
char map[1111][1111];
bool v[1111][1111];

inline void expand1(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty]) return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void getghost(){
    head=0; tail=0;
    for (int i=1;i<=m;i++){
        tail++;
        lx[tail]=i;
        ly[tail]=0;
        tail++;
        lx[tail]=i;
        ly[tail]=n+1;
    }   
    for (int i=1;i<=n;i++){
        tail++;
        lx[tail]=0;
        ly[tail]=i;
        tail++;
        lx[tail]=m+1;
        ly[tail]=i;
    }
    while (head        head++;
        if (map[lx[head]][ly[head]]==’P’ && lx[head]>0 && lx[head]<=m && ly[head]>0 && ly[head]<=n)
          continue;
        expand1(lx[head]-1,ly[head]);
        expand1(lx[head]+1,ly[head]);
        expand1(lx[head],ly[head]-1);
        expand1(lx[head],ly[head]+1);
    }   
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]==’P’ && !v[i][j])
          map[i][j]=’G’;
}

inline void expand(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty] || map[tx][ty]!='P') return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void bfs(int sx,int sy){
    head=0,tail=1;
    lx[1]=sx; ly[1]=sy;
    v[sx][sy]=true;
    while (head        head++;
        expand(lx[head]-1,ly[head]);
        expand(lx[head]+1,ly[head]);
        expand(lx[head],ly[head]-1);
        expand(lx[head],ly[head]+1);
        expand(lx[head]-1,ly[head]-1);
        expand(lx[head]-1,ly[head]+1);
        expand(lx[head]+1,ly[head]-1);
        expand(lx[head]+1,ly[head]+1);
    }   
    if (tail>ans) ans=tail;
}   

void solve(){
    memset(map,’P’,sizeof(map));
    memset(v,false,sizeof(v));
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        for (map[i][j]=getchar();map[i][j]==’ ‘ || map[i][j]==’n’;map[i][j]=getchar());
    getghost();
    memset(v,false,sizeof(v));
    ans=0;
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]==’P’ && !v[i][j])
          bfs(i,j);
    printf("%dn",ans);
}   

int main(){
    while (scanf("%d%d",&m,&n)!=EOF) solve();
    return 0;   
}