Entries from 2017-03-01 to 1 month
http://main.edu.pl/en/archive/oi/2/mud題意： 首都在 ( 0, 0 ) 的位置，有 M 個人在首都裡。接著有 L 條線，每條線有若干個城市，依序用線上和前一個 ( 第一個城市和首都 ) 的距離以及人數描述。要求選一個點使得所有人到該點的總花費最小，一個人行走一單…
http://main.edu.pl/en/archive/oi/2/kpk題意： 給一張圖，有若干障礙物，給始點和終點，問是否可以不左轉不倒回從始點走到終點，可以的話輸出最短路徑的方案。資料規模： In the first line of the standard input there are two integers separated by a s…
http://main.edu.pl/en/archive/oi/2/pal題意： 給一個字串，問最多和最少可以拆分成幾個偶數長度迴文，存在的話輸出方案。資料規模： The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. …
http://main.edu.pl/en/archive/oi/2/drz題意： 這裡限制樹的每個節點的兒節點必須是 0 或者 2，否則不稱做樹。 給編號由小到大的葉節點的深度，求樹是否存在，存在的話輸出每個節點的父節點編號，以及樹的括號序列表示。資料規模： In the first line of th…
UVa Online Judge題意： 給 12 條邊各自的顏色，顏色是 [ 1, 6 ] 間的整數，問可以組成多少種不同的立方體。旋轉後相同則視兩立方體相同。資料規模： The first line of input contains T (1 ≤ T ≤ 60), the number of test cases. Then T test cases follow…
UVa Online Judge題意： 給一個 R * C 的圖，保證周圍都是牆( # )，也不能拜訪 ( X )，起點在 ( S )，問在拜訪最多 ( * ) 的前提下，最短迴路的最小字典序序列序列是什麼。資料規模： The input file contains no more than 20 test cases. The details of e…
Problem - B - Codeforces題意： 給一個字串，你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。資料規模： N, K ≤ 1e5 TL: 1000 ms ML: 256 MB解法： 因為 K 很小，所以按字典序小的出隊，接上自己後一個字符再丟回一個優先隊列…
Problem - 228E - Codeforces題意： 給 N 個點 M 條邊，邊有邊權 0 或 1。每次操作選取一個點，將和此點連接的所有邊的權值反轉。問存不存在一種反轉方式可以讓所有邊的邊權變為 1，若有則輸出方案。資料規模： N ≤ 100 解法： 考慮每個邊，其實只能被兩端點…
ACM-ICPC Live Archive題意： 給兩個字串 A 和 B，你要選擇一個 [ L, R ] 使得所有滿足 L ≤ x ≤ R 的 x 都滿足 A[ x ] ≠ B[ x ] 的比率佔長度的 p% 以下。求最長長度。資料規模： N ≤ 1.5e5解法： 考慮對 A[ x ] ≠ B[ x ] 先做前綴和，令前 x 個字符裡相異的…
Problem - D - Codeforces題意： 問有多少 A, B, C 數列的組合，使得 ( A[ i ] + B[ i ] ) % N = C[ i ]，且 A, B, C 都是 [ 0, N ) 的排列。資料規模： The single line contains integer n (1 ≤ n ≤ 16). TL: 1500 ms ML: 256 MB解法： 有用到這題的結論，…
Problem - 19B - Codeforces題意： 有 N 種商品各一個，若購買第 i 種商品，需要花費 C[ i ] 單位的錢，但是可以得到 T[ i ] 單位的店員不注意的時間，而店員不注意的時間每單位可以供你偷一件尚未購買的商品。問你最少要付多少錢才能獲得所有商品。資料規模…
今天一整天是自習 聽說一模的第三題賽後評分結果明天會公佈 一整天實在是沒什麼力，只有打五題 師大這邊貌似西餐廳修禮拜六、中餐廳休禮拜日 不過今天西餐廳廚師遲到，挨餓許久 但吃得實在有點膩，跟第一次吃相比可以感覺撐很多，絕對不是因為份量變多 聽到…
Problem - C - Codeforces題意： 給一個長度為 N 的大寫英文字母組成的字串，一次操作可以將任一兩相鄰字符交換，問最少要多少次交換才能使得 "VK" 不以子字串形式出現。資料規模： The first line of the input contains an integer n (1 ≤ n ≤ 75) — the l…
Problem - 13C - Codeforces完全就是同一個題 只是這題要滾動才不會 MLE，然後詢問的是非遞減，所以不需要用到減下標的技巧。題意： 給一個陣列 A，可以任意讓值 +1 或 -1 任意多次，問最少要幾次才能將 A 變成非遞減數列。資料規模： MAXA ≤ 1e9 N ≤ 5000 T…
Problem - 11D - Codeforces題意： 給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。資料規模： N ≤ 19 TL: 2000 ms解法： 考慮一個環，選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊，假設原本是 abcd 這樣的環，那其實可以用點的集合和…
Problem - 8C - Codeforces題意： 給原點 ( sx, sy )，以及 N 個座標 X, Y。每次至多選兩個座標，依序拜訪完後，回到原點。問最好的路徑，使得路徑長最小。兩個座標的路徑長為歐幾里德距離的平方。資料規模： The first line of the input file contains the…
Problem - B - Codeforces題意： 給一棵邊權為 1 的樹，問所有有序點對的距離總和。資料規模： N ≤ 2e5 K ≤ 5 TL : 2000 ms解法： 考慮樹分治，分治後都是一個子問題。分別結算子樹本身的貢獻後，計算每個需要經過當前這個重心的點對的貢獻，以及以當前這個…
早上自習 複習 FFT，持久化結構，CRT 吃中餐廳，西餐廳沒開 吃一根巧克力棒 考試 13:00 ~ 17:15 主機爛所以 +15 分鐘 第一題給一個 01 矩陣，每個聯通分量用一個最小的矩形覆蓋，重疊的矩形又要被一個最小的矩形覆蓋，問最後所有矩形的左上座標右下座標。我…
Problem - 257D - Codeforces題意： 給數列 a，滿足 a[ i ] ≤ a[ i + 1 ] ≤ 2 * a[ i ]。要求對每項定正負，使得總和介於 [ 0, a[ 0 ] ]。資料規模： The first line contains integer n (1 ≤ n ≤ 1e5) — the size of the array. The second line contains s…
Problem - G - Codeforces題意： 給 M 個工作時間，N 個人的特徵 D[ i ] 與 R[ i ]，代表第 i 個人在一天工作時，需要前 D[ i ] 單位時間預熱，然後才能開始算入工作時數，而每一天的工作時數總和起來需要 R[ i ]。問分別每個人會在第幾天做完他的作業，做不…
http://ioinformatics.org/locations/ioi16/contest/day2/paint/paint-TWN.pdf 1959 - [IOI 2016] Paint | TIOJ INFOR Online Judge題意： 給一個序列含 '.', 'X', '_'，分別代表該位置的字符為未知、必為黑色、必為白色。再給 K 個數字 C[]，代表由左到右看…
http://ioinformatics.org/locations/ioi16/contest/day2/messy/messy-TWN.pdf 1960 - [IOI 2016] Messy | TIOJ INFOR Online Judge題意： 你可以將任意數量的無號 n 位數丟 ( add_element() )進一個 set 裡面，然後呼叫 compile_set()，這個 set 裡面的所有…
1006 -- Biorhythms題意： 細節不好說明，但總之給 p, i, e, d，滿足聯立模方程式： ( x + d ) % 23 = p ( x + d ) % 28 = e ( x + d ) % 33 = i 求 x。解法： 就是一個中國剩餘定理模板。28 非質數，如果要用尤拉定理搞要先求 phi 函數才能求模逆元，但最近…
早上 7:45 起來集合搭車 車上大家都在討論各種樹套樹，持久化結構 問了 Problem Setter 發現原來昨天除錯很久的題目是隱藏多筆測資 全域變數也要初始化，然後就過了 早上想 IOI 題，結果看題解還是無法融會貫通 午餐吃青醬雞肉義大利麵 繼續想 IOI 題，還是…
Problem - E - Codeforces題意： 給一個矩陣，表示每對人之間的憎恨值。現在要把人划分為 K 群，每群必須都是連續編號的人。一個群的憎恨值貢獻是所有編號的有序對的憎恨值總和。求最少憎恨值總和。資料規模： The first line contains two integers n and k…
早上以為 7:45 集合，結果原來是 7:40 被記遲到了，可是坐在車子最後面哪聽得到輔導員說話啊ˊ_>ˋ 今天被開放可以去 7-11 買早餐 買了 39 元組合飯糰加果汁，果汁太甜好難過 早上上了這兩週唯一一個鬆課，想不太起來課程名字... 好像是時間管理吧 感覺去年的…
http://ioinformatics.org/locations/ioi16/contest/day1/molecules/molecules-TWN.pdf 1956 - [IOI 2016] Molecules | TIOJ INFOR Online Judge題意： 給 L, U, W, N, result，要你找一個在集合 S，使得該集合為下標的 W 的總和在 L 和 U 之間 ( 含 )，寫在…
Problem - E - Codeforces題意： 有 N 個價值的物品，每個都有無限多個。輸出拿恰好 K 個物品可以產生出的所有值。資料規模： The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of produc…
No.243 出席番号(2) - yukicoder題意： 有 N 位可分別的學生，現在你要分配 0 ~ N - 1 的座位給他們。每個學生都有一個不喜歡的座位編號。求每個人都不作到不喜歡的座位編號的方案數，對 1e9 + 7 取模。資料規模： 生徒の数Nが最初の行で与えられる。1≤N≤500…
Problem - E - Codeforces題意： 一開始你有一個序列 P = { 1, 2, 3, .. N }。處理 Q 筆永久詢問，給 L, R，將 P[ L ] 和 P[ R ] 交換後，輸出當前 P 的逆序述對數。資料規模： The first line of the input contains two integers n and q (1 ≤ n ≤ 200 000…
