【AC_LCC_CWJ 第二场】World Final 2006

这场最后太疼了,都是我个人的原因,第一题有些情况没考虑到,于是最后A题这个大水题很遗憾地没过。

一开始师父有事就跑了,大概1个多小时以后又回来了。

这短时间LCC沉浸在G中,我沉浸在J中,貌似都不可自拔

然后后来我觉得J太大自然了,于是又看了一个Board,UESTC的队过了I,然后赶去围观,果断发现是水题,于是切掉。

接下来LCC大神在G题题意极度不清晰的情况下暴力试出了Accepted,Orz。

然后后来又看到了UESTC那队把B过了,我一看,迅速反应出这和昨天那题最大流的构图是一样,只要求个费用流就可以了。

但是第一遍提交的时候出现的很神奇的事情,我交上去Waiting,然后等了N久之后,UESTC也交了一个Waiting,在之后,LCC也交了一个Waiting,我顿时惊叹,题库爆了!然后再过了几秒之后,3个TLE出现,顿时觉得有点假。。。

然后手测了一些数据,发现由于精度问题,费用流跑了正向边以后又去跑反向边去了,然后+个eps以后就Y了。

此期间LCC用小号对E题不断进行轰炸,后来发现是输出的时候格式出了问题...

师父一跑来就说,D是数论,我来切,然后就切掉了~Orz!!!!

接着我看了A题,觉得比较简单,于是开切,然后由于一种情况没有考虑到,应该说题意上有一点误解。

就是这一句

the travel covered by a ticket be completed in order and without intervening travel

然后在我脑海里形成映像,后面的路程也是要完全吻合的,于是悲剧。。。

最后就5题了(B D E G I),师父表示当年WF2006最多的一队也就是6题。我顿时捶胸顿足……就差了我的A题啊

都是我的错……

下面简单说说我做的两题(都超级水):

B题就是要填一个m*n的矩阵c,分别给出每一行和每一列的和,然后每个格子还有一个实数权w,最后输出最小和最大的

Sum{c[i][j]*w[i][j]},有一些实权位-1的表示不可填。然后就是最小费用最大流+最大费用最大流了。

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22056

代码:http://xiudaima.appspot.com/code/detail/4554012

I题就一个Floyd

然后现在把A题补一下。

【题目链接】http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22055

就是给定20张机票,每张机票有一条旅行路线和一个价格,每次可以用一张机票路线的前缀,然后给定20个询问,每个询问都是一条路线,问你通过这些机票,最少花多少钱可以完成这条路线。完成这条路线时必须按顺序经过路线上的点,但是在路线的各点中间,你可以先跑去其它地方再飞回来。

【解法】

F[i,j,k]表示已经完成这个路线的前i个点,现在在第j张飞机票的第k个点时,最少的费用是多少。

由于有后效性,用SPFA来转移之。

然后就解决了

【Hint】题目给出的各城市的编号是任意的。。。如果处理的不好要先离散化。一般直接判等于就行。

【CODE】

http://xiudaima.appspot.com/code/detail/4490007

最后Orz LCC、Orz AC,鄙视我自己

加入对话

4条评论

  1. 回复小星娴:= =,我一开始是想选个等宽字体,后来发现大写I太像1了,就换了个不太像的。最后又觉得太细了。就加粗了。

留下评论

您的电子邮箱地址不会被公开。