D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder題意： 給相同節點數的兩個圖，對於每個點，求有多少點和它在兩個圖上都屬於相同的連通分量。資料規模： 節點數 2≦N≦2e5 兩個圖分別邊數 1≦K,L≦1e5 保證同一個圖不存在重邊 時限 2000 ms 記…

Problem - C - Codeforces題意： 給一個圖，每個節點都有一個連向另一個點的有向邊。求最小的 t，且 t ≥ 1，使得從每個節點 x 出發沿著有向邊走 t 次後達到的 y，從 y 出發沿著有向邊走 t 次也達到 x。若無法達成輸出 -1。資料規模： 節點數 1 ≤ N ≤ 100解法…

Problem - B - Codeforces題意： 給一個數列 A，和一個數 X。求數列中有多少無序對 ( i, j )，使得 A[ i ] XOR A[ j ] = X。資料規模： 1 ≤ n ≤ 1e5, 0 ≤ x ≤ 1e5 1 ≤ a[ i ] ≤ 1e5解法： 只要枚舉 i，就知道要求的另一個數是 X XOR A[ i ]。所以累加 X XOR …

Problem - A - Codeforces題意： 求 1378 ^ N 的最後一位數字資料規模： 0 ≤ N ≤ 1e9解法： 當 N = 0，是 1。 否則會循環，如 8, 4, 2, 6, 8, 4, 2, 6, ...時間 / 空間複雜度： O( 1 ) int N; void init(){ cin >> N; } void solve(){ // 1, 8, 4, 2, 6, 8, …

D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder題意： 給一個字串，每次可選取非兩端的任意字元使其消失，但前提是消失後不能有任意兩個相鄰字元相同。兩個人輪流做，先不能做的輸，求誰贏。資料規模： 3 ≤ | S | ≤ 1e5解法： 考慮最終狀態的…

No.179 塗り分け - yukicoder 平行移動するベクトルを枚挙し、チェックするだけ。 最大計算量はおよそ 100^2 * 50^2 少なくとも一つマスを塗るという制限に気をつけましょう。 #include <bits/stdc++.h> using namespace std; const string msg[] = { "NO", "YES" }; int in</bits/stdc++.h>…

No.85 TVザッピング(1) - yukicoder 証明が面白い。チェスをイメージしましょう。 kmjp.hatenablog.jp #include <bits/stdc++.h> using namespace std; const string msg[] = { "NO", "YES" }; signed main(){ int N, M, C; cin >> N >> M >> C; if( not ( N >= M ) ) swap(</bits/stdc++.h>…

Problem - C - Codeforces題意： 給一堆區間，求一個陣列，使得所有區間的最小 mex 最大。資料規模： 所求陣列長度 n, 區間數 m, 1 ≤ n, m ≤ 1e5 時限 2000 ms 記憶體 256 MB解法： 考慮最短區間，長度就是最大最小 mex。因為只要由左而右，小到大填數字，並…

キモい.... 説明するのにもキモい... c : 今もってるあたり数 b : 今まで買った数 e : 今まで食べた数 そこからリピートする部分を探して、バグ出さずに頑張っていじれば... #include <bits/stdc++.h> using namespace std; signed main(){ int N, K; cin >> N >> K; string</bits/stdc++.h>…

Problem - E - Codeforces題意： 給首領的編號，以及公司裡所有人各自的上級數量( 所有上級 )。求至少有多少人是謊報的。資料規模： 1 ≤ n ≤ 2e5, 1 ≤ s ≤ n 0 ≤ ai ≤ n - 1 時限 1000 ms 記憶體 256 MB解法： 首先檢查首領對不對，不對就直接改他。 接著看…

Problem - A - Codeforces題意： 一個方陣，初始所有值為 0，塞 1 進去，1 彼此不相鄰，且最後方陣必須上下、左右分別成對稱。給 1 的數量，求至少要邊長多少的方陣才能塞下。資料規模： 1 的個數 1 ≤ X ≤ 100解法： 先注意到因為必須對稱，奇數邊長的方陣一…

Problem - F - Codeforces前言： Codeforces Round #379 (Div. 2) F. Anton and School - pekempeyのブログ pekempeyさんの記事読んでやっとわかった。題意： 給相同長度的 B 序列和 C 序列。求是否存在一個 A 序列，滿足 不存在則輸出 -1，否則輸出滿足的任…

Problem - A - Codeforces題意： 給一行有標點符號，空格，和小寫英文字母的字串。求照英文書寫格式化後的樣子( 字與字之間一個空白，但標點符號和前面的字無空格 )。保證有解。資料規模： 一行含空白的字串，不超過 1e4 個字元。解法： 用 stringstream 讀…

1045 - A.細菌培養 | TIOJ INFOR Online Judge題意： 給矩形的座標，每次使矩形內的所有數字 * 2，初始時皆為 1，求所有操作後矩形內數字總和。資料規模： 座標 0 ≤ X, Y ≤ 10000 操作數 1 ≤ Q ≤ 200 時限 1000 ms 保證解 ≤ 8e18解法： 本來想用 imosu ( 前…

Problem - E - Codeforces題意： 給一棵樹，每個節點有顏色，黑或白。每次可以選一個同顏色的連通分量，將全部顏色反轉。求最少反轉次數，使得樹的所有節點同色。資料規模： 節點數 1 ≤ N ≤ 2e5解法： 先對原圖做連通分量縮點去想。如果用連通分量個數變化的…

Problem - C - Codeforces題意： 給若干個條碼，由六個 0 ~ 9 之間的數字組成。求一個最大 K，保證就算打錯 K 個數字，依然可以確定是哪個條碼。數據範圍： 條碼的數量 1 ≤ N ≤ 1000解法： 首先顯然如果 N = 1，那一定是 K = 6，全部打錯都行。否則顯然 K = …

Problem - B - Codeforces題意： 給通知的順序，若是新的人的通知則會到訊息版最上面，否則會將舊的人提到訊息版的最上面。求最終樣貌。數據範圍： 通知數 1 ≤ N ≤ 2e5 通知的人名 1 ≤ | name | ≤ 10解法： 在動態過程中，每個人名一定只會對應到一個位置，…

Problem - 519D - Codeforces題意： 給 26 個英文字母各自的花費，接著一個字串。求有多少子字串，滿足頭尾字母相同，且扣去頭尾字母後的花費總和為 0。數據範圍： 花費 -1e5 ≤ cost[ i ] ≤ 1e5 字串長度 1 ≤ | seq | ≤ 1e5解法： 先預處理前綴花費和，並做…

Problem - 567C - Codeforces 題意： 給一個數列和 K，求有多少三個元素構成的有序遞增等比子序列，其比為 K。 解法： 預處理，使可以查詢每個值存在於哪些位置，且這些位置是排序好的。接著枚舉中間的數字，左右邊的數字將會隨之確定，因此將答案增加指定數…

https://www.hackerearth.com/april-circuits/approximate/2b-bear-and-walk-1/ It is not difficult to come up to the maze solving left / right hand rule. www.youtube.com Since the path is connected, it will work. However, there are several dif…

https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-vowels-2/ Simply simulate as the description provides. #include <bits/stdc++.h> using namespace std; const int MAXS = 50 + 2; const string vowel = "aeiouy"; string s; void solve(){ int vo</bits/stdc++.h>…

Problem - D - Codeforces 2 elements with same value should never co-exist since it will be an even number, which will not be a prime number when summed, unless they were both 1. 2 even numbers nor 2 odd numbers can not co-exist as well. So…

Dashboard - Round 1A 2016 - Google Code Jam There are two possible ways to form a maximum cycle: 1. Sum up for each pair ( u, v ) that share bidirectional edges, length of chain that starts with u, and v, such like f[ f[ .. f[ v ] ] ] u ->…

Dashboard - Round 1A 2016 - Google Code Jam The constraints were small ( T ≤ 50, N ≤ 50, H ≤ 2500 ) so I stuck and thought it could be solved by some brute force methods. However, if the point is reached, it will very easy. Thinking it cle…

Problem - D - Codeforces It's clear that if the final colour is determined, and some vertex u has decided whether to flip or not, all the other vertices that are of the same component of u will decide itself whether should be flipped or no…

Problem - C - Codeforces Many people were hacked for this problem, for cases where leading zeros exist. Simply find answer for each suffix from smaller length, and it will do fine. P.S. This round was unrated QQ. #include <bits/stdc++.h> using namespace </bits/stdc++.h>…

Problem - C - Codeforces Take any point first, there will be at least one triangle that does not contain any other points inside, which can be formed with it. In order to avoid points inside the triangle, we can simply take any two points …

Dashboard - Qualification Round 2016 - Google Code Jam There are several solutions, and mine is of the easier one. Since the input is fixed, 16 and 32, observing that both of them are even numbers, we will come up to that, given any number…

Dashboard - Qualification Round 2016 - Google Code Jam It just feels like it will definitely finish before 20000 times, if solution exists. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; typedef long long ll; ll n; void solve(){ </bits/stdc++.h>…

Problem - A - Codeforces 一開始以為有二分性質，結果原來只需要暴力。。然後我預處理的部份也寫得太複雜了，其實根本可以更暴力的搞，會很好寫的。 #include <bits/stdc++.h> using namespace std; const int MAXPQ = 1e4 + 4; const int MAXT = 6e6 + 6; typedef long lo</bits/stdc++.h>…