alpc12 @ Refugee @ Harbin
廢話少說(shuō)，直入正題。
比賽開始，52 ABC，我DEF，剩下62.
不一會(huì)有人過(guò)J。看了看，沒(méi)做過(guò)。52說(shuō)A水，讓52跟我說(shuō)了題意，確認(rèn)后就讓52上去敲了。
測(cè)了幾個(gè)數(shù)據(jù)沒(méi)問(wèn)題后Submit，但是Judge沒(méi)給判，其實(shí)是Judge Down了。
根據(jù)場(chǎng)上形勢(shì)，下來(lái)之后和52討論J。我們只是想了一些確定無(wú)解的條件，然后覺(jué)得可以嘗試一下，畢竟場(chǎng)上
過(guò)了那么多人，所以就試著提交了。這個(gè)時(shí)候1個(gè)小時(shí)不到。
之后Judge還是Down著。這時(shí)候62跟我說(shuō)了一個(gè)優(yōu)先隊(duì)列廣搜的題目，和62確認(rèn)了沒(méi)有問(wèn)題，
決定讓62上去敲。但是比賽結(jié)束后證明交這個(gè)題的絕大部分隊(duì)伍都tle（很出乎意料），
只是當(dāng)時(shí)judge down沒(méi)法跟題，所以上去敲，決策上并沒(méi)有錯(cuò)誤。
接著Judge 恢復(fù)了，我們交的2個(gè)題都AC了，當(dāng)時(shí)我記得排名是第5，還挺靠前的額。
62的H題 TLE 了。我看了board，沒(méi)有人過(guò)H，心里想不能在這道題上耗時(shí)了。
之后52發(fā)現(xiàn)F題是簡(jiǎn)單題，Board上也顯示出來(lái)了。和52確認(rèn)之后，52上去把這個(gè)題干掉了。返回Yes。
根據(jù)場(chǎng)上形勢(shì)，是一道最短路+最小權(quán)匹配的題目給我。我用費(fèi)用流敲的。過(guò)了樣例之后測(cè)了幾個(gè)數(shù)據(jù)沒(méi)什么問(wèn)題
就交了 YES.這個(gè)時(shí)侯好像是12：20.還有1個(gè)小時(shí)40分鐘，排名靠前。很有希望。
好像是之后62上去優(yōu)化自己的H題（或者是之前，記不清了），結(jié)果還是TLE。
根據(jù)場(chǎng)上形勢(shì)，G題和B題過(guò)題人數(shù)差不多。B題留給62，我和52搞G。52想出來(lái)一種Topo排序的做法，我覺(jué)得有點(diǎn)
麻煩，當(dāng)時(shí)不知道怎么就覺(jué)得逆向的記憶化搜索很好寫，覺(jué)得沒(méi)有問(wèn)題就上去寫了。寫完出不了樣例弄了挺久
才發(fā)現(xiàn)這樣做還是需要順推來(lái)確定無(wú)效狀態(tài)。當(dāng)時(shí)加了一個(gè)順推去掉無(wú)用狀態(tài)還是不行，頭腦有點(diǎn)糊涂了。
當(dāng)時(shí)必須做決策了。時(shí)間是13：17分。我覺(jué)得自己的方法可能有問(wèn)題，一時(shí)之間又沒(méi)想出是哪里出的問(wèn)題，既然如此，就當(dāng)機(jī)立斷
讓52來(lái)敲這個(gè)題，因?yàn)槲矣X(jué)得52思路清晰，肯定能出這個(gè)題。下來(lái)之后和62稍微討論了下B題，但是
我對(duì)B題這種類型都不感冒，也沒(méi)幫上什么忙。62說(shuō)要用Euler函數(shù)水一下，我覺(jué)得等F題過(guò)了可以試試。
52的這道題敲的和我一樣，問(wèn)題迭出。在不斷的查找問(wèn)題，修改程序中，時(shí)間慢慢過(guò)去，比賽快要接近尾聲了。
中間62去水了一下B，結(jié)果敲著發(fā)現(xiàn)水法是錯(cuò)的，只得作罷。比賽接受了，G題就這樣夭折了。
賽后分析。本場(chǎng)比賽的失誤集中在G題上。我是罪魁禍?zhǔn)住?br>其實(shí)我的程序在加上順推去掉無(wú)用狀態(tài)的時(shí)候應(yīng)該把拆的點(diǎn)來(lái)做廣搜。而不是原圖的點(diǎn)。這里改了就能過(guò)了。
而52的程序則不知道哪里錯(cuò)了。我沒(méi)有想清楚就上去敲，而出了問(wèn)題之后大腦糊涂，想不出來(lái)哪里錯(cuò)了。
其實(shí)也許當(dāng)時(shí)調(diào)試一下就能發(fā)現(xiàn)錯(cuò)誤。不過(guò)覺(jué)得在賽場(chǎng)上調(diào)試很浪費(fèi)時(shí)間，不敢調(diào)。人生如戲，當(dāng)時(shí)覺(jué)得
52來(lái)敲這個(gè)題肯定能過(guò)，其實(shí)也確實(shí)不一定的。這個(gè)地方要好好反思。以后比賽不會(huì)再重敲了。
比賽的時(shí)候一定要保持清醒，大腦糊涂了也就完蛋了。
4題，罰時(shí)較少，Rank24.
發(fā)揮不好，因?yàn)镚題該出。
總是有很多如果。如果G題能一敲就過(guò)，我們就會(huì)有時(shí)間，比如我用JAVA高精度+分?jǐn)?shù)模板來(lái)做D題。。
也許，也許我們就能取得好成績(jī)了。。。
可是沒(méi)有如果啊。唉。
4隊(duì)差2名就是銀牌了，很是可惜。祝福他們下場(chǎng)比賽勝利。
祝福alpc的所有隊(duì)伍在以后的Regional發(fā)揮出色。這里我無(wú)限祈禱中。!
題目簡(jiǎn)略描述 by wywcgs：（我偷下懶啊）
A : 一個(gè)球體組成的金字塔，每層都是三角形。第一層1個(gè)，第二層1+2個(gè)，第三層1+2+3個(gè)，第n層1+2+3+....+n個(gè)。從第一層開始往下按順序給每個(gè)小球編號(hào)，每層的三角形也是從上到下遍。現(xiàn)在給定一個(gè)編號(hào)，求它的位置，也就是層數(shù)、層內(nèi)的列數(shù)和列內(nèi)的第幾個(gè)。
B : 一個(gè)數(shù)有K個(gè)約數(shù)（算自己）就叫K維數(shù)。求第n大的K維數(shù)。n <= 10000, K <= 100且K為質(zhì)數(shù)或完全平方數(shù)。
C : 100個(gè)點(diǎn)的帶權(quán)無(wú)向圖，每個(gè)點(diǎn)連著一個(gè)港口。有n艘船，船數(shù)和圖頂點(diǎn)數(shù)相等。每艘船有一個(gè)初始位置，是圖中的一個(gè)頂點(diǎn)。每個(gè)港口只能停一艘船，問(wèn)怎么調(diào)度能讓所有船都停到港口里，總路程的和最小。
D : AX = b的線性方程組求解，A是n*n的方陣，維數(shù)最多到100。要精確解，用分?jǐn)?shù)輸出。
E : 算法不太難，但是5個(gè)小時(shí)內(nèi)幾乎不可做。
一個(gè)迷宮，最多3層。每層的最外圍都用障礙包圍住了。
迷宮內(nèi)有出發(fā)點(diǎn)，目的地，障礙，上樓的樓梯，下樓的樓梯，怪獸，門，鑰匙。其中出發(fā)點(diǎn)，目的地只有一個(gè)，上下樓梯每層最多一個(gè)。每道門必須用一個(gè)鑰匙大開，每個(gè)鑰匙只能用一次，門只需要打開一次就永久開放。門最多30個(gè)，怪獸最多26個(gè)。
定義障礙和門圍成的一圈的內(nèi)部空地叫一個(gè)房間。房間內(nèi)可能會(huì)有怪獸，所以冒險(xiǎn)者在進(jìn)入房間之后要和怪獸搏斗。上下樓梯、開始點(diǎn)和目的地所在的房間里沒(méi)有怪獸。
每個(gè)房間最多3個(gè)怪獸，每個(gè)怪獸都有他們的hp和攻擊力，攻擊力就是一次攻擊減的hp數(shù)。冒險(xiǎn)者有100點(diǎn)hp和100發(fā)子彈，冒險(xiǎn)者的攻擊要耗費(fèi)子彈。冒險(xiǎn)者者有10種攻擊模式，每一種耗費(fèi)的子彈和造成的傷害均不同，在輸入中給出如果有多個(gè)怪獸，冒險(xiǎn)者必須分別消滅。冒險(xiǎn)者先攻擊，然后每個(gè)怪獸（還活著的話）分別攻擊，然后循環(huán)。。每場(chǎng)戰(zhàn)斗結(jié)束之后，冒險(xiǎn)者的hp和子彈數(shù)都會(huì)重新填滿。消滅怪獸之后就能任意拿房間里的東西。
問(wèn)最后冒險(xiǎn)者能否到達(dá)目的地，輸出是否即可。
F : 給定一個(gè)數(shù)i，對(duì)i, i+1, i+2求和。要求求和過(guò)程中任何一位都不能產(chǎn)生進(jìn)位，十進(jìn)制數(shù)。給定一個(gè)數(shù)n < 10^10，問(wèn)小于等于n的數(shù)中有多少滿足條件。
G : 一個(gè)有向無(wú)環(huán)圖，10000個(gè)點(diǎn)，每個(gè)點(diǎn)都有一個(gè)權(quán)。滿足只有一個(gè)點(diǎn)在拓?fù)湫蜃铐敹恕＿@個(gè)點(diǎn)是起點(diǎn)。有一艘船從這個(gè)點(diǎn)出發(fā)，有兩個(gè)玩家分別操縱，第一個(gè)玩家走第一步，第二個(gè)玩家走第二步，第三個(gè)玩家再走第三步，類推。必須順著有向邊走。直到不能走為止，最后的得分是路徑上所有點(diǎn)權(quán)的和。如果該權(quán)>=某常數(shù)F則玩家1贏，否則2贏。問(wèn)1是否能必勝。
H : 一片海域，最大20*20。里面有障礙，漩渦，出發(fā)地和目的地。有一艘船要到達(dá)目標(biāo)，它能做兩個(gè)操作，普通走和加速走。普通走一次走一格，加速走一次走d <= 5格。加速走必須要路徑上的d格不能有障礙，否則不允許加速。漩渦必須加速走才能穿過(guò)，普通走不能穿過(guò)。加速有次數(shù)限制，在輸入數(shù)據(jù)中給出。穿越一個(gè)漩渦減少1點(diǎn)HP。要滿足在減少HP最少的前提下用最短的步數(shù)到達(dá)目標(biāo)，問(wèn)這個(gè)最短的步數(shù)。
I : 一個(gè)簡(jiǎn)單無(wú)向圖（無(wú)自環(huán)無(wú)平行邊），最多1000個(gè)點(diǎn)。給1000個(gè)數(shù)，是這1000個(gè)點(diǎn)的度。文是否有一個(gè)圖和滿足給定的度條件。
J : 題目具體沒(méi)搞懂，也記不請(qǐng)了，當(dāng)是也沒(méi)細(xì)想。直覺(jué)像計(jì)算幾何 + 動(dòng)態(tài)規(guī)劃一類的東西。
寫的比較簡(jiǎn)略，有時(shí)間再補(bǔ)一補(bǔ)。很晚了。
Ranklist
1 清華大學(xué) What's up? 7 金
2 清華大學(xué) IronGods 7 金
3 復(fù)旦大學(xué) HugeHydralisk 7 金
4 天津大學(xué) TJU_HanoiTower 6 金
5 浙江大學(xué) Sirius 6 金
6 武漢大學(xué) ChaeYeon 6 金
7 浙江大學(xué) Genesis 6 金
8 中山大學(xué) ZSU_Remiel 6 金
9 北京交通大學(xué) BJTU_ImBa 6 金
10 復(fù)旦大學(xué) Butcher 6 金
11 復(fù)旦大學(xué) HeavenHell 6 金
12 華中科技大學(xué) hustruggle 5 銀
13 武漢大學(xué) Slash 5 銀
14 清華大學(xué) Traveller 5 銀
15 同濟(jì)大學(xué) FamilyAllHandsRush 5 銀
16 吉林大學(xué) supernova 5 銀
17 中山大學(xué) ZSU_Rapheal 5 銀
18 北京大學(xué) montage 5 銀
19 大連理工大學(xué)軟件學(xué)院 VIPers 5 銀
20 北京大學(xué) AcmTeam08 5 銀
21 北京大學(xué) CrazyAC 5 銀
22 華中科技大學(xué) salute 5 銀
23 中山大學(xué) ZSU_Gabriel 4 銀
24 國(guó)防科技大學(xué) Refugee 4 銀
25 福州大學(xué) ACFighters 4 銀
26 哈爾濱工程大學(xué) HRB-team0 4 銀
27 北京理工大學(xué) Bit-bear 4 銀
28 北京交通大學(xué) BJTU_Action 4 銀
29 北京郵電大學(xué) Sapphire 4 銀
30 北京航空航天大學(xué) DDR3 4 銀
31 哈爾濱工業(yè)大學(xué) Aaron 4 銀
32 福州大學(xué) Sakyamuni 4 銀
33 浙江大學(xué) gdb 4 銀
34 北京郵電大學(xué) EagleHustle 4 銀
35 西安電子科技大學(xué) CET-6 4 銅
36 國(guó)防科技大學(xué) Nirvana 4 銅
37 東北林業(yè)大學(xué) tiger 4 銅
38 西安交通大學(xué) xjtuzlz 4 銅
39 北京化工大學(xué) Bucteam_NoRP 4 銅
40 浙江理工大學(xué) skyrocket 4 銅
41 杭州電子科技大學(xué) HDU_microant 4 銅
42 中國(guó)地質(zhì)大學(xué) newHope 4 銅
43 廈門大學(xué) XMU_HCP 4 銅
44 寧波大學(xué) JustDoIt 3 銅
45 電子科技大學(xué) Knight 3 銅
46 湖南大學(xué) sword 3 銅
47 北京師范大學(xué) GREEDY 3 銅
48 山東大學(xué) Kakport 3 銅
49 大連理工大學(xué)創(chuàng)新學(xué)院 Newbie 3 銅
50 北京師范大學(xué)珠海分校 BNUEP_int_ijk 3 銅
51 浙江大學(xué)城市學(xué)院 SuperZucc 3 銅
52 浙江工業(yè)大學(xué) Cheers 3 銅
53 南開大學(xué) Falco 3 銅
54 哈爾濱工業(yè)大學(xué) Martians 3 銅
55 五邑大學(xué) WYU_Fantasy 3 銅
56 東北大學(xué) zephyr 3 銅
57 新加坡 KZ-NTU 3 銅
58 廣州大學(xué) GoodGoodStudy 3 銅
59 中國(guó)人民大學(xué) Kingbase 3 銅
60 吉林大學(xué) supergiant 3 銅
61 上海師范大學(xué) Tinman1 3 銅
62 東北師范大學(xué)軟件學(xué)院 NENUSoftware_Golde 3 銅
63 日本會(huì)津大學(xué) WATCH.C 3 銅
64 電子科技大學(xué) Bishop 3 銅
65 華東師范大學(xué) Kop 3 銅
66 杭州電子科技大學(xué) HDU_Fantasy 3 銅
67 浙江師范大學(xué) KartRider 3 銅
68 天津大學(xué) TJU_Buddha 3 銅
69 北華大學(xué) Beihua_Sailing 3 銅