解題區/解題區 - UVa

UVa 12887 - The Soldier's Dilemma

Problem

N 個人不同高，現在佔一排，任挑三個人的身高從左向右的相對高度，不存在矮、高、中的情況有多少種。

Sample Input

1
2
3
2
2
3

Sample Output

1
2
2
5

Solution

卡塔蘭數 (Catalan number)。

每一次考慮加入一個最高的人，窮舉最高的人應該佔在哪個位置，則其左、右側也要滿足定義，同時左側的人都要比右側的人高。最後得到公式如下，與卡塔蘭數相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h> 
/*
add tallest people in position i
ways[n] = \sum ways[i] * ways[n-i-1].
			   ^^^^^^[1] ^^^^^^^^^^[2]
[1] left tree pos[0, i-1]
[2] right tree pos[i+1, n-1]
then label of right tree must small than label of left tree
=> Catalan number, an = (4n-2)/(n+1) * an-1
*/
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra, lb -= n/m*rb;
        } else {
            ra -= n/m*la, rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    return i ? (la%mod+mod)%mod : (ra%mod+mod)%mod;
}
#define MAXN 5005
long long Catalan[MAXN];
const long long mod = 1000000007LL;
int main() {
    Catalan[0] = Catalan[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        Catalan[i] = Catalan[i-1] * (4 * i - 2) %mod;
        Catalan[i] = Catalan[i] * inv(i+1, mod) %mod;
    }
    int n, testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        printf("%lld\n", Catalan[n]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12880 - Book Club

Problem

有 N 個人的愛書俱樂部，他們會喜歡某些人的書，如果相互喜歡對方的書就可以進行交換，現在要問的是否每個人都能找到能夠交換的對象，讓每個人都獲得新書。

如果 A -> B, B -> C, C -> A，那麼他們可以環狀地交換新書。

Sample Input

1
2
3
4
5
6
7
8
9
10
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5

Sample Output

1
YES

Solution

每個人只能找一個對象進行交換，找二分圖的 perfect matching。

二分圖中左側是每個人，右側是想要交換的對象，兩邊的個數都是 N。匹配完會找到數個環狀，這就是最後的交換情況。然而由於點數很多，用匈牙利算法可以減枝來加快，每一次擴充路徑都必須得成功。如果使用 maxflow，則盡可能減少邊的無效使用。

當然可以使用 maxflow 貪心預流、匈牙利貪心匹配過後，再套用算法，速度有可能會快上許多，以下的模板還真好用，減少無效使用於分層圖，所以速度快上很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2) {
        g.Init(2 * n + 2);
        int source = 2 * n, sink = 2 * n + 1;
        for (int i = 0; i < n; i++)
            g.Addedge(source, i, 1), g.Addedge(i + n, sink, 1);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g.Addedge(x, y + n, 1);
        }
        
        int matching = g.Maxflow(source, sink);
        puts(matching == n ? "YES" : "NO");
    }
    return 0;
}
/*
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
*/
Read More +
解題區/解題區 - UVa

UVa 12878 - Flowery Trails

Problem

在國家公園的步行路道上要在兩側放置花卉，而主辦單位認為只要在其中兩個重要景點的最短路徑上的道路放置即可。通常大部分人只會走最短路徑。

請問總花費為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1

Sample Output

1
2
3860
18

Solution

最短路徑可能有數條，因此要窮舉每一條邊是否在最短路徑上，已知景點分別為 st 和 ed ，那麼找到 st -> u 和 ed -> v 的單源最短路徑，接下來窮舉 u -> v ，加上 st -> u 和 v -> ed ，得到 st -> u -> v -> ed 的最少花費，檢查是否等於最短路徑長即可。

這一題是雙向圖，如果是單向圖則要反轉邊，才能對 ed 進行單源最短路徑 (SSSP)。在這一題寫 SSSP 使用 SPFA 算法，也許 dijkstra 也是挺不錯的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm> 
using namespace std;
#define MAXN 32767
vector< pair<int, int> > g[MAXN];
int dist1[MAXN], dist2[MAXN];
void spfa(int st, int ed, int dist[]) {
    static int inq[MAXN];
    queue<int> Q;
    int u, v, w;
    dist[st] = 0, Q.push(st);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].first, w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v])
                    inq[v] = 1, Q.push(v);
            }
        }
    }
}
int main() {
    int n, m;
    int x, y, w;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(make_pair(y, w));
            g[y].push_back(make_pair(x, w));
        }
        
        for (int i = 0; i < n; i++)
            dist1[i] = dist2[i] = 0x3f3f3f3f;
        spfa(0, n-1, dist1);
        spfa(n-1, 0, dist2);
    
        int sp = dist1[n - 1], ret = 0;
        for (int i = 0; i < n; i++) {
            x = i;
            for (int j = 0; j < g[i].size(); j++) {
                y = g[i][j].first, w = g[i][j].second;
                if (dist1[x] + w + dist2[y] == sp)
                    ret += w;
            }
        }
        printf("%d\n", ret * 2);
    }
    return 0;
}
/*
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 12876 - City

Problem

現在給定格子狀的街區，每一個街區只會與垂直、水平的相鄰街區有通行的人行道。現在已知每個街區有多少人行道，求未知的街區人行道數量情況。

Sample Input

1
2
3
4
5
1
3 3
2 2 3
1 -1 3
1 1 0

Sample Output

1
1

Solution

二分圖黑白染色，知道每一個只會與相鄰上下左右的街區相鄰，那麼就像國際象棋一樣的黑白染色，相鄰的人行道一定只會連接於黑跟白之間。

分別計算黑和白的 degree 總數，差的絕對值就是未知街區的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
using namespace std;
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 testcase, n, m, x;
//	scanf("%d", &testcase);
    ReadInt(&testcase);
    while (testcase--) {
//		scanf("%d %d", &n, &m);
        ReadInt(&n);
        ReadInt(&m);
        int odd = 0, even = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
//				scanf("%d", &x);
                ReadInt(&x);
                if (x == -1)	continue;
                if ((i+j)&1)
                    odd += x;
                else
                    even += x;
            }
        } 
        printf("%d\n", abs(odd - even));
    }
    return 0;
}
/*
1
3 3
2 2 3
1 -1 3
1 1 0
*/
Read More +
解題區/解題區 - UVa

UVa 10266 - Surveying

Problem

從隨機幾點進行觀察，可以知道其相對高度。

現在給定數組觀察的部分紀錄，求在某一點的觀察的數據，如果可以得到完整的則輸出整個地圖的相對高度，如果不齊全、或者發生矛盾，則參考範例輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 2
1 2
1 1 10 1 2 10
1 2 20 2 2 30 2 1 30
2 2
1 1
1 1 10 1 2 10
2 2
1 2
1 1 10 1 2 10
1 1 20 1 2 30

Sample Output

1
2
3
4
5
6
0 0
10 10
the lack of measurements
conflicting measurements

Solution

不斷地部分記錄進行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define MAXN 128
vector<int> g[MAXN][MAXN];
struct Survey {
    int x, y, h;
    Survey(int a = 0, int b = 0, int c = 0):
    x(a), y(b), h(c) {}
};
vector< vector<Survey> > D;
int n, m;
int spfa(int sx, int sy) {
    int ret[MAXN][MAXN], used[MAXN][MAXN] = {};
    vector<int> sid;
    sid.resize(D.size(), 0);
    int x, y, h, id, tx, ty;
    queue<int> X, Y, ID;
    used[sx][sy] = 1, ret[sx][sy] = 0;
    for (int i = 0; i < g[sx][sy].size(); i++) {
        int u = g[sx][sy][i];
        X.push(sx), Y.push(sy), ID.push(u);
        sid[u] = 1;
    }
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        id = ID.front(), ID.pop();
        int shift = 0;
        for (int i = 0; i < D[id].size(); i++) {
            if (D[id][i].x == x && D[id][i].y == y) {
                shift = ret[x][y] - D[id][i].h;
                break;
            }
        }
        for (int i = 0; i < D[id].size(); i++) {
            tx = D[id][i].x, ty = D[id][i].y;
            h = D[id][i].h + shift;
            if (used[tx][ty] && h != ret[tx][ty])
                return 0;
            ret[tx][ty] = h;
            if (used[tx][ty] == 0) {
                used[tx][ty] = 1;
                for (int j = 0; j < g[tx][ty].size(); j++) {
                    int u = g[tx][ty][j];
                    if (sid[u]) continue;
                    X.push(tx), Y.push(ty), ID.push(u);
                    sid[u] = 1;
                }
            }
        }
    }
    
    int ok = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ok &= used[i][j];
        }
    }
    if (ok) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%d%c", ret[i][j], j == m ? '\n' : ' ');
            }
        }
    } else {
        puts("the lack of measurements");
    }
    return 1;
}
char line[1048576 * 8];
int main() {
    int testcase, bx, by;
    int x, y, h;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        scanf("%d %d", &bx, &by);
        while (getchar() != '\n');
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                g[i][j].clear();
        D.clear();
        while (gets(line)) {
            if (line[0] == '\0')   break;
            stringstream sin(line);
            int id = (int) D.size();
            vector<Survey> item;
            while (sin >> x >> y >> h) {
                item.push_back(Survey(x, y, h));
                g[x][y].push_back(id);
            }
            D.push_back(item);
        }
        int f = spfa(bx, by);
        if (!f) {
            puts("conflicting measurements");
        }
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 3
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 2 2 30 2 1 30
 
 2 2
 1 1
 1 1 10 1 2 10
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 1 2 30
 */
Read More +
解題區/解題區 - UVa

UVa 10253 - Series-Parallel Networks

Problem

給定 N 條邊，去除掉同構的情況，請問有多少個不同的串并連網路。

Sample Input

1
2
3
4
1
4
15
0

Sample Output

1
2
3
1
10
1399068

Solution

首先，拆分結果可以依序按照串－并－串－并 … 或者并－串－并－串 …

這樣會形成樹圖，其中奇數層是串/并，而偶數層是并/串，如此一來，要找到 N 個葉節點的樹有多少不同種的。根據兩種不同的分層方式，隨後乘上 2 就是答案。

定義 dp[i][j] 表示總共有 j 個葉節點的樹，並且每個子樹的葉節點最多 i 個 (至少)。這麼定義有它的好處，而不去直接定義 恰好 。

接著組合其具有 k 個樹－其子樹最多 i 個葉節點，剩下不足的葉節點，弄成一個樹，使用重複排列防止重複的計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h> 
#include <algorithm>
using namespace std;
long long dp[32][32] = {};
/*
parallel/series
consider parallel/series operation -> node, 
n-edge == counting number of tree with n-leaf node.
dp[i][j]: at most i-leaves in subtree, total j-leaves.
dp[i][j] = \sum C(ret[i] + k - 1, k) \times dp[i-1][j - i*k]
				^^^^^^^^^^^^^^^^^^^^[1]		^^^^^^^^^^^^^^^[2]
[1]: pick k subtree with at most (i-1)-leaves, total i-leaves
[2]: a subtree with at most (i-1)-leaves, total (j-i*k)-leaves
*/
long long C(long long n, long long m) {
    long long ret = 1;
    m = min(m, n-m);
    for (long long i = 1; i <= m; i++)
        ret = ret * (n + 1 - i) / i;
    return ret;
}
int main() {
    
    long long ret[32] = {};
    ret[1] = 1;
    for (int i = 1; i <= 30; i++)
        dp[0][i] = 0, dp[i][1] = 1;
    for (int i = 0; i <= 30; i++)
        dp[i][0] = 1;
    for (int i = 1; i <= 30; i++) {
        for (int j = 2; j <= 30; j++) {
            for (int k = 0; i * k <= j; k++) {
                dp[i][j] += C(ret[i] + k - 1, k) * dp[i-1][j - i*k];
            }
        }
        ret[i+1] = dp[i][i+1];
    }
    
    int n;
    while (scanf("%d", &n) == 1 && n)
        printf("%lld\n", n == 1 ? 1 : ret[n] * 2);
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1482 - Playing With Stones

Problem

有 N 堆石頭，每次選一堆，只能不能拿大於一半的石頭總數。

求兩個人都採用最佳策略，請問誰輸誰贏。

Sample Input

1
2
3
4
5
6
7
8
9
4 
2 
4 4 
3 
1 2 3
3 
2 4 6
3 
1 2 1

Sample Output

1
2
3
4
NO 
YES 
NO 
YES

Solution

建造 SG 函數進行觀察，接著直接套用 SG 函數的 nim 規則。

關於 SG

让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i<k，都存在x的一个后继y满足g(y)=i。也 就是说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏， Nim游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶 点的SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！

http://baike.baidu.com/view/2855458.htm

Sprague-Grundy 圖示演說參考

對於博弈，一直以來盡可能靠記憶化搜索 dp 完成，寫題基本上也還算過得去，在大數據的題目上，除了幾個噁心的數學分析外，利用記憶化搜索進行小數據觀察，真的沒搞頭的題目，大多解法是所謂的 SG 函數 (Sprague-Grundy)。

再不學點新的，就要沒有看得懂的題目可以刷了 … 如果因為看不懂題目，而增加對英文的仇恨值，都不知道溢位幾個世紀去了。

SG 函數簡單而言是對於針對某一類型的博弈遊戲，可以轉換成 Nim 遊戲，每一個 SG 函數的 value 對應 Nim 遊戲中一堆石頭的個數。新世界！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <string.h>
void buildSG() { // observe rule
    int mex[1024] = {}, SG[50];
    SG[0] = 0;
    for (int i = 1; i < 50; i++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 1; j <= i/2; j++)
            mex[SG[i - j]] = 1;
        int sg = 0;
        for (sg = 0; mex[sg]; sg++);
        SG[i] = sg;
        printf("%d : %d\n", i, SG[i]);
    }
}
long long SG(long long x) {
    return x%2 == 1 ? SG(x/2) : x/2; 
}
int main() {
//	buildSG();
    int testcase, n;
    long long x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            ret ^= SG(x);
        }
        puts(ret ? "YES" : "NO");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1404 - Prime k-tuple

Problem

查找區間內，相鄰 k 個質數中，滿足最大減最小恰好為 s 的情況有多少個。

Sample Input

1
2
1
100 200 4 8

Sample Output

1
2

Solution

a, b 大小簡直不可思議，就算能做到全搜索，建表時間是線性，也必須跑上 20 億乘上 20。

先做一次 sieve，接著對 [a, b] 進行 local sieve，題目雖然沒說明 b - a 的大小，實際看來是非常小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
#define maxL (50000>>5)+1
#define MAXN (2000000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
#define GET2(x) (mark2[x>>5]>>(x&31)&1)
#define SET2(x) (mark2[x>>5] |= 1<<(x&31))
int mark[maxL], mark2[MAXN];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 50000;
    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;
        }
    }
}
int local_sieve(int a, int b, int k, int s) {	
    int sqr = sqrt(b), gap = b - a;
    memset(mark2, 0, ((gap>>5) + 1) * 4);
    
    for (int i = 0; i < Pt && P[i] <= sqr; i++) {
        int p = P[i], base = a / p * p;
        while (base <= p)	base += p;
        for (int j = base; j <= b; j += p)
            SET2(j - a);
    }
    if (a == 1)	SET2(0);
    queue<int> Q;
    int ret = 0;
    for (int i = 0; i <= gap; i++) {
        if (!GET2(i)) {
            if (Q.size() == k - 1) {
                if (k == 0)
                    ret += s == 0;
                else if ((a + i) - Q.front() == s)
                    ret++;
            }
            Q.push(a + i);
            while (Q.size() >= k)	Q.pop();
        }
    }
    return ret;
}
int main() {
    sieve();
    
    int testcase;
    int a, b, k, s;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d %d", &a, &b, &k, &s);
        printf("%d\n", local_sieve(a, b, k, s));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1291 - Dance Dance Revolution

Problem

跳舞機共有四個方向，兩隻腳必須在某一個時刻按到該按鈕。

1
2
3
#1#
204
#3#

一開始雙腳站立於 0 的位置，每一個時刻只能移動一隻腳。

每一次移動的花費，0 到任何位置都是消耗體力 2、其餘數字移動到相鄰格子消耗體力 3、其餘數字移動到相面格子消耗體力 4，腳不動消耗體力 1。

過程中雙腳不能站立於同一個格子。

Sample Input

1
2
3
1 2 2 4 0 
1 2 3 4 1 2 3 3 4 2 0 
0

Sample Output

1
2
8 
22

Solution

dp[i][j][k] 分別記錄時刻 i，左腳所在位置 j，右腳所在位置 k。分別進行轉移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int A[32767];
int cg[5][5] = {
    {0, 2, 2, 2, 2},
    {INF, 1, 3, 4, 3},
    {INF, 3, 1, 3, 4},
    {INF, 4, 3, 1, 3},
    {INF, 3, 4, 3, 1}
};
int main() {
    while (scanf("%d", &A[0]) == 1 && A[0]) {
        int n = 1;
        for (; scanf("%d", &A[n]) && A[n]; n++);
        int dp[2][5][5]; // [][left][right]
        memset(dp, 0x3f, sizeof(dp));
        int p = 0, q = 1;
        dp[p][0][0] = 0;
        for (int i = 0; i < n; i++) {
            p = !p, q = !q;
            memset(dp[p], 0x3f, sizeof(dp[p]));
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    int l = A[i];
                    if (j != l) {
                        dp[p][j][l] = min(dp[p][j][l], dp[q][j][k] + cg[k][l]);
                    }
                    if (k != l) {
                        dp[p][l][k] = min(dp[p][l][k], dp[q][j][k] + cg[j][l]);
                    }
                    if (j == l || k == l) {
                        dp[p][j][k] = min(dp[p][j][k], dp[q][j][k] + 1);
                    }
                }
            }
        }
        
        int ret = INF;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ret = min(ret, dp[p][i][j]);
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}
/*
 1 2 2 4 0
 1 2 3 4 1 2 3 3 4 2 0
 0
 */
Read More +
解題區/解題區 - UVa

UVa 1267 - Network

Problem

有一個 N 節點的樹，要架設服務的 server，必須滿足所有葉節點到最近的 server 距離小於等於 M。一開始會給定一個架好的 server。

求最少的放置個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2 14 
12 2 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11 
14 
3 4 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11

Sample Output

1
2
1 
0

Solution

針對加好的 server，將這個 server 當作 root，將 tree 轉換成 rooted tree，接著使用貪心。

盡可能放置越遠越好，根據 dfs 搜索的順序，查看內部節點 u，其子樹最遠的葉節點深度為何，以及子樹內部距離最近的 server 所在。

共計三種可能

  • 節點 u 逼不得已情況下放置 server
  • 節點 u 無須 server，其子樹的葉節點都已經符合標準
  • 節點 u 無須 server，其子樹的葉節點必須靠另外一個子樹的最近 server 服務。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int n, m, s, x, y;
int ret = 0;
int dfs(int u, int p, int dep, int &place) {
    int leaf = 0, pp = 0x3f3f3f3f;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == p)
            continue;
        int p;
        int tmp = dfs(v, u, dep + 1, p);
        pp = min(p, pp);
        leaf = max(leaf, tmp);
    }
    place = pp;
    if (leaf - dep + pp - dep <= m)
        leaf = 0;
    if (leaf == dep + m) {
        place = dep;
        ret += (u != s), leaf = 0/*, printf("place %d, %d\n", u, place)*/;
    }
    if (g[u].size() == 1)
        return dep;
    else
        return leaf;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &n, &s, &m);
        for (int i = 0; i <= n; i++)
            g[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        ret = 0;
        int foo;
        dfs(s, -1, 0, foo);
        printf("%d\n", ret);
    }
    return 0;
}
/*
2 
14 12 2 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11 
14 3 4 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11
*/
Read More +