2011年3月24日 星期四

Codeforces #69

題目不太難,只是有些題目比較難讀懂,遲開始了,最後得分比較低。

A: 在三維空間的原點上有一物件。應用了次矢量為的力後,問最終物件是否原地不動。
答案﹕檢查 $\sum_i\vec{F_i} = \vec{0}$ 即可。

B: 一條長度為的跑道上有個section。每個跑手會在個section進行賽跑。假設個section每次賽跑都是分開進行的,若在某section裡下注了第跑手贏出而真的贏出的話,則得到元。每人每section賽跑時間都是。不能在沒人跑的賽道中下注,不能在沒有某參賽者不賽跑的section向其下注,問最多可以贏到多少錢?

好煩的題目。但只是直接枚舉每個section,在有人跑的回報裡取最大值,然後總和就是答案。

C: 給了種神器的原材料名稱,和種神器所需要的原材料及其數量。現在有個玩家和次採購。每次採購皆說明是哪位玩家買了甚麼原材料。
保証每次採購後只會有最多一種合作神器可以作成,問最後每人手上每種神器的數量,和有多少種神器。

直接就是做,比賽時沒過是因為我以為輸出的是玩家名稱,而不是神器的數量…

D: 在某座標上放了一隻棋子。兩個玩家輪流玩遊戲。每次可選取個之中的一個矢量然後加到該棋子上,保証矢量非零並且數值非負。除移動外,另可以選擇應用反射,即,但每位玩家只能在遊戲中應用一次。玩家不能把棋子移離原點距離以外。問若兩個玩家皆采取最佳策略,問誰會勝出。

經典的動態規劃題。但可以留意反射是沒有作用的,因為對方可以再應用一次反射抵銷。
另可以用SG定理,注意需處理SG函數為0的位置。

E: 給定一數組和,詢問對於,之間出現僅一次的元素的最大值,不存在的話則輸出"Nothing"。

直接的單調隊列題。大部分選手都用STL的set,我則用了Priority Queue來做,幸好沒有超時。主要做法是當需要處理新的元素時,把最舊的元素統計減1,然後把新元素的統計加1,若是新出現的元素則放到隊列內。每次輸出時把第一個隊列置頂的元素輸出,且其需要符合統計數為1。若不合資格則把它移除。

2011年3月19日 星期六

Codeforces #68

比賽題目較為簡單,但是仍然表現得不夠好。

A: 問給了4個互相不同的數,給了範圍,問當中有多少個數,使得在至少7種的不同排列中,該數在取模的順序下仍然保持不變。看了之後都不用懷疑,直接就暴搞了。但留意一下取模順序本來就是符合交換性的,即,因此只需對一種排列(例如輸入中的排列)下試了所有數看看是否在取模順序下不變即可。省卻了24!的排列。
然而,本題有的算法。假設,可知保持取模下不變的數只能在,即,其餘取模是多餘的。因此答案即是。

B: 給定個整數,定義操作,使得操作後。給定,問經過若干次操作後,能使得的話,它們的數值最多為多少。

直接的想法就是二分答案。設為經過若干次操作後最終每個數的一致值,定義



不難看出是總供給量,是總需求量。若則表示經過若干次操作後所有數皆等於。若則表示供過於求,即太低;若則表示供不應求,即太高。應用二分法求最大的使得供求相符即可。

C: 給了一個有向無環圖,最多6個頂點,而且是完全圖。每條邊有要求流量最少最多值,和啟動值。設在邊流量是,啟動值,則費用是。求一個可行的網絡流,源是點1,匯是點,需要符合上下限,要求流量最小,其次則要求費用最大。上下限最多是5,啟動費用最多是6。若沒有流量則毋需計算啟動費用。

明顯地數據範圍極小,可以考慮暴試。設為第點的注入量。對源點則有。DFS狀態為,當中。此程序會嘗試從點抽取之間的注入量,加到之中,然後按情況嘗試。當達到即可中止。但嘗試量最多是,肯定會超時。要應用一些prunning技巧。首先,當在狀態的時候,若已經大於最小流量值則中止嘗試。另,嘗試的時候,應直接取走其注入量,並留意是否,若否則中止搜索。

D: 待補。