Problem - D - Codeforces題意： 給一個亂的括弧序列，求有幾個不同 ( 任一元素來自原本序列的不同下標 ) 的子序列，是個正確的括弧匹配序列，且前半是 '('，後半是 ')'。資料規模： The only line of the input contains a string s — the bracket sequence…

7:00 起床，不想吃早餐，繼續睡 搭專車到公館校區，貌似有人太晚醒所以被要求自己來，好可怕 CF 跳到 1000 以下 AC 的題目開始寫 大部份挑分治跟動態規劃 早上教授拉 UVA 的題目要完成 一題水 SCC 一題水匈牙利 另一題作死網路流 中午吃青醬雞肉燉飯，超膩 …

Problem - D - Codeforces題意： 給 A 數列。求 min{ ( j - i )^2 + Sigma( A[ i + 1 .. j ] )^2, 1 ≤ i 資料規模： The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 1e4 …

Problem - 234G - Codeforces題意： 有 N 個人。輸出 N 場以內的遊戲，每一場用其中一隊的所有人的編號描述。必須滿足，經過每場後，每對人都有對局過。資料規模： N ≤ 1000解法： 考慮分治，經由遞迴假設左半和右半以滿足，那只要左邊在形成一對就可以。 如…

Problem - D - Codeforces題意： 問 N 個節點組成的二叉樹，深度不少於 H 的方案有幾種。資料規模： H ≤ N ≤ 35解法： dp[ i ][ j ] : N 個節點的二叉樹，深度等於 H 的方案數 兩種轉移，首先當前的根是一定要的，一種是左空或又空，另一種是兩個都非空。時…

Problem - 128C - Codeforces題意： 給一個 N * M 的矩形。現在要做 K 次操作，每次需將原本的矩形嚴格變小，但必須邊長都是整數。問方案數對 1e9 + 7 取模。資料規模： 1 ≤ N, M, K ≤ 1000解法： 二維問題很常有的一個技巧，那就是發現兩個維度獨立。 考慮…

Problem - 314C - Codeforces題意： 給一個 N 個數組成的數列 A。現在有人把 A 的所有相異的非遞減子序列都生出來了。輸出，對這些子序列分別求，不比該子序列的字典序大的所有子序列的方案數，的總和，對 1e9 + 7 取模。資料規模： The first line contains…

Problem - D - Codeforces題意： 給一個 N 個正整數組成的 A 數列。可以選一個連續區間，並決定每個數值分別的正負號，但其總和必須為 0 才合法。問有幾種合法的選取方式，選取方式相異若左界或右界不同，或任意一個元素分配到的正負號不同。輸出方案數對 1e…

Problem - 215D - Codeforces題意： 有 N 個地點要依序拜訪。每個地點都要叫至少一台車，一台車的花費為 cost。車的溫度為 t，學生能忍受的溫度為 T。一個車內如果有 x 個學生，那麼該車的溫度為 t + x。對於一個車，如果車的溫度大於 T，在車裡面的所有學生…

Problem - 404D - Codeforces題意： 給一個字符串，裡面只有 0, 1, 2, *, ? 五種符號。如果是數字，表示左右的 * 個數加起來一定有那麼多。如果是 ? 代表未確定。求有幾種 ? 的代入方式使得序列合法，對 1e9 + 7 取模。資料規模： The first line contains s…

Problem - 431D - Codeforces題意： 給 M, K。求一個 N，滿足 1 ≤ N ≤ 1e18 且在二進制下，[ N + 1, 2 * N ] 中恰有 M 個數恰有 K 個 1。資料規模： The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1e18; 1 ≤ k ≤ 64).解法： 直覺…

Problem - 156C - Codeforces題意： T 筆測資。每次給一個字串。有一種操作可以進行：選取兩個不同位置的字符，一個變成字典序小一的字符，另一個變成字典序大一的字符。特別的，a 沒有字典序小一的字符，z 沒有字典序大一的字符，而沒有相應的字符就不能進…

Problem - 768E - Codeforces題意： N 堆石頭，輪流取，不能取的輸。對於某一堆石頭，不能拿走同個數量的石頭兩次。求後手勝敗。資料規模： First line consists of a single integer n (1 ≤ n ≤ 1e6) — the number of piles. Each of next n lines contains…

Problem - D - Codeforces題意： 求長度為 N 且沒有領導 0 的正整數中，有多少數字存在一個非 0 的後綴 y，使得 k 整除 y。輸出方案術對 m 取模。資料規模： Input consists of three integers n, k, m (1 ≤ n ≤ 1000, 1 ≤ k ≤ 100, 1 ≤ m ≤ 1e9).解法： dp[…

Problem - E - Codeforces題意： 給一個無向圖，有些邊是壞掉的。求一個 1 走到 N 的最短路徑，使得此路徑壞掉的邊最少，且路徑外沒壞掉的邊最少。資料規模： The first line of input contains two integers n, m (2 ≤ n ≤ 1e5, ), the number of cities an…

早上鬧鐘設 6:30，快 7:00 才離開被窩，氣溫 13 度 打理一下之後，就抱著不安的期待下去迎接自助早餐 選項大概有什錦麵、沙拉、西瓜等等，但我只吃得下吐司，幸好奶油跟果醬都不錯 然後有鮮奶跟柳橙汁，我狂喝柳橙汁 快 8 點上車，原來新店這裡到公館師大還…

這次是到公館的師大，到了之後領個便當，然後就待待待，待到快 19 點，接著就回旅館了 旅館跟去年比起來真的太好了QQ 好到會感動 然後室友要考 AIME，今晚就沒跟我住了 一個人在雙人房裡，超爽！！！！ 邊聽音樂邊愜意地寫題目，覺得人生都值了 想說要調整一…

Problem - 547C - Codeforces題意： 給 N 個數字的數列 A。接著 Q 筆操作，每次將 A[ idx ] 取出 / 放入一個櫃子。求每次操作完，櫃子裡有多少無序對，其最大公因數為 1。資料規模： N, Q ≤ 2e5 max{ A } ≤ 5e5 TL: 2000 ms解法： 令 p 序列為當前櫃子裡的值…

Problem - E - Codeforces題意： 有 N 個堆，第 i 個堆有 S[ i ] 個元素，每個元素都有權值 C[ i ][ j ] 。玩家 A 每次選一個堆，取最上面的元素，玩家 B 每次選一個堆，取最下面的元素。玩家 A 開始，並輪流操作。求雙方最大化自己的權值總和為前提，玩家 A…

Problem - D - Codeforces題意： 給 K，求一個無向圖鄰接矩陣，使得節點 1 到節點 2 的最短路徑恰有 K 個。資料規模： 1 ≤ K ≤ 1e9 輸出的圖的節點數 ≤ 1000解法： 考慮二進制枚舉，需要 *2 就往右連一個菱形，需要 +1 就從節點 1 連到當前的終點。 #include <bits/stdc++.h></bits/stdc++.h>…

https://www.hackerrank.com/challenges/hyperrectangle-gcd題意： 有 K 個箱子，裡面分別有 [ 1, N[ i ] ] 的數字。現在要從每個箱子里抽一個數字，求其最大公因數。問所有取法可以產生的最大公因數總和。資料規模： Constraints 1 2 1 p.s. T * nk * K 明…

https://www.codechef.com/problems/COPRIME3可以先看這個連結了解 Mobius Inversion 是什麼： A Dance with Mobius Function - Posts - Quora題意： 給 N 個數字的數列 A，問有多少對 ( i, j, k ) 滿足 i 資料規模： N ≤ 1e5 1 ≤ A[ i ] ≤ 1e6解法： 和上方…

Problem - B - Codeforces題意： 給 N 個元素的序列，M 筆詢問，問考慮 A[ L, R ] 有多少不同的數字 A[ x ] 出現恰好 A[ x ] 次。資料規模： The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1e5) — the size of array a and the…

3866 -- Exclusive Access 2題意： 給一個 N 個無向邊的圖。求一種方案使所有邊定向，並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模： N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母，數量不超過 15。 TL: 5000 ms ML: 655…

1065 -- Wooden SticksDilworth Theorem題意： T 筆測資。給 N 個座標，求排序後最少的相鄰對數滿足右邊的點不在以左邊的點為原點的第一象限 ( 在線上也算第一象限 )。資料規模： The input consists of T test cases. The number of test cases (T) is give…

ZOJ :: Problems :: Show Problem題意： 給 N 個 M 維的向量，並給關於每個維度的權值 W。求兩個不同的向量，使得兩個向量在每個維度的差的絕對值乘上對應的權值，總和起來最大。輸出最大總和。資料規模： There are no more than 15 cases. Process to the …

Problem - B - Codeforces題意： 有 n 個人，現有一個 a * b 的土地。可以任意伸長寬和高，希望面積不小於 6 * n 的前提下，面積最小，求最小面積和對應的長寬。資料規模： n, a, b ≤ 1e9 TL: 1000 ms解法： 不失一般性假設 a ≤ b，顯然最佳解的 a 的上界為 …

2127 -- Greatest Common Increasing Subsequence題意： 給兩個數列 A, B，長度分別為 N, M，求最長公共遞增子序列。資料規模： 元素大小在 int32 範圍 N, M ≤ 500 TL: 2000 ms解法： 顯然可以定義 O( N^3 ) 的 dp，但這裡考慮 O( N^2 )。 dp[ i ][ j ] : B[…

Problem Description: You are given a string S. You want to find minimum length of string A, such that you could print S with A stamped on a paper arbitrary times. When making a new stamp, it is allowed to cover part of the string on the pa…

Problem Description: Given N, you want to know max{ LCM(x,y,z), 1≤x,y,z≤N }.Constraints: 1≤T≤1000 1≤n≤1e6Sample Input: 3 7 9 100Sample Output: 210 504 960300Solution: It is obvious that we would like some of the largest x, y, z, such that …