Tag Archives: POJ

[ACM] POJ2184解题报告

晚上真happy, ac了前天开始的题,还写了点东西..好久没写东西了啊 ^_<

最近做了几道背包(好像就两道吧..),自己总结一下

(为什么我突然觉得这种假装有人会看我写的东西的语气很诡异..显然很诡异啊, 赶快找点人来看..)

目前就做过01背包 完全背包 和多重背包吧.
严格的背包, 可以根据背包九讲上把除了v(1)到v(N)全附成0x80000000(负无穷), 然后按照不严格背包的思路DP
这种情况下, 如果对每一层优化, 就是最后一层只算v[V], 倒2层只从v[V-vn]..V[V]那样的优化, 这样如果严格背包得不到结果, 那就不知道不严格背包的结果了, 虽然也确实没要求..
做非严格背包也可以用严格背包的方法, 从最后的v[]数组中选出最大的即可, 但是这样不能使用每层的优化

然后像http://poj.grids.cn/problem/1276/discuss/这样不求价值只求空间占用的题目, 显然是用严格背包(不然求毛啊), 因为不用存储价值量, v[]用bool型即可, 和上面思路一样, 只是负无穷是false, 非负无穷(这个体积大小可以做到被完全占用)是true

http://poj.grids.cn/problem/2184/status/ 这个开始用的二维背包..傻逼了. 后来发现只要把s看成体积, f看成价值即可. 替换的时候比较体积和价值的和. 因为要求的东西和体积\价值有直接联系, 思维上转换一下就行

错了一天的原因是s可能是负的!! 太阴险了, 01背包刷新v[]的时候是从后像前, 否则就是完全背包. 但是如果某个物品体积是负的, 从后向前刷新v[]前面刷新过的的就会影响接下来的比较..

代码: (用个数组记录非负无穷的数组元素就能0ms吧 懒得折腾了 复杂度O(2*10^7)无压力AC…)

#include <stdio.h>
#include <stdlib.h>
#define orz 200001

int main() {
	int N,s[100],f[100];
	int a[orz];
	int k,result;

	scanf("%d",&N);
	for(int i=0;i<N;i++)
		scanf("%d%d",s+i,f+i);

	for(int i=0;i<orz;i++)
		a[i]=(int)-2e9;
	a[(orz/2)]=0;

	for(int i=0;i<N;i++) {
	    if(s[i]>0) {
            for(int j=orz-1-s[i];j>=0;j--)
                if(a[j]!=(int)-2e9 && a[j+s[i]]<a[j]+f[i])
                    a[j+s[i]]=a[j]+f[i];
	    }
        else {
            for(int j=-s[i];j<=orz-1;j++)
                if(a[j]!=(int)-2e9 && a[j+s[i]]<a[j]+f[i])
                    a[j+s[i]]=a[j]+f[i];
        }
	}

    result=(int)-2e9;
    for(int i=(orz/2);i<orz;i++) {
        if(a[i]<0)
            continue;
        result=a[i]+i>result?a[i]+i:result;
    }
	printf("%d\n",result-(orz/2));

	return 0;
}

[ACM] POJ1024解题报告

思路是board上的.. 经常是不看board没法做啊
思路非常牛B, 来自board上的apunix同学

用BFS,首先设墙和题目已给的路径上的所有点为used,剩余点为unused,然后利用BFS算出从起点到除墙以外的那些点的最短距离,然后利用BFS算出从终点到除墙以外的那些点的最短距离。
(1)判断最短路径是否唯一
如果不唯一,对于那些unused的点,必存在一个点,从起点到这点的最短距离加上从终点到这点的最短距离等于题目给出的最短距离长度
(2)判断墙是否多余
检查题目给出的墙分隔的那些点对,对一个一个被墙分隔的点对(a1,b1),(a2,b2),如果分隔它们的墙是多余的,那么从起点到(a1,b1)的最短距离加上从终点到(a2,b2)的最短距离必大于题目给出的最短距离长度pathlen,且从起点到(a2,b2)的最短距离加上从终点到(a1,b1)的最短距离也必大于pathlen,也就是起点,(a1,b1),(a2,b2),终点不可能在一个最短路径上,也就没必要用墙分隔了

一个小逻辑 有墙多余<=>存在一个墙多余
如果有m个墙是多余的,那么只考虑拿掉这m个墙中的一个其他m-1不动, 这个墙还是多余的, 因为路线完全没有依靠它

我犯了个错误.. 我以为终点一定在[w-1][h-1], 还有有人把每个点到终点/起点的距离初始化为-1, 那么如果有一个区域是封闭的会容易出错.
我是初始化为2E9, 继而中间想到的一个细节是, 这里没问题, 以后如果这些表示正无限的数相加 会超出int表示范围变成负的.. 要小心

代码:
Continue reading

[ACM] POJ1021解题报告

这是一道.. 怎么说呢 只能用龌龊来形容的题目..

折腾了两天, 重写了两遍, 第一次在题目里用链表, 有点为难自己的意思, 不过确实暂时还没想到其他可以省空间的办法.

思路:

1. 每一块用一个节点存储, 存储方式我用的点阵..   先随便找出一个点 然后dfs搜出这个点所在的区域

2. 每一块cake正过来反过来各转4个90度, 用从上到下从左到右一个点一个点比过去这样来排序, 有点傻不过还没发掘出什么具有[旋转不变性]的数学方法可以算出方向不同的cake的特征.

Continue reading

[ACM] POJ1014解题报告

题目:
6种球, 价值分别为1..6, 给出每种的数量, 问能不能分成价值相同的两堆

思路:
1. 将它当成背包问题来看, 包的容积一定(这里的”体积”就是球的价值, 包的容积V=球总价值的一半), 问能不能分成相等两堆即, 包是不是能装满.
2. 这里不用球背包问题中的极值, 不存在价值的概念, 所以v数组用bool型就可以.
3. 因为每种球数量有限制所以不是典型的完全背包问题(目前就看了两个..01背包和完全背包), 我对v中的每一个true它后面每i个赋值成为true, 直到这层的球耗尽. 比如开始v[0]=true v[1..V]=false, 1球的数量为10, 则第一层i循环后, v[0..10]=true v[11.V]=false
4. 3中直接赋值会对后面的计算有影响, 我很蹩脚的另外建了个列表作临时用…
5. 一次AC, 但是时间效率很低, 7XXms..都快超了(大家都爱说..都快超了), 感觉应该是算法过于繁琐..还倒来倒去的, 有空得试试O(log V/c[i])那算法
6. <背包九讲>下载 http://axlarts.com/uploads/documents/pack9lessons.doc 没作者 没写版权声明 直接转了..

代码:

 #include <cstdio>
 #include <cstring>

 int main() {
    int n[7],N,V;
    bool v[60001],t[60001];
    N=0;
    while(++N) {
        V=0;
        bool isEnd=true;
        for(int i=1;i<=6;i++) {
            scanf("%d",n+i);
            V+=n[i]*i;
            if(n[i])
                isEnd=false;
        }
        if(isEnd)
            break;

        printf("Collection #%d:\n",N);
        if(V%2) {
            printf("Can't be divided.\n\n");
            continue;
        }

        ///initialize
        V/=2;
        v[0]=true;
        memset(v+1,false,V);

        for(int i=1;i<=6;i++) {
            memset(t,false,V+1);
            for(int j=0;j<=V;j++) {
                if(!v[j])
                    continue;
                for(int k=0;k<=n[i]*i;k+=i) {
                    if((j+k)>V)
                        break;
                    t[j+k]=true;
                }
            }
            for(int j=1;j<=V;j++)
                v[j]=t[j];
        }

        if(v[V])
            printf("Can be divided.\n\n");
        else
            printf("Can't be divided.\n\n");
    }
    return 0;
 }

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