Problem - A - Codeforces題意： 有 N 個人，用一個 01 序列描述，0 代表小孩，1 代表大人。給定 C1, C2，你要將這些人分群，使得每個群至少有一個大人，而且最小化 sum( C1 + C2 * ( X[ i ] - 1 )^2 )，其中 X[ i ] 代表第 i 個群的人數。制約： The first …

Round #25 (Div. 2 only)題意： 給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1，轉換後，所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右，且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。制約： 1 ≤ N, M ≤ 1000解法： 將…

Round #25 (Div. 2 only)題意： 給一個排列 1 ~ N，問最長的一個子序列，滿足：頭尾元素都比所有中間的元素大。輸出長度。制約： 1 ≤ N ≤ 1e5解法： 不失一般性，假設最長的這個子序列的頭 i 和尾 j 滿足：i 枚舉所有 i，令 j 為 i 顯然這個 j 是最優的，而…

No.489 株に挑戦 - yukicoder題意： 買賣股票，買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i 制約： 2 ≤ N ≤ 1e5 1 ≤ D 1 ≤ K ≤ 1e6 1 ≤ xi ≤ 1e6解法： 努力寫了一次線段樹，但 python 也很給力的 TLE 了。 經典的滑動視窗： window[ i ]: i …

No.497 入れ子の箱 - yukicoder題意： 給 N 個箱子，用三維各自的長度描述。一個箱子 i 容得下另一個箱子 j 若且唯若 X[ i ] > X[ j ] and Y[ i ] > Y[ j ] and Z[ i ] > Z[ j ]。問最多可以形成多少幾層的箱子。制約： 1≤N≤1000 1≤Xi,Yi,Zi解法： 依最小的…

No.502 階乗を計算するだけ - yukicoder題意： 給 n，求 X： X = n! mod (1e9+7)制約： 0 ≤ n ≤ 1e18解法： 首先 n ≥ 1e9 + 7 時，X 顯然為 0。 本地建表，將 1e7 的倍數都填上去，那麼計算量便是至多 1e7。 MOD = int( 1e9 + 7 ) ''' Used for offline prep…

No.496 ワープクリスタル (給料日前編) - yukicoder題意： 你有 N 顆一次性的魔法石頭，第 i 顆可以幫你在 X 軸上 + X[ i ]，Y 軸上 + Y[ i ]，但花費魔力 C[ i ]。你現在在 ( 0, 0 )，你的目的地是 ( Gx, Gy )。另外一種移動方式是向上或向右一格，花費 F。…

No.491 10^9+1と回文 - yukicoder題意： 給 N，問有幾個數字不超過 N，是 1e9 + 1 的倍數，並且是迴文。制約： N ≤ 1e18解法： 怒猜超過 1e9 之後不會有迴文了。( 求證明 ) 所以要求的其實是 1e9 以下的迴文數。 因為是迴文，所以只要枚舉左半邊，也就是大約…

Dashboard - Qualification Round 2017 - Google Code Jam題意： 給 N * N 的棋盤，以及一些士兵。士兵有三種 : { 'x', '+', 'o' }，若沒有士兵用 '.' 描述。一個格子至多一個士兵。士兵配置的規則如下： 1. 任意兩個在同個水平或鉛直線上的士兵，必須有其中…

Dashboard - Qualification Round 2017 - Google Code Jam題意： 有 N 個空間排成一排，有 K 個人依序決定自己要進哪個空間。令一個空間 i 的左邊連續空房間的數量為 L[ i ]，右邊連續空房間的數量為 R[ i ]，那麼任何人都會優先考慮 min( L[ i ], R[ i ] ) …

Dashboard - Qualification Round 2017 - Google Code Jam題意： 問不超過 N 的最大的，以十進制表示時，由左到右檢視，數字呈非遞減的數為何。制約： 1 ≤ T ≤ 100. 1 ≤ N ≤ 1e18. 解法： 一開始寫數位統計 dp 寫到快哭出來。 仔細想想，只要倒著決定就可以…

Dashboard - Qualification Round 2017 - Google Code Jam題意： 給一個由 '+', '-' 組成的序列。問能不能透過任意次操作將該序列全部元素變成 '+'。操作只有一種，將連續 K 個元素內容反轉。制約： 1 ≤ T ≤ 100. Every character in S is either + or -. 2 …

F: Infinite Sequence - AtCoder Regular Contest 071 | AtCoder題意： 問有多少無窮長度數列 A[] 滿足： 1. i 的下一個元素開始連續 A[ i ] 個皆相同 2. 對所有的 N ≤ i, j，A[ i ] = A[ j ] 輸出答案對 1e9 + 7 取模。制約： 1≤n≤1e6 n は整数解法： 首先…

D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder題意： 在二維座標系上，給 N 個縱線，M 個橫線，問所有可形成的四邊形面積總和。輸出答案對 1e9 + 7 取模。制約： 2≤n,m≤1e5 xi,yi は整数である。解法： 首先顯然兩個維度可以獨立看待，因此考慮…

E: TrBBnsformBBtion - AtCoder Regular Contest 071 | AtCoder題意： 給字串 S, T。Q 筆詢問，指定 S 的某個子字串 S'， T 的某個子字串 T'，問是否能透過施行以下操作任意次由 S' 轉換為 T'。 1. 將 'A' 換成 "BB" 2. 將 'B' 換成 "AA" 3. 將 "AAA" 換成 "…

C: 怪文書 / Dubious Document - AtCoder Regular Contest 071 | AtCoder題意： 給 N 個字串，求一個最長的字串，若相同則字典序最小，使得每一個字串都能透過任意刪除、交換位置得到。制約： 1≤n≤50 i=1,…,n に対して、 1≤|Si|≤50 i=1,…,n に対して、 Si は…

Problem - E - Codeforces題意： 給 N, M，求： 資料規模： The only line contains two integers n, m (1 ≤ n, m ≤ 1e13) — the parameters of the sum.解法： 首先觀察到 因此所求可以寫成 考慮比較簡單的這個問題： 這個的求法是基於平方分割，細節和這篇…

Well, I know that posting this might no be completely appropriate but...題意： 問 [ 1, 1e15 ] 所有整數的因數平方總和為多少。解法： 也就是平方分割，而枚舉 d 轉換成枚舉 N // d 那部分我一直很搞不清楚，但其實只要知道這件事就可以理解： 這件事成…

Problem - 327C - Codeforces題意： 給一個大數 A，將其複製 K 次連接成一個新的大數 S。問有多少種方法任意刪除 S 中的數字，使得留下來的數字被 5 整除。允許領導 0，但不允許空字串。兩個方法相同若且唯若兩個方法刪除的數字的位置都是一樣的。資料規模：…

Problem - B - Codeforces題意： 給正整數 N，問有多少正整數不超過 N，在十進制下可以用不超過兩種數字表示。資料規模： N ≤ 1e9解法： dp[ i ][ j ][ k ][ l ]: 已處理 N 的長度為 i 的前綴，已使用的數字是 ( j, k )，滿足 j 用 python 的編程瓶頸在於宣…

Problem - B - Codeforces題意： 很水，不太重要，這裡記錄 python 的讀 / 寫檔。 前三行有，就等價 C++ 開了 freopen() import sys sys.stdin = open( 'input.txt', 'r' ) sys.stdout = open( 'output.txt', 'w' ) N, K = map( int, input().split() ) K -=…

Problem - D - Codeforces題意： 給一個長度為 N 的數列 A[]。T 筆詢問，問對 [ L, R ] 中存在的所有相異數值 s，SUM( K[ s ] * K[ s ] * s ) 是多少。K[ s ] 代表 [ L, R ] 區間中，s 出現的次數。資料規模： First line contains two integers n and t (1 …

Round #23 (Div. 2 only)題意： 給 N 個相異正整數，問最少要移除幾個數字，能使任意兩個數字的和不為質數。輸出方案。限制： 2≤N≤2000 The elements of S are distinct integers between 1 and 10^5解法： 首先顯然偶數+偶數以及奇數+奇數的情形一定不會產…

Round #23 (Div. 2 only)題意： 給若干個中心，現在你要以這些中心擺放圓。有左數起第 i 個圓的半徑可以是 [ L[ i ], R[ i ] ] 中任意整數。兩個相鄰的圓必須相切。問有幾種方案。限制： 2≤N≤1e5 The point coordinates are given in increasing order and t…

Round #23 (Div. 2 only)題意： 給一個長度 M 的排列 P，現在要做一個 N * M 的矩陣，第 i 行是 P^i( P )。 問 M 個列分別的數值總和為何。限制： 1 ≤ N, M ≤ 1e5解法： 顯然會形成一些循環，用 dfs 找出這些循環並記錄每個節點在每個循環中哪個位置，預處理…

Round #23 (Div. 2 only)題意： 有 N 個城市，以座標描述。兩個城市之間的移動的所需時間是曼哈頓距離。有些城市是特別的 ( S = 1 )，特別的城市之間可以花費 T 單位時間進行瞬間移動。Q 筆詢問，每次問兩個城市之間最少需要花費的移動時間。限制： 2≤N≤1000…

Problem - 301A - Codeforces題意： 給一個長度為 2 * N - 1 的數列 A。你可以進行任意次以下的操作： 選擇任意 N 個相異的元素，讓他們的符號反轉 ( 乘上 -1 )。 問操作後，可以得到的最大數列和為何。資料規模： The first line contains an integer n (2 …

Problem - E - Codeforces題意： 給一個 N * N 的鄰接矩陣表示 ( i, j ) 間的邊的距離。問最遠點對的距離為何。 但是，規定不能用類如 for, while, repeat 等關鍵詞 ( 詳見題目本身 )。資料規模： The first line of the input contains a single integer N …

Problem - B - Codeforces題意： 這是愚人節題，瓶頸貌似是在要花點時間把這稍微被打亂的文章看完。 總之題意就是給 M, R，問 [ 0, ∞ ] 這些整數中，有多少百分比的 d 對任意一個 0 ≤ i 資料規模： N, MAXM, MAXR ≤ 16解法： 顯然會以 LCM 為單位形成週期。…

Problem - E - Codeforces題意： 給 N 個數字的數列 A[]。你可以選至多 K 個數字，將它們變成自己的階乘，這個操作對同一個元素只能使用一次。問有幾種方法可以得到一個子集合，其總和恰為 S。兩種方法相同若且唯若集合相同且施加的操作相同。資料規模： The…