Year: 2006

Tired…

Posted on by snoopy

There is a bit tired for all members in the lab, all of us have a sleep this noon, but for most of us it’s useless, and someone was watching TV or play games. Anyhow, I don’t want to solve any problem anymore, and I hope to have a few days to relax myself.

Something was wrong…

Posted on by snoopy

We did a bad job on the recently warm up contests, and on the OnlineJudge, a CTU2002Open problem is puzzling me, I tried many ways to solve it, but all of them got a wrong answer… :(

This afternoon, when we falling a bad status on the contest, I used a paper to cut my finger bleeding… what a fool…

The Cranberries – Never Grow Old

Posted on by snoopy

很好听的一首歌, 一开始是在一个用WOW第一人称视角拍摄的一个小电影里面听到, 后来一直在疯狂的找, 可惜都被误导了. 后来在电台里听过, 在路过宿舍楼下的时候听过, 就是不知道名字, 凭自己的猜测歌词也不对. 昨天随手乱放自己电脑里面的歌原来本来就有, 看了看来源, 是CCTV5天下足球里面给巴乔离开时候专题片的音乐, 中文译成了<愿你青春永驻>, 有很多地方中文的歌词还是挺不错的.

下载是在http://mp3.baidu.com上找到的, 有asf和mp3的, 其中asf好像都是天下足球里面的mv, 赞

A Highlight Plugins for Microsoft Writer

Posted on by snoopy

A plugins for Microsoft writer, it can makes your code with colors, a useful plugins for  loggers who always pasted codes on their blog.

Visite this site for information and download: Highlight4Writer

This is a sample used Highlight4Writer :)

#include <stdio.h>
#define MAX 1000

const int sub[10];

int main()
{
  int a,b;
  while(scanf("%d%d",&a,&b)!=EOF)
    printf("%dn",a+b);
  return(0);
}

个人赛,后两天

Posted on by snoopy 
编号.题目                    来源        简单说明
D3A.Bishops                 not found   简单公式题
D3B.Football Coach          not found   最大流
D3C.CLRS                    not found   DFS或者强联通分量
D3D.Sequence Again          POJ2478     筛素数法求欧拉函数
D3E.Intervals               not found   线段树
D3F.Matrix                  not found   矩阵构造+矩阵乘法

D4A.area                    not found   DP+凸包
D4B.Prime                   not found   求素数距离,筛法求素数到3*10^7
D4C.Traveling Queen Problem POJ2919     BFS+集合DP,BT题,我看标程都头大
D4D.Squares                 not found   BFS+Hash打表或双向BFS
D4E.Candies                 not found   贪心带硬搞
D4F.Card Game               POJ2062     最大匹配或者贪心

p.s.来源标注为not found均为目前还未找到来源的题,其中部分为KO原创,部分为
只改描叙的陈题

个人赛,前两天

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&lt;=ny;v++)
        if((lx[u]+ly[v]==w[u][v])&amp;&amp;(fy[v]&lt;0)) {
            fy[v]=1;
            if((maty[v]&lt;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&lt;=nx;i++) {
        lx[i]=-INF;
        for(j=1;j&lt;=ny;j++)
            if(w[i][j]&gt;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&lt;=nx;i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k=1;k&lt;=nx;k++)
                if(fx[k]&gt;0)
                    for(j=1;j&lt;=ny;j++)
                        if((fy[j]&lt;0)&amp;&amp;(lx[k]+ly[j]-w[k][j]&lt;p))
                            p=lx[k]+ly[j]-w[k][j];
            for(j=1;j&lt;=ny;j++) ly[j]+=(fy[j]&lt;0?0:p);
            for(k=1;k&lt;=nx;k++) lx[k]-=(fx[k]&lt;0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i=1;i&lt;=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&lt;=ny;v++)
        if((mat[u][v])&amp;&amp;(fy[v]&lt;0)) {
            fy[v]=1;
            if((maty[v]&lt;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&lt;=nx;i++)
        if(matx[i]&lt;0) {
            memset(fy,-1,sizeof(fy));
            ret+=path(i);
        } // end of if(matx[i]...
    return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************