Category Archives: 未分类

[ACM] POJ1011 POJ2362解题报告, 状态压缩

10年9月17号Update…
状态压缩BFS 40行水过.. 代码是POJ2362的, 一样的题.. 原来本文只有1011

#include <stdio.h>

bool dfs(int a[],int u,int n,int __s,int start)
{
    if (start==n)
        return true;
    for(int i=(1<<start);i<(1<<n);i+=(2<<start)) {
        if(i&u)
            continue;
        int count=0;
        for(int j=0;j<n;j++)
            count+=a[j]*((i>>j)&1);
        if(count!=__s)
            continue;

        int __u=u|i;
        int j;
        for(j=0;j<n && ((__u>>j)&1);j++);
        if(dfs(a,__u,n,__s,j)) {
            /* DEBUG
            for(int k=0;k<n;k++)
                if((i>>k)&1)
                    printf("%d ",a[k]);
            printf("\n");   */
            return true;
        }
    }
    return false;
}


int main()
{
    int N;
    scanf("%d",&N);
    while (N--)
    {
        int n,a[21],count=0;
        scanf("%d",&n);
        for (int i=0;i<n;i++)
        {
            scanf("%d",a+i);
            count+=a[i];
        }
        printf("%s\n",count%4?"no":(dfs(a,0,n,count/4,0)?"yes":"no"));
    }
    return 0;
}

Continue reading

[ACM] POJ1061解题报告

扩展欧几里德,ap+bq=c,此题中

a=m-n;
b=-l;
c=y-x;

递归到当b=0是停止此时p一定为1,q值不定,不妨设为0,再递归上去得到p0,然后通解是

p = p0 + b/Gcd(a, b) * t
q = q0 – a/Gcd(a, b) * t

此处有一个小问题 导致了我一直不能AC
设c是gcd的n倍,那么p0*=n,然而后面b/Gcd(a, b) * t要不要乘以n呢,答案是不要,没搞清楚为什么,反正不乘就过了..

#include <cstdio>
#include <cmath>
    /*  p = p0 + b/Gcd(a, b) * t
        q = q0 - a/Gcd(a, b) * t
    45 165 63 22 10000          */

__int64 d;

void exgcd(__int64 *p,__int64 *q,__int64 a,__int64 b) {
    __int64 x,y;
    if(!b) {
        *p=1;
        *q=0;
        d=a;
        return;
    }
    exgcd(&x,&y,b,a%b);
    *p=y;
    *q=(x-a/b*y);
    return;
}

int main() {
    __int64 x,y,m,n,l,a,b,c,p,q,t;
    scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
    a=m-n;
    b=-l;
    c=y-x;
    exgcd(&p,&q,a,b);
    if(c%d) {
        printf("Impossible\n");
        return 0;
    }
    n=c/d;
    t=(b/d);
    t=t>0?t:-t;
    p=(n*p%t+t)%t;
    printf("%I64d\n",p);
    return 0;
}

[ACM] POJ2965 ver.2

if(a[i][j]==’+’)直接把结果矩阵里面以i,j为中心的十字全部改变bool值就好了,方便的算法
但是应该效率高啊 怎么这么慢.. 比递归慢好几倍 奇怪..

#include <cstdio>
#include <cstring>
int main() {
    char a[4][5];
    int r[32];
    int i,j,k,n=0,temp;
    for(i=0;i<4;i++)
        gets(a[i]);
    for(i=0;i<4;i++)
        for(j=0;j<4;j++) {
            temp=0;
            for(k=0;k<4;k++)
                temp+=a[i][k]/2+a[k][j]/2;
            temp-=a[i][j]/2;
            if(temp%2) {
                r[n++]=i;
                r[n++]=j;
            }
        }
    printf("%d\n",n/2);
    for(i=0;i<n;i+=2)
        printf("%d %d\n",r[i]+1,r[i+1]+1);
}

[ACM] POJ2965解题报告

爽死了 两个小时又切掉一题某人的fail!
递归大美!!! 我的思维和机器的思维真是惊人的合拍啊^^

思路:
把矩阵分成两个三角矩阵


  -+--
-  ---
--  --
-+-  -

这样然后先对上三角的第行和下三角的(左起)第列枚举,接着对上三角第行和下三角第列枚举,关键就是在从“一”进入“二”的时候 对左上角的矩形进行判断,这一个矩形是进入“二”以后再也接触不到的一个区域,如果此区域不是全部open那以后的递归就不用做了,大大提高效率 :) 自己想出来的噢~~ AC32ms 看了比绝大部分人快 也~~

debug用了大半个小时 其实只有一个错……上三角的最后一行没有进行枚举,无法得到结果,浪费那么长时间遗憾啊
debug的时候想到的技巧:因为递归层数太多显然无法一步一步调试 于是我加了这段判定代码:

if(r[0][0]&&!r[0][1]&&r[0][2]&&r[0][3]
 &&!r[1][0]&&!r[1][1]&&!r[1][2]&&!r[1][3]
 &&!r[2][0]&&!r[2][1]&&!r[2][2]&&!r[2][3]
 &&r[3][0]&&!r[3][1]&&r[3][2])
	i=1;

在i=1;上面设breakpoint就可以一步到达终点来调试了..开始多加了个&&r[3][3]因为下面的bug一直搞不出来
擦 来不及了 赶快贴了代码去学校抄作业

#include <cstdio>


bool a[4][4],r[4][4];

void change(int x,int y) {
    int i;
    for(i=0;i<4;i++) {
        a[x][i]=a[x][i]?false:true;
        a[i][y]=a[i][y]?false:true;
    }
    a[x][y]=a[x][y]?false:true;
    r[x][y]=r[x][y]?false:true;
}

bool calc(bool istop,int row,int from) {
    int i,j;

    /*TESTER
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++)
            printf("%d",r[i][j]);
        printf("\n");
    }

    if(r[0][0]&&!r[0][1]&&r[0][2]&&r[0][3]
    &&!r[1][0]&&!r[1][1]&&!r[1][2]&&!r[1][3]
    &&!r[2][0]&&!r[2][1]&&!r[2][2]&&!r[2][3]
    &&r[3][0]&&!r[3][1]&&r[3][2])
        i=1;*/

    if(!istop&&row==3) {
        for(i=0;i<4;i++)
            if((!a[i][3])||(!a[3][i]))
                return false;
        return true;
    }
    if(istop) {
        if(from>3-row)
            return calc(false,row,0);
        if(calc(true,row,from+1))
            return true;
        change(row,from+row);
        if(calc(true,row,from+1))
            return true;
        change(row,from+row);
        return false;
    }
    else {
        if(from>2-row) {
            for(i=0;i<=row;i++)
                if((!a[i][row])||(!a[row][i]))
                    return false;
        return calc(true,row+1,0);
        }
        if(calc(false,row,from+1))
            return true;
        change(row+from+1,row);
        if(calc(false,row,from+1))
            return true;
        change(row+from+1,row);
        return false;
    }
}

int main() {
    int i,j,n;
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++)
            a[i][j]=getchar()=='-'?true:false;
        getchar();
        r[i][j]=false;
    }
    calc(true,0,0);
    n=0;
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(r[i][j])
                n++;
    printf("%d\n",n);
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(r[i][j])
                printf("%d %d\n",i+1,j+1);
    return 0;
}

[ACM] POJ1573解题报告

夜里边切题边等电影缓冲真是太爽了..
正在慢慢的切某人切不下来的题..
1573挺简单的 以后这种模拟的数组我都从1开始就好了..省得墨迹墨迹的整的头大..

主要就是想到一个监视指针的方法..做个tester指针数组 对应map上面所有的单元
这样本来看不懂的指针地址(0x22fb18这样)就能通过查找tester来获得它的位置(tester是一个地址的数组 找到对应的 然后数数)

详见下图 ap是tester,p==0x22fb18,在ap中排第10个,则p==*(ap[9])

#include <cstdio>
#include <cstring>
typedef struct spot {
    char c;
    bool b;
    int n;
} Spot;
Spot *p;

void move() {
    switch(p->c) {
        case 'N':
            p-=12;
            break;
        case 'S':
            p+=12;
            break;
        case 'E':
            p+=1;
            break;
        case 'W':
            p-=1;
    }
}

int main() {
    int i,enter,j,n,rows,cols;
    Spot a[12][12];
    /*Tester
    Spot *(ap[3][6]);
    for(i=0;i<3;i++)
        for(j=0;j<7;j++)
            ap[i][j]=a[i]+j;*/
    while(1) {
        for(i=0;i<144;i++) {
            ((Spot *)a+i)->c=-1;
            (a[0]+i)->b=false;
        }
        n=0;
        scanf("%d%d%d",&rows,&cols,&enter);
        if(!rows&&!cols&&!enter)
            return 0;
        getchar();
        for(i=1;i<=rows;i++) {
            for(j=1;j<=cols;j++)
                a[i][j].c=getchar();
            getchar();
        }
        p=a[1]+enter;
        /* TESTER
        for(i=0;i<rows;i++) {
            for(j=1;j<=cols;j++)
                printf("%c",a[i][j].c);
            printf("\n");
        } */
        while(1) {
            p->b=true;
            p->n=n;
            if(p->c==-1) {
                printf("%d step(s) to exit\n",n);
                break;
            }
            move();
            if(p->b) {
                printf("%d step(s) before a loop of %d step(s)\n",p->n,n+1-p->n);
                break;
            }
            n++;
        }
    }
    return 0;
}

[ACM] POJ1009解题报告

做了一夜 再也不想敲键盘了..等等再报告 贴出来先 (其实又没人看….)

没有什么任何优化 直接0msAC 真不好意思 XD

#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXNUM 2000

typedef struct pair {
    int v,l;
} Pair;

typedef struct pointer {
    int p,num;
} Pointer;

Pair a[MAXNUM],r[MAXNUM];
int width,prow,rp;
Pointer p2,p5,p8;

void calc();
void set(Pointer *target,int p,int num);
void go(int spit,int steps);
void gop(Pointer *p,int steps);
int pre(Pointer p);
int next(Pointer p);
int spit();;

int main() {
    int i;
    while(1) {
        rp=0;
        scanf("%d",&width);
        if(width==0) {
            printf("0\n");
            return 0;
        }
        for(i=1;;i++) {
            scanf("%d%d",&a[i].v,&a[i].l);
            if(!a[i].v&&!a[i].l)
                break;
        }
        a[0].v=a[i].v=-1;
        a[0].l=a[i].l=width;
        r[0].v=-1;
        r[1].l=0;
        calc();
        printf("%d\n",width);
        for(i=1;;i++) {
            printf("%d %d\n",r[i].v,r[i].l);
            if(!r[i].v&&!r[i].l)
                break;
        }
    }
}

void calc() {
    int i,counter;
    int x,y,z,steps;
    prow=1;
    set(&p2,0,1);
    set(&p5,1,1);
    counter=0;
    for(i=1;counter<=width;i++)
        counter+=a[i].l;
    i--;
    set(&p8,i,width-counter+a[i].l+1);
    while(1) {
        if(a[p5.p].v==-1)
            break;
        x=a[p2.p].l-p2.num;
        y=a[p5.p].l-p5.num;
        z=a[p8.p].l-p8.num;
        steps=x>y?y:x;
        steps=steps>z?z:steps;
        if(steps<3) {
            go(spit(),1);
            continue;
        }                           //可在此处插入判断边界程序
        go(spit(),1);
        go(spit(),steps-1);
    }
    rp++;
    r[rp].v=r[rp].l=0;
}

void set(Pointer *target,int p,int num) {
    target->p=p;
    target->num=num;
}

int spit(){
    int result=0,i=0,temp,x=a[p5.p].v;
    bool top=false,bottom=false;
    if(a[p2.p].v==-1)
        top=true;
    if(a[p8.p].v==-1)
        bottom=true;
    if(prow!=1) {
        if(!top)
            result=(temp=fabs(pre(p2)-x))>result?temp:result;
        result=(temp=fabs(pre(p5)-x))>result?temp:result;
        if(!bottom)
            result=(temp=fabs(pre(p8)-x))>result?temp:result;
    }
    if(prow!=width) {
        if(!top)
            result=(temp=fabs(next(p2)-x))>result?temp:result;
        result=(temp=fabs(next(p5)-x))>result?temp:result;
        if(!bottom)
            result=(temp=fabs(next(p8)-x))>result?temp:result;
    }
    if(!top)
        result=(temp=fabs(a[p2.p].v-x))>result?temp:result;
    if(!bottom)
        result=(temp=fabs(a[p8.p].v-x))>result?temp:result;
    return result;
}

int pre(Pointer p) {
    if(p.num==1)
        return(a[p.p-1].v);
    else
        return(a[p.p].v);
}

int next(Pointer p) {
    if(p.num==a[p.p].l)
        return(a[p.p+1].v);
    else
        return(a[p.p].v);
}

void go(int spit,int steps) {
    if(r[rp].v==spit)
        r[rp].l+=steps;
    else {
        rp++;
        r[rp].v=spit;
        r[rp].l=steps;
    }
    gop(&p2,steps);
    gop(&p5,steps);
    gop(&p8,steps);
    prow=(prow+steps-1)%width+1;
}

void gop(Pointer *p,int steps) {
    p->num+=steps;
    while(p->num>a[p->p].l) {
        p->num-=a[p->p].l;
        p->p++;
    }
}

[ACM] POJ1135解题报告

Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase “domino effect” comes from).

啥都不用说了..原来我想出来的算法 在五十年前已经被一名叫做的Dijkstra同学提出来了.. 恨啊 晚生半个世纪
Dijkstra’s algorithm传送门
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
右边图示很销魂

前面都差不多就是当结果是between a  and b时需要技巧,我是在所有dominoes都倒下后将所有连接的节点进行计算,多米诺卡在ab之间的时间等于(a.time+b.time+ab之间时间)/2,当b是由a推倒时,这个数值就等于b的时间,不可能超过最长时间,因而无需额外考虑,方便啊!

#include <cstdio>
#include <cstring>
#define MAXNUM 500

typedef struct card{
    int time;
    int l[MAXNUM+1];
    bool touched,out;
} Card;

int n,p,p1=-1,p2;
float time;
Card a[MAXNUM+1];

void dij();
void between();

int main() {
    int c,b,l,m;
    int i,N=1;
    Card ini;   //used to initialize
    memset(ini.l,-1,sizeof(int)*(MAXNUM+1));
    ini.time=0;
    ini.touched=false;
    ini.out=false;
    scanf("%d%d",&n,&m);
    while(n!=0) {
        for(i=1;i<=MAXNUM;i++)
            a[i]=ini;
        p1=-1;
        time=0;

        for(i=0;i<m;i++) {
            scanf("%d%d%d",&c,&b,&l);
            a[c].l[b]=a[b].l[c]=l;
        }
        a[1].touched=true;
        for(i=1;i<=n;i++)
            dij();
        between();
        printf("System #%d\nThe last domino falls after %.1f seconds, ",N,time);
        if(p1!=-1)
            printf("between key dominoes %d and %d.\n\n",p1,p2);
        else
            printf("at key domino %d.\n\n",p);
        N++;
        scanf("%d%d",&n,&m);
    }
    return 0;
}

void dij() {
    int i,j,reachtime;
    p=-1;
    for(i=1;i<=n;i++) {
        if(!a[i].touched||a[i].out)
            continue;
        if(p==-1||a[p].time>a[i].time)
            p=i;
    }
    for(i=1;i<=n;i++) {
        if(a[p].l[i]==-1||a[i].out)
            continue;
        reachtime=a[p].time+a[p].l[i];
        if(!a[i].touched||a[i].time>reachtime) {
            a[i].time=reachtime;
            a[i].touched=true;
        }
    }
    a[p].out=true;
    time=a[p].time;
}

void between() {
    int i,j;
    float t;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++) {
            if(a[i].l[j]==-1||(t=(float)(a[i].time+a[j].time+a[i].l[j])/2)<=time)
                continue;
            p1=i;
            p2=j;
            time=t;
        }
}

[ACM] POJ1125 解题报告

老田用的弗洛伊德 我觉得我的快一点..不知道叫啥算法 无招胜有招了 (墨镜)
每个人身上两种属性 传到他需要的时间(int time)以及他是否往下传播(bool set)
unit向他的contact传播 => contact.time=unit.settime

[contact](传播到此contact所需时间)+unit.time

1.开始选择的人start, start.set=true
2.扫描所有的unit, 如果set==true则对他的每一个contact判断, 若contact.time>unit.time+unit.setting(contact), 则用这个较快的time赋值,并且contact.set=true, 下一轮用新的time传播给这个contact的contact们
3.重复2知道所有unit.set==false为止
4.判断是否有unit没有触及到

#include <cstdio>

 typedef struct unit {
     int num;
     int contact[99];
     int settime[99];
     bool set;
     int time;
 } Unit;

 typedef struct aa {
     int start;
     int time;
 } Result;

void calc();
int search();

Unit a[101];
Result x,result;
int n;

int main() {
    int i,j,start;
    scanf("%d",&n);
    while(n) {
        for(i=1;i<=n;i++) {
            scanf("%d",&a[i].num);
            for(j=0;j<a[i].num;j++)
                scanf("%d%d",&a[i].contact[j],&a[i].settime[j]);
        }
        result.start=-1;
        for(start=1;start<=n;start++) {
            for(i=1;i<=n;i++) {
                a[i].set=false;
                a[i].time=-1;
            }
            a[start].set=true;
            a[start].time=0;
            i=0;
            while(i<n+1) {
                calc();
                for(i=1;i<=n;i++)
                    if(a[i].set==true)
                        break;
            }
            x.time=search();
            x.start=start;
            for(i=1;i<=n;i++)
                if(a[i].time==-1) {
                    x.start=-1;
                    break;
                }
            if(x.start==-1)
                continue;
            if(x.time<result.time||result.start==-1)
                result=x;
        }
        if(result.start==-1)
            if(n==0)
                printf("0 0\n");
            else
                printf("disjoint\n");
        else
            printf("%d %d\n",result.start,result.time);
        scanf("%d",&n);
    }
    return 0;
}

void calc() {
    int i,j,spreadtime;
    for(i=1;i<=n;i++)
        if(a[i].set) {
            for(j=0;j<a[i].num;j++) {
                spreadtime=a[i].time+a[i].settime[j];
                if(a[a[i].contact[j]].time>spreadtime||a[a[i].contact[j]].time==-1) {
                    a[a[i].contact[j]].time=spreadtime;
                    a[a[i].contact[j]].set=true;
                }
            }
            a[i].set=false;
        }
}

int search() {
    int max,i;
    max=a[1].time;
    for(i=2;i<=n;i++)
        if(a[i].time>max)
            max=a[i].time;
    return max;
}

 

[ACM] POJ1661 解题报告

AC大美..之前一直WA到死 把search部分做成函数就AC了 实在不知道哪错了回头再看..
动态规划能不用递归就不用 循环从底层开始算到Jimmy落脚点那一层

#include <cstdio>
#include <cstdlib>
typedef struct flat {
    int l,r,h,lmin,rmin;
} Flat;
Flat a[1001];
int N,MAX;

void search(int i,int k,bool bLeft);
int compare(const void *a,const void *b);

int main() {
    int i,j,location;
    int t,X,Y;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d%d",&N,&X,&Y,&MAX);
        for(i=1;i<=N;i++)
            scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h);
        qsort(a+1,N,sizeof(a[0]),compare);
        for(i=1;i<=N+1;i++) {
            if(a[i].l<=X&&a[i].r>=X||i==N+1) {
                a[i-1].l=a[i-1].r=X;
                a[i-1].h=Y;
                location=i-1;
                break;
                }
        }
        for(i=N;i>=location;i--) {
            for(j=i+1;j<=N;j++)
                if(a[j].h!=a[i].h)
                    break;
        search(i,j,true);
        search(i,j,false);
        }
        printf("%d\n",a[location].lmin);
    }
    return 0;
}

void search(int i,int k,bool bLeft) {
    int x,*min,gotol,gotor,fall;
    if(bLeft) {
        x=a[i].l;
        min=&a[i].lmin;
    }
    else {
        x=a[i].r;
        min=&a[i].rmin;
    }
    for(;k<=N;k++)
        if(a[k].l<=x&&a[k].r>=x)
            break;

    if(k==N+1)
        if(a[i].h>MAX)
            *min=-1;
        else
            *min=a[i].h;
    else {
        fall=a[i].h-a[k].h;
        if(fall>MAX)
            *min=-1;
        else {
            gotol=fall+x-a[k].l+a[k].lmin;
            gotor=fall+a[k].r-x+a[k].rmin;
            if(a[k].lmin==-1)
                if(a[k].rmin==-1)
                    *min=-1;
                else
                    *min=gotor;
            else
                if(a[k].rmin==-1)
                    *min=gotol;
                else
                    if(gotol<gotor)
                        *min=gotol;
                    else
                        *min=gotor;
        }
    }
}

int compare(const void *a,const void *b) {
    return ((Flat *)b)->h-((Flat *)a)->h;
}

[ACM] Longest increasing subsequence

#include <cstdio>
int main() {
    int a[1000],maxlen[1000]={0};
    int *p,*max=maxlen;
    int i,j,N;
    scanf("%d",&N);
    for(i=0;i<N;i++) {
        scanf("%d",a+i);
        p=maxlen+i;
        for(j=0;j<i;j++)
            if(a[j]<a[i]&&maxlen[j]>*p)
                p=maxlen+j;                 //求以a[i]为终点的最长上升子序列长度
        maxlen[i]=*p+1;
        if(maxlen[i]>*max)
            max=maxlen+i;
    }
    printf("%d\n",*max);
    return 0;
}