Problem - 126B - Codeforces 題意： 給一個字串，求最長子字串，滿足存在一個前綴和它相等，一個後綴和它相等，一個非前綴也非後綴也和它相等。 解法： 先預處理字串的 rolling hash，接著把滿足所有前綴和後綴相等的長度押入一個有序容器。 接著對那個容器…

PEG Judge - IOI '15 - Sorting 首先我們要想到，如果 k回合內能完成，那麼 k + 1回合內一定也能完成，這是很顯然的，因為對方換了什麼，換回來就行了。所以我們可以進行二分搜，現在問題就簡化成要在O( n ) 判斷 k回合內可不可能達成。 接著要發現，設原始…

http://sprout.tw/oj/pro/72/ 一個三分搜模板。每次總是縮小至少三分之一的搜索範圍，慢慢走往凹點。 #include <cstdio> int n; double a[10], b[10], c[10]; double S(double t){ double mx = 0; for(int i = 0; i < n; ++i) if(a[i]*(t-b[i])*(t-b[i])+c[i] > mx) </cstdio>…

Bug Party | Aizu Online Judge 很容易想到，如果固定最小值b，那麼我們必須由小到大拿進所有a，直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和，條件形式複雜，如果不加功夫用持久化線段樹亂搞…

D: 高橋君ボール1号 - AtCoder Beginner Contest 026 | AtCoder 精度が怖い。 出力するものがたとえ1e-10の誤差だけあったとしても関数が出るものに1e-5ぐらい影響がまだるので、ちゃんと限界まで行かないとやばい。 #include <bits/stdc++.h> using namespace std; const i</bits/stdc++.h>…

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder Search for the minimum height that is possible. Judge by the deadline, which should be pre-calculated and sorted. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXH = </bits/stdc++.h>…

Problem - D - Codeforces If a bound is set, i.e. to construct a way to buy k gadgets before some day x, we have an obvious greedy strategy where we will choose the cheapest currency days for both currency, then we will enumerate the number…

http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day2.pdf guess: 数当て (Guess Them All) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 首先可以用 O( N )把 1的位置給找出來，接著對其他每個數字分別做區間的二分搜，找出它的位置。例如要找…

UVa Online Judge 移項一下就能得到方程式 h[ i ] = ( h[ i - 1 ] + 1 ) * 2 - h[ i - 2 ]，所以只要前兩項確定，後面所有都會跟著唯一確定。前面的項越小，後面的項一定就成關係的一齊變小，所以二分枚舉第二項可不可行就好了。 注意輸出前要再呼叫一次 ok(…

UVa Online Judge 馬上會想到二分搜最大速度，而判斷的部分就會變成經典的置點問題。每個點 ( 作業 )都有左界和右界，只能將它置於其中。一個經典的算法是先將每個點以其左界限制做排序，然後由左到右依次考慮每個位置該放置哪個點，這部分可以利用優先佇列…

Problem - E - Codeforces We are to find x that will give minimum for max{ ABS( SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) ) Ɐ 1 ≤ i ≤ j ≤ n }. Let us first remove absolute and get max{ max{ SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) Ɐ 1 ≤ i ≤ j ≤ n }, max{ - SUM( a…

UVa Online Judge 可以先依據邊的溫度求最小瓶頸生成樹，但這裡生成的條件是起點和終點為同一個連通分量即可。求出最小溫度後對這些邊求起點至終點的最短路徑就行了。無聊寫了SPFA跟Dijkstra，運行時間一模一樣。 #include <bits/stdc++.h> using namespace std; const int </bits/stdc++.h>…

UVa Online Judge 由於順序無關，我們可以將每個操作獨立出來，令 dsum( u ) 為作用在 u 上的所有 d 權和，那麼對於一個邊 u -> v，它的最終邊權是 w( u, v ) + dsum( u ) - dsum( v )。由於題目要求最小值極大化，我們考慮二分搜尋，假設最小值的最大可能為…

UVa Online Judge 要求平均權值極大化，一個很常用的技巧是假設平均權值為 x，如果我們將全部的值減去 x以上的值，或全部減去 x - 1以下的值，前者和後者的差異在總和小於 0和大於 0。題目特別要求的是環，所以我們發現我們可以二分搜尋最接近正確答案的 x，…