0w1

Square Decomposition

Yuki 550 夏休みの思い出(1)

Problem Description: Solve f(x) = x * x * x + A * x * x + B * x + C, given A, B, and C. Output the solutions in increasing order.Constraints: -1e18 -1e9 It is guaranteed that there are exactly 3 distinct solutionsSolution: pekempey showed …

HR Nominating Group Leaders ( Mo's Algorithm, Sqrt Decomposition )

Programming Problems and Competitions :: HackerRank題意: N 個人排成一排,每個人對人投一個票。Q 筆詢問,問 [ L, R ] 中,是否有恰好得到 X 票的人,如果有,輸出其中編號最小的。制約: 1 ≤ T ≤ 5 1 ≤ N, Q ≤ 1e5 N 的總和和 Q 的總和不超過 3e5。解…

Monthly Training Farm - May 2017 C. factor1 ( Math, Sqrt Decomposition )

ICPC Blog Online JudgeProblem Description: Given A, B, print number of positive factors of all values between integer in [ A, B ].Constraints: 1 ≤ A ≤ B ≤ 1e14Solution: Consider calculating result of [ 1, B ] - [ 1, A - 1 ]. It uses simila…

HE Numbers Summation ( OEIS, Math, Square Root Decomposition )

https://www.hackerearth.com/challenge/competitive/april-circuits-17/algorithm/numbers-summation/題意: 給 N,求 S 對 1e9 + 7 取模。制約: 1 ≤ N ≤ 1e15解法: 無恥怒查 OEIS。 如果想認真解起來,要領應該跟這個是一樣的。時間 / 空間複雜度: O( N…

CFR 616 E. Sum of Remainders ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N, M,求: 資料規模: The only line contains two integers n, m (1 ≤ n, m ≤ 1e13) — the parameters of the sum.解法: 首先觀察到 因此所求可以寫成 考慮比較簡單的這個問題: 這個的求法是基於平方分割,細節和這篇…

PE 401 Sum of squares of divisors ( Math, Sqrt Decomposition )

Well, I know that posting this might no be completely appropriate but...題意: 問 [ 1, 1e15 ] 所有整數的因數平方總和為多少。解法: 也就是平方分割,而枚舉 d 轉換成枚舉 N // d 那部分我一直很搞不清楚,但其實只要知道這件事就可以理解: 這件事成…

CFR 792 E. Colored Balls ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N 種球的個數 A[]。要求按照下列規則將其分箱: 1. 同一個箱子不能存在兩種球 2. 最多球的箱子的球數和最少球的箱子的球數之差不得超過 1 3. 所有球都必須存在於一個箱子裡 4. 不得有空箱 問最佳的分箱方式下,可以用最少…

CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )

Problem - C - Codeforces題意: 給一個長度為 N 的陣列,用顏色描述。要求對於所有 K 資料規模: N ≤ 1e5解法: 據說這可以用資料結構 ( 樹狀數組 ) 直接做掉,但我看不懂。 首先答案一定是非嚴格遞減的。 這題的重點在於看透一個結論:「答案的種類大約在 …

CFR 466 B. Wonder Room ( Square root decomposition, Math )

Problem - B - Codeforces題意: 有 n 個人,現有一個 a * b 的土地。可以任意伸長寬和高,希望面積不小於 6 * n 的前提下,面積最小,求最小面積和對應的長寬。資料規模: n, a, b ≤ 1e9 TL: 1000 ms解法: 不失一般性假設 a ≤ b,顯然最佳解的 a 的上界為 …

CFR 567 D. One-Dimensional Battle Ships ( Sqrt Decomposition )

Problem - 567D - Codeforces題意: 有 1 * N 的棋盤,K 艘長度為 A 的船,不接觸且不重疊地擺放在其中。你接著對 M 個相異位子依序開槍,但你的朋友每一次都說你撲空。求第幾次開槍後是可以確定你的朋友說謊。若無解輸出 -1。資料規模: N ≤ 2e5 M ≤ 2e5解…

CFR 449 A. Jzzhu and Chocolate ( Math, Sqrt Decomposition )

Problem - 449A - Codeforces題意: 給一個 n * m 的巧克力板,要割 k 次,每次只能割還沒割過的整數水平線或鉛直線,求最小的塊面積最大可以為何。測資規模: A single line contains three integers n, m, k (1 ≤ n, m ≤ 1e9; 1 ≤ k ≤ 2e9).解法: 貌似有…

Yuki 176 2種類の切手 ( Math, Square Root Decomposition )

No.176 2種類の切手 - yukicoder先に T ≥ lcm( A, B ) させるように余る lcm( A, B ) * k を最大の整数 k で取る。 すると最悪の場合、T = 1e9, max( A, B ) = min( A, B ) = 1e4.5 となる。 しかしここで max( A, B ) を枚挙しても間に合う。 O( sqrt( T ) …

BZOJ 1036 树的统计 ( 樹平方分割 )

Problem 1036. -- [ZJOI2008]树的统计Count このテクすごいね、猛練習しよう。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e4 + 4; const int MAXQ = 2e5 + 5; const int INF = 0x3f3f3f3f; int n; vector< int > es[ MAXN ], bes[ MAXN ]; int par[</bits/stdc++.h>…

UVA 12086 Potentiometers ( 平方分割 Range Sum Query )

UVa Online Judge Range Sum Query の基礎問題を平方分割で処理した。 ncastar.hatenablog.com この記事が大変参考になりました。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; int kase; int n; int a[ MAXN ]; int BS; vector< int > bucket</bits/stdc++.h>…

CFR 13 E. Holes ( 平方分割 )

Problem - E - Codeforces 第一次寫平方分割,不太習慣。這題的關鍵在於維護一些值,使得可以O( 1 ) 完成一個塊的查詢。操作也要逆著做回來( 由右到左 ) 才會正確。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; in</bits/stdc++.h>…