0w1

Entries from 2016-12-07 to 1 day

CFR 742 D. Arpa's weak amphitheater and Mehrdad's valuable Hoses ( DP, Knapsack, Union Find )

Problem - D - Codeforces題意: 給每個人的重量和權值。再給每對朋友的關係。x 和 y 屬於同個朋友圈,若存在一個序列 a[ 0 ], a[ 1 ], .. a[ i ],滿足所有相鄰的人都是朋友。對於每個朋友圈,可以選一個人,或選所有的人,或都不選,邀請到派對。但是派對…

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