个人赛,前两天

Posted on by snoopy 
发信人: snoopy (Snoopy@T13), 信区: ACM_ICPC
标  题: 个人赛前两天题目来源
发信站: 珞珈山水BBS站 (Sat Aug 12 10:05:22 2006), 转信

非官方版本,今天早上找了一个小时找全了的
第二天的G据KO说是原创,但是和Tongji的1004防御导弹是一样的

编号.题目            来源        简单说明
D1A.dna             POJ1080     DP
D1B.Game            POJ1143     集合DP+博弈?
D1C.spell           POJ1035     直接硬搞
D1D.Frames          POJ1128     模拟?
D1E.Cable           POJ1064     转换成整数二分
D1F.2046            POJ1733     并查集+Hash
D1G.Transmitters    POJ1106     简单计算几何,算叉乘

D2A.Excel-lent      POJ2273     模拟,类进制转换
D2B.Dice            POJ1481     简单双重DFS
D2C.Rocket Height   POJ2276     初等几何,推公式
D2D.Slides          POJ1486     类匹配思想,硬搞
D2E.Lotto           POJ2193     DP,要用longlong
D2F.Optimal         POJ1480     BFS硬搞
D2G.Sequence        Tongji1004  贪心

除了第二天的G,全部都是没做过的...ft

最优匹配(Kuhn_Munkras算法)

Posted on by snoopy 
// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^3)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-th node is visited, matx[x] means x match matx[x],
// maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays are start at 1

int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    fx[u]=1;
    for(v=1;v<=ny;v++)
        if((lx[u]+ly[v]==w[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((lx[u]...
    return(0);
} // end of int path()

int PerfectMatch()
{
    int ret=0,i,j,k,p;

    memset(ly,0,sizeof(ly));
    for(i=1;i<=nx;i++) {
        lx[i]=-INF;
        for(j=1;j<=ny;j++)
            if(w[i][j]>lx[i])
                lx[i]=w[i][j];
    } // end of for(i...

    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k=1;k<=nx;k++)
                if(fx[k]>0)
                    for(j=1;j<=ny;j++)
                        if((fy[j]<0)&&(lx[k]+ly[j]-w[k][j]<p))
                            p=lx[k]+ly[j]-w[k][j];
            for(j=1;j<=ny;j++) ly[j]+=(fy[j]<0?0:p);
            for(k=1;k<=nx;k++) lx[k]-=(fx[k]<0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i=1;i<=ny;i++) ret+=w[maty[i]][i];
    return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************

最大匹配(匈牙利算法)

Posted on by snoopy 
// ** Start of MaximumMatch *******************************
// Name: MaximumMatch by Hungray O(n^3)
// Description: mat is the adjacency matrix, nx,ny are the size of x and y,
// fy is used for marking whether the k-th node is visited, matx[x] means x
// match matx[x], maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays start at 1

int nx,ny,mat[MAXN][MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    for(v=1;v<=ny;v++)
        if((mat[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((mat[u][v]...
    return(0);
} // end of int path()

int MaximumMatch()
{
    int i,ret=0;
    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++)
        if(matx[i]<0) {
            memset(fy,-1,sizeof(fy));
            ret+=path(i);
        } // end of if(matx[i]...
    return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************

KMP

Posted on by snoopy

直接抄的武大李春葆老师的数据结构上的改进KMP

// return the first matching string2 in the string1
#include <stdio.h>
#include <string.h>
#define MaxSize 1000

typedef struct
{
    char ch[MaxSize];
    int len;
} SqString;

void GetNextval(SqString t,int nextval[])
{
    int j=0,k=-1;
    nextval[0]=-1;
    while(j<t.len)
    {
        if((k==-1)||(t.ch[j]==t.ch[k]))
        {
            j++;
            k++;
            if(t.ch[j]!=t.ch[k]) nextval[j]=k;
            else nextval[j]=nextval[k];
        }
        else k=nextval[k];
    }
}

int KMP(SqString s,SqString t)
{
    int nextval[MaxSize],i=0,j=0,v;
    GetNextval(t,nextval);
    while((i<s.len)&&(j<t.len))
    {
        if((j==-1)||(s.ch[i]==t.ch[j]))
        {
            i++;
            j++;
        }
        else j=nextval[j];
    }
    if(j>=t.len) v=i-t.len;
    else v=-1;
    return(v);
}

int main()
{
//    freopen("kmp.in","r",stdin);
//    freopen("kmp.out","w",stdout);

    SqString str1,str2;
    gets(str1.ch);
    str1.len=strlen(str1.ch);
    gets(str2.ch);
    str2.len=strlen(str2.ch);
    printf("%dn",KMP(str1,str2));
    return(0);
}

RMQ

Posted on by snoopy

从whummd的blog上copy来的,加了点自己的修改,正在看,集训加油

// StandCode for RMQ, return the smallest number in array s[i..j]
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 1000000
int f2[30];
int s[MAXN];
int r[MAXN][22];

void make_f2(int n)
{
    int i;
    for(i=0;i<=n;i++)
        f2[i]=1<<i;
    return;
}

void make_RMQ(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        r[i][0]=s[i];
    for(j=1;j<=log(n)/log(2);j++)
        for(i=1;i<=n;i++)
            r[i][j]=min(r[i][j-1],r[i+f2[j-1]][j-1]);
    return;
}

int RMQ(int i,int j)
{
    int k=int(log(j-i+1)/log(2));
    return(min(r[i][k],r[j-f2[k]+1][k]));
}

int main()
{
    freopen("rmp.in","r",stdin);
    freopen("rmp.out","w",stdout);

    int n,i,start,end;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    make_f2(20);
    make_RMQ(n);
    while(scanf("%d%d",&start,&end)!=EOF)
        printf("%dn",RMQ(start,end));
    return 0;
}

关于Baidu的一些思考 – 不要争执那些没意义的东西

Posted on by snoopy

昨天看的Baidu的一本更多意义是宣传的书,虽然有广告的肉麻嫌疑,不过还是有很多值得慢慢讨论一下的.说一些书里的内容,说一些自己的体会.

1st,不要争论那些与己无关的东西,除非你是在大专辩论赛上.
这是一个很重要的命题,以前的自己,总是花了太多时间在跟别人争吵,或者自己一厢情愿的认为那是一种辩论,是一种人生观价值观的体现,其实是一种很无聊的东西,有什么意义呢?毫无意义,只是在没有价值的浪费自己的时间.以前的自己,总喜欢对很多东西发表评论,自以为是,以为看明白了世间的种种,其实也不过是井底之蛙,并且,智者的重要表现之一,就是学会保持沉默.往往,沉默是金,因为过分的争执和自大,会失去很多朋友,同时,过度的自我膨胀会遮挡自己的眼睛,从而不能看清楚很多东西.往往,真正的智者都是一语中的,没有丝毫的拖泥带水.

2nd,在没看明白自己面对的问题前,不要轻易评论,哪怕是在心里.
这个是我自己加入的,以前的自己就经常是这样,别人话说到一半,或者一个事情的背景完全不明白的情况下,就在大放厥词,往往,在贬低了自己的同时也让其他人看轻了自己.现在起要好好的观察,学习,这就够了,关于谁是谁非,那是后来的无聊人做的事情.

3rd,少说多做,努力,努力.
俞军每周工作100个小时,以至现在的搜索引擎泰斗,不知道书里对这个有没有夸大其词,不过,至少那个态度还是在那里的,回头看看自己,每周真正投入在学习中的有多少?更多的时间自己都用来干吗了?今天看了很多题,结果都是自己不会的算法,虽然一个敏感度能告诉自己应该如何去做,但是无法实现,什么都不算,一个白日梦而已.

4th,我总是在进行所谓的思考,继续思考,直到发现思考的问题过时转而去思考下一个问题.
这很不好,那么多的时间为什么都要浪费在空想上,给自己一个目标,继而为之努力.从现在来说,重要的内容是考研和工作,今天想到的是能不能两者兼而有之.对自己的能力有充分的信心,虽然因为那个事情对自己的打击非常的大,但是自己还是非常的自信,这不是盲目的自大,而是自信,虽然现在的自己好像颓废的完全不成样子,只要振作起来,我还会是最好的.对过去的两年或者更久,浪费的时间已经无法挽回,自己需要的,只是从现在开始努力,做最好的自己,燃烧力量,给所有人证明自己的价值,最需要看到的,是自己.

以后要注意克制自己不要总把时间花在这种事情上,一段时间能安心下来想明白一件事情就好,不必要太过于探究.好好努力,好好加油,好好生活.

奇怪的生活方式

Posted on by snoopy

最近的睡眠时间越来越奇怪了,昨天晚上是从7点半睡到9点40北吵醒,然后实在吵的不行就索性爬了起来,然后准备1点睡的看一个好玩的东西看到3点.今天早上6点醒了一次,看表,太早,接着睡到萌萌7点20敲门.起来,过来机房干活.

生活还是挺有规律的,争取晚上能好好睡足至少7个小时,吃饭后休息一会先睡觉,然后起来玩到半夜继续睡到早上.