0w1

Random

CFR 364 D. Ghd ( Random, Math )

Problem - D - Codeforces題意: 給長度 N 的數列 A。問最大的數,使得該數是數列中一半以上的數的因數為何。制約: N ≤ 1e6 A ≤ 1e12解法: 令答案為 g,那麼有一半以上的數字是 g 的倍數。 因此考慮隨機選取一個下標 r,把所有 gcd( A[ r ], A[ i ] ) 算出…

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 )。制約…

Yuki 241 出席番号(1) ( Random )

No.241 出席番号(1) - yukicoder題意: 每個人有 [ 0, N - 1 ] 的整數中獨特的一個編號,且都有一個不喜歡的座位號碼。現在要將 [ 0, N - 1 ] 的整數分配給他們做為座位號碼。求一組方案,使得每個人都不坐在自己討厭的座位號碼上。資料規模: 人數 1≤N≤50 …

CFR 742 E. Arpa’s overnight party and Mehrdad’s silent entering ( Bicoloring / Random )

Problem - E - Codeforces題意: 在一個圓桌上吃飯,有兩種飯,希望每連續三個人,都一定有一個人吃不一樣的東西。每個人都有一個唯一對應的伴侶,而伴侶之間也規定不能吃一樣的東西。求合法分配的結果。若無法分配,輸出 -1。資料規模: 情侶對數 1 ≤ n ≤ 1…

Yuki 58 イカサマなサイコロ ( DP or Monte Carlo )

No.58 イカサマなサイコロ - yukicoder 制限が小さいゆえMonte Carlo で適当にやってもおk。 DP: #include <bits/stdc++.h> using namespace std; signed main(){ int N, K; cin >> N >> K; vector< vector< double > > dpn( N + 1, vector< double >( N * 6 + 1 ) ); dpn[ </bits/stdc++.h>…

CFR 330 E. Graph Reconstruction ( Random Search )

Problem - E - Codeforces The deterministic solution for this problem is quite difficult. However, it is easy to come up with a randomised algorithm. There are primarily 2 types of randomised algorithms, Monte Carlo that runs in a certain t…