作者存档：edward_mj

[POJ 3273 Monthly Expense]二分答案

【题目大意】

给定一个数组A[i]，1<=a[i]<=10000

求把它分成M份，每份的和不超过一个值K。

问K最小是多少？

【算法分析】

注意到A[i]都是正数，所以我们可以二分答案，然后线性贪心判断即可。

如果A[i]存在负数的话，这个算法就不正确了。

【其它】

1WA，1A。悲剧，忘了删文件。

另外一开始想了挺久的。。。最主要是读题不够仔细，没看到那个A[i]>=1

【CODE】

#include #include #include typedef long long LL;
int m,n;
int a[101111],Max=0;

bool flag(LL limit){
    int num=1;
    LL sum=a[1];
    for (int i=2;i<=n;i++)
      if (sum+a[i]>limit){
          num++;
          sum=a[i];
      }
      else sum+=a[i];
    if (num>m) return false;
    return true;
}   

int main(){
    scanf("%d%d",&n,&m);
    LL sum=0;
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (a[i]>Max) Max=a[i];
        sum+=a[i];
    }   
    LL l=Max,r=sum,mid;
    while (l        mid=(l+r)/2;
        if (flag(mid)) r=mid;
                  else l=mid+1;
    }
    printf("%lldn",l);
}   

[POJ1988 Cube Stacking]并差集

【题目大意】

同银河英雄传说。。。

【算法分析】

并差集之~

这题更简单，直接输出s[i]即可。

【其它】1A

。。。无意水，是在找银河英雄传说的提交网站时无意碰到的。。。

【CODE】

#include #include #include const int n=30000;
int T;
int f[31111],s[31111],tail[31111];
char c;

int gf(int x){
    if (f[x]==x) return x;
    int tf=gf(f[x]);
    s[x]+=s[f[x]];
    f[x]=tf;
    return tf;
}   

void Union(){
    int x,y;
    scanf("%d%d",&y,&x);
    gf(x); gf(y);
    s[f[y]]=1;
    int fy=f[y];
    f[f[y]]=tail[f[x]];
    tail[f[x]]=tail[fy];
}   

void Count(){
    int x;
    scanf("%d%d",&x);
    gf(x);
    printf("%dn",s[x]);
}   

int main(){
    for (int i=1;i<=n;i++){
        f[i]=i;
        s[i]=0;
        tail[i]=i;
    }   
    scanf("%d",&T);
    for (int i=1;i<=T;i++){
        c=getchar();
        while (c==’ ‘ || c==’n’) c=getchar();
        if (c==’M’) Union();
               else Count();
    }   
}   

[NOI2002 day1 银河英雄传说]并差集

【算法分析】

直接上一个并差集，然后+两个辅助数组s[i],tail[i]

s[i]表示f[i]到i的距离

tail[i]表示i所在的团的最尾部是哪个

然后维护即可。

【其它】1A

【CODE】

#include #include #include const int n=30000;
int T;
int f[31111],s[31111],tail[31111];
char c;

int gf(int x){
    if (f[x]==x) return x;
    int tf=gf(f[x]);
    s[x]+=s[f[x]];
    f[x]=tf;
    return tf;
}   

void Union(){
    int x,y;
    scanf("%d%d",&y,&x);
    gf(x); gf(y);
    s[f[y]]=1;
    int fy=f[y];
    f[f[y]]=tail[f[x]];
    tail[f[x]]=tail[fy];
}   

void Count(){
    int x,y;
    scanf("%d%d",&x,&y);
    if (gf(x)!=gf(y)){
        printf("-1n");
        return;
    }   
    int ans=abs(s[x]-s[y])-1;
    if (ans<0) ans=0;
    printf("%dn",ans);
}   

int main(){
    freopen("galaxy.in","r",stdin);
    freopen("galaxy.out","w",stdout);
    for (int i=1;i<=n;i++){
        f[i]=i;
        s[i]=0;
        tail[i]=i;
    }   
    scanf("%d",&T);
    for (int i=1;i<=T;i++){
        c=getchar();
        while (c==’ ‘ || c==’n’) c=getchar();
        if (c==’M’) Union();
               else Count();
    }   
}   

[POJ 1739 Tony’s Tour]基于连通性的状态压缩动态规划、男人8题

【题目大意】

给定一个M*N的矩阵，问从左下角经过所有非障碍点到达右下角有多少种方案？

【算法分析】

我们先把图改一下。

比如说样例

..

..

那么改成

……

.####.

.#..#.

......

这样转化以后，就变成求哈密顿回路的方案数了。

因为最外面那一圈必须走。

于是用Cdq的论文的方法解决。

【其它】1A，hash开到10003是47MS,开到473 是32MS。。。果然我的怎么说都比较慢啊。。。

【CODE】

#include #include #include #include #define cf(x) (1<<(x))
using namespace std;
const int key=473;
const int INF=0x7FFFFFFF;
typedef long long LL;
struct gtp{int y,next;}g[200000];
int m,n,ng,pg,e,mx,my;
char c[15][15];
LL fl[2][200000],ans;
int sl[2][200000];
int tot[2],ls[key];

inline void init(){e=0;memset(ls,0,sizeof(ls));}
inline void addedge(int x,int y){e++; g[e].y=y; g[e].next=ls[x]; ls[x]=e;}
inline int ChaTou(int t1,int t2){
    if (!t1 && !t2) return 0;
    if (t1) return 1;
    return 2;
}   

void add(int s,LL f){
    int st=s; if (st>=key) st%=key;
    for (int t=ls[st];t;t=g[t].next)
      if (sl[ng][g[t].y]==s){
          fl[ng][g[t].y]+=f;
          return;
      }
    sl[ng][++tot[ng]]=s;
    fl[ng][tot[ng]]=f;
    addedge(st,tot[ng]);
}

bool input(){
    ng=1; pg=0; ans=0; tot[0]=0; tot[1]=0;
    scanf("%d%d",&m,&n);
    if (!m && !n) return false;
    int i,j;
    char ch;
    memset(c,’#’,sizeof(c));
    for (i=0;i      for (j=0;j        for (ch=getchar();ch!=’#’&&ch!=’.’;ch=getchar());
        c[i+2][j+2]=ch;
      }
    m+=2; n+=4;
    for (j=0;j    for (i=0;i    for (i=0;i    c[m-1][1]=’.’; c[m-1][n-2]=’.’;
    init();
    add(1+cf((n<<1)+1),1);
    mx=0; my=0;
    for (i=0;i      for (j=0;j        if (c[i][j]==’.’){
            mx=i;
            my=j;
        }   
    return true;
}   

void No(int j){
    int k,t1,t2;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        if ((s&cf((j<<1)))||(s&cf((j<<1)+1))||(cf((n<<1))&s)||(cf((n<<1)+1)&s)) continue;
        add(s,fl[pg][k]);
    }   
}

void Yes(int I,int j){
    int k,lct,uct,ts,i,top,ct;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        LL &f=fl[pg][k];
        uct=ChaTou(s&cf((j<<1)),s&cf((j<<1)+1));
        lct=ChaTou(s&cf((n<<1)),s&cf((n<<1)+1));
        if (!j && lct) continue;
        ts=(INF-cf((j<<1))-cf((j<<1)+1)-cf((n<<1))-cf((n<<1)+1))&s;
        switch (lct){
            case 0:
                switch (uct){
                    case 0:
                        add(ts|cf((j<<1))|cf((n<<1)+1),f);
                        break;
                    case 1:
                        add(ts|cf((j<<1)),f);
                        add(ts|cf((n<<1)),f);
                        break;
                    case 2:
                        add(ts|cf((j<<1)+1),f);
                        add(ts|cf((n<<1)+1),f);
                        break;
                }   
                break;
            case 1:
                switch (uct){
                    case 0:
                        add(ts|cf((j<<1)),f);
                        add(ts|cf((n<<1)),f);
                        break;
                    case 1:
                        top=0;
                        for (i=j;;i++){
                            ct=ChaTou(s&cf((i<<1)),s&cf((i<<1)+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }
                        add((ts^cf((i<<1)+1))|cf((i<<1)),f);
                        break;
                    case 2:
                        if (I==mx && j==my && ts==0) ans+=f;
                        break;
                }   
                break;
            case 2:
                switch (uct){
                    case 0:
                        add(ts|cf((j<<1)+1),f);
                        add(ts|cf((n<<1)+1),f);
                        break;
                    case 1:
                        add(ts,f);
                        break;
                    case 2:
                        top=0;
                        for (i=j;;i–){
                            ct=ChaTou(s&cf((i<<1)),s&cf((i<<1)+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }   
                        add((ts^cf((i<<1)))|cf((i<<1)+1),f);
                        break;
                }   
                break;
        }   
    }   
}            

void dp(){
    for (int i=0;i      for (int j=0;j          if (!i && !j) continue;
          ng=1-ng;
          pg=1-pg;
          tot[ng]=0;
          init();
          if (c[i][j]==’#’) No(j);
                       else Yes(i,j);
      }
}   

int main(){
    while (input()){
      dp();
      cout << ans << endl;
}   
    return 0;   
}   

[Ural 1519 Formula 1]基于连通性的状态压缩动态规划

【题目大意】

给定一个M*N的矩阵，让你求其中非障碍格的哈密顿回路有多少种。

【算法分析】

按照CDQ的论文所写。

我用两个二进制位来表示插头：

00表示无插头

01表示“(”插头

10表示“)”插头

然后就分类讨论即可。

实现上，我用一个hash表来达到定位的目的。

因为这样表示状态很多，但是实际上状态是非常稀疏的，所以我开一个线性表来保存扩展到的状态，然后更新的时候，就从hash表里指向过去，然后维护一下就好了。

【其它】1A，跑了109MS

【CODE】

#include #include #include #include #define cf(x) (1<<(x))
using namespace std;
const int key=10003;
const int INF=0x7FFFFFFF;
typedef long long LL;
struct gtp{int y,next;}g[1000000];
int m,n,ng,pg,e,mx,my;
char c[13][13];
LL fl[2][20000],ans;
int sl[2][20000];
int tot[2],ls[key];

inline void init(){e=0;memset(ls,0,sizeof(ls));}
inline void addedge(int x,int y){e++; g[e].y=y; g[e].next=ls[x]; ls[x]=e;}
inline int ChaTou(int t1,int t2){
    if (!t1 && !t2) return 0;
    if (t1) return 1;
    return 2;
}   

void add(int s,LL f){
    int st=s%key;
    for (int t=ls[st];t;t=g[t].next)
      if (sl[ng][g[t].y]==s){
          fl[ng][g[t].y]+=f;
          return;
      }
    sl[ng][++tot[ng]]=s;
    fl[ng][tot[ng]]=f;
    addedge(st,tot[ng]);
}   

void input(){
    ng=1; pg=0; ans=0;
    scanf("%d%d",&m,&n);
    int i,j;
    for (i=0;i      for (j=0;j        for (c[i][j]=getchar();c[i][j]!=’*’&&c[i][j]!=’.’;c[i][j]=getchar());
    if (c[0][0]==’*’) add(0,1);
                 else add(1+cf(n*2+1),1);
    mx=0; my=0;
    for (i=0;i      for (j=0;j        if (c[i][j]==’.’){
            mx=i;
            my=j;
        }   
}   

void No(int j){
    int k,t1,t2;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        if ((s&cf(j*2))||(s&cf(j*2+1))||(cf(n*2)&s)||(cf(n*2+1)&s)) continue;
        add(s,fl[pg][k]);
    }   
}

void Yes(int I,int j){
    int k,lct,uct,ts,i,top,ct;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        LL &f=fl[pg][k];
        uct=ChaTou(s&cf(j*2),s&cf(j*2+1));
        lct=ChaTou(s&cf(n*2),s&cf(n*2+1));
        if (!j && lct) continue;
        ts=(INF-cf(j*2)-cf(j*2+1)-cf(n*2)-cf(n*2+1))&s;
        switch (lct){
            case 0:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2)|cf(n*2+1),f);
                        break;
                    case 1:
                        add(ts|cf(j*2),f);
                        add(ts|cf(n*2),f);
                        break;
                    case 2:
                        add(ts|cf(j*2+1),f);
                        add(ts|cf(n*2+1),f);
                        break;
                }   
                break;
            case 1:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2),f);
                        add(ts|cf(n*2),f);
                        break;
                    case 1:
                        top=0;
                        for (i=j;;i++){
                            ct=ChaTou(s&cf(i*2),s&cf(i*2+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }
                        add((ts^cf(i*2+1))|cf(i*2),f);
                        break;
                    case 2:
                        if (I==mx && j==my && ts==0) ans+=f;
                        break;
                }   
                break;
            case 2:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2+1),f);
                        add(ts|cf(n*2+1),f);
                        break;
                    case 1:
                        add(ts,f);
                        break;
                    case 2:
                        top=0;
                        for (i=j;;i–){
                            ct=ChaTou(s&cf(i*2),s&cf(i*2+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }   
                        add((ts^cf(i*2))|cf(i*2+1),f);
                        break;
                }   
                break;
        }   
    }   
}            

void dp(){
    for (int i=0;i      for (int j=0;j          if (!i && !j) continue;
          ng=1-ng;
          pg=1-pg;
          tot[ng]=0;
          init();
          if (c[i][j]==’*’) No(j);
                       else Yes(i,j);
      }
}   

int main(){
    input();
    dp();
    cout << ans << endl;
    return 0;   
}