Codeforces Round #617 (Div. 3)題解
d2總是掉分的，只有打打d3才能維持一下基礎分這樣子
注意本文所有代碼均為Python3
A. Array with Odd Sum（奇數(shù)和數(shù)列）
題目大意：給定長為n的數(shù)列，可以在數(shù)列中選擇任意兩個數(shù)，使第一個覆蓋另外一個。問在任意次操作后，能不能使得數(shù)列總和不可被2整除。
沒必要的題解：把問題所給數(shù)列的每個數(shù)抽象為奇數(shù)和偶數(shù)，我們只需要判斷數(shù)列里面有沒有偶數(shù)以及有沒有奇數(shù)，如果都有，顯然我們可以構造出一個滿足條件的數(shù)列。如果只有奇數(shù)，我們的操作沒有意義，這時判斷一下序列的長度如果是奇數(shù)那直接滿足題意，其余情況就都是NO了。
附上代碼：
B. Food Buying（買嘢吃）
題目大意：你去超市消費碰上滿十返一（返現(xiàn)）活動，問你可以在花光現(xiàn)有所有錢的情況下達到花多少錢的效果。
題解：當現(xiàn)有錢大于等于10時，一定可以得到返利。我們做個循環(huán)，每次取現(xiàn)有錢整除以10的結果，這部分就是返利，令現(xiàn)有的錢減去這部分已經(jīng)參與返利的錢并把它計入結果，再把返利加回現(xiàn)有錢數(shù)，直到現(xiàn)有錢小于10就行了。
附上代碼：
C. Yet Another Walking Robot（走路機器人）
題目大意：機器人被按照ULRD四個字符為方向安排一個路線（不是玩游戲用的WASD但可以這么理解）。你的任務是從這個路線中選擇連續(xù)且最短的一段進行刪除，使得機器人的行進路線不變。如果存在無法刪除的情況，輸出-1（那既然刪還要最短一開始就別讓我刪啊）。對于每組數(shù)據(jù)，輸出格式是【起始刪除下標】【空格】【結束刪除下標】。
題解：py體現(xiàn)優(yōu)勢的地方來力對于每一步移動，更新它的當前坐標值，看看之前有沒有來過這個坐標，來過的話答案就產(chǎn)生了一個。如果當前下標減去之前來過時的下標比當前答案還要小的話，目前的答案就是更優(yōu)的答案。
怎么記這個坐標呢，其實因為要求最短且連續(xù)的移動序列，對于每個坐標只需要記錄最近一次來過的時候?qū)囊苿涌刂谱址南聵思纯伞?/p>
附上代碼：
D. Fight with Monsters（打怪）
題目大意：你和友仔一起回合制地打怪，每次碰到一個新的怪物總是你先動手，然后輪到友仔再輪到你如此交替直到怪死（怪物單方面挨打，不用考慮怪物的攻擊）。你希望盡可能多的收掉怪物的人頭，于是你想辦法開掛跳過友仔的回合，但是你最多只能開k次掛。現(xiàn)在已知你和你友仔的攻擊，開掛次數(shù)k和每個怪物的血量，問你最多能拿到幾個人頭。
輸入第一行分別是怪物數(shù)n，你的攻擊力a，友仔的攻擊力b，開掛次數(shù)上限k。
第二行分別是每個怪物的血量。
題解：對每個怪物，由于你和友仔輪流攻擊，可以先對怪物血量對攻擊力總和即a+b求模，模的結果如果在區(qū)間[1,a]內(nèi)那顯然這個怪物不開掛也可以被你收掉。反之讓模的結果-1再去整除以a的結果就是需要開多少次掛才能收掉這個怪物。特判一下模的結果為0時怪物恰好被友仔掐死，那我們就加回b，恢復到被友仔懟前怪物剩余血量再整除以a處理。把剩余的這些結果統(tǒng)計起來塞進一個新的列表，排序后貪心地選擇前幾個開掛次數(shù)最少就可以拿到的怪物即可。
附上代碼：
E. String Coloring（字符串染色）
題目大意：現(xiàn)給一字符串，你可以給每個字符染上一種顏色，注意只有異色相鄰的兩個字符才能互換位置，你希望在染色后通過若干換位操作使得字符串恢復為字典序。
E1：字符串長度不超過200，且只能染為0和1兩種顏色。如果存在可行染色方案，輸出YES并按字符順序輸出你的染色。如不行，輸出NO。
E2：字符串長度不超過200000，找出一種最少顏色的染色方案，輸出顏色數(shù)，并按字符輸出對應的染色（編號從1起）。
題解：官方給的做法是動態(tài)規(guī)劃。對于每個字符，統(tǒng)計該字符前并且字典序嚴格大于該字符的所有字符所占用最大顏色編號。該字符所占用顏色編號即為此編號+1?？梢宰C明該字符必定需要且僅需要跟其前面字典序大于該字符的字符進行交換操作，而交換需要異色，故只有當前字符采用一種與前述字符都不重復的全新的顏色才能避免交換沖突。
如果當前字符前面已經(jīng)沒有字典序大于它的字符，即當前狀態(tài)下無需交換，那么當前字符可以采用第一種顏色。
由于給定的是小寫字符集，我們可以用一個26維的表來裝每個字符對應的當前采用最大顏色序數(shù)。
時間復雜度為O(n)。
附上代碼：
E1：
E2：
F. Berland Beauty（伯 蘭 之 美）
題目大意：按鄰接表給定一棵樹，然后對于以下m條線路，按如下信息給出：
出發(fā)點a，到達點b，途經(jīng)（最短路的途徑）各邊的最小邊權g。
如果所給的m條信息中存在矛盾，輸出-1。否則輸出每條所給邊的有效權值（如存在多個可能的值可以任意輸出其中一個）。
輸入數(shù)據(jù)的第一行表示所給樹的節(jié)點數(shù)n。接下來的n-1行是這棵樹的鄰接表表示。
n∈[2,5000]
m∈[1,5000]
樣例圖解：
題解：首先，如果這題你有LCA做法那可以的話交流一下？
拿到樹的圖時，我們先花費n^2時間遍歷這棵樹獲取每個節(jié)點的父節(jié)點，這里可以避免之后使用dfs來找路。這里以節(jié)點1作為整棵樹的根節(jié)點。
我們可以初始化時把每條邊的權值記為1（最小可能的權值），因為每次給的權值是所遍歷的所有邊中最小的，因此在處理共m次更新路徑權值操作中就可以把兩個點間的所有邊的權值設為max{當前邊權值，更新操作中所給權值g}。
那么怎么檢測沖突呢？
對于共m條的每條更新路徑，待所有上述更新操作完畢后再次對于每條路徑進行遍歷看看是否每條邊的最小權值等于g即可。
py選手注意這道題的鏈狀特殊數(shù)據(jù)會讓dfs找父節(jié)點的操作爆棧。另外注意本代碼的邊權beauty記在父節(jié)點上。
不知道封面能不能補圖= =
