Subscribed unsubscribe Subscribe Subscribe

0w1

Yuki 514 宝探し3 ( Ad hoc, Interactive )

No.514 宝探し3 - yukicoder題意: 在一個 1e9 * 1e9 的平面上,有個座標藏著寶藏。你每次可以問一個點和寶藏的曼哈頓距離是多少。請在兩次以內的詢問找到寶藏位置。解法: 問 ( 0, 0 ) 得距離 A,接著問 ( 0, A ) 得距離 B,那麼寶藏一定在 ( B / 2, A - B…

CFR 622 D. Optimal Number Permutation ( Ad hoc )

Problem - 622D - Codeforces題意: 要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列,使得以下 s 最小。 d[ i ] 為 i 處於的兩個位置形成的距離。制約: 1 ≤ N ≤ 5e5解法: 看解說,覺得非常神祕,遇到類似題應該還是不會。 主要想法是這樣,猜測可以直接…

CFR 803 B. Distances to Zero ( Ad hoc )

Problem - B - Codeforces題意: 給一個數列,其中至少有一個元素為 0。對每一個位置輸出離它最近的 0 的距離。制約: The first line contains integer n (1 ≤ n ≤ 2e5) — length of the array a. The second line contains integer elements of the array …

CFR 798 D. Mike and distribution ( Adhoc / Random )

Problem - D - Codeforces題意: 給長度 N 的兩個數列 A, B,求構造一個 C[],使得 len( C ) ≤ N / 2 + 1,且所有元素相異,且任意 i 滿足 1 ≤ C[ i ] ≤ N,並有 sum( A[ k ] for k in C ) * 2 > sum( A ) 且 sum( B[ k ] for k in C ) * 2 > sum( B )。制約…

CFR 795 K. Stepan and Vowels ( Ad hoc )

Problem - K - Codeforces題意: 給一個長度為 N 的字串,要求進行壓縮,規則如下: 若 "aeiouy" 任意一個字符連續出現兩次以上,則壓縮為一個。 例外是若 'e' 或 'o' 連續出現恰兩次,則不能壓縮。制約: The first line contains the integer n (1 ≤ n ≤ 1…

CFR 795 J. Stepan's Series ( Ad hoc )

Problem - J - Codeforces題意: 給一個長度為 N 的字串,由 "YN?" 組成。'?' 有可能為 'Y',有可能為 'N'。給定一個 K,問是否有可能存在一個連續 'N' 子字串長度恰為 K。注意連續 'N' 子字串必須是最大的,也就是左界左邊和右界右邊的元素必須為 'Y'。制約…

CFR 795 H. Repairing Of String ( Ad hoc )

Problem - H - Codeforces題意: 給 C[],C[ i ] 代表長度為 i 的元素種類單一子字串的數量。求構造字串。制約: The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string. The second line contains the seque…

CFR 795 D. Lie or Truth ( Ad hoc )

Problem - D - Codeforces題意: 給長度 N 的 A, B 數列。問是否可以只任意排列 [ L, R ] 區間內的元素,使得 A = B。制約: The first line contains three integers n, l, r (1 ≤ n ≤ 1e5, 1 ≤ l ≤ r ≤ n) — the number of Vasya's cubes and the position…

Yuki 491 10^9+1と回文 ( Ad hoc, Palindrome )

No.491 10^9+1と回文 - yukicoder題意: 給 N,問有幾個數字不超過 N,是 1e9 + 1 的倍數,並且是迴文。制約: N ≤ 1e18解法: 怒猜超過 1e9 之後不會有迴文了。( 求證明 ) 所以要求的其實是 1e9 以下的迴文數。 因為是迴文,所以只要枚舉左半邊,也就是大約…

GCJ 2017 Qual B. Tidy Numbers ( Ad hoc )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 問不超過 N 的最大的,以十進制表示時,由左到右檢視,數字呈非遞減的數為何。制約: 1 ≤ T ≤ 100. 1 ≤ N ≤ 1e18. 解法: 一開始寫數位統計 dp 寫到快哭出來。 仔細想想,只要倒著決定就可以…

ARC 071 E - TrBBnsformBBtion ( Ad hoc )

E: TrBBnsformBBtion - AtCoder Regular Contest 071 | AtCoder題意: 給字串 S, T。Q 筆詢問,指定 S 的某個子字串 S', T 的某個子字串 T',問是否能透過施行以下操作任意次由 S' 轉換為 T'。 1. 將 'A' 換成 "BB" 2. 將 'B' 換成 "AA" 3. 將 "AAA" 換成 "…

CFR 788 B. Weird journey ( Euler's Path, Ad hoc )

Problem - B - Codeforces題意: 給一個 N 點 M 邊的無向圖,問有幾種方法,可以經過 M - 2 個邊洽兩次,剩下 2 個邊洽一次。沒有重邊,但可能有自環。兩個方法不同,若且唯若拜訪洽一次的任意一邊不同。資料規模: The first line contains two integers n,…

CFR 792 D. Paths in a Complete Binary Tree ( Ad hoc, Binary Search )

Problem - D - Codeforces題意: 給一個完滿二元樹,用最大編號描述。二元樹上的編號是遞迴配置的,如圖: 給 Q 筆詢問,每筆詢問給起點編號,以及操作字串,字串由 { 'U', 'L', 'R' } 組成,對於不可執行的操作無視之。問終點編號為何。資料規模: The firs…

CFR 613 C. Necklace ( Ad hoc, Palindrome )

Problem - C - Codeforces題意: 給 'a' ~ 'a' + N - 1 各個字母的出現頻度。要求構造一個環狀的字串,使得最多處切下去會是迴文。資料規模: N ≤ 26 出現頻度總數不超過 1e5解法: 因為至少要有一個迴文就必須有不超過一個奇數的頻度,所以接下來可以分開討…

CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

Problem - C - Codeforces題意: 給一個圖,要求放 K 個機器人並給出每個機器人的路徑,路徑長至多為 ceil( 2 * N / K ),使得所有節點都被至少一個機器人拜訪過。資料規模: N, M ≤ 2e5解法: 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS,…

POI 2 Stage 2 Triangles ( Ad hoc, Math, Fibonacci )

http://main.edu.pl/en/archive/oi/2/tro題意: 給很多邊的長度,問是否可以構成三角形,可以的話輸出方案。資料規模: In the standard input there is a finite sequence of at least three positive integers not greater then 1e9, terminated by the nu…

IOICJ 92 Double path tree ( Ad hoc, Timestamp )

Problem Description: Given a tree, you want to do the least amount of operations to assert that for any two distinct nodes, there are at least two distinct simple paths that connect them.Constraints: 1≤T≤300 3≤n≤1e5 1≤xi,yi≤n A valid tree …

CFR Educational 17 C. Two strings ( Ad hoc )

Problem - C - Codeforces題意: 給字串 A, B,求最短的一個 B 的子字串,使得從 B 刪去這段子字串後的新字串 B' 為 A 的一個子序列。輸出 B'。資料規模: 字串長度不超過 1e5 TL: 2000 ms ML: 256 MB解法: 由左到右枚舉 A 的字串的切割點,並透過預處理這…

CFR 351 A. Jeff and Rounding ( Ad hoc, Math )

kmjp さんの記事を参考にしました。 Problem - A - Codeforces題意: 給你 2 * N 個數字,要把 N 個數向下取整,另外 N 個數向上取整。問總和的最小變化量是多少。資料規模: The first line contains integer n (1 ≤ n ≤ 2000). The next line contains 2n …

CFR 533 E. Correcting Mistakes ( Ad hoc )

Problem - E - Codeforces題意: 給你長度 N,以及長度 N 的兩個相異字串 S 和 T。求有多少可能的字串 W,使得從 W 刪去一個字符可以成為 S,也能成為 T。資料規模: The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T. T…

Bangladesh OI 2016 National Round pF. Batman and Robin ( Ad hoc )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意: 給你 L, A,代表字串的大小,以及可能字符集合大小。 接著給字串,以數字…

CFR 14 D. Two Paths ( Ad hoc, Tree, DP )

Problem - 14D - Codeforces題意: 給一棵樹,求兩個不相交的路徑,長度乘積最長可以是多少。資料規模: 節點數: 2 ≤ N ≤ 200 時間限制:1000 ms 空間限制:64 MB解法: 因為樹原本是連通的,而不能相交其實就是有一條路徑可以把他們連起來卻不准連起來,所…

Yuki 318 学学学学学 ( Ad hoc / Segment Tree )

No.318 学学学学学 - yukicoder題意: 給一個數列 A。現在要產生另一個數列 B。產生的步驟為: for each integer t in 1 to 1e9: __for each integer x in leftmostPositionInA( t ) to rightmostPositionInA( t ): ____B[ x ] = t 求 B 的最終樣貌資料規模…

ARC 065 D - 連結 ( Ad hoc )

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

CFR 742 C. Arpa's loud Owf and Mehrdad's evil plan ( Ad hoc )

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

CFR 742 B. Arpa’s obvious problem and Mehrdad’s terrible solution ( Ad hoc )

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 …

CFR 742 A. Arpa’s hard exam and Mehrdad’s naive cheat ( Ad hoc, Periodic )

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, …

ARC 064 D - An Ordinary Game ( Ad hoc, Game Theory )

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

Yuki 179 塗り分け ( Ad hoc )

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

Yuki 85 TVザッピング(1) ( Ad hoc )

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>…

CFR 740 C. Alyona and mex ( Ad hoc )

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

Yuki 78 クジ付きアイスバー ( Ad hoc, Periodic )

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

CFR 738 E. Subordinates ( Ad hoc )

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

CFR 201 A. Clear Symmetry ( Ad hoc, Math )

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

CFR 732 F. Anton and School ( Ad hoc, Binary Enumeration )

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

CFR 147 A. Punctuation ( Ad hoc )

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

TIOJ 1045 A.細菌培養 ( Ad hoc )

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

CFR 734 E. Anton and Tree ( Ad hoc, Tree )

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

CFR 637 C. Promocodes with Mistakes ( Ad hoc, Bruteforce )

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

CFR 637 B. Chat Order ( Ad hoc, Set )

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

CFR 519 D. A and B and Interesting Substrings ( Ad hoc )

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

CFR 567 C. Geometric Progression ( Map )

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

HE April Circuits 2B - Bear and Walk ( Left / RIght hand rule )

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…

HE April Circuits 1A - Bear and Vowels ( Simulation )

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>…

CFR Educational 12 D. Simple Subset ( Math + Adhoc )

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…

GCJ 2016 R1A pC. BFFs ( Graph Adhoc )

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 ->…

GCJ 2016 R1A pB. Rank and File ( Adhoc )

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…

CFR 664 D. Graph Coloring ( Adhoc )

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…

CFR 664 C. International Olympiad ( Adhoc )

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>…

CFR 618 C. Constellation ( Adhoc )

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 …