edward_mj

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

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