edward_mj

[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;
}

[ZOJ 3301 Make Pair]排序、贪心

【题目大意】

给偶数个人分组，使得组员的体重相差值之和最小。

【算法分析】

该次月赛的送分题。

显然，排序以后按顺序两两匹配即可。

证明：

若a<=b<=c<=d

即证明：d-c+b-a<=d-a+c-b

推导出：b<=c

符合条件，所以得证。

【CODE】

#include #include #include #include #include using namespace std;
struct datatype{int d,pos;}a[11111];
int n;

inline bool cmp(datatype x,datatype y){
return x.d}

int main(){
    int tc=0;
    while (scanf("%d",&n)!=EOF){
        tc++;
        if (tc!=1) printf("n");
        for (int i=1;i<=n;i++) scanf("%d",&a[i].d);
        for (int i=1;i<=n;i++) a[i].pos=i;
        sort(&a[1],&a[n+1],cmp);
        for (int i=1;i          printf("%d %dn",a[i].pos,a[i+1].pos);
    }
}

[ZOJ 3300 Mahjong]暴力DFS

【题目大意】

给出13张牌（1~9）,问摸到什么牌能赢。把所有方案在同一行输出。

【算法分析】

暴力DFS，其实有更好的复杂度为O(9*9)的方法，GDKOI上有原题。。。

但是这题规模太小了，直接暴力

【CODE】

#include #include #include #include using namespace std;

int a[20],h[20],num;
bool flag;

void dfs(int i){
    if (flag) return;
    if (num==0){
        flag=true;
        return;
    }
    while (h[i]==0) i++;
    if (h[i]>=3){
        h[i]-=3;
        num-=3;
        dfs(i);
        h[i]+=3;
        num+=3;
    }
    if (h[i] && h[i+1] && h[i+2]){
        h[i]–; h[i+1]–; h[i+2]–;
        num-=3;
        dfs(i);
        num+=3;
        h[i]++; h[i+1]++; h[i+2]++;
    }
}

bool tryit(){
    flag=false;
    num=12;
    dfs(1);
    return flag;
}

bool solve(){
    memset(h,0,sizeof(h));
    for (int i=1;i<=14;i++){
        h[a[i]]++;
      }
    for (int i=1;i<=9;i++)
      if (h[i]>4) return false;
    for (int i=1;i<=9;i++)
      if (h[i]>=2){
          h[i]-=2;
          if (tryit()) return true;
          h[i]+=2;
      }
    return false;
}

int main(){
    for (;;){
        if (scanf("%d",&a[1])==EOF) break;
        for (int i=2;i<=13;i++) scanf("%d",&a[i]);
        bool st=false;
        for (int i=1;i<=9;i++){
            a[14]=i;
            if (solve()){
                if (st) printf(" ");
                printf("%d",i);
                st=true;
            }
        }
        printf("n");
    }
}

[ZOJ 3296 Connecting the Segments]后缀数组、RMQ、贪心

【题目大意】

给一个串，让你求他最少由多少个可重叠的回文串所组成。输出ans-1（要拼接几次）

【算法分析】

令读入的串为s，s’为s翻转以后的字符串，然后再令S=s+’$’+s’。

对S建立后缀数组，height和lcp

然后枚举对称中心（注意，对称中心可能在字符上，也可能在字符之间,即回文串长度为偶数）

然后利用lcp求出最长覆盖区间。

然后问题变为用最少的区间去覆盖1~n这一段。

直接贪心：先将区间按L排序，然后枚举答案，看答案为ans时最多能覆盖到多远。

如果覆盖完整个1~n，那就可以输出了。

【其它】

TLE,WA了无限遍。。。

一个原因是因为一开始倍增算法里面用的C++的sort，后面改成基数排序就不超时了。

然后另一个原因是因为没有考虑到回文串为偶数长度时，对称轴不在字符上。

另外很不幸。。。我垫底了

果然大家用的都是DC3。。。只有我不会。。。

Submit Time Language Run Time(ms) Run Memory(KB) User Name 2010-02-21 17:03:31 C++ 70 1456 ConanKudo 2010-02-22 10:38:50 C++ 250 11148 lccycc 2010-02-21 19:42:45 C++ 400 20692 ILJ 2010-02-21 17:12:23 C++ 430 12416 zgmf_x20a 2010-02-22 17:53:00 C++ 510 21368 my icpc is going on,有要事先闪了 2010-02-22 17:56:12 C++ 510 21368 my icpc is going on,有要事先闪了 2010-02-22 17:50:59 C++ 520 22152 my icpc is going on,有要事先闪了 2010-02-22 17:48:57 C++ 540 26536 my icpc is going on,有要事先闪了 2010-02-22 18:22:56 C++ 550 23324 my icpc is going on,有要事先闪了 2010-02-22 18:21:04 C++ 600 23324 my icpc is going on,有要事先闪了 2010-02-22 22:52:08 C++ 720 13856 edward

【CODE】

#include #include #include #include #include using namespace std;
const int N=55555*2;
int n,e;
char S[N],lg[N];
int rank[N],sa[N],height[N],ls[N];
int lcp[N][18],TOT;
struct qj{int l,r;}d[N];
struct satmp{int a,b,pos;}a[N];
struct gtp{int next;satmp y;}g[N];

void init(){
    int i,j;
    n=strlen(S+1);
    S[n+1]=’$’;
    j=n+1;
    for (i=n;i>=1;i–){
        j++;
        S[j]=S[i];
    }
    n=j;
    lg[1]=0;
    for (int i=2;i<=n;i++)
      if (i==1<                      else lg[i]=lg[i-1];
}

void Jsort(){
    int i,t,tot;
    e=0; tot=0; memset(ls,0,sizeof(int)*(n+1));
    for (i=1;i<=n;i++){
        e++;
        g[e].y=a[i];
        g[e].next=ls[a[i].b];
        ls[a[i].b]=e;
    }
    for (i=1;i<=n;i++)
      for (t=ls[i];t;t=g[t].next)
        a[++tot]=g[t].y;

    e=0; tot=0; memset(ls,0,sizeof(int)*(n+1));
    for (i=n;i>=1;i–){
        e++;
        g[e].y=a[i];
        g[e].next=ls[a[i].a];
        ls[a[i].a]=e;
    }
    for (i=1;i<=n;i++)
      for (t=ls[i];t;t=g[t].next)
        a[++tot]=g[t].y;
}

inline bool cmp(satmp X,satmp Y){
return X.a}

void GetRank(){
    int R=0;
    for (int i=1;i<=n;i++){
      if (!R || a[i].a!=a[i-1].a || a[i].b!=a[i-1].b) R++;
      rank[a[i].pos]=R;
    }
}
void build(){
    for (int i=1;i<=n;i++){a[i].a=S[i];a[i].b=0;a[i].pos=i;}
    sort(a+1,a+n+1,cmp);
    GetRank();
    for (int K=0;1<        int k=1<        for (int i=1;i<=n;i++){
            a[i].a=rank[i]; a[i].b=0;
            if (i+k<=n) a[i].b=rank[i+k];
            a[i].pos=i;
        }
        Jsort();
        GetRank();
    }
    for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void makeheight(){
    height[1]=0;
    int i,j,k,st;
    for (i=1;i<=n;i++){
        if (rank[i]==1) continue;
        st=max(height[rank[i-1]]-1,0); j=i+st; k=sa[rank[i]-1]+st;
        while (j<=n && k<=n && S[j]==S[k]){j++;k++;st++;}
        height[rank[i]]=st;
    }
}

void initlcp(){
for (int i=1;i<=n;i++) lcp[i][0]=height[i];
for (int k=1;1< for (int i=1;i+(1< lcp[i][k]=min(lcp[i][k-1],lcp[i+(1<}

inline int Lcp(int l,int r){
    if (l>r) swap(l,r);
    l++;
    int k=lg[r-l+1];
    return min(lcp[l][k],lcp[r-(1<}

void Ml(){
    int i,j=n+1,LCP;
    TOT=0;
    for (i=1;i<=n/2;i++){
        j–;
        LCP=Lcp(rank[i],rank[j]);
        TOT++;
        d[TOT].l=i-LCP+1;
        d[TOT].r=i+LCP-1;
    }
    j=n+1;
    for (int i=1;i        j–;
        LCP=Lcp(rank[i+1],rank[j]);
        TOT++;
        d[TOT].l=i-LCP+1;
        d[TOT].r=i+LCP;
    }
    n/=2;
}

inline bool TXcmp(qj X,qj Y){
return X.l}

void TanXin(){
    sort(d+1,d+1+TOT,TXcmp);
    int now=0,ans,i=0,expand;
    for (ans=1;;ans++){
        expand=0;
        while (i<=TOT && d[i+1].l<=now+1){
            i++;
            if (d[i].r>expand) expand=d[i].r;
        }
        now=expand;
        if (now>=n){
            printf("%dn",ans-1);
            return;
        }
    }
}

int main(){
    while (scanf("%s",S+1)!=EOF){
        init();
        build();
        makeheight();
        initlcp();
        Ml();
        TanXin();
        memset(S,0,sizeof(S));
    }
}

[ZOJ 3298 Crack]KMP

【题目大意】

给一个串A，一个串B，然后在B串中，从A串的某个位置开始匹配，然后匹配到A串末尾又匹配回A串开头，然后问最长的匹配段是多少?

如果A串在B串中没有一个正常的从1开始的匹配的话，输出bad。

【算法分析】

当时没想到，经lcc教导，终于明白了。。。ORZ！

先KMP。

我是开了一个邻接表，记录连续的完全匹配。

然后给每一个连续的完全匹配向前和向后延伸。然后去更新ans即可。

【CODE】

#include #include struct gtp{int y,next;}g[1001111];
int m,n,e;
int next[1111];
int P[1111],T[1001111];
int tot;
int belong[1001111],ls[1001111];

void makenext(){
    next[1]=0;
    int i,j=0;
    for (i=2;i<=m;i++){
        while (j>0 && P[j+1]!=P[i]) j=next[j];
        if (P[j+1]==P[i]) j++;
        next[i]=j;
    }
}

inline void addedge(int &x,int &y){
    e++;
    g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

void kmp(){
    for (int i=1;i<=n;i++){
        belong[i]=0;
        ls[i]=0;
    }
    tot=0;
    e=0;
    int i,j=0;
    for (i=1;i<=n;i++){
        while (j>0 && P[j+1]!=T[i]) j=next[j];
        if (P[j+1]==T[i]) j++;
        if (j==m){
            if (!belong[i-m]){
                tot++;
                belong[i]=tot;
            }
            else belong[i]=belong[i-m];
            addedge(belong[i],i);
            j=next[j];
        }
    }
}

void solve(){
    if (tot==0){
        printf("badn");
        return;
    }
    int i,j,k,t,now,ans=0,num,st;
    for (i=1;i<=tot;i++){
        j=g[ls[i]].y+1;
        k=1;
        while (j<=n && k<=m && P[k]==T[j]){j++; k++;}
        j–; k–;
        now=k; num=0;
        for (t=ls[i];t;t=g[t].next){num++;st=g[t].y-m;}
        now+=m*num;
        j=st; k=m;
        while (j>=1 && k>=1 && P[k]==T[j]){j–; k–;}
        now+=m-k;
        if (now>ans) ans=now;
    }
    printf("%dn",ans);
}

int main(){
    for (;;){
        if (scanf("%d%d",&m,&n)==EOF) break;
        for (int i=1;i<=m;i++) scanf("%d",&P[i]);
        for (int i=1;i<=n;i++) scanf("%d",&T[i]);
        makenext();
        kmp();
        solve();
    }
}