发信人: 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<=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 *********************************
最大匹配(匈牙利算法)
// ** 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 *********************************
最近要做的事情(08/05)
给自己一些没做完或者要打算做的事情做个记录吧
继续看CLRS上的Graph Algorithms, 8.7开始做题调整状态
几个匹配的题,可以测一下自己对标程的应用
最大匹配: 1274, 1422, 1469, 1719, 2060, 2239, 2495, 2536
最优匹配: 2195
KMP
直接抄的武大李春葆老师的数据结构上的改进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
从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的一些思考 – 不要争执那些没意义的东西
昨天看的Baidu的一本更多意义是宣传的书,虽然有广告的肉麻嫌疑,不过还是有很多值得慢慢讨论一下的.说一些书里的内容,说一些自己的体会.
1st,不要争论那些与己无关的东西,除非你是在大专辩论赛上.
这是一个很重要的命题,以前的自己,总是花了太多时间在跟别人争吵,或者自己一厢情愿的认为那是一种辩论,是一种人生观价值观的体现,其实是一种很无聊的东西,有什么意义呢?毫无意义,只是在没有价值的浪费自己的时间.以前的自己,总喜欢对很多东西发表评论,自以为是,以为看明白了世间的种种,其实也不过是井底之蛙,并且,智者的重要表现之一,就是学会保持沉默.往往,沉默是金,因为过分的争执和自大,会失去很多朋友,同时,过度的自我膨胀会遮挡自己的眼睛,从而不能看清楚很多东西.往往,真正的智者都是一语中的,没有丝毫的拖泥带水.
2nd,在没看明白自己面对的问题前,不要轻易评论,哪怕是在心里.
这个是我自己加入的,以前的自己就经常是这样,别人话说到一半,或者一个事情的背景完全不明白的情况下,就在大放厥词,往往,在贬低了自己的同时也让其他人看轻了自己.现在起要好好的观察,学习,这就够了,关于谁是谁非,那是后来的无聊人做的事情.
3rd,少说多做,努力,努力.
俞军每周工作100个小时,以至现在的搜索引擎泰斗,不知道书里对这个有没有夸大其词,不过,至少那个态度还是在那里的,回头看看自己,每周真正投入在学习中的有多少?更多的时间自己都用来干吗了?今天看了很多题,结果都是自己不会的算法,虽然一个敏感度能告诉自己应该如何去做,但是无法实现,什么都不算,一个白日梦而已.
4th,我总是在进行所谓的思考,继续思考,直到发现思考的问题过时转而去思考下一个问题.
这很不好,那么多的时间为什么都要浪费在空想上,给自己一个目标,继而为之努力.从现在来说,重要的内容是考研和工作,今天想到的是能不能两者兼而有之.对自己的能力有充分的信心,虽然因为那个事情对自己的打击非常的大,但是自己还是非常的自信,这不是盲目的自大,而是自信,虽然现在的自己好像颓废的完全不成样子,只要振作起来,我还会是最好的.对过去的两年或者更久,浪费的时间已经无法挽回,自己需要的,只是从现在开始努力,做最好的自己,燃烧力量,给所有人证明自己的价值,最需要看到的,是自己.
以后要注意克制自己不要总把时间花在这种事情上,一段时间能安心下来想明白一件事情就好,不必要太过于探究.好好努力,好好加油,好好生活.
奇怪的生活方式
最近的睡眠时间越来越奇怪了,昨天晚上是从7点半睡到9点40北吵醒,然后实在吵的不行就索性爬了起来,然后准备1点睡的看一个好玩的东西看到3点.今天早上6点醒了一次,看表,太早,接着睡到萌萌7点20敲门.起来,过来机房干活.
生活还是挺有规律的,争取晚上能好好睡足至少7个小时,吃饭后休息一会先睡觉,然后起来玩到半夜继续睡到早上.
7月7日,晴
武汉在下雨
北京时间7月2日凌晨1:47,我的世界杯结束了
标 题: 北京时间7月2日凌晨1:47,我的世界杯结束了
发信站: 珞珈山水BBS站 (Sun Jul 2 14:21:02 2006), 转信
终于还是在这里轰然倒下,但是,走的没有一点遗憾,不是我不希望前进,是点球大战中,我不断祈祷的心只是在往下沉.
喜欢一个队,没有理由,同样,支持也是没理由的.看球,却总是快乐的时候少,难过的时候多,也许,我们认为快乐是应该的,必然的,所以我们没理由那么牢记.而失落,是会一直压在心头的痛.
02年,开始爱上England,理由是很奇怪的我玩FIFA WorldCup2002用最顺手的就是England,在班里所向披靡,最后导致联网玩这个游戏都被强制不准选England.
那一年世界杯我高一,小组赛一直到半决赛的时间我们都是在学校里偷偷跑外面去看,或者是在课桌里放上收音机听.期末前不久的周末补课,请假回家,一个多小时的车程后回家一打开电视机,是巴西的R10在上半场结束前得R11突破后的传球得分,1:1.那一场比赛,Owen很早进球,典型的Owen式进球,速度与灵活,加上对那些一瞬即逝的机会的把握,那个少年,依然如故.
下半场R11的任意球破门时,在惊艳于如此漂亮的弧线的时候,我觉得,我的2002世界杯就快要结束了,在结束后看见希曼的眼泪的时候,我只能无语,然后换台,等吃晚饭.
最后我看了3,4名决赛和决赛,因为我们放假了,德国的Ballack缺席决赛,让我觉得那场比赛的精彩程度大打折扣,R9的两个进球,也是感觉一般.
04年欧洲杯,对无视高考的人来说,是很开心的时刻,对法国的那场球,怕吵醒爸妈而设置的不那么响的闹钟没把我弄醒,醒来时已经快结束了,打开电视机的时候齐达内在进那场比赛法国队的第一个球,还没摆脱无奈,却看见了2:1的结果,很不能接受的看完了赛后的精彩瞬间,然后睡觉.第二天起来看重播,知道结果后是如此的无奈,看着Beckham把点球打飞,只能说,无奈.
对葡萄牙的那场比赛凌晨2:15开始.记得很清楚,因为我按时起来了,看完了全场.Owen那个追风少年还是一如既往的Owen式进球,但是还是很可惜被扳平,然后拖入加时.全场体力透支的22个人毫无章法的在银球制规则下居然在加时打成了2:2,点球决战.
Beckham罚丢了England的第一个球,也是他那次欧洲杯的第二个点球.5轮过后是4:4平,加一轮,继续平.Vassell的点球被光手的Ricardo扑出,然后Ricardo亲自打进最后一球后,看着外面泛白的天,欲哭无泪,抱着一个快被磨破的球就跑家旁边的小学操场上去对墙抽到脚再次知道痛.
今年的世界杯,我们在期末考,但是依然会看球到至少1点,1/4决赛的第一天,就是一场点球大战,德国式的男人Ballack带领德国继续前进,让我还在憧憬自己喜欢的3个球队能一起进入四强.等England的复仇,赛前的八卦新闻什么都有,我希望的是英格兰能90分钟内干净利落结束比赛,不要在拖到点球了.
比赛开始后也没觉得什么了,都在闷战,都有机会,有射门,有扑救,有门柱,有飞机,拼抢上,也都很激烈.但是,Beckham的受伤意外离场,Rooney的暴力行径被红牌罚下,让我只能祈祷,偷袭得手或者拖入点球以曾经失败的方式结束失败.这一次双方在加时赛的体力还能保持没出现大的动作变形,除了那个越位在先的球,一切都波澜不惊.
点球开始前同学就在说有不好的预感,England的Owen,Beckham,Rooney都不在,能罚点球的,悬.当看到第一个是Lampard的时候,同学说预感要坏事,结果就被这个乌鸦嘴给说中了,我的心如同电视画面上的Gerrard一样的难过,他都要哭出来了.葡萄牙连续两个自己打出去加上Hargreaves的进球,让阴暗的天重新露出了阳光.但是,Gerrard这个我一直坚持是个阳光男孩在点球点上罚出的球再次被扑出,让我只能掩面祈祷.第四轮,葡萄牙进球,Carragher居然还罚球违例的弄进去了,重罚,心理上的压力让那个球很舒服的被Ricardo给拿到,在心里,我已经快要接受England要回家的事实,但是,还是在期待奇迹的出现.
C.Ronaldo在点球点前把那个球放了很久,然后在鸣哨后结束了我的2006世界杯,这一次,段喧也没有发飙.
坐在隔壁的电脑前蒙了一会,然后放下掩面的手,接受这个事实,于是回宿舍一口气喝完了一瓶1L的矿泉水,当时的感觉,心碎.然后站在在淋浴下,看从头浇到脚的水流过眼前,希望自己看不见自己的眼泪,宁愿相信是被虫子迷了眼睛.
想起一句很经典的话,曾经是给相爱的人的,曾经也有很多阿根廷球迷在引用,现在,在02WC和04Euro后再次拿出来写给自己:
爱是等待
爱是忍耐
爱是接受她的一切错误并笑对命运的安排
希望能快点看到不再等待的那一天…
—
※ 来源:·珞珈山水BBS站 bbs.whu.edu.cn·[FROM: 222.20.237.*]