解題區/出題解題

[ACM 題目] 計畫巧遇

Description

Background

正陷入暗戀的蘿莉控，對象正是那小海女 “能年犬”，為了與其相遇，做了一個情報偵測器，但總不能刻意繞道去相遇，這顯然會相當接近跟蹤狂。根據情報網顯示，地圖將會長得跟樹狀圖一樣，接著會有一連串的消息顯示小海女疑似出現的地方，同時也會被驗證是假消息。

能年犬

蘿莉控只想知道如果從 x 點回到家的路上，有沒有機會遇到小海女。如果事先知道將會在哪個場所相遇，就能事先準備。接下來就請你協助他了！

Problem

給定一棵樹，樹根編號 0，每個點一開始的權重為 0，操作有以下兩種。

操作 M x : 將節點 x 的權重從 0->1 或者 1->0。
操作 S x : 輸出從 x 到 root 路徑上，第一個權重為 1 的節點編號。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

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
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
10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
10
M 1
S 8
S 4
M 0
M 7
M 9
S 5
M 3
M 8
S 5
31
0 1
0 2
0 3
1 4
1 5
2 6 
2 7
3 8
4 9
4 10
4 11
6 12
6 13
12 14
12 15
13 16
13 17
14 18
14 19
14 20
17 21
17 22
20 23
21 24
21 25
22 26
22 27
23 28
24 29
24 30
10
M 6
S 29
S 9
M 0
S 9
S 6
S 2
M 6
S 29
S 6

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
1
-1
1
3
6
-1
0
6
0
0
0

Solution

1
Read More +
解題區/解題區 - UVa

UVa 12793 - Confederation

Problem

在三維空間中劃分區域，給定 N 個平面，對於每一個點而言形成 N-tuple 的資訊 (0/1 左側、右側)。請問哪一個 N-tuple 具有最多點，輸出最多的點個數即可。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2 5
1 0 0 1
2 0 0 8
0 1 0
2 2 2
3 3 3
5 5 5
2 18 4
4 8
0 0 1 1
1 0 1 2
-1 1 1 3
-1 -1 1 3
0 0 5
0 0 4
0 0 -2
1 0 5
40 19 104
13 26 84
89 -45 18
3 1 0

Sample Output

1
2
3
5

Solution

直接將平面帶入每一個點，得到 N-tuple 資訊，接著對這個資訊做 RS hash 下，直接壓 int 去做 count，這樣會快於 map<string, int>。

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 <map> 
#include <algorithm>
using namespace std;
int main() {
    int n, m, x, y, z;
    int A[512], B[512], C[512], D[512];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d %d %d %d", A+i, B+i, C+i, D+i);
        map<unsigned int, int> R;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &z);
            unsigned int a = 63689, b = 378551;
            unsigned int value = 0;
            for (int j = 0; j < n; j++) {
                if (A[j] * x + B[j] * y + C[j] * z > D[j])
                    value = value * a + 1;
                else
                    value = value * a + 0;
                a *= b;
            }
            R[value]++;
        }
        int ret = 0;
        for (map<unsigned int, int>::iterator it = R.begin();
            it != R.end(); it++)
                ret = max(ret, it->second);
        printf("%d\n", ret);
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 12796 - Teletransport

Problem

目標從太空船 S 到太空船 T，每一個太空船上有 N 個按鈕，每一種按鈕可以傳送到指定的太空船上，請問 L 步從 S 到 T 的按法有幾種。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2 20
1 1
2 2 2 2
1 1 1 1
2 29
1 1
2 2 2 2
1 1 1 1
2 0
1 1
2 2 2 2
1 1 1 1
2 0
1 2
2 2 2 2
1 1 1 1
3 2
3 1
1 2 2 2
2 1 3 2
2 2 3 1

Sample Output

1
2
3
4
5
7776
0
1
0
4

Solution

既然按鈕都不同，那就可以轉換成一般的 Graph，然後轉化成 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h> 
#include <string.h>
const int mod = 10000;
struct Matrix {
    int v[100][100];
    int row, col; // row x col
    Matrix(int n, int m, int a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++) {
            for(int k = 0; k < col; k++) {
                if (v[i][k])
                for(int j = 0; j < x.col; j++) {
                    ret.v[i][j] += v[i][k] * x.v[k][j],
                    ret.v[i][j] %= mod;
                }
            }
        }
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
};
int main() {
    int N, L, S, T;
    int x, y;
    while (scanf("%d %d", &N, &L) == 2) {
        scanf("%d %d", &S, &T);
        Matrix m(N, N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 4; j++) {
                scanf("%d", &x), x--;
                m.v[i][x]++;
            }
        }
        Matrix ret = m ^ L;
        S--, T--;
        printf("%d\n", ret.v[S][T]);
    }
    return 0;
}
/*
2 20
1 1
2 2 2 2
1 1 1 1
2 29
1 1
2 2 2 2
1 1 1 1
2 0
1 1
2 2 2 2
1 1 1 1
2 0
1 2
2 2 2 2
1 1 1 1
3 2
3 1
1 2 2 2
2 1 3 2
2 2 3 1
*/
Read More +
解題區/Latex

[轉] Latex ACM-ICPC template

要一下出題目規格，就有漂亮的 latex pdf！

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
\documentclass[12pt,psfig,epsf]{article}
\setlength{\topmargin}{-1in}
\setlength{\textheight}{10in}
\setlength{\textwidth}{5.5in}
\usepackage{epsfig}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{graphicx}
\begin{document}
\begin{center}
   {\Large\bfseries Problem test}\\			% Problem Number
   {\large\bf Hello World}\\			% Problem Name
   {\large Input File: {\em test.in}}\\		% Input file name
   {\large Time Limit: {\em 1 Second}}\\	% Time limit in seconds
\end{center}
% Problem description here
Output hello world !
% Technical Specification and constraints
%\vspace*{.3in} \noindent {\large \bfseries Technical Specification}
%\begin{enumerate}
%\item The . . .
%\end{enumerate}
% Input File Format
\vspace*{.3in} \noindent {\large \bfseries Input File Format}\\
Input consists of several datasets.  ...
% Output File Format
\vspace*{.3in} \noindent {\large \bfseries Output Format}\\
For each dataset, ....
% Sample Input
\vspace*{.3in} \noindent {\large \bfseries Sample Input} 
\begin{verbatim}
morris
\end{verbatim}
% Sample Output
\vspace*{.3in} \noindent {\large \bfseries Output for the Sample Input}
\begin{verbatim}
hello morris !
\end{verbatim}
\end{document}
Read More +
解題區/出題解題

[ACM 題目] 人格分裂

Problem

某 M 現在正在平面座標上的原點 (0, 0)，現在四周被擺放了很多很多鏡子，某 M 可以藉由鏡子與他的人格小夥伴對話，請問那些鏡子可以見到小夥伴。

鏡子可以當作一個線段，之間不會交任何一點，只要能見到該鏡子中一小段區域就算可見到。

備註：不考慮反射看到。

Input

輸入有多組測資。

每組測資第一行將會有一個整數 n (n < 32767)，表示總共有多少個鏡子。
接著會有 n 行，每一行上會有 4 個整數 sx, sy, ex, ey，表示鏡子所在的線段。

(-32767 < sx, sy, ex, ey < 32767)

Output

對於每組測資輸出一行，每一行將會有 n 個整數 (0/1)，分別表示輸入中第 i 個鏡子是否可見到。

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
1
5 -5 5 5
4
4 2 5 -2
2 4 6 1
5 5 8 1
3 -4 7 -1
7
-1 2 3 1
2 4 5 -1
-3 -1 1 -2
-1 -4 3 -2
-2 -4 1 -5
-4 1 -1 4
-3 4 -4 3
1
1 1 2 2
2
-1 3 -2 -2
-2 -1 -3 -1

Sample Output

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

More

sample 2

sample 3

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 河道分界

Problem

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

Input

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

Output

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

Sample Input

1
2
3
4
5
6
7
8
9
8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

Sample Output

1
2
3
4
5
6
[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

More

sample

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 樹形鎖頭

Problem

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

Input

輸入有多組測資。

每一組測資第一行 會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

Output

每組測資輸出一行，分別將節點權重輸出。

Sample Input

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

Sample Output

1
5 3 5 3 2 4 8

Solution

1
Read More +
解題區/解題區 - UVa

UVa 12792 - Shuffled Deck

Problem

給定一種洗牌方式，請問重複多少次之後會復原到原本一開始的排列。

Sample Input

1
2
3
4
4
6
2
100002

Sample Output

1
2
3
4
4
3
2
100002

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[1<<21], used[1<<21] = {};
int testcase = 0;
long long gcd(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;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            if (i&1)
                A[i] = i/2;
            else
                A[i] = i/2 + n/2;
        }
        
        testcase++;
        long long lcm = 1;
        for (int i = 0; i < n; i++) {
            if (A[i] != i && used[i] != testcase) {
                int ss = 0;
                for (int j = i; used[j] != testcase; j = A[j])
                    used[j] = testcase, ss++;
                lcm = lcm / gcd(lcm, ss) * ss;
            }
        }
        printf("%d\n", lcm);
    }
    return 0;
}
/*
4
6
2
100002
*/
Read More +
解題區/解題區 - UVa

UVa 12797 - Letters

Problem

找一條最短路徑從左上到右下，並且中間經過的字母不會有同時大小寫出現，也就是說 A 和 a 不能同時出現、B 和 b 不能同時出現 …

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6
DdaAaA
CBAcca
eEaeeE
bBbabB
DbDdDc
fFaAaC
7
aAaaaaa
aAaaaAa
aAaaaAA
aaAaAaa
AaAaaAa
aaAAaAa
aaaaaAa

Sample Output

1
2
13
-1

Solution

窮舉可使用的字符，對於每一種限定方式進行 bfs 搜索。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int N, letter_cnt[128], letter_used[128];
int used[128][128] = {}, dist[128][128], testcase = 0, ret;
char g[128][128];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
void dfs(int idx) {
    if (idx == 10) {
        queue<int> X, Y;
        int tx, ty, x, y;
        if (letter_used[g[0][0]] == 0)
            return;
        testcase++;
        X.push(0), Y.push(0);
        used[0][0] = testcase;
        dist[0][0] = 1;
        while (!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            if (x == N-1 && y == N-1) {
                ret = min(ret, dist[x][y]);
                return;
            }
            for (int i = 0; i < 4; i++) {
                tx = x + dx[i], ty = y + dy[i];
                if (tx < 0 || ty < 0 || tx >= N || ty >= N)
                    continue;
                if (used[tx][ty] == testcase || letter_used[g[tx][ty]] == 0)
                    continue;
                used[tx][ty] = testcase;
                dist[tx][ty] = dist[x][y] + 1;
                X.push(tx), Y.push(ty);
            }
        }
        return ;
    }
    int c = 0;
    if (letter_cnt[idx + 'a']) {
        letter_used[idx + 'a'] = 1;
        dfs(idx+1);
        letter_used[idx + 'a'] = 0;
        c++;
    }
    if (letter_cnt[idx + 'A']) {
        letter_used[idx + 'A'] = 1;
        dfs(idx+1);
        letter_used[idx + 'A'] = 0;
        c++;
    }
    if (c == 0)
        dfs(idx+1);
}
int main() {
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%s", g[i]);
        memset(letter_cnt, 0, sizeof(letter_cnt));
        memset(letter_used, 0, sizeof(letter_used));
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                letter_cnt[g[i][j]]++;
        ret = 0x3f3f3f3f;
        dfs(0);
        printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12791 - Lap

Problem

在賽車運動中，常用 Lap 表示套一圈賽道所消耗的時間，現在有多名賽車手，給予最快一圈多久、最慢一圈多久，請問在最快車手第幾圈的時候，可以倒追最慢的車手。

Sample Input

1
2
3
4
1 10
4 8
5 7
6875 7109

Sample Output

1
2
3
4
2
2
4
31

Solution

懶得推導公式，二分倒追的時間，找到何時會產生倒追，再計算第幾圈即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h> 
#include <math.h>
int main() {
    int X, Y;
    while (scanf("%d %d", &X, &Y) == 2) {
        double l = 0, r = 1e+30, mid;
        int ret = 0;
#define eps 1e-8
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            if (mid * (1.0/X - 1.0/Y) >= 1)
                r = mid;
            else
                l = mid;
        }
        printf("%.0lf\n", ceil(mid/X));
    }
    return 0;
}
Read More +