Problem - 461B - Codeforces題意： 給一顆樹，和每個節點是黑是白。求樹的分割組合數，滿足分割後的所有組合都恰有一個黒点，求其余数。數據範圍： 節點數 2 ≤ N ≤ 1e5解法： 樹形動態規劃寫起來真蛋疼。。。 將 0 作為根，轉換為有根樹上的問題。 dp[ i ][…

Problem - C - Codeforces題意： 給一個無向圖，保證任兩點之間至多存在一個路徑。接著若干比詢問，第一種詢問求某個點所在的連通塊裡的最遠距離( 直徑 )，第二種詢問須將兩個點所在的連通塊用最優方法，將一條邊兩端點分別連上兩連通塊中各一個點，使連接後…

Problem - E - Codeforces題意： 給一張帶權有向圖。求最長路徑長度，路徑滿足邊權嚴格遞增。數據範圍： 節點 2 ≤ N ≤ 3e5 邊數 1 ≤ M ≤ min( N * ( N - 1 ) / 2, 3e5 ) 邊權 1 ≤ W[ i ] ≤ 1e5 保證無自環，無重邊。解法： 先考慮將邊權小至大排序。此時發現…

Problem - D - Codeforces題意： 給陣列大小，目標高度，和陣列。可以對陣列進行任意次操作，將某個區間全部加一。前提是任意區間的左界不重複，右界也一樣。求方案數，使得陣列中所有元素為目標高度。數據大小： 陣列大小 N ≤ 2000 目標高度 H ≤ 2000 陣列…

Problem - F - Codeforces 題意： 給 N, K，代表有多少學生，以及花費總和上限。接著給學生們的實力 A。現在把學生分組，一組的花費是最大實力和最小實力的差。求花費不超過 K，將所有學生分組的方案數，求其餘數。 解法： 先將學生按實力排序後，定義動態規…

Problem - B - Codeforces 題意： 給一個序列 A，要你求一個相同長度的 B 序列，使 B 序列中任意兩個數字皆互質，此前提下 SIGMA{ abs( A[ i ] - B[ i ] ) } 最小。輸出 B 的長相。 解法： A 最大只會有 30，可以證明 B 只需考慮 [ 1, 60 ] 內的數。因為如果…

Problem - 479E - Codeforces 題意： 給 N, A, B, K，代表有幾層樓，初始在哪層，哪層是禁止樓層，要轉移多少次。由 x 轉移到 y 是合法的若且唯若 | x - y | 解法： dp[ i ][ j ] : 已轉移 i 次，最後一次在第 j 層樓時的方案數。 如果樸素轉移，會變成 O( N…

Problem - D - Codeforces 題意： 公主和龍玩一個遊戲，背包裡初始有若干個白老鼠和若干個黑老鼠。公主先開始，輪流取一個老鼠出來，先取出白老鼠的贏。取出後不放回，但龍取老鼠之後，會有一隻還在背包裡的老鼠，平等隨機地逃走消失不再回來。當背包裡沒有…

Problem - 540D - Codeforces 題意： 在一座島上有三種人，只出剪刀，只出石頭，只出布的人。每一秒都有一對人會相見。每對人相見的機率都相同，如果相見的是同一種人，則什麼都不會發生，否則他們會決鬥，就跟一般猜拳規則一樣定勝負，輸的人會死掉。給三種…

Problem - 294B - Codeforces 題意： 給一堆相同高度的書，用厚度和寬度描述。放書的方法是相放一層豎的，再將剩下的橫放在那層上。橫放的那層寬度總和不得超過下面豎著放的那層厚度總和。求最小厚度總和。 解法： 由於書的厚度只有兩種，因此可以分開枚舉兩…

Problem - 455B - Codeforces 題意： 玩連續 K 輪遊戲。每輪遊戲規則都一樣，初始時為空字串，輪流向字串結尾添加一個新的字元，操作後必須是字典中某個字的前綴。若無法進行合法的操作，則判為失敗。敗者為下一輪遊戲的先手。兩人採取最優策略爭奪第 K 輪的…

Problem - 557C - Codeforces 題意： 一個桌子有若干個腳，每個腳用其高度和拔掉該腳所需花費描述。求最小總花費，使得最常的腳是絕對多數( 過所有腳數量一半 )。 解法： 利用各種預處理。枚舉最大長度後，透過各種前綴和快速得到更大長度的花費總和，接著枚…

Problem - 340D - Codeforces 題意： 給一個元素相異序列用以描述一個圖，所有逆序數對之間存在一條無向邊。求最大獨立集合( 集合中所有點接無邊連接 )的數量。 解法： 只要沒有逆序數對，就不會有邊。沒有逆序數對意味著是遞增序列。因此問題轉換成求 LIS。…

Problem - C - Codeforces 題意： 給一堆節點，表示節點上有寶石，重複輸入節點代表有多少寶石，和一開始跳躍的距離 D，代表初始時在 D 編號的島上，且最後一次跳躍的距離是 D。接著每次移動可以選擇移動最後一次移動的長度 -1 / 0 / +1，但不能不移動( 移動…

Problem - 375B - Codeforces 題意： 給一個 0/1 矩陣，求最大全 1 矩形面積。 解法： 先預處理 dp[ i ][ j ] : 在 row i, col j, 向右延伸連續 1 的最長長度。 接著對於每個固定左界，將每一行收集起來，由大到小排序。這時候就能 O( N ) 更新答案。 int N,…

Problem - 269B - Codeforces 題意： 給一堆東西的編號和位置，保證輸入位置是由小到大，操作可以將任意一個東西移到任意一個地方，求最少操作數使編號隨位置非嚴格遞增。 解法： 就是 N - LIS。 int N, M; vi S; vd X; void init(){ cin >> N >> M; S = vi(…

Problem - 660C - Codeforces 題意： 給 0, 1 組成的序列，求修改至多 K 個數字之後的最長連續 1 子序列長度，及整體長相。 解法： 預處理前綴和，接著二分搜答案。每次確認答案是否對只需要 O( N )。 int N, K; vi A; void init(){ cin >> N >> K; A = vi( …

Problem - C - Codeforces 題意： 給一個有向無環圖，保證 1 到 N 連通，有邊權。求不超過給定 T 的總邊權下，由 1 移動到 N 最多可以經過多少不同節點，以及其路徑。 解法： dp[ i ][ j ] : 最後在 i 號節點，已拜訪 j 個節點。 因為拜訪過的節點不可能再被…

Problem - 416C - Codeforces 題意： 給一堆客人的要求，用人數和獲益描述，接著給一些桌子其容量。每個桌子只能招待一組客人的要求，而某個桌子可以招待一組客人若且唯若其容量不小於人數，此時若選擇配對則獲得該獲益。求最大總獲益，並輸出對應配對。 解…

Problem - 713C - Codeforces 題意： 給一組數列，每次操作可以將一個數字增加或減少 1，求最少的操作數，使得數列嚴格遞增。 解法： 首先看到嚴格遞增，將每個數字減去自己的下標後，就可以轉換成非嚴格遞增，題目或許會比較好解。接著考慮，如果有幾個數字…

Problem - 653B - Codeforces 題意： 給字串初始的長度，和若干組操作。操作用兩個字串描述，第一個是兩個字母，第二個是一個字母，代表若且唯若當前準備要進行操作的字串前兩個字母和指定操作的字串一致，就可以將該字串轉換成指定操作的第二個字串( 字母 )…

Problem - 615B - Codeforces 題意： 給一張不一定連通的圖。求一個序列，使起點至終點都相鄰，且編號遞增，此前提下序列長度和序列末尾節點的度數之乘積最大。 解法： dp[ i ] : 以 i 節點為末尾的最長序列長度 更新方向顯然是由編號小的節點至大的就行了。…

Problem - 611C - Codeforces 題意： 給一張有一些格子有障礙物的圖，接著多組詢問，用左上和右下座標描述。對於每筆詢問輸出該塊在原圖中，有多少種可以放 1 * 2 的條狀物的方法。 解法： 做二維前綴和，回答時再進一步刪去跨邊界的條狀物數量。 dp[ i ][ j…

Problem - 607B - Codeforces 非常神奇的一道題 題意： 給一個數列，每一次操作將一連續區間的回文刪除，刪除某區間後其左右會連接。求最少刪除數，使整個數列被刪除。 解法： dp[ i ][ j ] : 刪除原序列的 [ i, j ] 區間元素需要的最少操作數。 dp[ i ][ j …

Problem - 5C - Codeforces 題意： 給括弧序列，求連續區間之最長的合法匹配長度，和其數量。 解法： 對於每個閉括弧，預處理和其配對的開括弧位置，並藉以更新對應的最遠合法左界。如果當前這個閉括弧能配對，那麼最遠合法的左界就是其對應的開括弧左邊一個…

Problem - 567C - Codeforces 題意： 給一個數列和 K，求有多少三個元素構成的有序遞增等比子序列，其比為 K。 解法： 預處理，使可以查詢每個值存在於哪些位置，且這些位置是排序好的。接著枚舉中間的數字，左右邊的數字將會隨之確定，因此將答案增加指定數…

Problem - 550C - Codeforces 題意： 給一個大數，求任意刪除數字，使其為 8 的倍數。 解法： 如果有 0，那麼就變 0。否則基於 8 的倍數只與後三位有關的性質，進行動態規劃，紀錄 0 至 999 的數是否可以達到。 string _seq; void init(){ cin >> _seq; } vi…

Problem - 547b - Codeforces 題意： 給一組數列。對於 x for each 1 to N，輸出數列中，屬於連續 x 個元素構成的區間裡最小值的最大值。 解法： 由大的數字至小，每次將大的數字和左右的數字於並查集結構中，以位置為單位並在一起，若且為若左右的數比它本…

Problem - 545C - Codeforces 題意： 在一維空間中給一堆樹，用位置和高度描述。現在要砍樹，砍完可以選擇向其左方或右方倒，倒完後高度就會往那方向躺平佔據區間。求可以砍多少樹，使得任意點不被兩棵樹同時佔據。 解法： dp[ i ][ j ] : 考慮前 i 棵樹，最…

Problem - 543A - Codeforces 題意： 給 N, M, B, MOD, 分別是編程者數量，程式碼行數，可容忍的 bug最大上限數，和神秘餘數。接著一行給出各編程者一行會寫出多少 bug。從一號開始，每個編程者完成剩餘的行數中任意多個( 0 ~ 完成 )，求完成指定的程式碼行…