alpc12 @ Refugee @ Harbin
廢話少說，直入正題。
比賽開始，52 ABC，我DEF，剩下62.
不一會有人過J。看了看，沒做過。52說A水，讓52跟我說了題意，確認(rèn)后就讓52上去敲了。
測了幾個數(shù)據(jù)沒問題后Submit，但是Judge沒給判，其實(shí)是Judge Down了。
根據(jù)場上形勢，下來之后和52討論J。我們只是想了一些確定無解的條件，然后覺得可以嘗試一下，畢竟場上
過了那么多人，所以就試著提交了。這個時候1個小時不到。
之后Judge還是Down著。這時候62跟我說了一個優(yōu)先隊(duì)列廣搜的題目，和62確認(rèn)了沒有問題，
決定讓62上去敲。但是比賽結(jié)束后證明交這個題的絕大部分隊(duì)伍都tle（很出乎意料），
只是當(dāng)時judge down沒法跟題，所以上去敲，決策上并沒有錯誤。
接著Judge 恢復(fù)了，我們交的2個題都AC了，當(dāng)時我記得排名是第5，還挺靠前的額。
62的H題 TLE 了。我看了board，沒有人過H，心里想不能在這道題上耗時了。
之后52發(fā)現(xiàn)F題是簡單題，Board上也顯示出來了。和52確認(rèn)之后，52上去把這個題干掉了。返回Yes。
根據(jù)場上形勢，是一道最短路+最小權(quán)匹配的題目給我。我用費(fèi)用流敲的。過了樣例之后測了幾個數(shù)據(jù)沒什么問題
就交了 YES.這個時侯好像是12：20.還有1個小時40分鐘，排名靠前。很有希望。
好像是之后62上去優(yōu)化自己的H題（或者是之前，記不清了），結(jié)果還是TLE。
根據(jù)場上形勢，G題和B題過題人數(shù)差不多。B題留給62，我和52搞G。52想出來一種Topo排序的做法，我覺得有點(diǎn)
麻煩，當(dāng)時不知道怎么就覺得逆向的記憶化搜索很好寫，覺得沒有問題就上去寫了。寫完出不了樣例弄了挺久
才發(fā)現(xiàn)這樣做還是需要順推來確定無效狀態(tài)。當(dāng)時加了一個順推去掉無用狀態(tài)還是不行，頭腦有點(diǎn)糊涂了。
當(dāng)時必須做決策了。時間是13：17分。我覺得自己的方法可能有問題，一時之間又沒想出是哪里出的問題，既然如此，就當(dāng)機(jī)立斷
讓52來敲這個題，因?yàn)槲矣X得52思路清晰，肯定能出這個題。下來之后和62稍微討論了下B題，但是
我對B題這種類型都不感冒，也沒幫上什么忙。62說要用Euler函數(shù)水一下，我覺得等F題過了可以試試。
52的這道題敲的和我一樣，問題迭出。在不斷的查找問題，修改程序中，時間慢慢過去，比賽快要接近尾聲了。
中間62去水了一下B，結(jié)果敲著發(fā)現(xiàn)水法是錯的，只得作罷。比賽接受了，G題就這樣夭折了。
賽后分析。本場比賽的失誤集中在G題上。我是罪魁禍?zhǔn)住?br>其實(shí)我的程序在加上順推去掉無用狀態(tài)的時候應(yīng)該把拆的點(diǎn)來做廣搜。而不是原圖的點(diǎn)。這里改了就能過了。
而52的程序則不知道哪里錯了。我沒有想清楚就上去敲，而出了問題之后大腦糊涂，想不出來哪里錯了。
其實(shí)也許當(dāng)時調(diào)試一下就能發(fā)現(xiàn)錯誤。不過覺得在賽場上調(diào)試很浪費(fèi)時間，不敢調(diào)。人生如戲，當(dāng)時覺得
52來敲這個題肯定能過，其實(shí)也確實(shí)不一定的。這個地方要好好反思。以后比賽不會再重敲了。
比賽的時候一定要保持清醒，大腦糊涂了也就完蛋了。
4題，罰時較少，Rank24.
發(fā)揮不好，因?yàn)镚題該出。
總是有很多如果。如果G題能一敲就過，我們就會有時間，比如我用JAVA高精度+分?jǐn)?shù)模板來做D題。。
也許，也許我們就能取得好成績了。。。
可是沒有如果啊。唉。
4隊(duì)差2名就是銀牌了，很是可惜。祝福他們下場比賽勝利。
祝福alpc的所有隊(duì)伍在以后的Regional發(fā)揮出色。這里我無限祈禱中。!
題目簡略描述 by wywcgs：（我偷下懶啊）
A : 一個球體組成的金字塔，每層都是三角形。第一層1個，第二層1+2個，第三層1+2+3個，第n層1+2+3+....+n個。從第一層開始往下按順序給每個小球編號，每層的三角形也是從上到下遍。現(xiàn)在給定一個編號，求它的位置，也就是層數(shù)、層內(nèi)的列數(shù)和列內(nèi)的第幾個。
B : 一個數(shù)有K個約數(shù)（算自己）就叫K維數(shù)。求第n大的K維數(shù)。n <= 10000, K <= 100且K為質(zhì)數(shù)或完全平方數(shù)。
C : 100個點(diǎn)的帶權(quán)無向圖，每個點(diǎn)連著一個港口。有n艘船，船數(shù)和圖頂點(diǎn)數(shù)相等。每艘船有一個初始位置，是圖中的一個頂點(diǎn)。每個港口只能停一艘船，問怎么調(diào)度能讓所有船都停到港口里，總路程的和最小。
D : AX = b的線性方程組求解，A是n*n的方陣，維數(shù)最多到100。要精確解，用分?jǐn)?shù)輸出。
E : 算法不太難，但是5個小時內(nèi)幾乎不可做。
一個迷宮，最多3層。每層的最外圍都用障礙包圍住了。
迷宮內(nèi)有出發(fā)點(diǎn)，目的地，障礙，上樓的樓梯，下樓的樓梯，怪獸，門，鑰匙。其中出發(fā)點(diǎn)，目的地只有一個，上下樓梯每層最多一個。每道門必須用一個鑰匙大開，每個鑰匙只能用一次，門只需要打開一次就永久開放。門最多30個，怪獸最多26個。
定義障礙和門圍成的一圈的內(nèi)部空地叫一個房間。房間內(nèi)可能會有怪獸，所以冒險者在進(jìn)入房間之后要和怪獸搏斗。上下樓梯、開始點(diǎn)和目的地所在的房間里沒有怪獸。
每個房間最多3個怪獸，每個怪獸都有他們的hp和攻擊力，攻擊力就是一次攻擊減的hp數(shù)。冒險者有100點(diǎn)hp和100發(fā)子彈，冒險者的攻擊要耗費(fèi)子彈。冒險者者有10種攻擊模式，每一種耗費(fèi)的子彈和造成的傷害均不同，在輸入中給出如果有多個怪獸，冒險者必須分別消滅。冒險者先攻擊，然后每個怪獸（還活著的話）分別攻擊，然后循環(huán)。。每場戰(zhàn)斗結(jié)束之后，冒險者的hp和子彈數(shù)都會重新填滿。消滅怪獸之后就能任意拿房間里的東西。
問最后冒險者能否到達(dá)目的地，輸出是否即可。
F : 給定一個數(shù)i，對i, i+1, i+2求和。要求求和過程中任何一位都不能產(chǎn)生進(jìn)位，十進(jìn)制數(shù)。給定一個數(shù)n < 10^10，問小于等于n的數(shù)中有多少滿足條件。
G : 一個有向無環(huán)圖，10000個點(diǎn)，每個點(diǎn)都有一個權(quán)。滿足只有一個點(diǎn)在拓?fù)湫蜃铐敹恕＿@個點(diǎn)是起點(diǎn)。有一艘船從這個點(diǎn)出發(fā)，有兩個玩家分別操縱，第一個玩家走第一步，第二個玩家走第二步，第三個玩家再走第三步，類推。必須順著有向邊走。直到不能走為止，最后的得分是路徑上所有點(diǎn)權(quán)的和。如果該權(quán)>=某常數(shù)F則玩家1贏，否則2贏。問1是否能必勝。
H : 一片海域，最大20*20。里面有障礙，漩渦，出發(fā)地和目的地。有一艘船要到達(dá)目標(biāo)，它能做兩個操作，普通走和加速走。普通走一次走一格，加速走一次走d <= 5格。加速走必須要路徑上的d格不能有障礙，否則不允許加速。漩渦必須加速走才能穿過，普通走不能穿過。加速有次數(shù)限制，在輸入數(shù)據(jù)中給出。穿越一個漩渦減少1點(diǎn)HP。要滿足在減少HP最少的前提下用最短的步數(shù)到達(dá)目標(biāo)，問這個最短的步數(shù)。
I : 一個簡單無向圖（無自環(huán)無平行邊），最多1000個點(diǎn)。給1000個數(shù)，是這1000個點(diǎn)的度。文是否有一個圖和滿足給定的度條件。
J : 題目具體沒搞懂，也記不請了，當(dāng)是也沒細(xì)想。直覺像計(jì)算幾何 + 動態(tài)規(guī)劃一類的東西。
寫的比較簡略，有時間再補(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 國防科技大學(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 國防科技大學(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 中國地質(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 中國人民大學(xué) Kingbase 3 銅
60 吉林大學(xué) supergiant 3 銅
61 上海師范大學(xué) Tinman1 3 銅
62 東北師范大學(xué)軟件學(xué)院 NENUSoftware_Golde 3 銅
63 日本會津大學(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 銅