解題區/解題區 - UVa

UVa 12648 - Boss

Problem

給一個管理階層圖 (DAG)，一名員工可能被很多上司管理

  • 員工之間可能會交換職位
  • 詢問某名員工最年輕的上司年紀為何 (包含上司的上司 …)

Sample Output

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
7 8 9
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
P 7
T 4 2
P 7
P 5
T 1 4
P 7
T 4 7
P 2
P 6
6 5 6
10 20 30 40 50 60
1 5
1 4
3 6
2 5
4 5
P 1
P 5
P 6
T 1 6
P 1
P 4

Sample Output

1
2
3
4
5
6
7
8
9
10
11
18
21
18
18
*
26
*
10
30
30
60

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
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int visited[512];
int age[512];
vector<int> g[512], boss[512];
void dfs(int u, int em) {
    visited[u] = 1, boss[em].push_back(u);
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(visited[v])	continue;
        dfs(v, em);
    }
}
int main() {
    int N, M, I, x, y, em;
    char cmd[10];
    while(scanf("%d %d %d", &N, &M, &I) == 3) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &age[i]);
            g[i].clear(), boss[i].clear();
        }
        for(int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            g[y].push_back(x);
        }
        
        int mp[512];
        for(int i = 1; i <= N; i++) {
            mp[i] = i;
            memset(visited, 0, sizeof(visited));
            visited[i] = 1;
            for(int j = 0; j < g[i].size(); j++)
                if(!visited[g[i][j]])
                    dfs(g[i][j], i);
        }
        
        for(int i = 0; i < I; i++) {
            scanf("%s", cmd);
            if(cmd[0] == 'P') {
                scanf("%d", &em);
                int ret = 0x3f3f3f3f;
                em = mp[em];
                for(int i = 0; i < boss[em].size(); i++)
                    ret = min(ret, age[boss[em][i]]);
                if(ret == 0x3f3f3f3f)
                    puts("*");
                else
                    printf("%d\n", ret);
            } else {
                scanf("%d %d", &x, &y);
                swap(age[mp[x]], age[mp[y]]);
                swap(mp[x], mp[y]);
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12489 - Combating cancer

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

Sample Output

1
2
N
S

Solution

找到樹的最小表示法，用括號來表示一棵樹，則可以對所有的子樹的最小表示法做排序，就可以構成這個樹的最小表示法。一直遞歸下去就可以得到最小表示法。

但是這個最小表示法只能用在有根樹，因此對於無根樹利用拓樸排序找到樹的中心 (一個或者是兩個)。

因此最後相互比較中心的情況。

這一題為了加快可以使用 hash，而把字串比較和排序撇開，但是千萬不要拿不同中心兩個 hash 取最小值，再進行同構比較。原因會發生在於中心的取捨，如果直接定義拓樸最後兩個點作為中心，則有可能一點不是中心，那麼就會造成分析上的錯誤。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int dfsMinExp(int u, int p, vector<int> g[]) {
    vector<int>	branch;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == p)	continue;
        branch.push_back(dfsMinExp(v, u, g));
    }
    sort(branch.begin(), branch.end());
//	string exp = "";
//	for(int i = 0; i < branch.size(); i++)
//		exp += branch[i];	
//	return "(" + exp + ")";	
    int a = 63689, b = 378551;
    int ret = 0;
    branch.push_back(1);
    for(int i = 0; i < branch.size(); i++)
        ret = ret * a + branch[i], a *= b;
    return ret;
}
vector<int> getTreeMinExp(vector<int> g[], int n) {
    if(n == 1)	return vector<int>({1});
    int deg[10005] = {}, u, v;
    int topo[10005] = {}, idx = 0;
    queue<int> Q;
    for(int i = 1; i <= n; i++) {
        deg[i] = g[i].size();
        if(deg[i] == 1)	Q.push(i);
    }
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        topo[idx++] = u;
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(--deg[v] == 1)
                Q.push(v);
        }
    }
    vector<int> ret;
    ret.push_back(dfsMinExp(topo[idx-1], -1, g));
    ret.push_back(dfsMinExp(topo[idx-2], -1, g));
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, x, y;
    vector<int> g1[65536], g2[65536];
    while(scanf("%d", &n) == 1) {
        for(int i = 1; i <= n; i++)
            g1[i].clear(), g2[i].clear();
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g1[x].push_back(y);
            g1[y].push_back(x);
        }
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g2[x].push_back(y);
            g2[y].push_back(x);
        }
        vector<int> hash1 = getTreeMinExp(g1, n);
        vector<int> hash2 = getTreeMinExp(g2, n);
        int same = 0;
        for(int i = 0; i < hash1.size(); i++)
            for(int j = 0; j < hash2.size(); j++)
                same |= hash1[i] == hash2[j];
        puts(same ? "S" : "N");
//		printf("%d %d\n", hash1, hash2);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12486 - Space Elevator

Problem

將所有數字中出現 4 或者是 13 為子字串排除，將剩餘數字排序後，根據輸入輸出 i-th 的結果為何。(傳統避諱的樓層命名方式)

Sample Input

1
2
3
4
5
1
4
11
12
440

Sample Output

1
2
3
4
5
1
5
12
15
666

Solution

  • dp[i][0] 表示長度為 i 的情況下，不以 3 開頭的所有符合數字
  • dp[i][1] 表示長度為 i 的情況下，以 3 開頭的所有符合數字

接著，企圖添加 digit 在長度為 i-1 的數字前面，只要不添加 1 湊出 13 即可。直接禁用 4 就沒有什麼問題。

而隨後要輸出 i-th 的時候，用扣的方式依序得到 lower_bound。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    unsigned long long n;
    unsigned long long dp[30][2] = {};
    unsigned long long sum[30] = {};
    dp[0][0] = 1; // [1-9^3], dp[i][1] - [3(0-9)*]
    for(int i = 1; i < 30; i++) {
        for(int j = 0; j < 2; j++) {
            dp[i][0] = 8 * dp[i-1][0] + 7 * dp[i-1][1];
            dp[i][1] = dp[i-1][0] + dp[i-1][1];
        }
    }
    for(int i = 1; i < 30; i++)
        sum[i] = sum[i-1] + (dp[i-1][0] + dp[i-1][1])* 7 + dp[i][1] - dp[i-1][1];
    while(scanf("%llu", &n) == 1) {
        int len = 0;
        for(len = 1; sum[len] <= n; len++);
        int prev = 0;
        n -= sum[len-1];
        for(int i = len; i >= 1; i--) {
            int last = -1;
            for(int j = (i == len); j <= 9; j++) {
                if(j == 4 || (prev == 1 && j == 3))	continue;
                if(j == 1) { // [1] - [0-9^3]
                    if(n > dp[i-1][0]) {
                        n -= dp[i-1][0], last = j;
//						printf("%llu test\n", dp[i-1][0]);
                    } else {
                        break;
                    }
                } else {
                    if(n > dp[i-1][0] + dp[i-1][1]) {
                        n -= dp[i-1][0] + dp[i-1][1], last = j;
//						printf("%llu test\n", dp[i-1][0] + dp[i-1][1]);
                    } else
                        break;
                }
            }
            last++;
            if(last == 4)	last++;
            if(i == len && last == 0)	last = 1;
            if(prev == 1 && last == 3)	last = 5;
            printf("%d", last), prev = last;
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12484 - Cards

Problem

每一個序列，每次只能拿走首元素或者尾元素，Alberto 和 Wanderley 輪流取牌，由 Alberto 先手，請問遊戲最後 Alberto 最高能得多少分，而 Wanderley 會盡力阻止她。

Sample Input

1
2
3
4
5
6
4
0 -3 5 10
4
0 -3 5 7
4
47 50 -3 7

Sample Output

1
2
3
10
7
57

Solution

照著 dp 的思路下去，因為要輪流取，而 Wanderley 只會想要最小化 Alberto 分數，不會考慮自己的分數，因此轉移的時候會盡可能地小。

dp[i][j] 表示當前剩餘長度為 i, 起始首元素為 j，由於狀態太多，必須靠滾動數組來完成 dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int n, a[10005];
    long long dp[2][10005];
    while(scanf("%d", &n) == 1) {
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j + i < n; j++) {
                if((i&1) == 1)
                    dp[0][j] = max(dp[1][j+1] + a[j], dp[1][j] + a[j+i]);
                else
                    dp[1][j] = min(dp[0][j+1], dp[0][j]);
            }
        }
        printf("%lld\n", dp[0][0]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12483 - Toboggan of Marbles

Problem

給彈珠檯的高度和寬度，以及左右兩側延伸出的平台，問彈珠滾落的最大直徑為何？

Sample Input

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

Sample Output

1
2
2.00
1.41

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
enum LINE_TYPE {LINE, SEGMENT};
struct LINE2D {
    Pt s, e;
    LINE_TYPE type;
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
double onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
    int a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double closest(LINE2D l1, LINE2D l2) {
    if(l1.type == SEGMENT && l2.type == SEGMENT) {
        if(intersection(l1.s, l1.e, l2.s, l2.e))
            return 0;
        double c = 1e+30;
        if(between(l1.s, l1.e, l2.s))
            c = min(c, distProjection(l1.s, l1.e, l2.s));
        else
            c = min(c, min(dist(l1.s, l2.s), dist(l1.e, l2.s)));
            
        if(between(l1.s, l1.e, l2.e))
            c = min(c, distProjection(l1.s, l1.e, l2.e));
        else
            c = min(c, min(dist(l1.s, l2.e), dist(l1.e, l2.e)));
        /* opposite */
        if(between(l2.s, l2.e, l1.s))
            c = min(c, distProjection(l2.s, l2.e, l1.s));
        else
            c = min(c, min(dist(l1.s, l2.s), dist(l1.e, l2.s)));
            
        if(between(l2.s, l2.e, l1.e))
            c = min(c, distProjection(l2.s, l2.e, l1.e));
        else
            c = min(c, min(dist(l2.s, l1.e), dist(l2.e, l1.e)));
        return c;
    }
    if(l1.type == LINE && l2.type == LINE) {
        double a1, a2, b1, b2, c1, c2;
        a1 = l1.s.y - l1.e.y;
        b1 = l1.e.x - l1.s.x;
        c1 = - (a1 * l1.s.x + b1 * l1.s.y);
        a2 = l2.s.y - l2.e.y;
        b2 = l2.e.x - l2.s.x;
        c2 = - (a2 * l2.s.x + b2 * l2.s.y);
        if(a1 * b2 - a2 * b1 != 0)
            return 0;
        return distProjection(l1.s, l1.e, l2.s);
    }
    if(l1.type != l2.type) {
        if(l1.type == SEGMENT)
            swap(l1, l2);
        /* l1 LINE, l2 SEGMENT*/
        double a1, b1, c1;
        a1 = l1.s.y - l1.e.y;
        b1 = l1.e.x - l1.s.x;
        c1 = - (a1 * l1.s.x + b1 * l1.s.y);
        int v1, v2;
        v1 = a1 * l2.s.x + b1 * l2.s.y + c1;
        v2 = a1 * l2.e.x + b1 * l2.e.y + c1;
        if(v1 * v2 <= 0)
            return 0; // different side
        return min(distProjection(l1.s, l1.e, l2.s), distProjection(l1.s, l1.e, l2.e));
    }
    return -1;
}
int main() {
    int n;
    double L, H;
    LINE2D D[1024];
    while(scanf("%d", &n) == 1) {
        scanf("%lf %lf", &L, &H);
        for(int i = 0; i < n; i++) {
            D[i].s.x = i&1 ? L : 0;
            scanf("%lf %lf %lf", &D[i].s.y, &D[i].e.x, &D[i].e.y);
            D[i].type = SEGMENT;
        }
        
        LINE2D wall1, wall2;
        wall1.type = wall2.type = LINE;
        wall1.s.x = wall1.e.x = 0;
        wall1.s.y = 1, wall1.e.y = 0;
        
        wall2.s.x = wall2.e.x = L;
        wall2.s.y = 1, wall2.e.y = 0;
        
        double r = L;
        for(int i = 0; i < n; i++) {
            if(i&1)
                r = min(r, closest(wall1, D[i]));
            else
                r = min(r, closest(wall2, D[i]));
            if(i + 1 < n) {
                r = min(r, closest(D[i], D[i+1]));
            }
        }
        printf("%.2lf\n", r);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12446 - How Many... in 3D!

Problem

Given a 2x2xN box, in how many ways can you fill it with 1x1x2 blocks?
Input Format

The input starts with an integer T - the number of test cases (T <= 10,000). T cases follow on each subsequent line, each of them containing the integer N (1 <= N <= 1,000,000).

Output Format

For each test case, print the number of ways to fill the box modulo 1,000,000,007

Sample Input

1
2
3
4
3
1
2
3

Sample Output

1
2
3
2
9
32

Solution

把幾種情況畫出來，會發現有一種特別的之之型，最後會接上一個 1x2 的來湊滿一個 2 x 2 x N 的情況，為此我們必須要知道有多少這種之之型可以從哪裡拆分出來。

會在代碼中發現一個變數 c 存放的便是以之之型結束的方法數，之之型可以把最後一個 1x2 拿走，繼續延伸。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
long long dp[1048576] = {};
const long long mod = 1000000007LL;
int main() {
    dp[0] = 1, dp[1] = 2, dp[2] = 9, dp[3] = 32;
    long long c = 4;
    for(int i = 4; i <= 1000000; i++) {
        c = (c + dp[i-3] * 4)%mod; // {ZigZag}
        dp[i] = (dp[i-1] * 2 + dp[i-2] * 5 + c)%mod; 
    }
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
    return 0;
}
/*
1000
1
2
3
4
5
6
7
2
9
32
121
450
1681
6272
*/
Read More +
解題區/解題區 - UVa

UVa 12436 - Rip Van Winkle's Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long long data[250001];
void A( int st, int nd ) {
    for( int i = st; i <= nd; i++ ) data[i] = data[i] + (i - st + 1);
}
void B( int st, int nd ) {
    for( int i = st; i <= nd; i++ ) data[i] = data[i] + (nd - i + 1);
}
void C( int st, int nd, int x ) {
    for( int i = st; i <= nd; i++ ) data[i] = x;
}
long long S( int st, int nd ) {
    long long res = 0;
    for( int i = st; i <= nd; i++ ) res += data[i];
    return res;
}

Input

The first line of input will contain T (≤ 4*105) denoting the number of operations. Each of the next T lines starts with a character (‘A’, ‘B’, ‘C’ or ‘S’), which indicates the type of operation. Character ‘A’, ‘B’ or ‘S’ will be followed by two integers, st and nd in the same line. Character ‘C’ is followed by three integers, st, nd and x. It’s assumed that, 1 ≤ st ≤ nd ≤ 250000 and -105 ≤ x ≤ 105. The meanings of these integers are explained by the code of Rip Van Winkle.

Output

For each line starting with the character ‘S’, print S( st, nd ) as defined in the code. Dataset is huge, so use faster I/O methods.

Sample Input

1
2
3
4
5
6
7
8
7
A 1 4
B 2 3
S 1 3
C 3 4 -2
S 2 4
B 1 3
S 2 4

Output for Sample Input

1
2
3
9
0
3

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 262144
#define MAXM 1048576 + 10 
typedef long long LL;
LL sum[MAXM];
LL preB[MAXM], preD[MAXM]; // base, diff
LL sufB[MAXM], sufD[MAXM];
LL setB[MAXM], setD[MAXM];
void pushUp(int k) {
    sum[k] = sum[k<<1] + sum[k<<1|1];
}
void pushDown(int k, int l, int r) {
    int m = (l + r) /2;
    
    if(setB[k]) {
        setB[k<<1] = 1, setD[k<<1] = setD[k];
        setB[k<<1|1] = 1, setD[k<<1|1] = setD[k];
        preB[k<<1] = preD[k<<1] = sufB[k<<1] = sufD[k<<1] = 0;
        preB[k<<1|1] = preD[k<<1|1] = sufB[k<<1|1] = sufD[k<<1|1] = 0;
        sum[k<<1] = (m - l + 1) * setD[k];
        sum[k<<1|1] = (r - m) * setD[k];
        setB[k] = setD[k] = 0;
    }
    if(preB[k]) {
        preB[k<<1] += preB[k], preD[k<<1] += preD[k];
        preB[k<<1|1] += preB[k] + preD[k] * (m - l + 1), preD[k<<1|1] += preD[k];
        sum[k<<1] += (2 * preB[k] + (m - l) * preD[k]) * (m - l + 1)/2;
        sum[k<<1|1] += (2 * preB[k] + (r - l + m + 1 - l) * preD[k]) * (r - m)/2;
        preB[k] = preD[k] = 0;
    }
    if(sufB[k]) {
        sufB[k<<1] += sufB[k] + (r - m) * sufD[k], sufD[k<<1] += sufD[k];
        sum[k<<1] += (2 * sufB[k] + (r - m + r - l) * sufD[k]) * (m - l + 1)/2;
        sufB[k<<1|1] += sufB[k], sufD[k<<1|1] += sufD[k];
        sum[k<<1|1] += (2 * sufB[k] + (r - m - 1) * sufD[k]) * (r - m)/2;
//		printf("[%d %d] suffix %lld %lld , = %lld %lld\n", l, r, sufB[k], sufD[k], sum[k<<1], sum[k<<1|1]);
        sufB[k] = sufD[k] = 0;
    }
}
void modifyA(int k, int l, int r, int x, int y) {
    if(l > r)	return;
    if(x <= l && r <= y)  {
        preB[k] += l - x + 1, preD[k]++;
        sum[k] += (LL)(2 * (l - x + 1) + r - l) * (r - l + 1)/2;
        return;
    }
    pushDown(k, l, r);
    int m = (l+r) /2;
    if(y <= m)
        modifyA(k<<1, l, m, x, y);
    else if(x > m)
        modifyA(k<<1|1, m+1, r, x, y);
    else {
        modifyA(k<<1, l, m, x, y);
        modifyA(k<<1|1, m+1, r, x, y);
    }
    pushUp(k);
}
void modifyB(int k, int l, int r, int x, int y) {
    if(l > r)	return;
    pushDown(k, l, r);
    if(x <= l && r <= y)  {
        sufB[k] += y - r + 1, sufD[k]++;
        sum[k] += (LL)(2 * (y - r + 1) + r - l) * (r - l + 1)/2;
//		printf("BB [%d %d] %d\n", l, r, base);
        return;
    }
    int m = (l+r) /2;
    if(y <= m)
        modifyB(k<<1, l, m, x, y);
    else if(x > m)
        modifyB(k<<1|1, m+1, r, x, y);
    else {
        modifyB(k<<1, l, m, x, y);
        modifyB(k<<1|1, m+1, r, x, y);
    }
    pushUp(k);
}
void modifyC(int k, int l, int r, int x, int y, int mm) {
    if(l > r)	return;
    if(x <= l && r <= y)  {
        setB[k] = 1, setD[k] = mm;
        preB[k] = preD[k] = sufB[k] = sufD[k] = 0;
        sum[k] = (LL)mm * (r - l + 1);
//		printf("CCCC [%d %d] %lld\n", l, r, sum[k]);
        return;
    }
    pushDown(k, l, r);
    int m = (l+r) /2;
    if(y <= m)
        modifyC(k<<1, l, m, x, y, mm);
    else if(x > m)
        modifyC(k<<1|1, m+1, r, x, y, mm);
    else {
        modifyC(k<<1, l, m, x, y, mm);
        modifyC(k<<1|1, m+1, r, x, y, mm);
    }
    pushUp(k);
}
long long query(int k, int l, int r, int x, int y) {
    if(l > r)	return 0;
    pushDown(k, l, r);
    if(x <= l && r <= y) {
//		printf("qq[%d %d] %lld\n", l, r, sum[k]);
        return sum[k];
    }
    int m = (l + r)/2;
    long long ret = 0;
    if(x <= m)
        ret += query(k<<1, l, m, x, y);
    if(y > m)
        ret += query(k<<1|1, m+1, r, x, y);
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int T, st, nd, x;
    char cmd[128];
    while(scanf("%d", &T) == 1) {
        memset(sum, 0, sizeof(sum));
        memset(preB, 0, sizeof(preB));
        memset(preD, 0, sizeof(preD));
        memset(sufB, 0, sizeof(sufB));
        memset(sufD, 0, sizeof(sufD));
        memset(setB, 0, sizeof(setB));
        memset(setD, 0, sizeof(setD));
        while(T--) {
            scanf("%s", cmd);
            if(cmd[0] == 'C')
                scanf("%d %d %d", &st, &nd, &x);
            else
                scanf("%d %d", &st, &nd);
            switch(cmd[0]) {
                case 'A':
                    modifyA(1, 1, MAXN, st, nd);
                    break;
                case 'B':
                    modifyB(1, 1, MAXN, st, nd);
                    break;
                case 'C':
                    modifyC(1, 1, MAXN, st, nd, x);
                    break;
                case 'S':
                    long long ret = query(1, 1, MAXN, st, nd);
                    printf("%lld\n", ret);
                    break;
            }
        } 
    }
    return 0;
}
/*
1000
S 2 3
A 7 15
B 4 5
B 15 16
C 2 10 3
B 14 15
A 10 18
S 4 4
A 3 16
B 6 14
B 4 7
S 8 11
*/
Read More +
解題區/解題區 - UVa

UVa 12396 - Remoteland

Problem

求 N! 的因數中最大的完全平方數。

Sample Input

1
2
3
4
4
9348095
6297540
0

Sample Output

1
2
3
4
177582252
644064736

Solution

對 N! 做因數分解。

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
#include <stdio.h> 
#include <algorithm>
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[1048576], Pt = 0;
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 mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while(y) {
        if(y&1)
            ret *= x, ret %= mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
}
int main() {
    sieve();
    int n;
    const long long mod = 1000000007LL;
    while(scanf("%d", &n) == 1 && n) {
        long long ret = 1;
        for(int i = 0; i < Pt; i++) {
            long long p = P[i], cnt = 0;
            while(p <= n)
                cnt += n / p, p *= P[i];
            if(cnt < 2)	break;
            ret *= mpow(P[i], cnt/2*2, mod);
            ret %= mod;
        } 
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12368 - Candles

Problem

現在只有 0 - 9 共計 10 根蠟燭，有 N 個人過生日，每個人的生日年紀不大於 100。

最多用 10 根蠟燭，來表示每一個人的生日。每個人的生日可以用兩個整數加總，或者單純用一個整數表示。

Sample Input

1
2
3
2 10 11
1 30
0

Output for Sample Input

1
2
Case 1: 654
Case 2: 30

Solution

預建表，找到所有數字 [1, 100] 能用哪幾種蠟燭建出來。

測資很緊，不建表會一直 TLE。

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
#include <stdio.h> 
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int able[128][1024];
void build() {
    int d1, d2, d3, d4;
    for(int i = 1; i <= 100; i++) {
        if(i < 100) {
            if(i < 10) {
                d1 = i;
                able[i][1<<d1] = 1;
            } else {
                d1 = i%10, d2 = i/10;
                if(d1 != d2)
                    able[i][(1<<d1)|(1<<d2)] = 1;
            }
        }
        for(int j = 1; j < i; j++) {
            int a = j, b = i - j, mask = 0;
            if(a < 10) {
                mask |= 1<<a;
            } else {
                d1 = a%10, d2 = a/10;
                if(d1 == d2)
                    continue;
                mask |= (1<<d1)|(1<<d2);
            }
            if(b < 10) {
                if(mask&(1<<b))
                    continue;
                mask |= 1<<b;
            } else {
                d1 = b%10, d2 = b/10;
                if(d1 == d2)
                    continue;
                if(mask&((1<<d1)|(1<<d2)))
                    continue;
                mask |= (1<<d1)|(1<<d2);
            }
            able[i][mask] = 1;
        }
    }
    for(int i = 0; i < 128; i++) {
        for(int j = 0; j < 1024; j++) {
            for(int k = j; k; k = k&(k-1))
                able[i][j] |= able[i][j&(k-1)];
        }
    }
}
int main() {
    build();
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n, A[10], cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        map<int, int> R;
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        int ret = (1<<10)-1;
        for(int i = 0; i < (1<<10); i++) {
            if(__builtin_popcount(i) >= __builtin_popcount(ret))
                continue;
            int f = 1;
            for(int j = 0; j < n && f; j++)
                f &= able[A[j]][i];
            if(f) {
                ret = i;		
            }
        }							
        printf("Case %d: ", ++cases);
        for(int i = 9; i >= 0; i--) {
            if((ret>>i)&1)
                printf("%d", i);
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12363 - Hedge Mazes

Problem

給一無向圖，問任兩點是否存在唯一的路徑到達。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6 5 3
1 2
2 3
2 4
2 5
4 5
1 3
1 5
2 6
4 2 3
1 2
2 3
1 4
1 3
1 2
0 0 0

Sample Output

1
2
3
4
5
6
7
8
Y
N
N
-
N
Y
Y
-

Solution

唯一路徑，保證 x - y 之間走過的只會有橋 (由很多橋構成)，將所有橋找到，並且將橋兩端利用并查集合併 (構成大橋)

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[131072];
int visited[131072], depth[131072];
vector< pair<int, int> > bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    int back = 0x3f3f3f3f;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == p)	continue;
        if(!visited[v]) {
            int b = findBridge(v, u, dep+1);
            if(b > dep) {
                bridge.push_back(make_pair(u, v));
            }
            back = min(back, b);
        } else {
            back = min(back, depth[v]);
        }
    }
    return back;
}
int rank[131072], parent[131072];
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)	return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], parent[y] = x;
    else
        rank[y] += rank[x], parent[x] = y;
}
int main() {
    int n, m, q, x, y;
    while(scanf("%d %d %d", &n, &m, &q) == 3 && n+m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        bridge.clear();
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                findBridge(i, -1, 0);
            }
        }
        
        for(int i = 0; i < n; i++)
            rank[i] = 1, parent[i] = i;
        for(int i = 0; i < bridge.size(); i++)
            joint(bridge[i].first, bridge[i].second);
        for(int i = 0; i < q; i++) {
            scanf("%d %d", &x ,&y);
            x--, y--;
            puts(findp(x) == findp(y) ? "Y" : "N");
        }
        puts("-");
    }
    return 0;
}
Read More +