[ACM] POJ1009解题报告

108 Replies

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

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

[c]
#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++;
}
}
[/c]

108 thoughts on “[ACM] POJ1009解题报告”

  1. eggeek

    怎么会木有人看
    感觉要用双链表…….敲了一下午样例都调不过= =
    找度娘搜题解跑到这里来了….
    报告赶紧补上吧^ ^

    Reply ↓
  2. Viaxl

    这个是两年前的贴了，已经物是人非..
    不写代码了现在，根据我【极为】有限的印象，这题好像没什么数据结构，寻找边界就可以（显然..），比如
    150 150 150 150 150 150 150
    100 100 100 100 100 100 100
    100 100 100 100 100 100 100
    100 100 100 100 100 100 100
    100 100 100 100 100 100 100
    100 100 100 100 100 100 100
    100 100 100 100 99999 100 100
    100 100 100 100 100 100 100
    100 100 100 100 100 100 100
    100 100 100 150 150 150 150
    在【考虑同一列上中下三个数字】的情况下，在哪些位置【上中下任意数字】发生的改动，会影响结果

    哎ái呀..可能毫无用处, 以上是我零散的记忆.. 当时还给谁讲的所以记得一点点..
    果然解题报告什么的拖了两年心中就空无一物了。

    Reply ↓
  3. eggeek

    其实双链表也是这个用处……查找每个数据块后的就可以找到下一行的像素,超过一行停止查找就行了 每个数据块的首元素和为元素单独构成一个链表,因为要判断周围8格的情况…….像素被更新时,就在链表中间插入一个新的链表……

    orz…..FUNK那段视频的背景,好像设备齐全的样子,自己搭建的么,求指导

    Reply ↓
  4. Viaxl Post author

    笔记本+外接屏幕
    台式机+屏幕×2
    怎样实现鼠标在不同机器间切换？本来想弄个USB一分二神马的再写程序用快捷键锁定相应机器的按键，不过这样太麻烦了。
    终于有一天一哥们给我推荐了Synergy，通过网络共享的，延迟很小，巨好用。
    混音么我用的cubase，想学的话自己不断录点东西再听听大师的作品，（midi）控制器什么的用到的时候就自然买了 =D

    我主动忽略了算法的问题..

    Reply ↓

Leave a Reply

Your email address will not be published. Required fields are marked *