Category Archives:

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

怎样教育弟弟

[嘘]别吵 14:41:53
要不你给我充点吧,我去换游戏币

Viaxl 14:46:07
两张?

[嘘]别吵 14:46:25
最好两张,一张也行

Viaxl 14:46:44

[嘘]别吵 14:46:50
。。。

[嘘]别吵 14:46:53
两张

防沉迷

鈈緗飞 22:40:24
现在完全没意思啊WOW
Viaxl 22:41:27
主要是没朋友
鈈緗飞 22:41:53
主要是开学就不怎么玩了…
Viaxl 22:41:56
..拉电信
Viaxl 22:42:07
有朋友就有归属感 就要成瘾了..
鈈緗飞 22:42:36
-.-你也成砖家叫兽了
Viaxl 22:43:22
本来就是..
所以我玩网游不上瘾的原因也许就是人缘差?
鈈緗飞 22:44:19
我觉得主要是不沉迷所以没有朋友,所以不会沉迷的循环…

WOW台服客户端

http://www.wowtaiwan.com.tw/06Download/SupportTools/supporttools.asp?Page=3
下这个 《魔獸世界:巫妖王之怒》3.0.1安裝檔官網下載點:

无法提取种子文件 搜了一下 nga是这么说的

已经确认InstallWoW.exe不可以用WoWTorrentEx.exe转成种子文件再下载
因为这东西本身就是直连的
所以第一部分的下载必须忍受了,这个东西很慢,很恶心,出错要重来

所以只能慢慢下了

Almost Famous: Ask me again

-“I’m gonna live in morocco, for one year”
“I need a new crowd”
“Do you wanna come?”

-“Yes, yeah, yeah”

-“Are you sure?”

-“Ask me again”

-“do you want to come”

-“yes, yeah.”

it’s all happening
it’s all happening