天天看點

【9.7測試爆零記】

按照慣例,不會T1

開場看了三道題,T1多半是個組合數學DP,T2猜想是一個網絡流,T3一眼SB斐波那契拆通項公式。

随手推了一個式子,然後dfs序+樹剖+樹狀數組+重載複數,開場半個小時切掉T3,靜态debug了一波覺得沒什麼毛病就沒管了。

T2一眼貪心費用流,但是發現有一部分是經典的網絡流不可做題,需要強行某條邊流滿再流下一條。。。

發現費用隻在最後一個階段會産生影響,果斷放棄了費用的實際含義,調整為流量走向的優先級,跑最小費用最大流。然後推了若幹個錯誤的建圖方式。。。

最後調整了一波發現會有一種非常窒息的情況,一個決策必須先流4号點再流3号點,然而由于三号點不會對答案産生貢獻,是以在流了四号點之後我們希望先流這個決策對應的三号店。。。

發現要支援退流,而且退流失敗還要支援流回來。。。感覺T2不可做。

仔細一想,發現我們實際上會把所有流了四号點沒有流三号點的全部拿出來,有相同前驅的直接轉移。。。MD一般圖最大比對,由于不會帶花樹是以考場上寫的是Tutte矩陣的做法。

然後距離考試結束還有一個小時。。。

T1SB組合DP題,但是,為什麼不取模,怎麼辦,感覺要爆精度啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。。。

于是T1寫了十分,不管了丢了。

花了十分鐘靜态debug了一下T2,發現自己用Tutte矩陣的時候傳回結果沒有除以2,好險。。。然後順手給T2優化了一下常數。

然後頹了整整四十分鐘,最後十分鐘的時候L看我一臉頹态直接喊我交了。。。

然後下來一問,T2都覺得是網絡流,但是感覺自己能A的好像隻有我一個???flag

吃午飯的時候xjb立了一個flag。。。倒了

回去看了一下發現我T2T3A掉了,T1拿了意料中的十分。。。

結果TM告訴我T1标程直接開的long double???不會爆精度MMP。。。

AK不了,爆零了,告辭