Year: 2006

Tired…

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…

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

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

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

A Highlight Plugins for Microsoft Writer

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

个人赛,后两天

编号.题目                    来源        简单说明
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原创,部分为
只改描叙的陈题

个人赛,前两天

发信人: 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算法)

// ** 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 *********************************

最大匹配(匈牙利算法)

// ** 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 *********************************