1032 - 土撥鼠 (Groundhog) | TIOJ INFOR Online Judge 對 ( a, b ) 加邊的時候，對 a 的 val 加上 ( a, b ) 的雜湊函數值，對 b 的 val 減下 ( a, b ) 的雜湊函數值 詢問的時候判斷是否對所有 u 的 val 相加總和為 0。 #include <bits/stdc++.h> using namespace std; type</bits/stdc++.h>…

1276 - 對稱之山 (Mountain) | TIOJ INFOR Online Judge 題意： 求最長回文子字串長度 題解： 同學縮隨便 dp 就可以過了 ??!!! 本來要寫 SA ( N lg N )，想想有 codebook 就寫 O( N ) 的 SA 拿出 codebook 後看到這個 完全不知道在幹麻就 AC惹後注： 可以用…

1423 - 直線線段相交問題 (Intersection) | TIOJ INFOR Online Judge 枚舉所有點對，算出其直線方程式 ay + bx + c = 0 之後，判斷其他的點中有多少在這個直線方程上( 座標帶入後右式正 )，和下( 右式下 )，相乘後取總和。 #include <bits/stdc++.h> using namespace std; t</bits/stdc++.h>…

1170 - 競技場 (Arena) | TIOJ INFOR Online Judge dp[ i ][ j ] : 考慮 [ i, j ] 區間時，最大的獲益 dp[ i ][ j ] = max{ max( dp[ i ][ m ], dp[ m + 1 ][ j ] ) + sum( i, m ) * sum( m + 1, j ) | for all i ≤ m and m + 1 ≤ j } sum( i, j ) = sum of …

Problem - D - Codeforces 二分搜答案，對於所有考試，一定考最後一個日期，這時候就變區間置點問題，所有考試對應一個區間，且在該區間必須放置 k 個點。 注意考試時不能讀書。 bool cmp( pii a, pii b ){ if( a.first != b.first ) return a.first > b.fir…

D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Beginner Contest 045 | AtCoder 考慮每個點在分別在九宮格的每個可能位置上的那九宮格數量。對於每個那樣的點那樣的位置，增加對應的塗色數計數。由於包含 x 個點的九宮格會被算 x 次，最後要做一次除法…

事隔一年，看題目覺得都好水。。。當初是有多傻才沒辦法拿個能看得分數。

dp[ i ][ j ][ t ] : 到達 ( i, j ) 時，有無使用過炸彈( t )，此時最小的總值 因為可以上下左右彎來彎去，所以用 dijkstra 更新。 tuple 真好用。 #include <bits/stdc++.h> using namespace std; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< vv</bits/stdc++.h>…

dp[ i ][ j ] : 考慮完 B 字串的第 i 個字元，其尾端有 j 個字元是 A 字串的前綴，且B不含A，此時修改次數的最小值。 修改最後一個字元之後，尋找其最長的後綴使 A 的前綴與之相同。這部分用預處理。 #include <bits/stdc++.h> using namespace std; typedef vector< int > </bits/stdc++.h>…

暴力判斷就可以了。 顯然把最強的K + 1個依序跟對手最弱的K + 1個比，一定最優。 #include <bits/stdc++.h> using namespace std; typedef vector< int > vi; typedef vector< vi > vvi; typedef pair< int, int > pii; typedef vector< pii > vp; int K, N; vi S; // team </bits/stdc++.h>…

把其中一個字串的0和1對調就是標準的 LCS。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef pair< int, int > pii; template< class T1, class T2 > bool upmin( T1 &x, T2 v ){ if( x</bits/stdc++.h>…

時間複雜度很神秘混沌的題目。竟然這樣暴搜就可以過了。如果有人可以提出證明它是好/壞的，請務必告訴我。 用質數篩法把質數表先建出來後，對每次的詢問進行遞迴求解，無需剪枝。 注意不能減去比當前的數字大的質數，你會花很久時間才發現你是怎麼逾時的。 #…

Problem - D - Codeforcesdp[ i ][ j ][ k ] : number of minimum moves for a state described by ( i, j, k ), i int N; int dp[ MAXN ][ MAXN ][ MAXN ]; pii move[ MAXN ][ MAXN ][ MAXN ]; vi pre[ MAXN ][ MAXN ][ MAXN ]; string edge[ MAXN ]; typed…

Problem: Given N, N points on a 2D plane, and a value K, find the maximum D such that all points can be distributed into K non-empty subsets, where D is the minimum distance between any pair of points not in the same subset. Analysis: Cons…

Problem: Given a string s, number of operations N, operations as triples ( a, b, c ), for each moves s[ a, b ] behind the xth character after the new string, output the final string. Analysis: This could be easily done with binary search t…

A set that allows kth_element. ( Insert and remove does not allow duplicate ) struct rbst{ int val, size; ll sum; rbst *lc, *rc; rbst( int _v ) : size( 1 ), val( _v ), sum( _v ), lc( NULL ), rc( NULL ){} void pull(){ sum = val; sum += lc ?…

Referenced from here. // O( V + E ) #include <bits/stdc++.h> using namespace std; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< int > vi; typedef vector< vi > vvi; int MAXV; int var_inv( int x ){ // 1 idx if( x <= MAXV ) return </bits/stdc++.h>…

Note that only negative cycles that are reachable from the source should exert their influence on the other nodes that could be reached from them. const ll LINF = 1LL << 60; void solve(){ int N, M; cin >> N >> M; vvp G( N ); for( int i = 0…

O( 2^N * N^2 ) Given a weighed graph, we are to find the minimum distance of starting from some node, travelling through each other node exactly once, and coming back to the start. Since that will form a cycle, we can start at any arbitrar…

The first doubling SA that worked... This post will be updated soon. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e4 + 4; char s[ MAXN ]; struct suffix_array{ // O( N lg N lg N ) int n; vector< int > sa; suffix_array( const char *s ) :</bits/stdc++.h>…

Counts the frequency of each pattern in text. O( SIGMA( | P | ) ) string T; vs pattern; map< char, int > mci; struct node{ int val; int nxt[ 6 ]; }; vector< node > tree; int cnt = 1, num = 0, n; vi f, lst, occ_cnt; queue< int > que; map< s…

Burrows-Wheeler Transform and its inverse. See this and this. // BWT, O( N ^ 2 lg N ) due to SA string s; int slen; vi sa; bool sa_cmp( const int i, const int j ){ return s.substr( i, slen ) < s.substr( j, slen ); } void solve(){ cin >> s;…

Here are only a few rough notes I have grasped recently, and would probably not make much sense to any of you.First, it is proved that all NP problems ( Hamiltonian Path, Graph Coloring etc. ) can be reduced to SAT problem. One example is …

search - Ukkonen's suffix tree algorithm in plain English? - Stack Overflow Suffix tree. Ukkonen's algorithm - Codeforces struct suffix_tree{ char s[ MAXN ]; map< int, int > to[ MAXN ]; int len[ MAXN ], fpos[ MAXN ], link[ MAXN ]; int node…

// multiple pattern -- a.k.a. aho-corasick // O( T + P ) string text; vs pattern; struct trie{ vector< trie* > ch; trie *sfx; // suffix link: links to the end of the longest matched suffix trie *dict_sfx; // links to the end of suffix link…