2016-01-18

2016 Facebook Hacker Cup Round 1

Facebook Hacker Cup Round 1

A. Coding Contest Creation

給 $N$ 個整數序列，每一個整數表示題目難度，可以在序列中插入整數，目標在序列中依序挑出 4 個整數作為比賽題目配置，並且要求不改變原本序列順序，滿足題目難度嚴格遞增，相鄰題目難度不大於 10，請問至少加入幾道題目。 (意即要插入題目的數量使得序列長度被 4 整除。)

最保守的方式 DP，只需要 $\mathcal{O}(N)$ 時間，記錄狀態 dp[i] 表示前 i 個 (不含) 整數滿足前述要求至少要插入幾個數，得到

$$dp[i] = min(dp[i], dp[j] + 4 - (i-j+1)), \; i -3 \le j \le i, \; c_{j, i} + (i-j+1)\le 4$$

，計算 $c_{j, i}$ 列出 $A_j, A_{j+1}, ..., A_{i}$ 得知至少要插入幾個數，貪心計算兩兩數字之間的差值 $\textit{diff}_k$，$c_{j, i} = \sum (\left \lceil \frac{\textit{diff}_k}{10} \right \rceil - 1)$。每一個轉移最多 4 次，故時間複雜度 $\mathcal{O}(N)$。

B. Laundro, Matt

小夥伴有 $L$ 件未洗衣物，洗衣店有 $N$ 台洗衣機和 $M$ 台烘衣機，洗衣機和烘衣機一次只能處理一件衣物，而對於每一台洗衣機對於衣物都有不同的處理時間 $W_i$，烘衣機則固定每 $D$ 時間就能烘好一次衣物。小夥伴可以暫存洗好衣物的籃子無限大，同時移動衣物的時間快到可忽略，請問至少要隔多久才能帶著所有洗好烘好的衣物離開洗衣店。

時間軸模擬題，用 priority queue 維護時間軸，在每一個時間戳記下檢查事件發生。模擬兩台機器交換衣物會稍微複雜，事件定義有三種：

某洗衣機可以在 $t_i$ 時間完成洗好一件衣服，下一次事件發生則是 $t_i + W_i$。不考慮何時放入衣物，每一次抓最近可完成的洗衣機進行清洗，直接當作洗好。
若有空的烘衣機，將洗好但未烘的衣物放入烘衣機，並將此烘衣機設定忙碌。並且標記 $t_i + D$ 時間此烘衣機會從忙碌變成閒置。
從忙碌變成閒置的烘衣機，記錄有多少衣物洗好烘好。

時間複雜度 $\mathcal{O}(L \log (N+M))$。

C. Yachtzee

宅宅的退休工程師想建造遊艇，預算總額從 $[A, B]$ 隨機地挑一個，請問建造所剩餘金額的期望值為何。建造策略如下：

造遊艇分成 $N$ 個步驟，每一個步驟各自有其預算 $C_i$。
造完一艘後，便著手建造下一艘，
直到某一個步驟預算不夠，便放下手上的計劃。(可能建造出半艘船)

數學期望值計算，時間複雜度 $\mathcal{O}(N)$，窮舉在每一個步驟罷工，因為卡在區間 $[A, B]$，計算剩餘金額在此步驟停止會稍微複雜。一艘船需要的預算為 $C$，那麼在某些情況 $C_i$ 會完全被 $[A, B]$ 包含，累計期望值 $\frac{0+C_i}{2}$，接著針對部分在區間 $[A, B]$ 的邊界情況。計算方法很多，在此也不多作解釋。

D. Boomerang Tournament

$2^N$ 個人進行樹狀單淘汰賽，給予每名選手互打的獲勝結果，在還沒公佈對局樹狀圖之前，請問每名選手預期能得到的最好和最壞名次為何。排名為嚴格多於自己的勝場數的選手個數。

選手最多 16 位，直接來個 $\mathcal{O}(16!)$ 絕對不行。當然樹狀圖的對稱性也許足以讓數量變得在時間內可窮舉完畢，但寫起來也複雜許多。

因此，利用位元壓縮 dp[參與選手集合][勝者] = 1/0 記錄子樹的情況，只需要 $\mathcal{O}(2^{16} \times 16)$ 個狀態總數，在集合合併處理需要窮舉子集合，由於我們只需要窮舉特定集合大小，複雜度不會到 $\mathcal{O}(3^{16})$ 這麼慘。合併時根據兩子樹的勝者相對打，同時紀錄兩位可夠晉級的最大最小回合數即可。

### Solution ###

#### A. Coding Contest Creation ####

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int dp[MAXN];
int main() {
    int testcase, n, x;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        vector<int> A;
        for (int i = 0; i < n; i++)
            scanf("%d", &x), A.push_back(x);
        
        for (int i = 0; i <= n; i++)
            dp[i] = LMAX;
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            vector<int> S;
            for (int j = 0; j < 4 && i+j < n; j++) {
                if (j && A[i+j] <= A[i+j-1])
                    break;
                S.push_back(A[i+j]);
                int inner = 0;
                for (int k = 0; k < j; k++) {
                    int diff = S[k+1] - S[k];
                    inner += max(diff / 10 + (diff % 10 != 0) - 1, 0);
                }
//                printf("[%2d,%2d] %d %d\n", i, j, inner, (int) S.size());
                if (inner + S.size() <= 4) {
//                    printf("update %d = %d from %d\n", i+j+1, dp[i] + 4 - (int) S.size(), dp[i]);
                    dp[i+j+1] = min(dp[i+j+1], dp[i] + 4 - (int) S.size());
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, dp[n]);
    }
    return 0;
}

B. Laundro, Matt

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int main() {
    int testcase;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int L, N, M, D, W, target;
        multiset< pair<long long, int> > EMPTYN;
        multiset<long long> EMPTYM;
        set<long long> timeline;
        multiset< pair<long long, int> > S;
        scanf("%d %d %d %d", &L, &N, &M, &D);
        for (int i = 0; i < N; i++) {
            scanf("%d", &W);
            EMPTYN.insert({W, W});
            timeline.insert(W);
        }
        
        target = L;
        int basket = 0;
        int complete = 0;
        long long ret = 0;
        timeline.insert(0);
        while (timeline.size() != 0) {
            long long time = *timeline.begin();
            timeline.erase(timeline.begin());
            while (L != 0 && EMPTYN.begin()->first <= time) {
                pair<long long, int> e = *EMPTYN.begin();
                EMPTYN.erase(EMPTYN.begin());
                EMPTYN.insert({e.first+e.second, e.second});
                timeline.insert(e.first+e.second);
                L--, basket++;
            }
            while (!EMPTYM.empty() && *EMPTYM.begin() <= time) {
                EMPTYM.erase(EMPTYM.begin());
                M++;
                complete++;
                if (complete == target)
                    ret = time;
            }
            while (basket > 0 && M > 0) {
                basket--, M--;
                EMPTYM.insert(time + D);
                timeline.insert(time + D);
            }
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

C. Yachtzee

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
long long C[MAXN];
double f(double l, double r) {
//    printf("[%lf, %lf]\n", l, r);
    return (r - l) * (r + l) / 2;
}
int main() {
    int testcase;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N;
        double A, B;
        scanf("%d %lf %lf", &N, &A, &B);
        for (int i = 0; i < N; i++) {
            scanf("%lld", &C[i]);
        }
        
        double ret = 0;
        double sum = 0, pre = 0;
        for (int i = 0; i < N; i++)
            sum += C[i];
        for (int i = 0; i < N; i++) {
            double pp = ceil(A / sum);
            double qq = floor(B / sum);
            int st = pp, ed = qq;
            set<int> S;
            for (int j = max(0, st-3); j <= st+3; j++) {
                if (S.count(j))
                    continue;
                double l = j * sum + pre, r = j * sum + pre + C[i];
                if (max(l, A) <= min(r, B)) {
                    ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
                }
                S.insert(j);
            }
            for (int j = max(0, ed-3); j <= ed+3; j++) {
                if (S.count(j))
                    continue;
                double l = j * sum + pre, r = j * sum + pre + C[i];
                if (max(l, A) <= min(r, B)) {
                    ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
                }
                S.insert(j);
            }
            
            ret += f(0, C[i]) * max((ed-3) - (st+3)-1, 0);
            pre += C[i];
        }
        
        ret /= (B - A);
        printf("Case #%d: %.9lf\n", ++cases, ret);
    }
    return 0;
}
/*
 5
 2 100 200
 100 100
 2 100 200
 50 100
*/

D. Boomerang Tournament

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
int g[16][16];
int dp[1<<17][16];
int main() {
    int testcase;
    int cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        }
        
        int ret[16][2], A[16];
        A[0] = n/2;
        for (int i = 1; i < n; i++)
            A[i] = A[i-1]/2;
        for (int i = 0; i < n; i++)
            ret[i][0] = 0, ret[i][1] = __builtin_ffs(n)-1;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
            dp[1<<i][i] = 1;
        int round[64] = {1};
        for (int i = 0; i < 5; i++)
            round[1<<i] = i;
        for (int i = 0; i < (1<<n); i++) {
            int cnt = __builtin_popcount(i);
            if (cnt != (cnt & (-cnt)))
                continue;
            if (cnt == 1)
                continue;
            for (int j = (i-1)&i; j; j = (j-1)&i) {
                if (__builtin_popcount(j) != cnt/2)
                    continue;
                for (int p = 0; p < n; p++) {
                    if (dp[j][p])
                    for (int q = 0; q < n; q++) {
                        if (dp[i^j][q]) {
                            if (g[p][q]) {
                                dp[i][p] = 1;
//                                printf("%d %d %d\n", cnt, p, q);
                                ret[p][0] = max(ret[p][0], round[cnt]);
                                ret[q][1] = min(ret[q][1], round[cnt]-1);
                            } else {
//                                printf("%d %d %d\n", cnt, q, p);
                                dp[i][q] = 1;
                                ret[p][1] = min(ret[p][1], round[cnt]-1);
                                ret[q][0] = max(ret[q][0], round[cnt]);
                            }
                        }
                    }
                }
            }
        }
//        for (int i = 0; i < n; i++) {
//            printf("[%d] %d\n", i, dp[(1<<n)-1][i]);
//        }
        printf("Case #%d:\n", ++cases);
        
        int rank[16];
        for (int i = 0, sum = 0; i < n; i++) {
            sum += n>>(i+1);
            if ((1<<i) == n)
                rank[i] = 1;
            else
                rank[i] = n - sum + 1;
        }
        for (int i = 0; i < n; i++) {
            int a = ret[i][0];
            int b = ret[i][1];
//            if (ret[i][1] != n) a = max(a, ret[i][1]);
//            if (ret[i][0] != -1) b = min(b, ret[i][0]);
            printf("%d %d\n", rank[a], rank[b]);
        }
    }
    return 0;
}

Read More +

2016-01-13

解題區/解題區 - 其他題目

2016 Facebook Hacker Cup 資格賽

好一陣子沒用 C++ 解題，感覺新鮮。嗯 …

1	$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

Facebook Hacker Cup 2016 Qualification Round

A. Boomerang Constellations

給予在星空下每顆星的座標，找出由三點構成回力鏢樣貌的組合個數，需滿足一點到兩點距離相等。

窮舉所有可能 $\mathcal{O}(N^3)$ 將會 TLE。窮舉回力鏢中心座標 $O$，統計其餘點到 $O$ 的距離，對於相同距離計數，套用組合公式 $C(n, 2)$ 加總，時間複雜度 $\mathcal{O}(n^2 \log n)$

B. High Security

給予只有兩排的長形棋盤狀的營地，雇用最少警衛監視每一塊區域，有些區域會因遮蔽物擋住警衛視線，而警衛只能監視平行兩軸的連續相鄰格子。求最少警衛個數。

第一眼覺得是 flow 可解，但求最少的模型建不太出來 Orz，就決定貪心。在同一行，連續片段上必然放置一個警衛，優先將連續片段總數匹配另一行連續個數恰好為一，剩下的情況再利用連續個數恰好一個的相互匹配。

C. The Price is Correct

參與一場遊戲，獎品價值為 $P$，給訂 $N$ 個正整數序列，挑選連續的序列總和小於等於 $P$ 即可獲得獎品，請問有多少挑選方式。

由於是序列為正整數，前綴和具有單調性，滑動窗口統計方法數只需要 $\mathcal{O}(N)$。最懶得方式是直接二分搜尋 $\mathcal{O}(n \log n)$。

D. Text Editor

從 $N$ 個不同的單字中，打印恰好 $K$ 個輸出在螢幕上，操作有三種 1. 在尾端插入一個字符 2. 刪除字串尾端一個字符 3. 將緩衝區的字串印出來，並且在操作結束後，緩衝區大小為 0。求最少操作個數為何？

第一次遐想，由於要最少操作個數，想必前綴相似的都必須連續，因此先對所有單字排序，接著按照順序 DP。先不考慮操作 3，最後一定恰好為 $K$ 次，只需要考慮插入和刪除操作，維護最後一個在緩衝區為單字 $i$，轉移到下一個單字 $j$ 的成本是 len(Wi) + len(Wj) - LCP[i, j]*2 (刪除前面 $W_i$ 的後綴再加入 $W_j$ 的後綴)，因此要預處理 LCA[i, j]，題目給訂範圍應該不用套用 Trie 或者是 Suffix Array 進行查找，暴力計算即可。定義 DP[i][k] 表示目前打了 $k$ 個單字，最後一個單字恰好為 $i$ 的最少操作次數。在 DP 部分，時間複雜度 $\mathcal{O}(N^2 K)$。

Solution

Sol. A. Boomerang Constellations

#include <bits/stdc++.h>
using namespace std;
#define MAXN 2048
long long X[MAXN], Y[MAXN];
int main() {
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long ret = 0;
        for (int i = 0; i < n; i++)
            scanf("%lld %lld", &X[i], &Y[i]);
        
        for (int i = 0; i < n; i++) {
            map<long long, int> R;
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                long long dist = 0;
                dist += (X[i] - X[j])*(X[i] - X[j]);
                dist += (Y[i] - Y[j])*(Y[i] - Y[j]);
                R[dist]++;
            }
            for (auto &p : R)
                ret += p.second * (p.second-1)/2;
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

Sol. B. High Security

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1024
char g[2][MAXN];
int main() {
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        scanf("%s%s", g[0], g[1]);
        int ret = 0;
        int A[2][MAXN] = {}, B[2][MAXN] = {};
        int used[MAXN] = {};
        int gid = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.') 
                    continue;
                int x = j, cnt = 0;
                while (x < n && g[i][x] == '.')
                    x++, cnt++;
                x = j;
                gid++, ret++;
                while (x < n && g[i][x] == '.')
                    A[i][x] = gid, B[i][x] = cnt, x++;
                j = x;
            }
        }
        
//		for (int i = 0; i < 2; i++) {
//			for (int j = 0; j < n; j++)
//				printf("%d", A[i][j]);
//			puts("");
//		}
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.')
                    continue;
                if (B[i][j] == 1)
                    continue;
                if (used[A[i][j]])
                    continue;
                int x = j;
                while (x < n && g[i][x] == '.') {
                    if (g[!i][x] == '.' && !used[A[!i][x]] && B[!i][x] == 1) {
                        used[A[!i][x]] = 1;
                        ret--;
                        break;
                    }
                    x++;
                }
                while (x < n && g[i][x] == '.')
                    x++;
                j = x;
            }
        }
        
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.')
                    continue;
                if (used[A[i][j]])
                    continue;
                if (B[i][j] == 1) {
                    if (g[!i][j] == '.' && !used[A[!i][j]] && B[!i][j] == 1) {
                        used[A[!i][j]] = 1;
                        ret--;
                    }
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

Sol. C. The Price is Correct

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N;
long long P, B[MAXN], C[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %lld", &N, &P);
        for (int i = 1; i <= N; i++)
            scanf("%lld", &B[i]);
        C[0] = 0;
        for (int i = 1; i <= N; i++)
            C[i] = C[i-1] + B[i];
            
        long long ret = 0;
        for (int i = 1; i <= N; i++) {
            int idx = (int) (lower_bound(C, C + N+1, C[i] - P) - C);
            ret += i - idx;
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

Sol. D. Text Editor

#include <bits/stdc++.h>
using namespace std;
const int MAXS = 131072;
const int MAXN = 512;
const long long LLMAX = 1LL<<60;
char s[MAXS];
int common[MAXN][MAXN];
long long dp[MAXN][MAXN];
int main() {
    int testcase, cases = 0;
    int N, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &K);
        vector<string> A;
        
        A.push_back("");
        for (int i = 0; i < N; i++) {
            scanf("%s", s);
            A.push_back(s);
        }
        
        sort(A.begin(), A.end());
        N = A.size();
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                int cnt = 0, x = i, y = j;
                for (int k = 0; k < A[x].length() && k < A[y].length(); k++) {
                    if (A[x][k] != A[y][k])
                        break;
                    cnt++;
                }
                common[i][j] = common[j][i] = cnt;
            }
        }
        
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++)
                dp[i][j] = LLMAX;
        }
        dp[0][0] = 0;
//		for (int i = 0; i < N; i++)
//			printf("%s\n", A[i].c_str());
            
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                if (dp[i][j] == LLMAX)
                    continue;
                for (int k = i+1; k < N; k++) {
                    long long t = 0;
                    t += A[k].length() - common[i][k];
                    t += A[i].length() - common[i][k];
                    dp[k][j+1] = min(dp[k][j+1], dp[i][j] + t);
                }
//				printf("%d %d - %lld\n", i, j, dp[i][j]);
            }
        }
        
        long long ret = LLMAX;
        for (int i = 0; i < N; i++)
            ret = min(ret, dp[i][K] + (long long) A[i].length());
        printf("Case #%d: %lld\n", ++cases, ret+K);
    }
    return 0;
}

Read More +

2015-08-24

解題區/解題區 - 其他題目

2016 Google APAC Test 小結

不知道有這場比賽，無聊寫寫靜靜心。

A. Googol String

給定一個遞迴生成式，求 $S_{100}$ 的第 $n$ 位字符為何。

直接用遞迴返回去計算即可，狀態分別為 f(n, S_m, switch_flag)，如果超過 $S_{m-1}$ 的一半時，由於操作需要字串反轉，反向求位數和反轉操作即可。

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 128;
unsigned long long b2[MAXN];
int f(long long n, int m, int s) {
    if (m == 1)	return s;
    if (n <= b2[m-1])
        return f(n, m-1, s);
    if (n == b2[m-1]+1)
        return s;
    return f(b2[m-1]-(n-b2[m-1]-1)+1, m-1, !s);
}
int main() {
    b2[0] = 0;
    for (int i = 1; i < MAXN; i++)
        b2[i] = (b2[i-1]<<1)+1;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n;
        scanf("%lld", &n);
        printf("Case #%d: ", ++cases);
        for (int i = 0; i < MAXN; i++) {
            if (b2[i] >= n) {
                printf("%d\n", f(n, i, 0));
                break;
            }
        }
    }
    return 0;
}

B. gCube

有一個 ? 維空間，要抓數列區間 [L, R]內的數字，構成 R-L+1 的超長方體，請問等體積下的超正方體的邊長為何。

簡單地說要把區間內的數字相乘起來，並且開 n 次根，由於乘數結果會 overflow，套用 log() 來完成。

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 128;
unsigned long long b2[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, A[1024], x, y;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            double sum = 0;
            for (int j = x; j <= y; j++)
                sum += log(A[j]);
            sum /= (y - x + 1);
            printf("%.9lf\n", exp(sum));
        }
    }
    return 0;
}

C. gCampus

辦公室之間有一些道路，每一個道路通過會消耗時間，請問那些沒效率的邊不在任兩個辦公室的最短路徑上。

看起來是能直接丟 floyd algorithm，由於 $|V| \le 100$，只需要窮舉邊兩個端點的經過的最短路徑，複雜度為 $O(V^3 + E V^2)$，仔細看一下還挺大的。

套用單源短路徑 SSSP 的做法，對每一個點都跑一次 dijkstra，檢查 shortest path DAG，複雜度需要 $O(V E \log V)$，點數有點太小 (再大也不方便處理)，大約在數秒內就能跑完。

#include <bits/stdc++.h> 
using namespace std;
const int MAXV = 32767;
const int MAXE = 32767;
const long long INF = 1LL<<62;
struct Edge {
    int to, eid;
    long long w;
    Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
long long dist[MAXV];
void addEdge(int x, int y, long long v)  {
    edge[e].to = y, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[x], adj[x] = &edge[e++];
}
void dijkstra(int st, long long dist[], int n) {
typedef pair<long long, int> PLL;
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    set<PLL> pQ;
    PLL u;
    pQ.insert(PLL(0, st)), dist[st] = 0;
    while (!pQ.empty()) {
        u = *pQ.begin(), pQ.erase(pQ.begin());
        for (Edge *p = adj[u.second]; p; p = p->next) {
            if (dist[p->to] > dist[u.second] + p->w) {
                if (dist[p->to] != INF)
                    pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
                dist[p->to] = dist[u.second] + p->w;
                pQ.insert(PLL(dist[p->to], p->to));
            }
        }
    }
}
int main() {
    int testcase, cases = 0, n, m;
    int x, y, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        
        e = 0;
        for (int i = 0; i <= n; i++)
            adj[i] = NULL;
            
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            addEdge(x, y, w);
            addEdge(y, x, w);
        }
        
        int on[65536] = {};
        for (int i = 0; i < n; i++) {
            dijkstra(i, dist, n);
            for (int j = 0; j < n; j++) {
                for (Edge *p = adj[j]; p; p = p->next) {
                    if (dist[p->to] == dist[j] + p->w)
                        on[p->eid/2] = 1;
                }
            }
        }
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < m; i++) {
            if (!on[i])
                printf("%d\n", i);
        }
    }
    return 0;
}

D. gSnake

一個貪心蛇遊戲，一開始蛇在左上角長度為 1，並且面向右側。若盤面上黑白染色，所有的奇點都具有食物，每一秒蛇會執行一個動作，直到他咬到自己的身體為止。當蛇碰撞到牆壁時，他會從對稱的地方鑽出。而下一秒接觸到食物時，相當於頭往前直伸產生新的一節。

現在有一串指令，每一個指令告知蛇會在那一秒後，執行順時針或逆時針轉向，請問模擬指令直到死亡或者抵達 $10^9$ 秒，請問蛇的總長為何。

這一題看起來有點可怕，由於貪心蛇所在的棋盤大小偌大無比，導致模擬上複雜度難以估計，但仔細發現指令時間最多 $1 \le X_i \le 1000000$，意即 $10^6$ 秒將會固定方向，在這固定方向模擬，最多吃到 max(R, C) 的食物，接著進入鑽出鑽出的循環狀態，或者進入終盤死亡。

根據循環和模擬情況加總，最多 $O(1000000)$ 步。為了解決偵測，用一個 map< pair<X, Y>, int > 來記錄身體經過的時間點，只要時間點差小於身體總長，表示咬到自己。或者，實做一個 list，維護一個 set< pair<X, Y> > 將頭端插入，移動時將尾巴移除。前者時間複雜度 $O(n \log n)$ 其中 $n = 1000000$，後者跟自身長度有關，但實作稍微複雜。

#include <bits/stdc++.h> 
using namespace std;
const int MAXS = 100005;
const int MAXT = 10e9;
const int dx[4] = {0, 1, 0, -1};	// right, down, left, up
const int dy[4] = {1, 0, -1, 0};
int X[MAXS];
char CMD[MAXS][4];
int main() {
    int testcase, cases = 0, R, C, S;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &S, &R, &C);
        for (int i = 0; i < S; i++)
            scanf("%d %s", &X[i], &CMD[i]);
            
        int len = 1, x = 1, y = 1, dir = 0;
        int cmdIdx = 0, cnt = 0;
        
        set< pair<int, int> > F;
        map< pair<int, int>, int > PASS;
        
        for (int i = 1; i <= MAXT; i++) {
            if (cmdIdx == S && cnt > max(R, C)*2)	// cycle
                break;
            x += dx[dir], y += dy[dir];
            if (x == 0)	x = R;
            if (x > R)	x = 1;
            if (y == 0)	y = C;
            if (y > C)	y = 1;
            
            int &step = PASS[{x, y}]; 
            if (step == 0)	step = -0x3f3f3f3f;
            if (i - step < len)
                break;
            step = i;			
            
            if ((x+y)%2 == 1 && !F.count({x, y})) {
                F.insert({x, y});
                len++, cnt = 0;
            }
            
            if (cmdIdx < S && i == X[cmdIdx]) {
                if (CMD[cmdIdx][0] == 'R')
                    dir = (dir+1)%4;
                else
                    dir = (dir+3)%4;
                cmdIdx++, cnt = 0;
            }
            cnt++;
        }
        printf("Case #%d: %d\n", ++cases, len);
    }
    return 0;
}

Read More +

2015-08-16

解題區/解題區 - 其他題目

PTC 201508 八月小結

由於代碼有點長，所以就放在 Github 上進行瀏覽，在此只提供文字說明，題解代碼點我。

現在還沒提供 OJ 線上測試，不保證代碼和算法的正確性。

Problem A Date Matching Problem

在一個二分帶權匹配問題中，模擬近似解的做法：每一次挑選權值最大的兩個未配對男女，請問最後得到的帶權匹配最大為何。

純粹模擬，沒有要求最大帶權匹配，最大帶權匹配可以用 KM 算法或者是最少費用流去完成。題目沒說明權重是否有相同情況，那麼模擬結果可能會有點問題在。

在社群媒體中，用節點表示一個個體，節點和節點之間會有所關連，這時候用一條邊連接起來，邊上用權重大小表示關聯強度。現在要將這 $N$ 個節點分成恰好 $K$ 群，每一個節點只能分配到一個群集中，為了使得分群效果更好，定義分群的好壞程度，對於任意兩點若有一條邊且在不同群，則這些點對的邊權重最大值就是分群評價，這個評價分數越低越好，意即群之間的相似度越低越好。請求出分群評價最低為何。

貪心，按照邊權由大排到小，接著使用 disjoint set 並查集來合併，直到低於 K 群，此時的邊權就是答案。

Problem C Treasure

Alice 和 Bob 這對狗男女 又在玩遊戲，他們要分 $N$ 個寶物，每個寶物到兩個人手上的價值都不同，同時分配寶物的個數最多只能差 1，請問最少分配價值差的絕對值為何。

由於 $N \le 35$，直接窮舉 $O(2^N)$ 消耗時間，於是可以剖半搜索，類似中間相遇法，窮舉前一半、後一半的所有組合，接著二分去合併，時間複雜度 $O(2^{N/2} N)$。特別小心寶物數量只能差 1，需要窮舉其中一個人的分配數量、計算組合時紀錄其中一個人的個數。

Problem D Coloring Statues

夜晚不死之神－夜神月，由於他太無聊，決定去更改院子裡的雕像顏色，顏色只有黑白兩種，他會玩到所有雕像顏色都為黑色時停止，請問 $K$ 天之後黑色雕像的顏色數。

$N$ 個雕像排成一列，各自擁有初始化的顏色，每一天的規則如下

所有雕像顏色為黑色就停止操作 更改最左側的雕像顏色，滿足前面所有操作都不重複的狀態，並且結束這一天。
* 一天只能改一個雕像，並將黑色改白色、白色改黑色。

變化的格雷碼計算，$N, \; K$ 非常大，不能用遞迴慢慢窮舉。那麼就 wiki 得到計算方法。

unsigned int binaryToGray(unsigned int num) {
    return (num >> 1) ^ num;
}
unsigned int grayToBinary(unsigned int num) {
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1) {
        num = num ^ mask;
    }
    return num;
}

主要核心為這兩個二進制和格雷碼的相互轉換，需要運用二進制的大數操作，只有位移、XOR、加法模擬，代碼的複雜程度可以接受。特別小心，由於雕像一開始有初始狀態，最終盤面 (全黑) 與格雷碼實際會有所不同，需要做每一個位置的黑白交換，否則不能滿足與前幾天都不重複的狀態。

用大數方法模擬上面兩個函數，並且在加法運算和最終盤面之間偵測 overflow 即可，時間複雜度 $O(N^2)$。

Problem E CPU

多核心排程問題，有 $C$ 個 CPU，每一個 CPU 可以用 $K$ 種不同的效能去完成工作，選擇哪一種效能會反映在處理時間$T_i$ 和電量消耗$E_i$，不同顆 CPU 的情況也各自不同，但它們可以平行工作。現在要安排 $N$ 份工作，每一個工作有 $I$ 個單位指令，不用考慮先做後做的順序，一旦他們進入排入 CPU，則一定會做完才能排定下一份工作。

每一個工作指派到 CPU 上會有處理的周轉時間 $Tu$ (turnaround time) 和能量消耗 $E$ (enery cost)，給定兩個常數$R_t, \; R_e$ 分別為總評價的參數，目標使得$\sum Tu_i R_t + E_i R_e$ 最小。

把$R_t, \; R_e$ 直接反應到效能和電量消耗，融進去之後就不用考慮。

首先，解決單一個 CPU 操作如何解決排程問題，藉由預先支付來解決週期時間 (turnaround time) 的計算，因此剩餘工作有 $R$ 個時，若要選入$Job_i$ 且使用 CPU 的第 $j$ 個方案，花費為$I_i \times R \times T_i + I_i \times E_i$，預先支付剩下 $R$ 個工作會增加的量，每一次抓最小的工作進行安排，樸素實作需要 $O(N^2 K)$。

從數學公式看出來，指令個數$I_i$ 可以提出，觀察一下，就是最短工作優先 (SJF) 的想法讓 turnaround time 總和最小，排序指令數量由小到大安排即可，複雜度降至 $O(N \log N + NK)$。

接著，考慮多核心情況，由於不知一個核心有多少個工作，無法預先支付接下來的工作成本，但 SJF 的思路仍然成立，即在每一個核心中，工作順序仍然是按照指令數量由小到大依序做。為了解決無法支付的問題，反向安排工作，決定最後一個工作要分配到哪一個 CPU，對於安排工作去找到 CPU 的成本$\text{CPUjob}_i \times T_i + E_i$ 最小，並且累計那一個 CPU 已經安排多少個工作$\text{CPUjob}_i$，複雜度降至 $O(N \log N + N (K + \log C))$

Read More +

2015-08-13

解題區/解題區 - 其他題目

PTC 201506 六月小結

雖然有在 Facebook 上面討論，遲遲沒有貼出來。由於代碼有點長，所以就放在 Github 上進行瀏覽，在此只提供文字說明，題解代碼點我。

Problem A Magic Box

給定最多 n = 30 個數字，任意挑選至少一個數字相乘得到 P，求 P mod 1000000007 = K 的組合數有多少。

背景知識

中間相遇法
乘法反元素

藉由中間相遇法，拆成 A, B 兩堆，每一堆最多有 n/2 個數字，分別計算組合數的乘積結果的組合數 P mod 1000000007。窮舉 A 那一堆其中一個組合乘積為 PA，方法數為 CNT_PA，而為了使 PA * PB mod 1000000007 = K，利用乘法反元素，找到 PB = K * PA^-1 mod 1000000007，利用映射找到 CNT_PB，因此累計方法數就會增加 CNT_PA * CNT_PB。

特別小心 K = 0 要例外處理。

Problem B Hidden Lines

平面上給定一堆線段，請問由上而下看時，有多少被藏住的線段。

背景知識

分而治之
計算幾何
掃描線算法

將線段按照左端點的 x 座標值排序，接著對 x 軸座標進行分治，分治時維護區間內的天際線，合併兩個天際線的算法最慘需要 $O(n \log n)$，若不使用掃描線算法可以降到 $O(n)$，這類似合併排序，將兩個曲折的線段合併成一個。

最後遞歸 $T(n) = 2T(n/2) + O(n) = O(n \log n)$ 時間複雜度可以接受，但是代碼複雜度就很高。

Problem C Bombs

有兩種炸彈分別是單核和雙核炸彈，每一個核心都有兩個感測器，感測器又有兩種圓形、方形。若炸彈不會引爆，則至少一個核心被破壞。一個核心被破壞，則兩個感測器處於不運作。

圓形感測器不運作，則表示通過此感測器的線路都必須被剪斷。方形感測器不運作，則表示通過此感測器的線路保持正常。給予線路連接數個炸彈的感測器情況，請問是否存在一種剪斷線路的方案，滿足炸彈都不會被引爆。

背景知識

2-SAT

變形的 2-SAT 問題，對於每一個線段剪或不剪都是一個未知數，求方程式是否有解。對於單核炸彈而言，那個核心必須被破壞，保證通過兩個感測器的線路都必須符合不被運作的情況，一開始就指派線路剪斷或不能被剪斷。對於雙核炸彈而言，當一個核心正常，則另一個核心必然要被破壞，反之亦然，則可以 核心 A 的某條線路若正常運作導致 B 的某條線路是壞的 意即 A -> NOT B 的邏輯方程。

最後套用 2-SAT 問題進行矛盾檢查即可。

Problem D Quick Reversal

數個區間反轉操作，求奇數位數字總和

背景知識

模擬
離散處理

區間離散 + 暴力 $O(Q^2)$。區間反轉可以用 splay tree 或者是塊狀表加速，根據 SGU 187 的經驗，不會卡到 $O(Q \log Q)$

Problem E Milk Delivery

求數條 s-t 路徑恰好經過 K 條路，路上權值和最大。

背景知識

矩陣乘法
圖論

建表 $O(N^3 \log K)$，詢問 $O(1)$。

Read More +

2015-08-07

解題區/解題區 - 其他題目

BZOJ 1047 [HAOI2007] 理想的正方形

Problem

題目連結

在一個 $N \times M$ 的矩形中，找到一個 $K \times K$ 的正方形區域，求所有正方形區域中最大值減去最小值的差最小為何。

Sample Input

Sample Output

Solution

明顯地是一個滑動窗口，對於一維情況很明顯地直接套用單調隊列即可。

對於二維的滑動窗口，則可以對每一列維護一個列的單調隊列，對於某一行掃描時，再維護一個行的單調隊列，往右移動窗口時，把移動到列的單調隊列的極值加入，並且把超出窗口的列的極值移除。

由上至下、由左而右掃描每一行上的元素，找到以此元素為正方形右下角的正方形區域最大最小值。時間複雜度 $O(N^2)$，怕重複的代碼太多，直接寫成模板搭配 std::deque<> 來使用，但這樣的寫法會比純數組來得慢 (method interface 和 cache 的影響 …)。

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 1024;
template<typename WTYPE, bool FUNC(WTYPE, WTYPE)>
class MonoQueue {
public:
    deque< pair<int, WTYPE> > Q;
    int K;
    void setWindow(int K) {
        this->K = K;
    }
    inline void add(int idx, WTYPE val) {
        while (!Q.empty() && Q.front().first <= idx - K)
            Q.pop_front();
        while (!Q.empty() && FUNC(val, Q.back().second))
            Q.pop_back();
        Q.push_back({idx, val});
    }
    inline pair<int, WTYPE> top() {
        return Q.front();
    }
};
bool cmp1(int a, int b) { return a > b; }
bool cmp2(int a, int b) { return a < b; }
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int N, M, K, val;
    while (ReadInt(&N)) {
        ReadInt(&M);
        ReadInt(&K);
                
        MonoQueue<int, cmp1> mxC[MAXN];
        MonoQueue<int, cmp2> mnC[MAXN];
        for (int i = 0; i < M; i++)
            mxC[i].setWindow(K), mnC[i].setWindow(K);
        int ret = INT_MAX;
        
        for (int i = 0; i < N; i++) {
            MonoQueue<int, cmp1> mxR;
            MonoQueue<int, cmp2> mnR;
            mxR.setWindow(K), mnR.setWindow(K);
            for (int j = 0; j < M; j++) {
                ReadInt(&val);				
                mxC[j].add(i, val);
                mxR.add(j, mxC[j].top().second);
                
                mnC[j].add(i, val);
                mnR.add(j, mnC[j].top().second);
                
                if (i >= K-1 && j >= K-1)
                    ret = min(ret, mxR.top().second - mnR.top().second);
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Read More +

2015-08-04

解題區/解題區 - 其他題目

HDU 5307 - He is Flying

Problem

題目連結，加速以下的程序計算，下方程式需要 $O(N^3)$，若用前綴維護總和也需要 $O(N^2)$。

for l = 0 to n-1
    for r = l+1 to n-1
        sum = 0
        for k = l to r
            sum += A[k]
        ret[sum] += r-l+1

最後輸出所有 ret[sum] 的對應結果。

Sample Input

Sample Output

Solution

由於是一個很樸素的計算，為了加速運算不套點資料結構和算法是不行的。看到對於每一個結果都要輸出，因此可以想到快速傅立葉 FFT 的旋積計算，接下來就要思考如何構造多項式 (向量)。

假設前 $i$ 個數字的前綴和$s_i$，為了要計數反應在係數，而索引值要反應在項數，因此得到兩個 $x$ 多項式相乘，若要統計區間 $[l, r]$ 的總和，則反應在$(i - j) x^{s_i} \times x^{- s_j} = (i-j) x^{s_i - s_j}$。但這樣的計算無法一次完成，因此要拆成兩次計算，分別得到$i x^{s_i - s_j}$ 和$-j x^{s_i - s_j}$。

明顯地前者構造$(\sum i x^s_i) \times (\sum x^{-s_j})$，後者構造$(\sum x^s_i) \times (\sum -j x^{-s_j})$，利用快速傅立葉 $O(n \log n)$ 計算多項式相乘，隨後相扣即可。

特別注意到總和 0 要特別判斷，因為構造法無法計算。此外這題非常講究精準度，可以利用 NTT/FNT 全部都在整數運算，又或者使用 FFT 在 double 形態下完成，特別小心 FFT 通常會利用角度疊加 (合角公式) 來加速運算，但不幸地這裡會遇到精準度誤差，必須採用 cos, sin 全建表。其他人容易遇到要用 long double 取代 double 計算是因為這種寫法的問題。

FFT

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;
template<typename T> class TOOL_FFT {
public:
typedef unsigned int UINT32;
#define MAXN 262144
    complex<T> p[2][MAXN];
    int pre_n;
    T PI;
    TOOL_FFT() {
        pre_n = 0;
        PI = acos(-1);
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0; ; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline UINT32 FastReverseBits(UINT32 a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    
    void FFT(bool InverseTransform, vector<complex<T> >& In, vector<complex<T> >& Out) {
        // simultaneous data copy and bit-reversal ordering into outputs
        int NumSamples = In.size();
        int NumBits = NumberOfBitsNeeded(NumSamples);
        for (int i = 0; i < NumSamples; ++i) {
            Out[FastReverseBits(i, NumBits)] = In[i];
        }
        // the FFT process
        for (register int i = 1; i <= NumBits; i++) {
            int BlockSize = 1<<i, BlockEnd = BlockSize>>1, BlockCnt = NumSamples/BlockSize;
            for (register int j = 0; j < NumSamples; j += BlockSize) {
                complex<T> *t = p[InverseTransform];
                for (register int k = 0; k < BlockEnd; k++, t += BlockCnt) {
                    complex<T> a = (*t) * Out[k+j+BlockEnd];
                    Out[k+j+BlockEnd] = Out[k+j] - a;
                    Out[k+j] += a;
                }
            }
        }
        // normalize if inverse transform
        if (InverseTransform) {
            for (int i = 0; i < NumSamples; ++i) {
                Out[i] /= NumSamples;
            }
        }
    }
    void prework(int n) {
        if (pre_n == n)
            return ;
        pre_n = n;
        p[0][0] = complex<T>(1, 0);
        p[1][0] = complex<T>(1, 0);
        for (register int i = 1; i < n; i++) {
            p[0][i] = complex<T>(cos(2*i*PI / n ) , sin(2*i*PI / n ));
            p[1][i] = complex<T>(cos(2*i*PI / n ) , -sin(2*i*PI / n ));
        }
    }
    vector<T> convolution(complex<T> *a, complex<T> *b, int n) {
        prework(n);
        vector< complex<T> > s(a, a+n), d1(n), d2(n), y(n);
        vector<T> ret(n);
        FFT(false, s, d1);
        s[0] = b[0];
        for (int i = 1, j = n-1; i < n; ++i, --j)
            s[i] = b[j];
        FFT(false, s, d2);
        for (int i = 0; i < n; ++i) {
            y[i] = d1[i] * d2[i];
        }
        FFT(true, y, s);
        for (int i = 0; i < n; ++i) {
            ret[i] = s[i].real();
        }
        return ret;
    }
};
TOOL_FFT<double> tool;
complex<double> a[MAXN], b[MAXN];
vector<double> c;
int A[MAXN], sum[MAXN];
long long ret[MAXN], pr[262144];
int main() {
    pr[0] = 0;
    for (int i = 1; i < MAXN; i++)
        pr[i] = pr[i-1] + (long long)i*(i+1)/2;
    int testcase, n, m, s;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + A[i];
        
        s = sum[n];
        memset(ret, 0, sizeof(ret[0]) * (s+1));
        for (m = 1; m <= (s<<1); m <<= 1);
        
        memset(a, 0, sizeof(a[0])*m);
        memset(b, 0, sizeof(b[0])*m);
        for (int i = 1; i <= n; i++) {
            a[sum[i]] += complex<double>(i, 0);
            b[sum[i-1]] += complex<double>(1, 0);
        }
        
        c = tool.convolution(a, b, m);
        for (int i = 1; i < m; i++)
            ret[i] += round(c[i]);
        memset(a, 0, sizeof(a[0])*m);
        memset(b, 0, sizeof(b[0])*m);
        for (int i = 1; i <= n; i++) {
            a[sum[i]] += complex<double>(1, 0);
            b[sum[i-1]] += complex<double>(i-1, 0);
        }
        c = tool.convolution(a, b, m);
        for (int i = 1; i <= s; i++)
            ret[i] -= round(c[i]);
        for (int i = 1, z = 0; i <= n+1; i++) {
            if (i == n+1 || A[i] != 0)
                ret[0] += pr[z], z = 0;
            else
                z++;
        }        
        for (int i = 0; i <= s; i++) {
            printf("%lld\n", ret[i]);
        }
    }
    return 0;
}

NTT

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned int UINT32;
typedef long long INT64;
class TOOL_NTT {
public:
#define MAXN 262144
    const INT64 P = 50000000001507329LL; // prime m = kn+1
    const INT64 G = 3;
    INT64 wn[20];
    INT64 s[MAXN], d1[MAXN], d2[MAXN], y[MAXN];
    TOOL_NTT() {
        for (int i = 0; i < 20; i++)
            wn[i] = mod_pow(G, (P-1) / (1<<i), P);
    }
    INT64 mod_mul(INT64 a, INT64 b, INT64 mod) {
        return (a*b - (long long)(a/(long double)mod*b+1e-3)*mod+mod)%mod;
        //      INT64 ret = 0;
        //      for (a = a >= mod ? a%mod : a, b = b >= mod ? b%mod : b; b != 0; b>>=1, a <<= 1, a = a >= mod ? a - mod : a) {
        //          if (b&1) {
        //              ret += a;
        //              if (ret >= mod)
        //                  ret -= mod;
        //          }
        //      }
        //      return ret;
    }
    INT64 mod_pow(INT64 n, INT64 e, INT64 m) {
        INT64 x = 1;
        for (n = n >= m ? n%m : n; e; e >>= 1) {
            if (e&1)
                x = mod_mul(x, n, m);
            n = mod_mul(n, n, m);
        }
        return x;
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0;; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline UINT32 FastReverseBits(UINT32 a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    void NTT(int on, INT64 *In, INT64 *Out, int n) {
        int NumBits = NumberOfBitsNeeded(n);
        for (int i = 0; i < n; ++i)
            Out[FastReverseBits(i, NumBits)] = In[i];
        for(int h = 2, id = 1; h <= n; h <<= 1, id++) {
            for(int j = 0; j < n; j += h) {
                INT64 w = 1, u, t;
                int block = h/2, blockEnd = j + h/2;
                for(int k = j; k < blockEnd; k++) {
                    u = Out[k], t = mod_mul(w, Out[k+block], P);
                    Out[k] = u + t;
                    Out[k + block] = u - t + P;
                    if (Out[k] >= P)        Out[k] -= P;
                    if (Out[k+block] >= P)  Out[k+block] -= P;
                    w = mod_mul(w, wn[id], P);
                }
            }
        }
        if (on == 1) {
            for (int i = 1; i < n/2; i++)
                swap(Out[i], Out[n-i]);
            INT64 invn = mod_pow(n, P-2, P);
            for (int i = 0; i < n; i++)
                Out[i] = mod_mul(Out[i], invn, P);
        }
    }
    void convolution(INT64 *a, INT64 *b, int n, INT64 *c) {
        NTT(0, a, d1, n);
        s[0] = b[0];
        for (int i = 1; i < n; ++i)
            s[i] = b[n-i];
        NTT(0, s, d2, n);
        for (int i = 0; i < n; i++)
            s[i] = mod_mul(d1[i], d2[i], P);
        NTT(1, s, c, n);
    }
} tool;
INT64 a[MAXN], b[MAXN], c[MAXN];
int A[MAXN], sum[MAXN];
long long ret[MAXN], pr[262144];
int main() {
    pr[0] = 0;
    for (int i = 1; i < MAXN; i++)
        pr[i] = pr[i-1] + (long long)i*(i+1)/2;
    int testcase, n, m, s;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + A[i];
        
        s = sum[n];
        memset(ret, 0, sizeof(ret[0]) * (s+1));
        for (m = 1; m <= (s<<1); m <<= 1);
        
        memset(a, 0, sizeof(a[0])*m);
        memset(b, 0, sizeof(b[0])*m);
        for (int i = 1; i <= n; i++) {
            a[sum[i]] += i;
            b[sum[i-1]] ++;
        }
        tool.convolution(a, b, m, c);
        for (int i = 1; i < m; i++)
            ret[i] += c[i];
        memset(a, 0, sizeof(a[0])*m);
        memset(b, 0, sizeof(b[0])*m);
        for (int i = 1; i <= n; i++) {
            a[sum[i]] ++;
            b[sum[i-1]] += i-1;
        }
        tool.convolution(a, b, m, c);
        for (int i = 1; i <= s; i++)
            ret[i] -= c[i];
        for (int i = 1, z = 0; i <= n+1; i++) {
            if (i == n+1 || A[i] != 0)
                ret[0] += pr[z], z = 0;
            else
                z++;
        }        
        for (int i = 0; i <= s; i++) {
            printf("%lld\n", ret[i]);
        }
    }
    return 0;
}

NTT CRT

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef uint_fast32_t UINT32;
typedef long long INT64;
typedef uint_fast32_t INT32;
class TOOL_NTT {
public:
#define MAXN 262144
    //  INT64 P = 50000000001507329LL; // prime m = kn+1
    //  INT64 G = 3;
    INT32 P = 3, G = 2;
    INT32 wn[20];
    INT32 s[MAXN], d1[MAXN], d2[MAXN], c1[MAXN], c2[MAXN];
    const INT32 P1 = 998244353; // P1 = 2^23 * 7 * 17 + 1
    const INT32 G1 = 3;
    const INT32 P2 = 995622913; // P2 = 2^19 *3*3*211 + 1
    const INT32 G2 = 5;
    const INT64 M1 = 397550359381069386LL;
    const INT64 M2 = 596324591238590904LL;
    const INT64 MM = 993874950619660289LL; // MM = P1*P2
    TOOL_NTT() {
        for (int i = 0; i < 20; i++)
            wn[i] = mod_pow(G, (P-1) / (1<<i), P);
    }
    void reset(INT32 p, INT32 g) {
        P = p, G = g;
        for (int i = 0; i < 20; i++)
            wn[i] = mod_pow(G, (P-1) / (1<<i), P);
    }
    INT64 mod_mul(INT64 a, INT64 b, INT64 mod) {
        return (a*b - (long long)(a/(long double)mod*b+1e-3)*mod+mod)%mod;
        //      INT64 ret = 0;
        //      for (a = a >= mod ? a%mod : a, b = b >= mod ? b%mod : b; b != 0; b>>=1, a <<= 1, a = a >= mod ? a - mod : a) {
        //          if (b&1) {
        //              ret += a;
        //              if (ret >= mod)
        //                  ret -= mod;
        //          }
        //      }
        //      return ret;
    }
    INT64 mod_pow(INT64 n, INT64 e, INT64 m) {
        INT64 x = 1;
        for (n = n >= m ? n%m : n; e; e >>= 1) {
            if (e&1)
                x = mod_mul(x, n, m);
            n = mod_mul(n, n, m);
        }
        return x;
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0;; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline UINT32 FastReverseBits(UINT32 a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    void NTT(int on, INT32 *In, INT32 *Out, int n) {
        int NumBits = NumberOfBitsNeeded(n);
        for (int i = 0; i < n; ++i)
            Out[FastReverseBits(i, NumBits)] = In[i];
        for (int h = 2, id = 1; h <= n; h <<= 1, id++) {
            for (int j = 0; j < n; j += h) {
                INT32 w = 1, u, t;
                int block = h/2, blockEnd = j + h/2;
                for (int k = j; k < blockEnd; k++) {
                    u = Out[k], t = (INT64)w*Out[k+block]%P;
                    Out[k] = (u + t)%P;
                    Out[k+block] = (u - t + P)%P;
                    w = (INT64)w * wn[id]%P;
                }
            }
        }
        if (on == 1) {
            for (int i = 1; i < n/2; i++)
                swap(Out[i], Out[n-i]);
            INT32 invn = mod_pow(n, P-2, P);
            for (int i = 0; i < n; i++)
                Out[i] = (INT64)Out[i]*invn%P;
        }
    }
    INT64 crt(INT32 a, INT32 b) {
        return (mod_mul(a, M1, MM) + mod_mul(b, M2, MM))%MM;
    }
    void convolution(INT32 *a, INT32 *b, int n, INT64 *c) {
        reset(P1, G1);
        NTT(0, a, d1, n);
        s[0] = b[0];    for (int i = 1; i < n; ++i) s[i] = b[n-i];
        NTT(0, s, d2, n);
        for (int i = 0; i < n; i++) s[i] = (INT64)d1[i] * d2[i]%P;
        NTT(1, s, c1, n);
        reset(P2, G2);
        NTT(0, a, d1, n);
        s[0] = b[0];    for (int i = 1; i < n; ++i) s[i] = b[n-i];
        NTT(0, s, d2, n);
        for (int i = 0; i < n; i++) s[i] = (INT64)d1[i] * d2[i]%P;
        NTT(1, s, c2, n);
        for (int i = 0; i < n; i++)
            c[i] = crt(c1[i], c2[i]);
    }
} tool;
INT32 a[262144], b[262144];
INT64 c[262144];
int A[MAXN], sum[MAXN];
long long ret[MAXN], pr[262144];
int main() {
    pr[0] = 0;
    for (int i = 1; i < MAXN; i++)
        pr[i] = pr[i-1] + (long long)i*(i+1)/2;
    int testcase, n, m, s;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + A[i];
        
        s = sum[n];
        memset(ret, 0, sizeof(ret[0]) * (s+1));
        for (m = 1; m <= (s<<1); m <<= 1);
        
        memset(a, 0, sizeof(a[0])*m);
        memset(b, 0, sizeof(b[0])*m);
        for (int i = 1; i <= n; i++) {
            a[sum[i]] += i;
            b[sum[i-1]] ++;
        }
        tool.convolution(a, b, m, c);
        for (int i = 1; i < m; i++)
            ret[i] += c[i];
        memset(a, 0, sizeof(a[0])*m);
        memset(b, 0, sizeof(b[0])*m);
        for (int i = 1; i <= n; i++) {
            a[sum[i]] ++;
            b[sum[i-1]] += i-1;
        }
        tool.convolution(a, b, m, c);
        for (int i = 1; i <= s; i++)
            ret[i] -= c[i];
        for (int i = 1, z = 0; i <= n+1; i++) {
            if (i == n+1 || A[i] != 0)
                ret[0] += pr[z], z = 0;
            else
                z++;
        }
        for (int i = 0; i <= s; i++) {
            printf("%lld\n", ret[i]);
        }
    }
    return 0;
}

Read More +

2015-06-22

解題區/解題區 - 其他題目

TIOJ 1475 錄製專輯 (Record)

Problem

Jolin 是個愛唱歌的小孩，每次總喜歡邊唱邊用電腦把自己的歌聲錄下來，因此長久下來，在她的電腦裡，已儲存了為數不小的個人歌唱作品。由於耶誕節快要到了，為了準備一份特別的耶誕禮物給爸爸，Jolin 準備從電腦中儲存的個人歌唱作品，挑選幾首歌製成一張個人專輯 CD。由於每張 CD 的容量有限，而Jolin 的個人歌唱作品早已遠遠超過一張 CD 可收錄的容量，因此 Jolin 希望你可以幫她想辦法，讓她所製作的專輯中，能有數目最多的歌曲（請注意：每一首歌只能被收錄一次），同時必需剛好裝滿整張 CD，不留下任何未使用的空間。

Sample Input

5
10 50 30 70 60
80 
5
10 50 30 70 60
20

Sample Output

1
2

2 4
0 0

Solution

實作 C++ 簡單的加法、乘法大數，直接把別提的拿過來用。

套用 0/1 背包問題，額外增加大數紀錄方法數，最後乘上 $N!$ 即可。

#include <bits/stdc++.h> 
using namespace std;
class BigInteger {
public:
    vector<long long> v;
    long long MAXC;
    BigInteger(int x = 0) {
        v = vector<long long>(10, 0);
        v[0] = x;
        MAXC = 100000000;
        normal();
    }
    BigInteger operator+(const BigInteger &x) const {
        BigInteger r(0);
        r.v.resize(max(v.size(), x.v.size()) + 2, 0);
        for (int i = 0; i < v.size(); i++)
            r.v[i] += v[i];
        for (int i = 0; i < x.v.size(); i++)
            r.v[i] += x.v[i];
        r.normal();
        return r;
    }
    BigInteger operator*(const BigInteger &x) const {
        BigInteger r(0);
        r.v.resize(v.size() + x.v.size() + 2, 0);
        for (int i = 0; i < v.size(); i++) {
            if (v[i] == 0)
                continue;
            for (int j = 0; j < x.v.size(); j++)
                r.v[i+j] += v[i] * x.v[j];
        }
        r.normal();
        return r;
    }
    void normal() {
        for (int i = 0; i < v.size(); i++) {
            if (v[i] >= MAXC) {
                v[i+1] += v[i] / MAXC;
                v[i] %= MAXC;
            }
        }
        int s = (int) v.size() - 1;
        while (s > 0 && v[s] == 0)
            s--;
        v.resize(s+1);
    }
    bool isZero() const {
        if (v.size() > 1)   return false;
        return v[0] == 0;
    }
    bool operator<(const BigInteger &x) const {
    	if (v.size() != x.v.size())
    		return v.size() < x.v.size();
    	for (int i = v.size()-1; i >= 0; i--) {
    		if (v[i] != x.v[i])
    			return v[i] < x.v[i];
    	}
    	return false;
    }
    bool operator==(const BigInteger &x)  const {
        if (v.size() != x.v.size())
            return false;
        for (int i = v.size()-1; i >= 0; i--)
            if (v[i] != x.v[i])
                return false;
        return true;
    }
    void print() {
        printf("%lld", v[v.size()-1]);
        for (int i = (int) v.size() - 2; i >= 0; i--)
            printf("%08lld", v[i]);
    }
};
int main() {
    int N, M, A[128];
    BigInteger f[128] = {};
    f[0] = BigInteger(1);
    for (int i = 1; i < 128; i++)
        f[i] = f[i-1] * BigInteger(i);
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        scanf("%d", &M);
        
        sort(A, A + N);
        int dp[10005] = {};
        BigInteger dp2[10005] = {};
        dp2[0] = BigInteger(1), dp[0] = 0;
        for (int i = 0; i < N; i++) {
            int x = A[i];
            for (int j = M; j >= x; j--) {
                if (dp[j] < dp[j-x] + 1 && !dp2[j-x].isZero())
                    dp[j] = dp[j-x] + 1, dp2[j] = BigInteger(0);
                if (dp[j] == dp[j-x] + 1 && !dp2[j-x].isZero())
                    dp2[j] = dp2[j] + dp2[j-x];
            }
        }
        int a = dp[M];
        BigInteger b = dp2[M] * f[a];
        
        printf("%d ", a);
        b.print();
        puts("");
    }
    return 0;
}
/*
5
10 50 30 70 60
20 
*/

Read More +

2015-06-22

解題區/解題區 - 其他題目

BZOJ 2038 小 Z 的袜子

Problem

給一個序列，詢問一個區間中任挑兩個數字，這兩個數字相同的機率為何，將答案化簡後輸出。

Sample Input

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output

2/5
0/1
1/1
4/15

Solution

莫隊算法命名是莫濤隊伍想出來的，不算是特別算法命名，估計是比賽中想到，目前沒看到英文命名。

莫隊算法處理離線詢問，回答所有答案複雜度為 $O(N^{1.5})$，其中 N 是區間索引值的範圍大小。概念在於分塊處理如下：

對於每個詢問的左端點放置於同一塊去處理
每一次處理一個塊狀的所有詢問
對於同一塊，詢問的右端點嚴格遞增去處理，讓左端點不斷地移動

發現到單獨看左端點指針的移動，約為 $O(N^{1.5})$，只考慮同一塊，最多有 $N$ 的詢問，一個詢問會造成左端點移動 $O(N^{0.5})$。而單獨看又端點指針的移動，約為 $O(N^{1.5})$，由於只會有 $O(N^{0.5})$ 塊，每一塊最慘就是遞增的移動 $O(N)$。

只要轉移區間 (維護區間的答案、計數，例如從 [l, r] 變成 [l, r-1] 的答案維護，把區間左右端點變大變小 1 的轉移計算) 的速度快，則複雜度約為 $O(N^{1.5})$。有不少情況需要 $O(\log N)$ 的其他數據結構維護轉移，複雜度就會變成 $O(N^{1.5} \log N)$，必要時使用塊狀表去作為數據結構進行轉移，當詢問次數 Q 與序列長度 N 呈線性關係，塊狀表支持 $O(1)$ 修改，$O(N^{0.5})$ 統計，那複雜度又能壓回 $O(N^{1.5})$。

能使用莫隊算法的題目，其中也不少能使用持久化結構來完成，若不考慮空間使用量，持久化結構能支持離線預處理、在線詢問。

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 50005;
const int MAXV = 50005;
class Offline {
public:
    struct Event {
        static int PILE;
        int l, r, qid;
        Event(int a = 0, int b = 0, int c = 0):
            l(a), r(b), qid(c) {}
        bool operator<(const Event &x) const {
            if (l / PILE != x.l / PILE)
                return l < x.l;
            return r < x.r; 
        }
    };
    int A[MAXN], N, qsize;
    vector<Event> event;
    vector< pair<long long, long long> > ret;
    void init(int N) {
        this->N = N, qsize = 0;
        event.clear();
        memset(B, 0, sizeof(B));
        for (Event::PILE = 1; Event::PILE * Event::PILE < N; Event::PILE <<= 1);
    }
    void q_add(int l, int r) {
        event.push_back(Event(l, r, qsize));
        qsize++;
    }
    void run() {
        sort(event.begin(), event.end());
        ret.resize(event.size());
        
        int l = 1, r = 0;
        q_stat = 0;
        for (int i = 0; i < event.size(); i++) {
            while (r < event[i].r)	r++, update(A[r], 1);
            while (r > event[i].r)	update(A[r], -1), r--;
            while (l > event[i].l)	l--, update(A[l], 1);
            while (l < event[i].l)	update(A[l], -1), l++;
            long long a, b, len = event[i].r - event[i].l + 1;
            if (len > 1) {
                a = q_stat - len;
                b = len * (len - 1);
            } else {
                a = 0, b = 1;
            }
            ret[event[i].qid] = make_pair(a, b);
        }
    }
private:
    long long B[MAXV], q_stat;
    void update(int x, int val) {
        B[x] += val;
        q_stat += val * 2 * B[x] - 1;
    }
} off;
int Offline::Event::PILE = 16;
long long llgcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int N, M, l, r;
    while (scanf("%d %d", &N, &M) == 2) {
        off.init(N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &off.A[i]);
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &l, &r);
            off.q_add(l, r);
        }
        off.run();
        for (int i = 0; i < off.ret.size(); i++) {
            long long a = off.ret[i].first;
            long long b = off.ret[i].second;
            long long g = llgcd(a, b);
            a /= g, b /= g;
            printf("%lld/%lld\n", a, b);
        }
    }
    return 0;
}
/*
1 1
5
1 1
*/

Read More +

2015-06-22

解題區/解題區 - 其他題目

BZOJ 3065 帶插入區間 K 小值

Problem

詢問區間 K 小，額外支持插入一個元素到序列中。

Sample Input

10
10 5 8 28 0 19 2 31 1 22 
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27

Sample Output

Solution

直接修改可持久化塊狀鏈表的那一題 Zerojudge b411 記憶中的序列 2，把可持久化的記憶體拔掉，這樣就免得記憶體需求過大。出題者是想用替罪羊樹掛另一個平衡樹下去做。應該沒設想到塊狀鏈表在此題的速度也不算差。時限 60 秒大概跑了 30 秒，還不比樹套樹來得慢。

因為有插入操作，不管是主席樹還是函數式線段樹 (這兩個應該是同一個傢伙)，都無法辦到，只能靠可插入的平衡樹。

#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <limits.h>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 65536;
const int MAXQ = 262144;
class UnrolledLinkedList {
public:
    struct Node {
        vector<int> A, B;
        Node *next, *alias;
        Node() {
            A.clear(), B.clear(), next = alias = NULL;
        }
        Node* real() {
            if (alias)	return alias;
            return this;
        }
        void insert(int x, int val) {
            if (alias) {
                A = alias->A, B = alias->B;
                alias = NULL;
            }
            A.insert(A.begin() + x, val);
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void erase(int x) {
            int val = A[x];
            A.erase(A.begin()+x);
            B.erase(lower_bound(B.begin(), B.end(), val));
        }
        void change(int x, int val) {
            int t = A[x];
            A[x] = val;
            B.erase(lower_bound(B.begin(), B.end(), t));
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void relax() {
            B = A;
            sort(B.begin(), B.end());
        }
    };
    int PSIZE;
    stack<Node*> mem;
    Node* init(int A[], int n) { // A[1:n]
        free();
        PSIZE = max((int) sqrt(n), 2);
        for (int i = 1; ; i <<= 1) {
            if (i >= PSIZE) {
                PSIZE = i;
                break;
            }
        }
        
        Node *u, *v, *head;
        
        head = newNode();
        u = head, v = NULL;
        for (int i = 1; i <= n; i++) {
            if (u->A.size() == PSIZE) {
                u->next = newNode();
                v = u, u = u->next;
            }
            u->A.push_back(A[i]);
        }
        for (u = head; u != NULL; u = u->next)
            u->relax();
        return head;
    }
    Node* newNode() {
        Node* p = new Node();
        mem.push(p);
        return p;
    }
    Node* cloneNode(Node *u) {
        Node *t = u->real();
        Node *p = new Node();
        *p = *t, p->next = u->next, mem.push(p);
        return p; 
    }
    Node* aliasNode(Node *u) {
        Node *t = u->real();
//		Node* p = new Node();
//		p->alias = t, p->next = u->next, mem.push(p);
//		return p;
        return u;
    }
    Node* erase(Node *ver, int x) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->erase(x - l);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* insert(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l-1 <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->insert(x - l + 1, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* change(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->change(x - l, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    int findRank(Node *ver, int L, int R, int val, int threshold = INT_MAX) {
        Node *u, *v;
        int ret = 0;
        u = ver;
        for (int l = 1, r; u != NULL; u = u->next, l = r+1) {
            r = l + u->real()->A.size() - 1;
            if (L <= l && r <= R) {
                ret += upper_bound(u->real()->B.begin(), u->real()->B.end(), val) - u->real()->B.begin();
                L = r + 1;
            } else if ((l <= L && L <= r) || (l <= R && R <= r)) {
                int i = L - l;
                while (i < u->real()->A.size() && L <= R) {
                    if (u->real()->A[i] <= val)
                        ret++;
                    i++, L++;
                }
            }
            if (ret >= threshold)	return ret;
        }
        return ret;
    }
    int find(Node *ver, int L, int R, int k)  {	// kth-number
        int l = 0, r = 100005, mid, t = 0; // value in A[]
        while (l <= r) {
            mid = (l + r)/2;
            if (findRank(ver, L, R, mid, k) >= k)
                r = mid - 1, t = mid;
            else
                l = mid + 1;
        }
        return t;
    }
    Node* mergeNode(Node *u, Node *v) {
        Node *p, *q;
        Node *a = newNode();
        p = u->real(), q = v->real();
        a->next = v->next;
        a->A.insert(a->A.end(), p->A.begin(), p->A.end());
        a->A.insert(a->A.end(), q->A.begin(), q->A.end());
        a->B.resize(a->A.size());
        merge(p->B.begin(), p->B.end(), q->B.begin(), q->B.end(), a->B.begin());
        return a;
    }
    Node* splitNode(Node *u) {
        Node *t = u->real();
        Node *a = newNode(), *b = newNode();
        int n = t->A.size()/2;
        a->next = b, b->next = u->next;
        a->A.insert(a->A.begin(), t->A.begin(), t->A.begin()+n);
        b->A.insert(b->A.begin(), t->A.begin()+n, t->A.end());
        a->relax(), b->relax();
        return a;
    }
    Node* relaxList(Node *ver) {
        Node *a, *b, *u, *v, *t;
        int need = 0;
        for (u = ver, a = NULL; !need && u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) // merge
            	need = 1;
            if (u->real()->A.size() > (PSIZE<<1))	// split
            	need = 1;
        }
        if (!need)
        	return ver;
        stack<Node*> remove;	// static used 
        for (u = ver, a = NULL; u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) {	// merge
            	if (a == NULL)
            		a = mergeNode(u, u->next), b = a;
            	else
            		b->next = mergeNode(u, u->next), b = b->next;
            	remove.push(u), remove.push(u->next); // static used  
                u = u->next;
            } else if (u->real()->A.size() > (PSIZE<<1)) {	// split
            	if (a == NULL)
            		a = splitNode(u), b = a->next;
            	else
            		b->next = splitNode(u), b = b->next->next;
            	remove.push(u); // static used  
            } else {
            	if (a == NULL)	
                    a = aliasNode(u), b = a;
            	else			
                    b->next = aliasNode(u), b = b->next;
            }
        }
        while (!remove.empty()) { // static used  
        	u = remove.top(), remove.pop();
        	delete u;
        }	    	
        return a;
    }
    void debug(Node *head) {
        Node *u = head;
        printf("[");
    	while (u != NULL) {
        	for(int i = 0; i < u->real()->A.size(); i++)
            	printf("%d%s", u->real()->A[i], i != u->real()->A.size()-1 ? " " : " ");
        	u = u->next;
    	}
    	puts("]");
    }
    void free() {
        return ;
        while (!mem.empty()) {
            Node *u = mem.top();
            mem.pop();
            delete u;
        }
    }
} dream; 
int A[MAXN], n, q;
UnrolledLinkedList::Node *ver[MAXQ];
int main() {
    int x, y, v;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        ver[0] = dream.init(A, n);
//		dream.debug(ver[0]);
        int encrypt = 0;
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'I') {
                // insert A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.insert(ver[i-1], x-1, v);
            } else if (cmd[0] == 'Q') {
                scanf("%d %d %d", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                int t = dream.find(ver[i-1], x, y, v);
                printf("%d\n", t);
                encrypt = t;
                ver[i] = ver[i-1];
            } else if (cmd[0] == 'M') {
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.change(ver[i-1], x, v);
            }
//			dream.debug(ver[i]);
        }
    }
    return 0;
}
/*
5
1 2 3 4 5
9999
4 1 5 2
1 2 1
4 1 5 2
0 1
4 1 5 2
2 1
1 0 5
3 3 9
4 1 1 1
*/

Read More +

Facebook Hacker Cup Round 1

A. Coding Contest Creation

B. Laundro, Matt

C. Yachtzee

D. Boomerang Tournament

B. Laundro, Matt

C. Yachtzee

D. Boomerang Tournament

Facebook Hacker Cup 2016 Qualification Round

A. Boomerang Constellations

B. High Security

C. The Price is Correct

D. Text Editor

Solution

Sol. A. Boomerang Constellations

Sol. B. High Security

Sol. C. The Price is Correct

Sol. D. Text Editor

A. Googol String

B. gCube

C. gCampus

D. gSnake

Problem A Date Matching Problem

Problem B Community Detection in Social Media

Problem C Treasure

Problem D Coloring Statues

Problem E CPU

Problem A Magic Box

背景知識

Problem B Hidden Lines

背景知識

Problem C Bombs

背景知識

Problem D Quick Reversal

背景知識

Problem E Milk Delivery

背景知識

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

FFT

NTT

NTT CRT

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution