C Code a Trie

題意：有一個 Trie，其可能被插入了一些串，每個節點（含根節點）上都有一個值，這些值互不相同，在 Trie 上查詢一個串時如果找到了就回傳這個串結束節點的值，否則回傳最后到達的節點的值，給定若干個查詢串及查詢結果，問是否存在這樣的 Trie，有解時這個 Trie 最少有幾個節點，

對于一些串，如果它們的查詢結果相同，那么對它們的查詢都應在它們的 LCA 處結束，于是先對每個這樣的 LCA 打標記，如果一個 LCA 下有多個值不同的標記顯然無解，

做完后相當于建了一個原始的符合條件的 Trie，于是再 DFS 一遍以回收盡可能多的節點即可，

D Defuse the Bombs

最簡單的方法是二分最多能活多久，稍微好一點的方法在二分的基礎上發現規律，從而僅用一次排序就求出結果，

E Escape from the Island

題意：給定一個有向圖，經過每條邊的時間花費是 1 1 1，一個人可以重復下面的行動序列，直到到達 n n n 號點：將所有有向邊視作無向邊，從當前點開始移動經過至多 k k k 條邊（可以不移動），到達某點后隨機選擇該點的某條出邊（此時不可將有向邊視作無向邊）并沿該邊移動，如果該點無出邊則留在原地不動，但仍耗費 1 1 1 單位時間，問對于 ∈ [ 1 , n ] \in [1, n] ∈[1,n] 的每一個點 i i i，這個人以 i i i 作為最初起點時，在最壞情況下，他至少要花多少時間才能到達 n n n 號點，注意只要到達了 n n n 號點就算結束， n ≤ 1 0 5 , k ≤ 50 n \le 10^5, k \le 50 n≤105,k≤50，

設 f ( i , j ) f(i, j) f(i,j) 表示以 i i i 為起點，此前已經移動過 j j j 條邊時，到達 n n n 的最短時間，那么顯然有
f ( i , j ) = { min ? ( i , t ) ∈ E ∨ ( t , i ) ∈ E { f ( t , j ? 1 ) + 1 } max ? ( i , t ) ∈ E { f ( t , 0 ) + 1 } f(i, j) = \begin{cases} \min_{(i, t) \in E \vee (t, i) \in E}\left\lbrace f(t, j - 1) + 1\right\rbrace \\ \max_{(i, t)\in E} \left\lbrace f(t, 0) + 1\right\rbrace \end{cases} f(i,j)={min(i,t)∈E∨(t,i)∈E?{f(t,j?1)+1}max(i,t)∈E?{f(t,0)+1}?
在這兩種情況中取更小的那個，

于是可以從 n n n 點開始倒著做 BFS 以更新每一個狀態，每次先做第一種更新，如果對于一個 f ( i , j ) f(i, j) f(i,j) 其所有后繼 f ( t , 0 ) f(t, 0) f(t,0) 都計算完了但其本身還未被更新做第二種更新，

注意無出邊的情況，

#include <bits/stdc++.h>
#define MAXN 100005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, k, f[MAXN][55];
int at[MAXN], nxt[MAXN << 1], to[MAXN << 1], cnt;
int du[MAXN];
bool nodu[MAXN];
void init(){
    n = read(), m = read(), k = read();
    REP(i, 0, n)
        REP(j, 0, k)
            f[i][j] = 0x3f3f3f3f;
    cnt = 0;
    memset(at, 0, sizeof(int) * (n + 1));
    memset(du, 0, sizeof(int) * (n + 1));
    REP(i, 1, m){
        int u = read(), v = read();
        to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
        ++du[u];
    }
    memset(nodu, 0, sizeof(bool) * (n + 1));
    REP(i, 1, n) if (du[i] == 0) nodu[i] = true;
}
queue<pair<int, int> > q;
inline void local_update(int src, int t1, int dest, int t2){
    if (f[dest][t2] == 0x3f3f3f3f)
        f[dest][t2] = f[src][t1] + 1, q.emplace(dest, t2);
}
void solve(){
    REP(i, 0, k) f[n][i] = 0, q.emplace(n, i);
    while (!q.empty()){
        int u = q.front().first, t = q.front().second;
        q.pop();
        if (t > 0){
            for (int i = at[u]; i > 0; i = nxt[i])
                local_update(u, t, to[i], t - 1);
        } else {
            for (int i = at[u]; i > 0; i = nxt[i]){
                if (i & 1) continue ;
                --du[to[i]];
                if (!du[to[i]]){
                    REP(j, 0, k)
                        local_update(u, 0, to[i], j);
                }
            }
            if (nodu[u]){
                REP(j, 0, k)
                    local_update(u, 0, u, j);
            }
        }
    }
    REP(i, 1, n){
        printf("%d\n", (f[i][0] == 0x3f3f3f3f ? -1: f[i][0]));
    }
}
int main(){
    int T = read();
    REP(i, 1, T){
        printf("Case #%d:\n", i);
        init();
        solve();
    }
    return 0;
}

G Game of Cards

題意：有四種牌，點數各為 0、1、2、3，初始局面每種牌各有 c 0 , c 1 , c 2 , c 3 c_0, c_1, c_2, c_3 c0?,c1?,c2?,c3? 張，A 和 B 玩游戲，A 先手，當前玩家可以選擇現有的牌中點數加起來不超過 3 的兩張牌，將其替換成點數為它們點數之和的一張牌，不能操作者輸，問誰贏，

打表再一次戰勝了人類智慧，通過打表可以發現答案關于 c 0 c_0 c0? 模 2 2 2， c 1 c_1 c1? 模 3 3 3 成回圈節，于是對于這六種情況直接輸出規律即可，

要特判一些邊界情況，

H Hide and Seek

題意：二維格點平面上有兩個點，給定這兩個點各自離原點的曼哈頓距離（記為 d 01 , d 02 d_{01}, d_{02} d01?,d02?）以及兩點之間的曼哈頓距離（記為 d 12 d_{12} d12?），問這兩個點有多少種可能的位置 pair，

本題的推導非常依賴畫圖，并且情況非常多，大致可以畫這樣一個圖，

方便起見，我們先假設 d 01 ≤ d 02 d_{01} \le d_{02} d01?≤d02?，

1. d 01 = 0 d_{01} = 0 d01?=0，若 d 02 = d 12 > 0 d_{02} = d_{12} > 0 d02?=d12?>0 則答案為 4 d 02 4d_{02} 4d02?，若 d 02 = d 12 = 0 d_{02} = d_{12} = 0 d02?=d12?=0 則答案為 1 1 1，否則答案為 0 0 0，
2. d 01 > 0 d_{01} > 0 d01?>0，
   1. d 12 = 0 d_{12} = 0 d12?=0，若 d 02 = d 01 d_{02} = d_{01} d02?=d01? 則答案為 4 d 01 4d_{01} 4d01?，否則答案為 0 0 0，
   2. d 12 < d 02 ? d 01 d_{12} < d_{02} - d_{01} d12?<d02??d01?，則答案為 0 0 0，
   3. d 12 = d 02 ? d 01 d_{12} = d_{02} - d_{01} d12?=d02??d01?，則答案為 4 ( d 12 + d 01 ( d 12 + 1 ) ) 4(d_{12} + d_{01}(d_{12} + 1)) 4(d12?+d01?(d12?+1))，
   4. d 02 ? d 01 < d 12 < d 02 + d 01 d_{02} - d_{01}<d_{12}<d_{02} + d_{01} d02??d01?<d12?<d02?+d01?，則考慮 d 12 ? d 02 + d 01 d_{12} - d_{02} + d_{01} d12??d02?+d01? 是否是偶數，如果不是就意味著以 d 12 d_{12} d12? 為半徑的“圓”不會和以 d 02 d_{02} d02? 為半徑的“圓”于任何一個格點相交，答案為 0 0 0，否則答案為 4 ( 2 ? d 12 ? d 02 + d 01 + 2 2 + 2 d 01 ? 2 ) = 4 ( d 01 + d 02 + d 12 ) 4\left(2\cdot \frac{d_{12} - d_{02} + d_{01} + 2}{2} + 2d_{01} - 2\right) = 4(d_{01} + d_{02} + d_{12}) 4(2?2d12??d02?+d01?+2?+2d01??2)=4(d01?+d02?+d12?)，
   5. d 12 = d 02 + d 01 d_{12}=d_{02} + d_{01} d12?=d02?+d01?，則答案為 4 ( d 02 + d 01 ( d 02 + 1 ) ) 4(d_{02} + d_{01}(d_{02} + 1)) 4(d02?+d01?(d02?+1))，
   6. 對于更大的 d 12 d_{12} d12?，答案為 0 0 0，

J Joy of Handcraft

題意：給定 n n n 個燈，第 i i i 個燈亮度為 x i x_i xi?，且在 [ 2 k t i , 2 k t i + t i ] [2kt_i , 2kt_i + t_i] [2kti?,2kti?+ti?] 時間亮，在 [ 2 k t i + t i + 1 , 2 k t i + 2 t i ] [2kt_i + t_i + 1 , 2kt_i + 2t_i] [2kti?+ti?+1,2kti?+2ti?] 時間滅，其中 k ≥ 0 , k ∈ Z k \ge 0, k \in \mathbb{Z} k≥0,k∈Z，問對于 ∈ [ 1 , m ] \in [1, m] ∈[1,m] 的每一個時刻 j j j，沒滅的燈泡中最亮的有多亮，

比較簡單的做法是考慮每一個時刻會被哪些燈泡更新，這是一個經典的數論分塊問題，可以結合 ST 表在 O ( m log ? m + m m ) O(m \log m + m\sqrt{m}) O(mlogm+mm ?) 的時間內做出，常數小的話并不難卡過去，

出題人給的另一個更好的方法是將每個周期按亮度排序，然后從大到小更新每一個時刻的答案，被更新完的時刻直接刪掉，結合并查集就可以做到 O ( m log ? m + m α ( m ) ) O(m \log m + m\alpha(m)) O(mlogm+mα(m))，

K Knowledge is Power

題意：多次詢問，每次給定一個 n n n，問所有將 n n n 拆分成若干個（至少兩個）兩兩互質的數的拆分方案中，拆出的最大數和最小數的差，最小是多少， 5 ≤ n ≤ 1 0 9 5\le n \le 10^9 5≤n≤109，

分類討論，對于 6 6 6 無這樣的拆分方案，對于奇數可以直接拆成兩個相鄰的自然數，對于形如 4 k ( k ∈ Z + ) 4k(k \in \mathbb{Z}^+) 4k(k∈Z+) 的偶數拆成 2 k ? 1 , 2 k + 1 2k-1, 2k+1 2k?1,2k+1 是最優的，

對于其他偶數，暴力打表發現答案 ≤ 4 \le 4 ≤4，于是列舉情況解方程判斷即可，

L Lottery

題意：給定一個可重集 S S S，為 2 a i 2^{a_i} 2ai? 的數有 x i x_i xi? 個，問 ∣ { ∑ t ∈ T t : T ? S } ∣ |\left\lbrace \sum_{t \in T} t : T \subset S\right\rbrace| ∣{∑t∈T?t:T?S}∣，即用 S S S 中的數可以拼出多少個不同的數，

學過多重背包就知道 x i x_i xi? 個 2 a i 2^{a_i} 2ai? 可以等價地用一些 2 a i , 2 a i + 1 , ? 2^{a_i}, 2^{a_i+1}, \cdots 2ai?,2ai?+1,? 表示，其中每個數的出現次數均不超過 2，

這么轉換后會發現所有出現過的 2 的指數形成了若干個連續段（如 2 a i , 2 a i + 1 , 2 a i + 2 , ? 2^{a_i}, 2^{a_i+1}, 2^{a_i+2}, \cdots 2ai?,2ai?+1,2ai?+2,?），每一個段的答案乘起來就是答案，并且段內可以用 DP 計算貢獻，于是就做完了，

A A Colorful Grid

有點妙，找機會再補，

F Fracture Ray

有點難寫，找機會再補，

I Invaluable Assets

有點沒看懂題，找機會再補，

小結

比賽前一天晚上還在趕作業，本來以為要完蛋了，實際上確實完蛋了（還好隊友撈了我一把），

H 這個題本來應該在最后一小時順利推出的，結果腦子亂了，推了半天推不出來…

E 最后一小時看了下題目，但沒有很快想到拆點的做法…

希望 ICPC 的時候不要這么撈吧，