oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

alpc12 @ Refugee @ Harbin

Posted on 2008-10-16 04:07 oyjpart 阅读(4082) 评论(4)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
alpc12 @ Refugee @ Harbin
废话少说,直入正题。
比赛开始,52 ABC,我DEF,剩下62.
不一会有人过J。看了看,没做过。52说A水,让52跟我说了题意,确认后就让52上去敲了。
测了几个数据没问题后Submit,但是Judge没给判,其实是Judge Down了。
根据场上形势,下来之后和52讨论J。我们只是想了一些确定无解的条件,然后觉得可以尝试一下,毕竟场上
过了那么多人,所以就试着提交了。这个时候1个小时不到。
之后Judge还是Down着。这时候62跟我说了一个优先队列广搜的题目,和62确认了没有问题,
决定让62上去敲。但是比赛结束后证明交这个题的绝大部分队伍都tle(很出乎意料),
只是当时judge down没法跟题,所以上去敲,决策上并没有错误。
接着Judge 恢复了,我们交的2个题都AC了,当时我记得排名是第5,还挺靠前的额。
62的H题 TLE 了。我看了board,没有人过H,心里想不能在这道题上耗时了。
之后52发现F题是简单题,Board上也显示出来了。和52确认之后,52上去把这个题干掉了。返回Yes。

根据场上形势,是一道最短路+最小权匹配的题目给我。我用费用流敲的。过了样例之后测了几个数据没什么问题


就交了 YES.这个时侯好像是12:20.还有1个小时40分钟,排名靠前。很有希望。
好像是之后62上去优化自己的H题(或者是之前,记不清了),结果还是TLE。

根据场上形势,G题和B题过题人数差不多。B题留给62,我和52搞G。52想出来一种Topo排序的做法,我觉得有点
麻烦,当时不知道怎么就觉得逆向的记忆化搜索很好写,觉得没有问题就上去写了。写完出不了样例弄了挺久
才发现这样做还是需要顺推来确定无效状态。当时加了一个顺推去掉无用状态还是不行,头脑有点糊涂了。
当时必须做决策了。时间是13:17分。我觉得自己的方法可能有问题,一时之间又没想出是哪里出的问题,既然如此,就当机立断
让52来敲这个题,因为我觉得52思路清晰,肯定能出这个题。下来之后和62稍微讨论了下B题,但是
我对B题这种类型都不感冒,也没帮上什么忙。62说要用Euler函数水一下,我觉得等F题过了可以试试。
52的这道题敲的和我一样,问题迭出。在不断的查找问题,修改程序中,时间慢慢过去,比赛快要接近尾声了。
中间62去水了一下B,结果敲着发现水法是错的,只得作罢。比赛接受了,G题就这样夭折了。

赛后分析。本场比赛的失误集中在G题上。我是罪魁祸首。
其实我的程序在加上顺推去掉无用状态的时候应该把拆的点来做广搜。而不是原图的点。这里改了就能过了。
而52的程序则不知道哪里错了。我没有想清楚就上去敲,而出了问题之后大脑糊涂,想不出来哪里错了。
其实也许当时调试一下就能发现错误。不过觉得在赛场上调试很浪费时间,不敢调。人生如戏,当时觉得
52来敲这个题肯定能过,其实也确实不一定的。这个地方要好好反思。以后比赛不会再重敲了。
比赛的时候一定要保持清醒,大脑糊涂了也就完蛋了。

4题,罚时较少,Rank24.
发挥不好,因为G题该出。

总是有很多如果。如果G题能一敲就过,我们就会有时间,比如我用JAVA高精度+分数模板来做D题。。
也许,也许我们就能取得好成绩了。。。
可是没有如果啊。唉。
4队差2名就是银牌了,很是可惜。祝福他们下场比赛胜利。

祝福alpc的所有队伍在以后的Regional发挥出色。这里我无限祈祷中。!

题目简略描述 by wywcgs:(我偷下懒啊)

A : 一个球体组成的金字塔,每层都是三角形。第一层1个,第二层1+2个,第三层1+2+3个,第n层1+2+3+....+n个。从第一层开始往下按顺序给每个小球编号,每层的三角形也是从上到下遍。现在给定一个编号,求它的位置,也就是层数、层内的列数和列内的第几个。

B : 一个数有K个约数(算自己)就叫K维数。求第n大的K维数。n <= 10000, K <= 100且K为质数或完全平方数。

C : 100个点的带权无向图,每个点连着一个港口。有n艘船,船数和图顶点数相等。每艘船有一个初始位置,是图中的一个顶点。每个港口只能停一艘船,问怎么调度能让所有船都停到港口里,总路程的和最小。

D : AX = b的线性方程组求解,A是n*n的方阵,维数最多到100。要精确解,用分数输出。

E : 算法不太难,但是5个小时内几乎不可做。

一个迷宫,最多3层。每层的最外围都用障碍包围住了。
迷宫内有出发点,目的地,障碍,上楼的楼梯,下楼的楼梯,怪兽,门,钥匙。其中出发点,目的地只有一个,上下楼梯每层最多一个。每道门必须用一个钥匙大开,每个钥匙只能用一次,门只需要打开一次就永久开放。门最多30个,怪兽最多26个。
定义障碍和门围成的一圈的内部空地叫一个房间。房间内可能会有怪兽,所以冒险者在进入房间之后要和怪兽搏斗。上下楼梯、开始点和目的地所在的房间里没有怪兽。
每个房间最多3个怪兽,每个怪兽都有他们的hp和攻击力,攻击力就是一次攻击减的hp数。冒险者有100点hp和100发子弹,冒险者的攻击要耗费子弹。冒险者者有10种攻击模式,每一种耗费的子弹和造成的伤害均不同,在输入中给出如果有多个怪兽,冒险者必须分别消灭。冒险者先攻击,然后每个怪兽(还活着的话)分别攻击,然后循环。。每场战斗结束之后,冒险者的hp和子弹数都会重新填满。消灭怪兽之后就能任意拿房间里的东西。
问最后冒险者能否到达目的地,输出是否即可。



F : 给定一个数i,对i, i+1, i+2求和。要求求和过程中任何一位都不能产生进位,十进制数。给定一个数n < 10^10,问小于等于n的数中有多少满足条件。

G : 一个有向无环图,10000个点,每个点都有一个权。满足只有一个点在拓扑序最顶端。这个点是起点。有一艘船从这个点出发,有两个玩家分别操纵,第一个玩家走第一步,第二个玩家走第二步,第三个玩家再走第三步,类推。必须顺着有向边走。直到不能走为止,最后的得分是路径上所有点权的和。如果该权>=某常数F则玩家1赢,否则2赢。问1是否能必胜。

H : 一片海域,最大20*20。里面有障碍,漩涡,出发地和目的地。有一艘船要到达目标,它能做两个操作,普通走和加速走。普通走一次走一格,加速走一次走d <= 5格。加速走必须要路径上的d格不能有障碍,否则不允许加速。漩涡必须加速走才能穿过,普通走不能穿过。加速有次数限制,在输入数据中给出。穿越一个漩涡减少1点HP。要满足在减少HP最少的前提下用最短的步数到达目标,问这个最短的步数。

I : 一个简单无向图(无自环无平行边),最多1000个点。给1000个数,是这1000个点的度。文是否有一个图和满足给定的度条件。

J : 题目具体没搞懂,也记不请了,当是也没细想。直觉像计算几何 + 动态规划一类的东西。

写的比较简略,有时间再补一补。很晚了。

Ranklist
1 清华大学 What's up? 7 金 
2 清华大学 IronGods 7 金
3 复旦大学 HugeHydralisk 7 金
4 天津大学 TJU_HanoiTower 6 金
5 浙江大学 Sirius 6 金
6 武汉大学 ChaeYeon 6 金
7 浙江大学 Genesis 6 金
8 中山大学 ZSU_Remiel 6 金
9 北京交通大学 BJTU_ImBa 6 金
10 复旦大学 Butcher 6 金
11 复旦大学 HeavenHell 6 金
12 华中科技大学 hustruggle 5 银
13 武汉大学 Slash 5 银
14 清华大学 Traveller 5 银
15 同济大学 FamilyAllHandsRush 5 银
16 吉林大学 supernova 5 银
17 中山大学 ZSU_Rapheal 5 银
18 北京大学 montage 5 银
19 大连理工大学软件学院 VIPers 5 银
20 北京大学 AcmTeam08 5 银
21 北京大学 CrazyAC 5 银
22 华中科技大学 salute 5 银
23 中山大学 ZSU_Gabriel 4 银
24 国防科技大学 Refugee 4 银
25 福州大学 ACFighters 4 银
26 哈尔滨工程大学 HRB-team0 4 银
27 北京理工大学 Bit-bear 4 银
28 北京交通大学 BJTU_Action 4 银
29 北京邮电大学 Sapphire 4 银
30 北京航空航天大学 DDR3 4 银
31 哈尔滨工业大学 Aaron 4 银
32 福州大学 Sakyamuni 4 银
33 浙江大学 gdb 4 银
34 北京邮电大学 EagleHustle 4 银
35 西安电子科技大学 CET-6 4 铜
36 国防科技大学 Nirvana 4 铜
37 东北林业大学 tiger 4 铜
38 西安交通大学 xjtuzlz 4 铜
39 北京化工大学 Bucteam_NoRP 4 铜
40 浙江理工大学 skyrocket 4 铜
41 杭州电子科技大学 HDU_microant 4 铜
42 中国地质大学 newHope 4 铜
43 厦门大学 XMU_HCP 4 铜
44 宁波大学 JustDoIt 3 铜
45 电子科技大学 Knight 3 铜
46 湖南大学 sword 3 铜
47 北京师范大学 GREEDY 3 铜
48 山东大学 Kakport 3 铜
49 大连理工大学创新学院 Newbie 3 铜
50 北京师范大学珠海分校 BNUEP_int_ijk 3 铜
51 浙江大学城市学院 SuperZucc 3 铜
52 浙江工业大学 Cheers 3 铜
53 南开大学 Falco 3 铜
54 哈尔滨工业大学 Martians 3 铜
55 五邑大学 WYU_Fantasy 3 铜
56 东北大学 zephyr 3 铜
57 新加坡 KZ-NTU 3 铜
58 广州大学 GoodGoodStudy 3 铜
59 中国人民大学 Kingbase 3 铜
60 吉林大学 supergiant 3 铜
61 上海师范大学 Tinman1 3 铜
62 东北师范大学软件学院 NENUSoftware_Golde 3 铜
63 日本会津大学 WATCH.C 3 铜
64 电子科技大学 Bishop 3 铜
65 华东师范大学 Kop 3 铜
66 杭州电子科技大学 HDU_Fantasy 3 铜
67 浙江师范大学 KartRider 3 铜
68 天津大学 TJU_Buddha 3 铜
69 北华大学 Beihua_Sailing 3 铜


Feedback

# re: alpc12 @ Refugee @ Harbin   回复  更多评论   

2008-10-18 11:06 by You Bo
感觉G更像是树型博弈的变形

# re: alpc12 @ Refugee @ Harbin   回复  更多评论   

2008-10-20 08:32 by oyjpart
补充2点:
1.事后说发现B题看漏了一个条件,如果看到了就可以做出来,并不难
2.没想到52的G题算法居然是错的,怪不得也没敲过。我们俩真实无敌了,一人说了一遍自己的算法,都没觉得对方是错的.... -_-|||

# re: alpc12 @ Refugee @ Harbin   回复  更多评论   

2008-11-09 03:44 by czcomt@126.com
4题就可以拿个银奖,我们广州大学也要加油!合肥一定要拿银奖!harbin H题当时是我搞的,没TLE过,但是狂wa,你们会不会是题意没弄清楚?

# re: alpc12 @ Refugee @ Harbin   回复  更多评论   

2008-11-09 10:21 by oyjpart
在场提交的队伍中大部分都是TLE

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理