Problem - 510E - Codeforces題意： 給長度 N 的數列 A[]。要求將每個元素分別放在某個圓桌裡，一個圓桌必須滿足以下條件： 每個元素和兩個元素相鄰。 相鄰元素的和必須是質數。制約： 3 ≤ N ≤ 200 2 ≤ A[ i ] ≤ 1e4解法： 和是質數，那麼偶數一邊，奇數一邊…

Problem - 546E - Codeforces題意： 有 N 個城市，M 條無向邊。 起初第 i 個城市有 A[ i ] 個士兵。 現在進行一次移動，每個士兵都可以選擇不動，或者移動到相鄰的城市。 輸出方案，使得移動後第 i 個城市有 B[ i ] 個士兵。若不存在方案，輸出 -1。制約： 1…

Problem - 589F - Codeforces題意： 有 N 種菜，你想要全部都吃一樣多的時間。 第 i 道菜可以吃的時間是 [ A[ i ], B[ i ] )。 只能在整數區間內吃菜，而且是至多一道。 問你最多可以吃多久時間。制約： 1 ≤ N ≤ 100 0 ≤ A[ i ] 解法： 二分搜答案，每次重新…

Problem - 498C - Codeforces題意： 給長度為 N 的數列 A[]。 有 M 筆操作： u v：選一個 A[ u ] 和 A[ v ] 的公因數 g，進行 A[ u ] /= g, A[ v ] /= g，保證 ( u + v ) % 2 == 1 問最多能有幾次，你選的公因數 g 不為 1。制約： 2 ≤ N ≤ 100 1 ≤ M ≤ 100 1…

Problem - 808F - Codeforces題意： 你有 N 張卡。第 i 張卡有 P[ i ] 單位的力量，C[ i ] 單位的魔法性質，L[ i ] 的門檻。 你想組一個總力量不小於 K 單位的牌組，但是這些牌的門檻必須不超過你的等級，並且任意兩張的魔法性質總和不為質數。 你現在的等級…

Problem - 808E - Codeforces題意： 有 N 個物品，你的背包容量為 M。第 i 個物品容量為 W[ i ]，價值為 C[ i ]。求可容的最大可能價值總和。制約： 1 ≤ N ≤ 1e5 1 ≤ M ≤ 3e5 1 ≤ W[ i ] ≤ 3 1 ≤ C[ i ] ≤ 1e9解法： 如果只有兩種重量，那有多簡單。 考慮討…

Problem - 788E - Codeforces題意： 給長度 N 的數列 A[]。 這個數列代表士兵們，他們的強度。初始時所有士兵都是活著的。一個隊伍是合法的，如果他有 5 個人，令下標為 a 有 M 筆詢問，分為兩種： 1 x：反轉 x 號士兵的狀態 ( 保證活 -> 死 ) 2 x：反轉 x …

Problem - 794E - Codeforces題意： 給長度 N 的數列 A[]。現在輪流玩遊戲，選擇一個端點的元素，讓它消失。當元素數量為 1 的時候遊戲立即結束。先手的目標是最大化最後一個元素，後手的目標是最小化最後一個元素。先手打算作弊，自己操作連續 K 輪後，當作…

Problem - 794D - Codeforces題意： 有 N 個城市，M 條路。如果存在，輸出一個方案，為每個城市 u 分配一個數字 X[ u ]，使得 abs( X[ u ] - X[ v ] ) ≤ 1 若且唯若 u, v 相鄰。制約： N, M ≤ 3e5解法： 首先考慮這樣的一對城市 ( u, v )：它們的鄰接陣列，…

標ㄐㄧProblem - 794F - Codeforces題意： 給長度 N 的數列 A。有 Q 筆詢問，分兩種： 1 l r x y：代表要將 A[ l .. r ] 中所有 x 的數位變換成 y 2 l r：代表要輸出 A[ l .. r ] 的總和制約： N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9 For query type 1: y != 0解法： …

Problem - 776C - Codeforces題意： 給你一個長度 N 的序列，以及 K。問有多少個區間的總和是 K 的非負整數次方。制約： The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection …

Problem - E - Codeforces題意： 有 N 個商品，用價格描述。你一共要選擇 M 樣物品，使得 Masha 喜歡其中至少 K 件，Arkady 也喜歡其中至少 K 件。問最小花費，無解輸出 -1。制約： The first line contains three integers n, m and k (1 ≤ n ≤ 200000, 1 ≤…

Problem - D - Codeforces題意： 你有一個 H * W 的棋盤。你的目標是要在這之棋盤上能容下 A * B 的棋盤，但是容的時候邊之間必須平行或垂直。你有 N 個放大燈，選長或寬照上去之後那個邊會變 X[ i ] 倍。你可以以任意順序使用放大燈，問至少要用幾個放大燈…

Problem - C - Codeforces題意： 有 N 樣物品，用價格和價值描述。一樣物品可能是要用 C 類貨幣購買，也有可能是要用 D 類貨幣購買。選兩個相異的物品購買，使得價值總和最大。輸出價值總和。制約： The first line contains three integers n, c and d (2 ≤…

Problem - A - Codeforces題意： 有 N 張卡牌，正面和反面各有一個非負整數。現在兩個人玩遊戲，每場開局每張牌會均勻隨機呈正面向上或背面向上。把 N 個呈現在上的數字當做 N 堆的石頭，進行 Nim 的遊戲。雙方絕頂聰明的前提下，先手贏的機率為何。制約： T…

Problem - F - Codeforces題意： 有 N 隻老鼠，用座標描述。有 M 個洞，用座標和容量描述。一隻位於座標 x 的老鼠進到位於座標 y 的洞裡要花費 abs( x - y )。問最小花費總和為何，才能使所有老鼠進洞。制約： 1 ≤ N, M ≤ 5000 abs( X[ i ] ), abs( P[ i ] )…

Problem - D - Codeforces題意： 問 [ L, R ] 之間有多少整數，是可以被自身的所有非零數位整除。制約： T ≤ 10 1 ≤ L, R ≤ 9e18解法： 考慮 [ 1, x ] 的動態規劃： 一個顯然的狀態可以這樣定義： dp[ i ][ j ][ k ][ l ]: 考慮前 i 位，模 lcm( 1, 2, .. 9 …

Problem - E - Codeforces りんごさんの提出見て回答。題意： 有 N 個人，編號 1 到 N 要投票。投票可以使得當前的票數 +1 / +0 / -1 其中一個。每個人心目中都有一個期望票數，輪到他的時候他會依據當前的票數，操作使得接近他的期望票數。求對於所有 x，編…

Problem - D - Codeforces題意： 有 N 個城市，每對城市之間存在一個雙向路徑，每一條邊有一個死亡值 P。 一個路徑的死亡值是整條路徑上的邊的死亡值中的最小值。 對於每個城市 x，問一種方法，使得每個點對外都只留下一個有向邊，使得所有城市都會到達城市 …

Problem - C - Codeforces題意： 考慮一種整數的拆分方式，將一個數 x 拆分為 x = 1 + 2 + 4 + .. + 2^( k - 1 ) + r, 1 ≤ k and 0 ≤ r ≤ 2^k。原本有若干個數，進行這樣的拆分後，排序好，現在給你。問所有可能的原序列長度。制約： The first line contain…

Problem - B - Codeforces題意： 有 N 個人參加比賽，有五題，每個人的參數是五題的答對時間，沒有答對則以 -1 表示。一個人在一個題目的得分是這樣計算的： 考慮一個題，令 p 為答對人數，q 為參賽人數，則 p / q 對應到表格中的該題的最大分數。 對於一個…

Problem - A - Codeforces題意： 你現在寫了 y 個題目，答對了 x 個。你想知道你最少要再寫幾題才能有答對比率 p / q。若無解輸出 -1。制約： The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Each of the next t l…

Problem - 622F - Codeforces題意： 令 f( k, x ) = sum( pow( i, k ) for i in range( 1, x + 1 ) ) % ( 1e9 + 7 )。 問 f( K, N ) 是多少。制約： 1 ≤ N ≤ 1e9 0 ≤ K ≤ 1e6解法： 很神奇，還沒看到這題的時候我就有想過手算一樣的問題了，還蠻顯然是用拉格…

Problem - 622D - Codeforces題意： 要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列，使得以下 s 最小。 d[ i ] 為 i 處於的兩個位置形成的距離。制約： 1 ≤ N ≤ 5e5解法： 看解說，覺得非常神祕，遇到類似題應該還是不會。 主要想法是這樣，猜測可以直接…

Problem - 609F - Codeforces題意： 有 N 隻青蛙在一維數線上，用位置和舌頭長度描述。現在依序有 M 隻蚊子出現，用位置和營養值描述。一個在位置 x，舌頭長度 t 的青蛙可以吃位於位置 y 的蚊子若且唯若 x ≤ y ≤ x + t，而且這隻青蛙是所有能吃到這隻蚊子的…

Problem - 609E - Codeforces題意： 給一張圖，分別問每一條邊必須被選擇時的最小生成樹花費是多少。制約： N, M ≤ 2e5解法： 找出原圖的最小生成樹後，做倍增 LCA，同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹，直接輸出當前最小花費，否則…

Problem - 598C - Codeforces題意： 給 N 個非零向量，求任意一對夾角最小的向量對。資料規模： N ≤ 1e5解法： 極角排序。 atan2( y, x ) 回傳的範圍在 [ -pi, pi ] 之間，只有 atan2( 0, 0 ) 是未定義的。時間 / 空間複雜度： O( N lg N ) #include <bits/stdc++.h> using </bits/stdc++.h>…

Problem - F - Codeforces題意： 給 N 個元素的數列 A。問有幾種不同的非空子序列，其最大公因數不為 1。輸出方案數對 1e9 + 7 取模。制約： The first line contains one integer number n (1 ≤ n ≤ 100000). The second line contains n integer numbers a…

Problem - G - Codeforces題意： 給一個長度為 n 的 B 數列。現在將 B 數列黏貼 k 次變成一個新的數列。有 Q 筆詢問： op = 1: __將 [ l, r ] 中的元素全部更改為 x op = 2: __詢問 [ l, r ] 中的最小值制約： The first line contains two integers n and k…

Problem - E - Codeforces題意： 你在玩遊戲，一場有三種結果，勝/平/敗。你知道當你的勝利的場數和敗北的場數的絕對差在 K 以上時，會立刻退出遊戲。現在你有一個序列描述 N 場遊戲，而你知道你打完這 N 場後退出。有些紀錄被塗成 '?'，要你復原出一個合理…