分类存档：默认分类

[POJ1737 Connected Graph]组合数学、男人8题

【题目大意】

给定N个标号为1~N的点，让你求出对于这N个点，连一些边使得它成为无向连通图的方案有多少种。

【算法分析】

= =看了一下别人的思考过程。。。公式还是自己推的。。。

要利用补集思想，首先连边方案一共有2^(n*(n-1)/2)这么多种。（每条边取或者不取）

然后我们以于1连通的点的个数i为划分状态。

ans[n]=2^(n*(n-1)/2)-Q;

Q=SUM(ans[i]*C(i-1,n-1)*2^((n-i)*(n-i-1)/2))   1<=i

就是固定住1这个点，然后在剩下的n-1个点里取i-1个，总共i个点是1的联通块上的。

然后i个点的连通图有ans[i]这么多方案，所以乘起来，然后根据乘法原理，剩下有n-i个点，

能构成2^((n-i)*(n-i-1)/2)种方案，也都乘起来。

【其他】1A

跑得非常慢，在最后一面= =

【CODE】

#include #include #include using namespace std;
const int ml=372;

int n;
int C[55][55][ml+1];
int ans[55][ml+1];
int cf[1311][ml+1];
int tmp[ml+1],tmp2[ml+1];

struct BNT{
       void plus(int *x,int *y){
            for (int i=1;i<=ml;i++) x[i]+=y[i];
            for (int i=1;i                x[i+1]+=x[i]/10;
                x[i]%=10;
            }
       }

       void mul(int *x,int *y){
            memset(tmp,0,sizeof(tmp));
            for (int i=1;i<=ml;i++)
              for (int j=1;i+j-1<=ml;j++) tmp[i+j-1]+=x[i]*y[j];
            for (int i=1;i                tmp[i+1]+=tmp[i]/10;
                tmp[i]%=10;
            }
       }

       void dec(int *x,int *y){
            for (int i=1;i<=ml;i++) x[i]-=y[i];
            for (int i=1;i                while (x[i]<0){x[i]+=10; x[i+1]--;}
                while (x[i]>9){x[i]-=10; x[i+1]++;}
            }
       }
}Big;

void deal(int m){
     memcpy(ans[m],cf[m*(m-1)/2],sizeof(ans[m]));
     for (int i=1;i         Big.mul(ans[i],C[m-1][i-1]);
         memcpy(tmp2,tmp,sizeof(tmp));
         int q=m-i;
         Big.mul(tmp2,cf[q*(q-1)/2]);
         Big.dec(ans[m],tmp);
     }
}

void init(){
     memset(C,0,sizeof(C));
     memset(cf,0,sizeof(cf));
     C[0][0][1]=1;
     for (int i=1;i<=50;i++)
       for (int j=0;j<=i;j++){
           if (j) Big.plus(C[i][j],C[i-1][j-1]);
           Big.plus(C[i][j],C[i-1][j]);
       }
     cf[0][1]=1;
     for (int i=1;i<=1300;i++){
         for (int j=1;j<=ml;j++) cf[i][j]=cf[i-1][j]*2;
         for (int j=1;j             cf[i][j+1]+=cf[i][j]/10;
             cf[i][j]%=10;
         }
     }
     for (int i=1;i<=50;i++)
       deal(i);
}

void output(){
     int i=ml;
     while (!ans[n][i]) i–;
     for (int j=i;j>=1;j–) printf("%d",ans[n][j]);
     printf("n");
}

int main(){
    init();
    while (cin >> n && n) output();
}

[POJ1740 A New Stone Game]博弈、男人8题

【算法分析】

在纸上玩一下可以发现：

1、假设他们是两两配对的，那么，一个人取了以后，那么另一个人必然可以通过一种方案使得他仍然配对。所以后手必胜。

2、如果他们不是两两配对的，那么先取者必然可以通过弄数量最大的那一组使得他们变成两两配对，这样，自己就可以赢了。

所以，我们只需判断它给的是否两两配对。

【其他】1A

5/8个男人。。。

【CODE】

#include #include using namespace std;

int n,i,ans;
int a[10];

int main(){
    while (1){
          cin >> n;
          if (!n) break;
          for (i=0;i          sort(a,a+n);
          ans=0;
          if (!(n&1)){
            for (i=0;i              if (a[i]!=a[i+1]) ans=1;
            cout << ans << endl;
          }
          else cout << 1 << endl;
    }
}

[POJ1741 Tree]基于点划分的树的分治算法、男人8题

【题目大意】

给出一棵树，让你求树中距离<=K的点对个数。

【算法分析】

围观了一下漆子超大神的论文。。。表示那实在太简略了。。。我只能从中得到一些启发。

首先是按他说的那样，对树进行基于点的划分。

划分的方法是：每次对当前块选一个根，使得去掉这个点以后，划分出新的各个块中点数最多的最少。

这个利用DFS搜一下，维护一个表示以该节点为根的子树的点数多少的数组size[i]。然后当前这个点当分割点，分成各个块的大小就可以很容易算出来。

划分好以后，就从划分树的底层向顶层扫描（其实这个顺序只要是拓扑序就可以了）。

扫描上去的过程中，将划分树当前区间的点都放进一个队列里面，并将它们按到“划分点”的距离排个序。

然后用j从前面开始扫描，并维护另一个指针k，指向一个点满足k=max(k : dis[Q[k]]+dis[Q[j]]<=K)。

接着再减去那些与当前点在下一层里属于同一个划分区间的点的数量，就是经过该根并满足<=K的路径的数量。把它们全加起来就是ans。

【其他】

写了个朴素对拍调试才A。。。之前因为维护k指针的时候k–写在那个if前面了，所以搞错了。。。

终于成为了1/2个男人

【CODE】

#include #include #include #include #include #include using namespace std;
const int E=333333;
const int N=122222;
const int INF=1000000000;
struct edge{int x,y,w;edge *next;}g[E],*ls[N];
struct linetreetype{int l,r,dep,root;}tr[N*16];
int n,K,e,Qt,NowDep,ans;
int color[16][N],list[16][N],tot[16],dis[N],size[N];
int Q[N],use[N],done[N];

struct LineTreeFunction{
       int times,nowroot,nownum,trtot;

       void makelabel(int p,int *co,int fa){
            size[p]=times++;
            for (edge *t=ls[p];t;t=t->next)
              if (co[t->y]==co[p] && t->y!=fa){
                dis[t->y]=dis[p]+t->w;
                makelabel(t->y,co,p);
              }
            size[p]=times-size[p];
       }

       void choose_root(int p,int *co,int fa,int total){
           int now=0;
           if (fa) now=max(now,total-size[p]);
           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               now=max(now,size[t->y]);
           if (now           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               choose_root(t->y,co,p,total);
       }

       void buildnewlp(int p,int fa,int *co,int dep){
           list[dep][++tot[dep]]=p;
           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               buildnewlp(t->y,p,co,dep);
       }

       void build(int p,int l,int r,int dep){
            tr[p].l=l; tr[p].r=r; tr[p].dep=dep;
            int &st=list[dep][l];
            for (int i=l;i<=r;i++) color[dep][list[dep][i]]=p;
            if (l==r) return;
            dis[st]=0; times=0; nownum=INF;
            makelabel(st,color[dep],0);
            choose_root(st,color[dep],0,r-l+1);
            tr[p].root=nowroot;

            for (edge *t=ls[tr[p].root];t;t=t->next)
              if (color[dep][t->y]==p){
                int pt=tot[dep+1]+1,nt;
                buildnewlp(t->y,tr[p].root,color[dep],dep+1);
                nt=tot[dep+1];
                trtot++;
                build(trtot,pt,nt,dep+1);
              }
       }
}LineTree;

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

void init(){
     e=0;
     for (int i=1;i<=n;i++) ls[i]=NULL;
     memset(color,0,sizeof(color));
     memset(list,0,sizeof(list));
     memset(tot,0,sizeof(tot));
     for (int i=1;i         int x,y,w;
         scanf("%d%d%d",&x,&y,&w);
         addedge(x,y,w);
         addedge(y,x,w);
     }
     tot[1]=n;
     for (int i=1;i<=n;i++) list[1][i]=i;
}

bool cmp(int x,int y){
    return (dis[x])<(dis[y]);
}

void work(){
    ans=0;
    memset(use,0,sizeof(use));
    memset(done,0,sizeof(done));
    for (int i=LineTree.trtot;i>=1;i–){
        if (tr[i].l==tr[i].r) continue;
        dis[tr[i].root]=0;
        LineTree.times=0;
        LineTree.makelabel(tr[i].root,color[tr[i].dep],0);
        NowDep=tr[i].dep+1;
        Qt=0;
        int j,k=0;
        for (j=tr[i].l;j<=tr[i].r;j++)
          Q[++Qt]=list[tr[i].dep][j];
        sort(Q+1,Q+Qt+1,cmp);
        int *co=color[tr[i].dep+1];
        for (j=1;j<=Qt;j++){
          if (co[Q[j]] && use[co[Q[j]]]!=i){
              use[co[Q[j]]]=i;
              done[co[Q[j]]]=0;
          }
          while (k+1            k++;
            if (co[Q[k]])
              done[co[Q[k]]]++;
          }
          while (k>0 && dis[Q[j]]+dis[Q[k]]>K){
            if (co[Q[k]])
              done[co[Q[k]]]–;
            k–;
          }
          ans+=k-done[co[Q[j]]];
        }
    }
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    for (;;){
        scanf("%d%d",&n,&K);
        if (!n && !K) break;
        init();
        LineTree.trtot=1;
        LineTree.build(1,1,n,1);
        work();
        cout << ans << endl;
    }
}

[NOI2007 day1 社交网络]floyed变形

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1491

【算法分析】

就是利用floyed求最短路。然后加多一个数组表示num[i][j]表示从i到j的最短路的数目。

然后在松弛的地方因为乘法原理，应当变成num[i][k]*num[k][j]，相等的话要加上方案。

最后统计一下就好了。

【其它】1A

【CODE】

#include using namespace std;
int n,m;
int d[122][122];
long long num[122][122];

void input(){
    memset(d,50,sizeof(d));
    memset(num,0,sizeof(num));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        d[x][y]=w;
        d[y][x]=w;
        num[x][y]=1;
        num[y][x]=1;
    }   
}   

void floyed(){
    int i,j,k;
    for (k=1;k<=n;k++)
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if (i!=j && j!=k && i!=k){
              if (d[i][k]+d[k][j]                  d[i][j]=d[i][k]+d[k][j];
                  num[i][j]=num[i][k]*num[k][j];
              }   
              else if (d[i][k]+d[k][j]==d[i][j])
                  num[i][j]+=num[i][k]*num[k][j];
          }   
}   

void output(){
    int i,j,k;
    for (k=1;k<=n;k++){
        double ans=0;
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
            if (i!=j && j!=k && i!=k && d[i][j]==d[i][k]+d[k][j])
                ans+=num[i][k]*num[k][j]*1.0/num[i][j];
        printf("%.3lfn",ans);
    }   
}   

int main(){
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    input();
    floyed();
    output();
}   

[HDOJ3374 String Problem]字符串循环的最小表示

【题目大意】

寻找最小字典序循环串起始位置，和最大字典序循环串起始位置

并分别输出这个串在循环中所出现的次数。

【算法分析】

利用经典算法求出他们最小表示的位置。然后用KMP算出现了几次。

【其它】

1A。

好像挺慢的。。。

【CODE】

#include #include

char s[2001111],p[1001111];
int next[1001111],n;

int minshow(){
    int i=1,j=2,k=0;
    while (i<=n && j<=n && k<=n){
        if (s[i+k]==s[j+k]) k++;
        else{
            if (s[i+k]>s[j+k]) i+=k+1;
                          else j+=k+1;
            if (i==j) i++;
            k=0;
        }   
    }   
    return i}   

int maxshow(){
    int i=1,j=2,k=0;
    while (i<=n && j<=n && k<=n){
        if (s[i+k]==s[j+k]) k++;
        else{
            if (s[i+k]>s[j+k]) j+=k+1;
                          else i+=k+1;
            if (i==j) i++;
            k=0;
        }   
    }   
    return i}   

void kmp(int st){
    int i,j,ans=0;
    for (i=st,j=1;j<=n;i++,j++) p[j]=s[i];
   
    next[1]=0; j=0;
    for (i=2;i<=n;i++){
        while (j && p[j+1]!=p[i]) j=next[j];
        if (p[j+1]==p[i]) j++;
        next[i]=j;
    }   
   
    j=0;
    for (i=1;i<=n+n-1;i++){
        while (j && p[j+1]!=s[i]) j=next[j];
        if (p[j+1]==s[i]) j++;
        if (j==n){
            ans++;
            j=next[j];
        }   
    }   
    printf("%d %d",st,ans);
}   

int main(){
    while (scanf("%s",s+1)!=EOF){
        n=strlen(s+1);
        memcpy(s+n+1,s+1,sizeof(char)*n);
        kmp(minshow()); printf(" ");
        kmp(maxshow()); printf("n");
    }   
}