Codeforces #201 Div.1

比賽連結：http://codeforces.com/contest/346/

Problem A - Alice and Bob (by TreapKing)

看題目名稱就知道是一個Alice先手的遊戲了。題目會先給出一個數字都相異的數列，Alice先手，每一次行動是挑兩個數字x, y，然後把 | x - y | 加入數列，但如果 | x - y | 本來就存在就不能加，沒有行動可以做的人就輸了，問誰會贏。

題解：

先想只有兩個數字a, b的情況，那麼下一個操作就能做出a-b(正負先不理他xD)，在下一次會做出b - a-b = 2b-a 或 a-b - a = -b之類的，思考一陣會發現如果是給你a跟b，那麼應該對於所有整數x, y，ax + by應該都做得出來，不過會滿足 | ax + by | <= max(a, b)之類的。然後就會發現所有出現的數字都會是gcd(a, b)的倍數。官方的tuorial是直接提到不管怎麼樣最後數列的長相都一樣，然後就直接令d = gcd{ x[i] }，然後說最後的數列就會是{d, 2d, 3d, ... , max{x[i]} }。細節就看code吧。

code:

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
 #define debug(...) printf(__VA_ARGS__)
#else
 #define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

int main() {
 int n;
 scanf("%d", &n);
 int x = 0, mx = 0;
 for(int i=0; i<n; i++) {
  int tmp;
  scanf("%d", &tmp);
  x = __gcd(x, tmp);
  mx = max(mx, tmp);
 }

 puts((mx/x-n)%2 ? "Alice" : "Bob");
    
    return 0;
}

---

Problem C - Number Transformation II (by Yanger)

給你兩個正整數a, b (a >= b)，以及n個正整數Xi，今天每步有以下兩種選擇：
1. 在Xi裡面選一個數，讓a變成a - (a%Xi)
2. 使a--
問你最少要多少步可以讓a變成b。

n<= 10^5，所有數值都在10^9以內，但保證a-b <= 10^6。

題解：

首先有個greedy的想法，就是每一步都讓 a 變得越小越好。稍微想一下(其實想了蠻久)就發現很對，因為假設今天在某一步有兩個選擇a1和a2(a1 < a2)，那無論選a2後的下一步有多棒，選a1以後都能用相同的Xi走到那一步。
接下來的問題就變成每次要怎麼找當前最大的步伐了。結論是直接枚舉Xi去試就好。乍看起來很像O(n * (a - b))，但我們可以考慮一種走法：選定一個Xi 之後，就只用它和減一交替來走 (後面的渣渣再用減一處理)，然後發現這種走法裡面每兩步a就會減少Xi。所以其實只要維護好當前「還能用」(不會超過b)的Xi，每步步伐的量級就會是Max(Xi)，當Xi 全部相異的時候這就相當於n。算一算複雜度就會是好的O(a-b)。
有點幹的是題目沒有說Xi會相異，所以要事先把它unique掉。

code: http://codeforces.com/contest/346/submission/15577093

---

Problem D - Robot Control (by Yanger)

給一個點數、邊數最多都到10^6的有向圖，以及一個起點s和一個終點t。今天有個機器人要從起點走到終點。它有以下幾種性質：
1. 一踏到曾經踏過的點就會爆炸。
2. 沒路可走了(出度為0)就會爆炸。
3. 有不只一條路(出度大於1)的時候會隨機選一條走。
看起來很GG，但所幸聰明的你可以在它每走到一個有叉路的點的時候給它下指令，叫它走某個特定的邊，它在那個點就不會隨機了。
問你，最少需要幾個指令，可以保證機器人安全從s走到t?

題解：

從起點往下走前途茫茫，於是就想想從終點往回走。首先，一個指向終點的點，如果出度為一，則可以直接視為另一個安全的「終點」。把這些點都找完以後，如果另外有一個點的所有出邊都指向那些終點，那它也可以視為終點。照這樣遞迴找完所有終點以後，就代表，其他指向它們的點都需要一個指令才能安全到達。然後又可以接著做跟剛剛類似的事......
想想才發現這其實就是在反向圖上面做dijstra。而且因為需要的指令數只會在每個「階段」增加1，所以連priority queue都不需要。這樣複雜度就只是把所有邊遍歷一次而已，O(|E|)。詳細實作看code吧。

code: http://codeforces.com/contest/346/submission/15576591

---

Problem E - Doodle Jump (by Yanger)

給定整數a, n, p，定義數列Ai = a * i % p (0 <= i <= n)。
問Ai排序過後，相鄰值的差是否皆小於等於h ?
其中
1 <= a, p <= 10^9 且a, p互質
1 <= n < p
0 <= h <= 10^9

題解：

學官方舉個例，若a = 5, p = 23，則Ai會長得像這樣(這邊先不考慮n到多少，把全部都先列出來)：
0 5 10 15 20
2 7 12 17 22
4 9 14 19
1 6 11 16 21
3 8 13 18
換行的意思應該很明顯，列出來後會發現我們可以把Ai依照mod 5分成5 群。
有幾個觀察
1. 如果n不足以跑完第一群，最大間隔就直接是5。
2. 否則，第一群相當於把[0, 23) 隔成了幾個長度相等的子區間([0, 5], [5, 10], etc.)和後面的一些渣渣，而後面的數我們可以想像成去「填補」那些子區間。
3. 每一群恰好會填在每個子區間內的同一個相對位置，所以我們只要考慮一個子區間和每群中的一個數就好了。

整體就等同以2的步長在分割 [0, 5]，我們發現它其實是規模變小的原題 (a' = a - p % a, p' = a) 。所以我們可以一直遞迴下去，直到出現1.的情況再直接看答案。這邊其實都沒有考慮到2.中所謂的渣渣，不過經過一些證明可以知道它們根本不重要。

最後看複雜度，當a = p - 1的時候很明顯會慘掉，但因為取a = p - a 走出來其實一模一樣，所以我們每次只要取a' = min(a - p % a, p % a)，就能確保每遞迴一次a就至少會減半。這樣複雜度就會是好好的log了!!

code: http://codeforces.com/contest/346/submission/15824994