2015-05-15

[Tmt514] Beverage Cup 2 D - A Parking Problem

Problem

停車場有 n 個位置呈現單方向，由入口到出口分別編號為 1 到 n，現在有 m 名駕駛準備要停車，每名駕駛的停車方案都會先開到偏愛的車位上，如果發現已經有人停過，則會往後找一個空車位。由於駕駛入停車場任意順序。請問從 m 個駕駛中挑出 n 個駕駛，任意進入停車場，按照他們各自偏愛的停車方法，每一位都有停車位的合法選擇駕駛的方案數。

Sample Input

1
2
3

1
3
2 1 2

Sample Output

Solution

維護前 i 個位置中，挑選 j 名駕駛的方法數！dp[i][j] 表示前 i 個位置，挑選 j 個駕駛的方法數，並且滿足 j >= i，否則會有留空一格造成後續的非法解。窮舉下一個位置挑選的人數 k，得到 dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;

#include <stdio.h>
const int MOD = 1000000007;
const int MAXN = 64;
long long C[MAXN][MAXN] = {};
int main() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        long long dp[MAXN][MAXN] = {};
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = 0; k <= A[i+1] && j+k <= n; k++) {
                    dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;
                    dp[i+1][j+k] %= MOD;
                }
            }
        }
        printf("%lld\n", dp[n][n]);
    }
    return 0;
}
/*
 1
 3
 2 1 2
*/

Read More +

2015-05-15

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

[Tmt514] Beverage Cup 2 B - Dreamoon's Criterion

Problem

夢月解題目會根據夢月法則？如果題目需要花費大於等於 t 的時間，則定義題目難度為 hard，反之為 easy。小番茄 (求解釋) 準備 n 個題目請求夢月協助，但隨著每解一題，下一題的難度會隨著疲累值增加，疲累值為一個等差為 k 個數列。只打算解決 easy 的題目，請問在相同的 k 下，不同的 t 分別能解決的最多題數。

Sample Input

Sample Output

1
2

4
0

Solution

t 越大，能解的題目肯定越多！難度越低的題目一定會選，因此前 i 小難度的題目都會被挑。利用類似求方程式值的方式 (隨便講講，別太在意 f(x) = a0 + a1x + a2x^2 + a3x^3 … + anx^n，可以在 O(n) 完成的方法) 下去猜測？維護已選題目如果增加 k 不大於 t 且下一個題目難度也小於 t，則所有已選難度都增加 k！離線處理，將詢問的 t 由小到大排序，掃描過去？

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
int A[MAXN], Qt[MAXN], out[MAXN];
int main() {
    int testcase;
    int N, K, Q;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &K);
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        scanf("%d", &Q);
        for (int i = 0; i < Q; i++)
            scanf("%d", &Qt[i]);
        
        vector< pair<int, int> > QV;
        for (int i = 0; i < Q; i++)
            QV.push_back(make_pair(Qt[i], i));
        
        sort(QV.begin(), QV.end());
        sort(A, A+N);
        
        int idx = -1, sum = 0, t, mx = -0x3f3f3f3f;
        for (int i = 0; i < Q; i++) {
            t = QV[i].first;
            while (idx+1 < N && mx + K <= t && A[idx+1] <= t) {
                idx++, sum++;
                mx = max(mx+K, A[idx]);
            }
            out[QV[i].second] = sum;
        }
        
        for (int i = 0; i < Q; i++)
            printf("%d\n", out[i]);
    }
    return 0;
}
/*
 1
 5 2
 7 3 6 8 5
 2
 9
 1
*/

Read More +

2015-05-15

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

[Tmt514] Beverage Cup 2 A - Attack and Split

Problem

有一隻史萊姆可以進行分裂和合併，大小為 x 的史萊姆可以分裂成兩個小史萊姆 y 和 z，滿足 x = y + z。當兩個史萊姆大小 p, q 合併時，新的史萊姆為 r = p xor q。請問是否存在數次的分裂和合併，所有史萊姆都消失！

Sample Input

Sample Output

1
2
3

No
Yes
Yes

Solution

亂來的奇偶和判定！以下是不負責任的說法！對於一種合法解 {a1, a2}，則 {a1-1, 1, a2-1, 1} 也一定會合法，不斷地拆分下去，所有史萊姆的大小都是 1，也發現到總和一定是偶數。因此只要判斷總和的奇偶數。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int n;
        long long x, sum = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            sum += x;
        }
        puts(sum%2 ? "No" : "Yes");
    }
    return 0;
}
/*
 3
 1 1
 2 9 17
 3 12 15 19
*/

Read More +

2015-05-14

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

[Tmt514] Beverage Cup 2 Warmup C - Exploding CPU 2

Problem

詢問一個區間有多少鄒賽爾數 (Zeisel number)

鄒賽爾數是一種無平方數因數的數，而且至少有三個質因數可以用下式表示，質因數由小排到大滿足$p_{x} = A p_{x-1} + B$。

105, 1419, 1729, 1885, 4505, 5719, 15387, 24211, 25085, …

4505 = 1 * 5 * 17 * 53
A = 3, B = 2
p0 = 1
p1 = 3 * p0 + 2 = 5
p2 = 3 * p1 + 2 = 17
p3 = 3 * p2 + 2 = 53

找到 $10^{15}$ 以內的所有 Zeisel number。

Sample Input

1
2
3

2
4505 4505
0 5000

Sample Output

1
2

1
5

Solution

一開始設想，既然小於 $10^{15}$ 又要三個質數，那麼最小的質因數應該要小於 $10^5$，否則會超過指定範圍。

接著第一次嘗試時，窮舉變數 $A$ 針對第一個質因數$p_{1}$ 得到$B = p_{1} - A$，得到下一項在範圍內 … 這樣效率非常差。A 的範圍非常大，質因數也非常多，而且還要檢驗每一項是否質數，效能相當低落。

接著第二次嘗試時，窮舉$p_{1}, p_{2}$，這樣的計算量是 $10^5$ 內的質數個數 n，至少為 $O(n^2)$，嘗試一下發現速度還是太慢，藉由聯立方程式解出 A, B，卻有不少 A 是不存在的整數解。

1
2
3

A + B = p1
p1 A + B = p2
A = (p2 - p1)/(p1 - 1), B = p1 - A

接著第三次嘗試時，反過來窮舉，先讓 $A$ 一定有解，再看$p_{2}$ 是否為質數，因此$p_2 = p_1 + k \times (p_1 - 1)$，由於$p_{i} - 1$ 造成的增長幅度遠比質數個數快很多，效能上有顯著地提升。

現在還有一個疑問，保證$p_1 \le 10^5$，但是當$p_1$ 很小$p_2$ 可能會大於 $10^5$ 嗎，甚至必須窮舉到 $\sqrt{10^{15}}$？

這裡我不確定，放大範圍去嘗試時，發現找到的 Zeisel number 最多 9607 個，放大搜索範圍不再增加，那就不斷地縮減，讓找到的時間縮小不逾時。

1.980s TLE

不是說好限制 2.000s？1.980s 得到 TLE，第一次使用 NTUJ 真歡樂。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXL (10000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[5500000], Pt = 0;
vector<long long> ret;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
long long MAXVAL = 1e+15;
int isprime(long long v) {
    if (v < 2)	
        return 0;
    if (v < 10000000)
        return !GET(v);
    for (int i = 0; i < Pt && (long long) P[i] * P[i] <= v; i++)
        if (v%P[i] == 0)
            return 0;
    return 1;
}
void make() {
    for (int i = 0; i < Pt && P[i] < 100000; i++) {
        for (int j = P[i] + P[i]-1; j < 1000000; j += P[i] - 1) {
            if (!isprime(j))
                continue;
            long long A = (j - P[i])/(P[i]-1);
            long long B = P[i] - A;
            long long m = P[i], cnt = 1, mm = P[i];
            while (mm <= MAXVAL) {
                if (A && MAXVAL / m / A <= 0)
                    break;
                if (m * A + B <= m)
                    break;
                m = m * A + B;
                if (MAXVAL / mm / m <= 0)
                    break;
                if (!isprime(m))
                    break;
//				printf("%lld ", m);
                mm = mm * m, cnt ++;
                if (cnt >= 3) {
                    ret.push_back(mm);
//					printf("%lld %lld %lld\n", mm, A, B);
                }
            }
        }
    }
    sort(ret.begin(), ret.end());
    for (int i = 0; i < 243; i++)
        printf("%d\n", ret[i]);
//	printf("%d\n", ret.size());
}
int main() {
    sieve();
    make();
    int testcase;
    long long L, R;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld", &L, &R);
        int r = 0;
        for (int i = 0; i < ret.size(); i++)
            r += ret[i] >= L && ret[i] <= R;
        printf("%d\n", r);
    }
    return 0;
}
/*
2
4505 4505
0 5000
*/

Read More +

2015-05-14

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

[Tmt514] Beverage Cup 2 Warmup B - The Brush

Problem

給一個 $N \times N$ 的棋盤，放置城堡 (rook)，城堡只能攻擊同行同列，這裡更特別一些，只能攻擊右下角位置。

下方是一個 $5 \times 5$ 範例，其中 R 表示城堡的位置，* 表示城堡可攻擊的格子，也就是範例的第三組測資。

+-+-+-+-+-+
| | | | |R| 1
+-+-+-+-+-+ 
| | |R|*|*| 2
+-+-+-+-+-+
| |R|*|*|*| 3
+-+-+-+-+-+
|R|*|*|*|*| 4
+-+-+-+-+-+
|*|*|*|R|*| 5
+-+-+-+-+-+
 1 2 3 4 5

保證輸入中城堡不會出現在同行同列，請問可攻擊的格子有多少個 (意即計算 * 的數量)。

Sample Input

Sample Output

1
2
3

6
10
13

Solution

很明顯地發現，答案是 所有城堡可攻擊數量總和 扣除 交集點數量 ，兩兩城堡最多一個交集點，並且交集點不會重疊 (不同行列的關係)，而交集點只發生在逆序對中。因此找到逆序對總數，可以利用 D&C 的 merge sort 算法，或者套用 Binary indexed tree，利用掃描線思路找到逆序對。

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, A[131072];
int BIT[131072];
void modify(int x, int val) {
    while (x <= n) {
        BIT[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n); 
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        for (int i = 0; i <= n; i++)
            BIT[i] = 0;
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            ret += n - A[i];
            ret += n - i - 1;
            ret -= i - query(A[i]-1);
            modify(A[i], 1);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
3
3
1 2 3
5
5 4 3 2 1
5
5 3 2 1 4
*/

Read More +

2015-05-14

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

[Tmt514] Beverage Cup 2 Warmup A - Euler's Criterion

Problem

日本電影《博士熱愛的算式》中，

博士只有八十分鐘的記憶，　　　　　　　　　
一旦超過這個時間，　　　　　　　　　　　　
他的記憶就自動歸零，重新開始。　　　　　　
然而，博士卻用一個簡單的數學公式，　　　　
驗證了愛的永恆。

《博士熱愛的算式》

$$e^{i \pi} + 1 = 0 \\ e^{ix} = cos(x) + i sin(x) \\ e^{i \pi} = cos(\pi) + i sin(\pi) = -1$$

判斷 $a \equiv x^2 (\text{ mod } p)$ 中，$a$ 是否在模 $p$ 下是個平方數。則滿足

$a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 (\text{ mod } p)$

從歐拉定理 $a^{\varphi (p)} \equiv 1 (\text{ mod } p)$ 可以推導得到上述。接著給定一個集合，分別帶入 $a$, $p$ 有多少組合法解。

Sample Input

2
4
3 5 7 11
5
3 5 7 11 13

Sample Output

1
2

5
7

Solution

窮舉帶入，利用快速冪乘積檢驗之。

#include <stdio.h>
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
}
int main() {
    int testcase;
    int n, p[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n); 
        for (int i = 0; i < n; i++)
            scanf("%d", &p[i]);
            
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                if (mpow(p[i], (p[j]-1)/2, p[j]) == 1)
                    ret++;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Read More +

2015-05-14

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

SRM 659 Div1 PublicTransitHard

Problem

給一棵樹圖，然後可以放置傳送門與兩地，可以在一地經過傳送門，從另一個地點飛出，請問放置方法有多少種使得最遠兩點移動距離不大於 X。

Solution

看題解作！但我相信仍然是噁心的！

首先需要做樹形 dp 找到最長路徑，保留通過自己子樹最深三條、不通過自己子樹擁有最長路徑。

窮舉所有建設方案 $O(N^2)$，用 $O(log n)$ 時間驗證方案正確性。固定其中一個點 $A$，接著 Dfs 走訪另一點 $B$，$A$ 到 $B$ 之間只會有一條路徑 $A,u_1, u_2, ..., B$，壓縮其中的路徑變成一維，對於中間的每一點找到 hanging value，hanging value 也就是葉子到 u 的最長距離。

假設從 A 到 B 上的點特徵表示成 $(p_0, v_0), (p_1, v_1), (p_2, v_2), ..., (p_n, v_n)$ 其中 $p_i$ 表示從 A 出發的距離，$v_i$ 表示 hanging value。

Example

|        |    |         | ...    |
|        |    |    |    |        |
A(u0) - u1 - u2 - u3 - u4 ... - B(un)
|        |    |    |    |        |
|        |    |    |    |
|        |              Y        
|        X

一個 | 表示子樹的距離 1，從上圖中可以得到 $(p_0, v_0) = (0, 4)$, $(p_1, v_1) = (1, 3)$, $(p_2, v_2) = (2, 2)$, $(p_3, v_3) = (3, 2)$, $(p_4, v_4) = (4, 2)$ …

如果要從 u1 分支 X 抵達 u4 分枝 Y，

經過 u1 - u2 - u3 - u4 的最短距離為 $dist = p_4 - p_1 + v_1 + v_4 = 8$
經過 u1 - A - B - un-1 - ... - u4 的最短距離為 $dist = n - p_4 + p_1 + v_1 + v_4$

特別小心下列情況

| 
|                 |
A(u0) ---------- u1 - u2 - u3 - u4 ... - B(un)
|                /|
|\              / |\      <---- inner longest path > X, Stop Dfs
| \            /    \
|  \          /      \

假設 $X = 5$ 有可能 $v_i \le 5$ 但是內部的最長路徑本身就超過，就要停止 Dfs。

那移動的距離方案為通過、不通過傳送點兩種，任意兩點 p2 > p1，不滿足的方案滿足下列兩等式

$p_2 - p_1 + v_1 + v_2 > X$，轉化變成 $v_1 - p_1 > X - p_2 - v_2$
$LIM = X - (n - p_2 + p_1 + v_1 + v_2) < 0$，為了檢查不滿足，則 LIM 要最小化，則 $v_1 + p_1$ 要最大化。

根據 Dfs 逐漸加點，將問題轉化成 RMQ (對一條不滿足下的情況下，第二條要盡可能滿足，利用最大值找到最慘情況。)。

檢查從新加入的點 u，則查找區間 $[X-p_2-v_2, \infty]$ 的最大值 $v_i+p_i$，帶入得到 $LIM$。若 $LIM \geq 0$，得到建造方案合法。Dfs 傳遞下去時，另一種 $LIM$ (屏除子樹 $v_i$ 的計算會不同) 將會限制最多再往下 $LIM$ 層 ($LIM$ 相當於說距離限制還差多少，當往後搜索時，路徑上的節點計算出的 $LIM$ 會逐漸減少 1，若發上路徑上的所有 $LIM < 0$ 則不合法。)，超過這個限制會造成不經過 u 的兩點最短路徑大於 X。

最後特別小心，如果子樹內的最長路徑大於 X 也要停止走訪！接著就實作持久化線段樹，要完成噁心的樹走訪下，不同狀態的線段樹恢復與傳遞變化。

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
class SegementTree {
public:
    struct Node {
        int l, r, lson, rson;
        int mx;
    } node[1048576];
    int nodesize;
    int init(int l, int r) {
        nodesize = 0;
        int root = build(l, r);
        return root;
    }
    int build(int l, int r) {
        if (l > r)  return 0;
        int k = nodesize++;
        node[k].l = l, node[k].r = r, node[k].mx = -9999;
        node[k].lson = node[k].rson = 0;
        if (l == r) return k;
        int m = (l + r)/2;
        node[k].lson = build(l, m);
        node[k].rson = build(m+1, r);
        return k;
    }
    int change(int p, int x, int val) {
        int k = nodesize++;
        node[k] = node[p];
        node[k].mx = max(node[p].mx, val);
        if (node[k].l == node[k].r) return k;
        int m = (node[k].l + node[k].r)/2;
        if (x <= m)
            node[k].lson = change(node[p].lson, x, val);
        else
            node[k].rson = change(node[p].rson, x, val);
        return k;
    }
    int query(int k, int l, int r) {
        if (l <= node[k].l && node[k].r <= r)
            return node[k].mx;
        int m = (node[k].l + node[k].r)/2;
        if (r <= m)
            return query(node[k].lson, l, r);
        else if (l > m)
            return query(node[k].rson, l, r);
        else
        	return max(query(node[k].lson, l, r), query(node[k].rson, l, r));
    }
} segTree;
const int MAXN = 2048;
const int SHIFT = 4096, MAXR = 8192;	
class PublicTransitHard {
public:
    vector<int> g[MAXN];
    int dp[MAXN][3];
    int dp2[MAXN][2];
    int ret1, ret2, limitX, testA;
    void dfs(int u, int p) {
        dp[u][0] = 0, dp[u][1] = 0, dp[u][2] = 0;
        dp2[u][0] = 0, dp2[u][0] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == p)
                continue;
            dfs(v, u);
            int d = dp[v][0]+1;
            if (d > dp[u][2])
                dp[u][2] = d;
            if (dp[u][2] > dp[u][1])
                swap(dp[u][2], dp[u][1]);
            if (dp[u][1] > dp[u][0])
                swap(dp[u][1], dp[u][0]);
                
            d = max(dp[v][0] + dp[v][1], dp2[v][0]);
            if (d > dp2[u][1])
                dp2[u][1] = d;
            if (dp2[u][1] > dp2[u][0])
                swap(dp2[u][0], dp2[u][1]);
        }
    }
    void dfs2(int u, int p, int segId, int depth, int mnLIM) {
        int p2 = depth, v2 = dp[u][0];
        int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
        int LIM = limitX - (depth - p2 + mx + v2);
//		printf("query [%d, oo] = %d\n", limitX - p2 - v2 + 1, mx);
//		printf("testA %d - %d, %d %d, LIM = %d, mx = %d\n", testA, u, p2, v2, LIM, mx);
        if (depth > mnLIM)
            return ;
        if (LIM >= 0 && dp[u][0] + dp[u][1] <= limitX && dp2[u][0] <= limitX) {
//			printf("----- connect %d %d, \n", testA, u);
            if (testA == u)	ret1++;
            else			ret2++;
        }
            
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == p)
                continue;
                
            int d = dp[v][0]+1;
            if (d != dp[u][0])
                v2 = dp[u][0];
            else
                v2 = dp[u][1];
            
            if (d == dp[u][0]) {
                if (dp[u][1] + dp[u][2] > limitX)
                    continue;
            } else if (d == dp[u][1]) {
                if (dp[u][0] + dp[u][2] > limitX)
                    continue;
            } else {
                if (dp[u][0] + dp[u][1] > limitX)
                    continue;
            }
            
            d = max(dp[v][0] + dp[v][1], dp2[v][0]);
            if (d == dp2[u][0]) {
                if (dp2[u][1] > limitX)
                    continue;
            } else {
                if (dp2[u][0] > limitX)
                    continue;
            }
            
            
//			printf("dfs %d %d, update [%d] = %d\n", p2, v2, v2 - p2, v2 + p2);
            int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
            int LIM2 = limitX - (depth - p2 + mx + v2);
            int segId3 = segTree.change(segId, v2 - p2 + SHIFT, v2 + p2);
//			printf("dfs %d %d, update [%d] = %d, LIM2 = %d\n", p2, v2, v2 - p2, v2 + p2, LIM2);
            dfs2(v, u, segId3, depth+1, min(mnLIM, depth+LIM2));
        }
    }
    int countValidTeleporters(int N, vector<int> edges, int X) {
        ret1 = ret2 = 0, limitX = X;
        for (int i = 0; i < N; i++)
            g[i].clear();
        
        for (int i = 0; i < edges.size(); i++) {
            int u = i+1, v = edges[i];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        for (int A = 0; A < N; A++) {
            dfs(A, -1);
            int root = segTree.init(0, MAXR);
            testA = A;
//			puts("-----");
            dfs2(A, -1, root, 0, 9999);
        }
        return ret1 + ret2/2;
    }	
};
int main() {
    PublicTransitHard test;
//	int N = 4;
//	int edges[] = {0, 1, 2};
//	int X = 1;
//	int N = 3;
//	int edges[] = {0, 0};
//	int X = 2;
//	int N = 6;
//	int edges[] = {0, 0, 0, 1, 1};
//	int X = 2;
//	int N = 7;
//	int edges[] = {0, 1, 0, 1, 2, 4};
//	int X = 3;
    
//	int N = 16;
//	int edges[] = {0, 1, 0, 2, 0, 0, 4, 5, 8, 9, 10, 11, 8, 4, 6};
//	int X = 7;
    
    int N = 56;
    int edges[] = {0, 1, 1, 3, 1, 5, 1, 0, 8, 8, 10, 10, 12, 10, 10, 8, 16, 16, 18, 19, 19, 21, 19, 19, 24, 25, 25, 27, 18, 0, 30, 30, 30, 33, 34, 34, 34, 30, 38, 39, 39, 38, 42, 43, 0, 45, 45, 45, 48, 45, 45, 51, 45, 53, 54};
    int X = 12;
    
    int ret = test.countValidTeleporters(N, vector<int>(edges, edges + N - 1), X);
    printf("%d\n", ret);
    return 0;
}

Read More +

2015-05-14

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

SRM 659 Div1 CampLunch

Problem

有 M 個人連續 N 天都在同一個地方吃飯，請問它們購買餐點方案數。

與當天坐在相鄰附近的人，一起購買雙人分享餐，解決這天。
買一份雙人分享餐，連續吃兩天。
買一份單人餐，解決這天。

Solution

淡淡地憂傷，一個人買雙人分享餐吃兩天 … 不過沒關係，一道插頭 dp，相當於插入 $1 \times 2$ 或 $2 \times 1$ 塞滿盤面。但每一天相鄰的人都不同，因此壓縮 bitmask 狀態會需要變動，統一紀錄 $[1<<M]$ ，表示 $i-bit$ 第 $i$ 個人是否已經解決今天，接著對應 (up = self, left = 查找位置)，滾動數組進行轉移。

可以參照 UVa 11270 的解法。現在要處理的是變化的 colume 填充。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 17, MAXM = 17;
class CampLunch {
public:
    int dp[2][1<<MAXM];
    int count(int N, int M, vector <string> a) {
        memset(dp, 0, sizeof(dp));
        int flag = 0;
        dp[0][(1<<M)-1] = 1;
        for (int i = 0; i < N; i++) {			
            for (int j = 0; j < M; j++) {
                int p = flag, q = !flag;
                flag = 1 - flag;
                memset(dp[q], 0, sizeof(dp[q]));
                for (int k = (1<<M)-1; k >= 0; k--) {
                    int L, U;
                    int Lid, Uid;
                    int ways = dp[p][k];
                    
                    if (ways == 0)
                        continue;
                    
                    Lid = j == 0 ? -1 : (a[i][j-1] - 'A');
                    Uid = a[i][j] - 'A';
                    L = j == 0 ? 1 : ((k>>(Lid))&1);
                    U = (k>>Uid)&1;
                                        
                    if (L == 0 && U == 1) 	// plan 1, sit next to each other
                        dp[q][k|(1<<Lid)] = (dp[q][k|(1<<Lid)] + ways)%MOD;
                    if (U == 0) 			// plan 2, two consecutive days.
                        dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
                    if (U == 1)				// plan 3, single
                        dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
                    if (U == 1)				// reserve
                        dp[q][k^(1<<Uid)] = (dp[q][k^(1<<Uid)] + ways)%MOD;
                }
            }
        }
        
        return dp[flag][(1<<M)-1];
    }
};
int main() {
    CampLunch cl;
    string v[] = {"ABC","ABC"};
    int vv = cl.count(2, 3, vector<string>(v, v+2));
    printf("%d\n", vv);
    return 0;
}
/*
 2
2
{"AB","AB"}
*/

Read More +

2015-05-14

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

SRM 659 Div1 ApplesAndOrangesEasy

Problem

給定長度為 $N$ 個序列，在這序列中表示吃蘋果或者是橘子的順序，必須保證的是任意連續區間長度為 $K$ 中，最多只會吃 $K/2$ 個蘋果，已知部分位置一定是蘋果，請問序列中最多有幾個蘋果。

Solution

嘗試要用 $O(N)$ 的貪心解法，弄了快一個小時沒出來。弄 $O(N^2)$ 做一下就過，從尾端開始往前掃，來決定未知的地方 $i$ 是否要放蘋果，假若後綴 $[i, i+K-1]$ 的蘋果樹，如果總量小於限制將這個地方設置為蘋果，反之超過，將最鄰近的蘋果全部取消到符合規定。

#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
class ApplesAndOrangesEasy {
public:
    int maximumApples(int N, int K, vector<int> info) {
        const int MAXN = 4096;
        int A[MAXN] = {}, apple = K/2;
        int ret = (int) info.size();
        memset(A, -1, sizeof(A));
        for (int i = 0; i < info.size(); i++)
            A[info[i]] = 1;
        for (int i = N+1; i <= N + K; i++)
            A[i] = 0;
        for (int i = N; i >= 1; i--) {
            int sum = 0;
            for (int j = i; j < i+K; j++)
                sum += A[j] >= 1;
            if (sum < apple && A[i] == -1)
                A[i] = 2, ret++, sum++;
            if (sum > apple) {
                for (int j = i; j < i+K; j++) {
                    if (sum > apple && A[j] == 2) {
                        A[j] = -1, ret--, sum--;
                    }
                }
            }
        }
        return ret;
    }
};
int main() {
    ApplesAndOrangesEasy ap;
    int a[] = {1, 3};
    ap.maximumApples(3, 2, vector<int>(a, a + 2));
    return 0;
}

Read More +

2015-05-11

解題區/解題區 - UVa

UVa 11284 - Shopping Trip

Problem

宅宅喜歡收集 DVD，居住在編號 0 的地方，移動在街道之間需要成本。現在已知到某些店家可以獲得比網購還便宜的價錢，請問出門的最大獲益為何？

可以選擇經過某些店家而不入門購買，每一家店獲得利益後，不能再次獲得利益。

Sample Input

Sample Output

1 2	Daniel can save $3.50 Don't leave the house

Solution

街道圖最多 50 個節點，但是能獲得利益的店家最多 12 家，窮舉拜訪順序需要 $O(12!)$ ，但這樣的速度肯定太慢。先將點之間做最短路徑，只把挑選店家的部分抓出，移動花費就從最短路徑中得到。

利用狀態壓縮得到 dp[i][j]，表示已經經過的店家狀態 i、最後一個走訪店家的編號 j，這個狀態的花費就是從編號 0 出發，經過 i 狀態的所有店家，最後停留在 j，接著窮舉下一個店家 k，則

1	dp[i\|(1<<k)][k] = max(dp[i][j] - g[j][k] + profit[k])

g[i][j] 表示編號 i 到編號 j 的花費 (寫的時候注意對應點與壓縮後的編號)。

由於沒必要經過所有的店家，針對每一格狀態都嘗試返回原點 0，得到最大利益。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 64;
int main() {
    int testcase;
    int N, M, P;
    int u, v, a, b;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        
        int g[MAXN][MAXN], profit[MAXN] = {};
        int dp[1<<12][12];
        memset(g, 0x3f, sizeof(g));
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d.%d", &u, &v, &a, &b);
            g[u][v] = min(g[u][v], a * 100 + b);
            g[v][u] = min(g[v][u], a * 100 + b);
        }
        
        scanf("%d", &P);		
        for (int i = 0; i < P; i++) {
            scanf("%d %d.%d", &u, &a, &b);
            profit[u] += a * 100 + b;
        }
        
        // floyd algorithm
        for (int i = 0; i <= N; i++)
            g[i][i] = 0;
        for (int k = 0; k <= N; k++)
            for (int i = 0; i <= N; i++) 
                for (int j = 0; j <= N; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                    
        // get store
        vector<int> S;
        for (int i = 0; i <= N; i++) {
            if (profit[i] > 0)
                S.push_back(i);
        }
        
        // run dp
        vector< pair<int, int> > o;
        for (int i = 0; i < (1<<S.size()); i++) {
            for (int j = 0; j < S.size(); j++)
                dp[i][j] = -0x3f3f3f3f;
            o.push_back(make_pair(__builtin_popcount(i), i));
        }
                
        int ret = -0x3f3f3f3f;
        for (int i = 0; i < S.size(); i++) {
            u = S[i];
            dp[1<<i][i] = -g[0][u] + profit[u];
        }
        
        sort(o.begin(), o.end());
        for (int i = 0; i < o.size(); i++) {
            int state = o[i].second;
            for (int j = 0; j < S.size(); j++) {
                if (dp[state][j] == -0x3f3f3f3f)
                    continue;
                    
                u = S[j];
                ret = max(ret, dp[state][j] - g[u][0]);
                for (int k = 0; k < S.size(); k++) {
                    if ((state>>k)&1)
                        continue;
                    v = S[k];
                    dp[state|(1<<k)][k] = max(dp[state|(1<<k)][k], dp[state][j] - g[u][v] + profit[v]);
                }
            }
        }
        
        if (ret > 0)
            printf("Daniel can save $%d.%02d\n", ret/100, ret%100);
        else
            printf("Don't leave the house\n");
    }
    return 0;
}

Read More +