Problem - A - Codeforces題意： 一個方陣，初始所有值為 0，塞 1 進去，1 彼此不相鄰，且最後方陣必須上下、左右分別成對稱。給 1 的數量，求至少要邊長多少的方陣才能塞下。資料規模： 1 的個數 1 ≤ X ≤ 100解法： 先注意到因為必須對稱，奇數邊長的方陣一…

Problem - 559B - Codeforces題意： 對字串定義一個比較函數： 若 A == B 則 f( A, B ) = 1 若他們的長度相同，且長度為偶數，那麼分成兩半 A[ 0 .. size / 2 ), A[ size / 2, size ) 後，左右兩半對調，若對調後的 f( A', B ) = 1，那麼 f( A, B ) = 1。資…

Problem - 566F - Codeforces題意： 給一個嚴格遞增序列。求子序列最長長度，子序列滿足所有相鄰元素對，後一個元素可以被前一個整除。資料規模： 序列長度 1 ≤ N ≤ 1e6 元素大小 1 ≤ A[ i ] ≤ 1e6 時限 1000 ms 記憶體 256 MB解法： 注意到 [ 1, N ] 的數的…

Problem - F - Codeforces前言： Codeforces Round #379 (Div. 2) F. Anton and School - pekempeyのブログ pekempeyさんの記事読んでやっとわかった。題意： 給相同長度的 B 序列和 C 序列。求是否存在一個 A 序列，滿足 不存在則輸出 -1，否則輸出滿足的任…

Problem - B - Codeforces題意： 給一個圖，邊用四個值表示，( x, y, Cxy, Cyx )，代表 x 至 y 長度是 Cxy，y 至 x 長度是 Cyx。求是否存在一個正環，若存在則輸出最小環的長度。資料規模： 節點數 1 ≤ N ≤ 300 邊數 0 ≤ M ≤ N * ( N - 1 ) / 2 權值 -1e4 ≤ …

Problem - A - Codeforces題意： 給一行有標點符號，空格，和小寫英文字母的字串。求照英文書寫格式化後的樣子( 字與字之間一個空白，但標點符號和前面的字無空格 )。保證有解。資料規模： 一行含空白的字串，不超過 1e4 個字元。解法： 用 stringstream 讀…

Problem - E - Codeforces題意： 給一個序列，每次隨便選一個數字，加到字串尾。求有幾種方法，挑 B 個數字後，除以 X 的餘數為 K。資料規模： 數字量 2 ≤ N ≤ 50 000 1 ≤ B ≤ 1e9, 0 ≤ K 數字大小 1 ≤ A[ i ] ≤ 9 時限 2000 ms 記憶體 256 MB解法： dp[ i ]…

Problem - 559B - Codeforces 變字典序再比較就好 Problem - 321C - Codeforces Problem - 372B - Codeforces Problem - 459D - Codeforces

1045 - A.細菌培養 | TIOJ INFOR Online Judge題意： 給矩形的座標，每次使矩形內的所有數字 * 2，初始時皆為 1，求所有操作後矩形內數字總和。資料規模： 座標 0 ≤ X, Y ≤ 10000 操作數 1 ≤ Q ≤ 200 時限 1000 ms 保證解 ≤ 8e18解法： 本來想用 imosu ( 前…

シラバスに載ってて自分がまだよく知らないトピック： BCC Z-algorithm Minimax algorithm Sweeping line algorithm Bipartite Graphs O( VE ) Maximum Bipartite matching ∆ Maximum flow. Flow/cut duality theorem Euler Path / Cycle 2-D Tree Trie ∆ KM…

Sorted by number of ACs by descending order: Problem - 274B - Codeforces Problem - 650B - Codeforces Problem - B - Codeforces Problem - G3 - Codeforces ACしてるコード見ててもどして n^3 なのかわかん Problem - 432D - Codeforces Z Algorithm …

Problem - E - Codeforces題意： 給一棵樹，每個節點有顏色，黑或白。每次可以選一個同顏色的連通分量，將全部顏色反轉。求最少反轉次數，使得樹的所有節點同色。資料規模： 節點數 1 ≤ N ≤ 2e5解法： 先對原圖做連通分量縮點去想。如果用連通分量個數變化的…

Problem - C - Codeforces題意： 在一個棋盤上，起點 ( 1, 1 ) 終點 ( H, W )，給若干個禁止點，求不走遠路的路徑數，不經過禁止點，其餘數。資料規模： 1 ≤ H, W ≤ 1e5 禁止點數 1 ≤ N ≤ 2000解法： 預處理階乘表後，可以用組合公式 ( H + W ) ! / ( H ! * …

最近莫名有幹勁QQ 或許是突然發現身為選手的生涯已經在旦夕了( ? ) 也可能是因為部落格很讓人振奮啊啊啊 剛發現一些蠻好的資源 要好好利用一下 CFR 今年要破 1000 AC!! 然後中國 OI 題也來一波 POI 也來一波 這些大神的部落格也 follow 一波 一些基础数据结…

Problem - E - Codeforces題意： 在 [ 1, M ] 中，要算有多少種方法，可以有 N 個有序區間( ex: { [ 1, 2 ], [ 3, 4 ] } != { [ 3, 4 ], [ 1, 2 ] } )，不存在任一個區間包含另一個區間，且有至少一個區間的左界為 X，求其餘數。數據範圍： 需要區間數，值域…

Problem - D - Codeforces題意： 初始時在 x = 0，要到 x = M，一路上會有若干個地雷。有兩種移動方式，跑步可以一次跑無窮遠，但不能越過地雷，跳躍可以越過地雷，但必須先跑連續至少 S 格，才能進行一次至多 D 格移動的跳躍。所有移動都只能向右。求是否存…

Problem - C - Codeforces題意： 給若干個條碼，由六個 0 ~ 9 之間的數字組成。求一個最大 K，保證就算打錯 K 個數字，依然可以確定是哪個條碼。數據範圍： 條碼的數量 1 ≤ N ≤ 1000解法： 首先顯然如果 N = 1，那一定是 K = 6，全部打錯都行。否則顯然 K = …

Problem - B - Codeforces題意： 給通知的順序，若是新的人的通知則會到訊息版最上面，否則會將舊的人提到訊息版的最上面。求最終樣貌。數據範圍： 通知數 1 ≤ N ≤ 2e5 通知的人名 1 ≤ | name | ≤ 10解法： 在動態過程中，每個人名一定只會對應到一個位置，…

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< vvi > vvvi; typedef vector< vvvi > vvvvi; typedef vector< vvvvi > vvvvvi; typedef vector< ll > vl; typedef vector< vl </bits/stdc++.h>…

Problem - 255C - Codeforces題意： 給一個序列。求一個最長子序列的長度，子序列滿足相鄰的數字的差是正負交替。ex: 10, 20, 10, 20數據範圍： 序列長度 1 ≤ N ≤ 4000 元素大小 1 ≤ B[ i ] ≤ 1e6解法： 對每個元素預處理出現在哪些位置。接著考慮動態規劃 d…

Problem - 448C - Codeforces題意： 給不一定同高度的塔一排。油漆可以橫著刷也可以豎著刷，但橫著刷一次的時候，是不能跨過空的欄位。求最少要刷幾次才能刷好所有塔。數據範圍： 塔數 1 ≤ N ≤ 1e5 塔高度 1 ≤ H[ i ] ≤ 1e9解法： 遞迴考慮，最少塗刷次數可…

Problem - 519D - Codeforces題意： 給 26 個英文字母各自的花費，接著一個字串。求有多少子字串，滿足頭尾字母相同，且扣去頭尾字母後的花費總和為 0。數據範圍： 花費 -1e5 ≤ cost[ i ] ≤ 1e5 字串長度 1 ≤ | seq | ≤ 1e5解法： 先預處理前綴花費和，並做…

Problem - 276D - Codeforces題意： 給 L, R，求任一對 A, B，滿足 L ≤ A ≤ B ≤ R，可得的最大 A XOR B。數據範圍： 1 ≤ L ≤ R ≤ 1e18解法： 先將 L，R 轉換為二進制，若長度有差則補零在前頭。接著在這上面做動態規劃( 數位統計 )。 dp[ i ][ j ][ k ][ l ]…

Problem - 337D - Codeforces題意： 給一棵樹，和若干個指定節點，和 D。求有多少節點，滿足至最遠的指定節點的距離不大於 D。數據範圍： 指定節點數 M，樹大小 N，1 ≤ M ≤ N ≤ 1e5 0 ≤ D 解法： 以 0 為有根樹進行 DP dpd[ i ] : i 號節點與向下最遠的指定…

Problem - 120F - Codeforces題意： 給若干顆樹，現在連最少的邊使之連通，求連通後最大直徑。數據範圍： 樹數量 1 ≤ N ≤ 100 樹大小 2 ≤ s[ i ] ≤ 100解法： 求直徑總和即可。直徑的找法是，先對一任意一個點，找到其最遠點。該點至它的最遠點的距離即是直…

Problem - A - Codeforces題意： 給有序的名字表。求最長的字串長度，字串須能拆解成名字表裡的字，且順序須依照表中的順序，且連接的兩個字串，前面字串字尾需與後面字串字頭相同。最後的字串必須滿足字頭與字尾相等。數據範圍： 字串數 1 ≤ N ≤ 5e5 字串長…

Problem - C - Codeforces題意： 在一個桌子上，有 N 個武士兩兩相鄰等弧距坐著。每個武士都有心情好壞，求是否有一種武士的組合，滿足所有武士心情都好，且相鄰連接後是一個正多邊形( 同角同長度 )。數據範圍： 武士人數 3 ≤ N ≤ 1e5解法： 顯然要檢查的只…

Problem - 573B - Codeforces題意： 有若干個不一定相同高度的塔連續排成一排。每次操作會把滿足「上下左右其中一格子是空的」的所有單位為一的塊刪除。求幾次操作後才能將所有塔刪除。數據範圍： 塔數 1 ≤ N ≤ 1e5 塔高度 1 ≤ H[ i ] ≤ 1e9解法： 考慮一個…

Problem - 478D - Codeforces題意： 給兩種顏色方塊分別的數量，疊一座塔。塔的每一層顏色都必須相同，且頂層塊數為 1，每一層都必須比上面一層多恰一個方塊。求疊高度最高的塔的方案數。數據範圍： r: 紅方塊數量, g: 綠方塊數量, 0 ≤ r, g ≤ 2e5, 1 ≤ r + …

Problem - C - Codeforces題意： 給 A, B 陣列，求一組序列 { i1, i2, .. } 滿足 SIGMA{ A[ i ] } / SIGMA{ B[ i ] } = K。在此前提下，求 SIGMA{ A[ i ] } 的最大值。若無解則輸出 -1。數據範圍： 陣列大小 1 ≤ N ≤ 100 比例 1 ≤ K ≤ 10 陣列元素大小 1 ≤ A…