- 2018.08.03
- bzoj, DP & 記憶化搜尋, stl, 雜湊,
BZOJ2719 – [Violet 4]銀河之星 (記憶化搜尋 hash)
Description Input Output Solution 一看到這題的我是懵逼的,好像有好多狀態,媽媽怎麼辦? 然而仔細讀題目,轉動我們的腦子可以發現,由於每個棋子可以向各個方向移3格,且只會改變自身的位置,整個網格就被劃成了9個區域: 0 1 2 3 4 5 6 7 8 其中每個區域代表 […]
-->
程式前沿 幫助程式設計師解決問題,增加專業技能,提升個人能力與未來世界競爭力。
Description Input Output Solution 一看到這題的我是懵逼的,好像有好多狀態,媽媽怎麼辦? 然而仔細讀題目,轉動我們的腦子可以發現,由於每個棋子可以向各個方向移3格,且只會改變自身的位置,整個網格就被劃成了9個區域: 0 1 2 3 4 5 6 7 8 其中每個區域代表 […]
BX正在進行一個字串游戲,他手上有一個字串L,以及其他一些字串的集合S,然後他可以進行以下操作:對於一個在集合S中的字串p,如果p在L中出現,BX就可以選擇是否將其刪除,如果刪除,則將刪除後L分裂成的左右兩部分合並。舉個例子,L=’abcdefg’ , S={‘d […]
傳送門 題目大意: 小銘銘最近獲得了一副新的桌遊,遊戲中需要用 m 個騎士攻佔 n 個城池。 這 n 個城池用 1 到 n 的整數表示。除 1 號城池外,城池 i 會受到另一座城池 fi 的管轄, 其中 fi < i。也就是說,所有城池構成了一棵有根樹。這 m 個騎士用 1 到 m 的整數表示 […]
傳送門 題目: 就是同時有k個人從一顆有n個節點的樹的根節點出發, 走過的點都可以累加到ans中, 一個點只能被累加一次, 問最大能累加多少. 思路: 其實最開始做這道題是用的倒著做的, 然後dp了一下, 現在學了這個就用這個再做做, 實際上我們從葉子節點開始每次每個節點只加在價值最大的那個子節點上 […]
【題目】 Description 給你一個無向圖,N(N<=500)個頂點, M(M<=5000)條邊,每條邊有一個權值Vi(Vi<30000)。給你兩個頂點S和T,求一條路徑,使得路徑上最大邊和最小邊的比值最小。如果S和T之間沒有路徑,輸出”IMPOSSIBLE”,否則輸出這個比 […]
題目描述 在某城市裡住著 n 個人,任何兩個認識的人不是朋友就是敵人,而且滿足: 1、我朋友的朋友是我的朋友; 2、我敵人的敵人是我的朋友; 所有是朋友的人組成一個團伙。告訴你關於這 n 個人的 m 條資訊,即某兩個人是朋友,或者某兩個人是敵人,請你編寫一個程式,計算出這個城市最多可能有多少個團伙? […]
團伙 題目背景: bzoj1370 分析:並查集,對於兩個敵人,將x與y n,y與x n,合併,然後對於朋友,將x與y合併,然後就可以符合題目要求了,敵人的敵人是朋友,朋友的朋友是朋友,注意對於朋友,x n與y n不能合併,因為沒有說朋友的敵人一定是敵人。最後統計1 ~ n中有多少集合就可以了 So […]
對於朋友,我們直接合並兩人所在的集合。對於敵人,我們分別合併一人與另一人的敵人。我們只需再記下每個人的一個敵人即可。最後統計有多少個連通塊便是答案 #include<cstdio> #include<cstring> #define N 1005 inline int rea […]
題目描述 傳送門 題目大意:給定一棵樹,邊的顏色為黑或白,初始時全部為白色。維護兩個操作: 1.查詢u到根路徑上的第一條黑色邊的標號。 2.將u到v 路徑上的所有邊的顏色設為黑色。 Notice:這棵樹的根節點為1 題解 先將所有操作正著進行一遍,將所有的黑邊相鄰的點按照關係合併,就是一個集合中的代 […]
題解:注意到 f(i, k) 一定單調, 從小到大列舉每一個 i , 分解素數可以求出此時滿足條件的最小的 N …… 看程式碼把 ಥ_ಥ …… 不會證明複雜度…. n 乘若干個 log ? hhhhhhhh #include<cstdio> #include<algorithm&g […]