2894 Arrange the Problem Set
2895 Cache
Recommended首先我們用1000大的cache，這樣次數最少。
然后我們試著用更小的cache來達到同樣的效果。
注意到對兩個地址i和j，如果他們的request區間有overlap,那么所滿足i % n == j % n的n就不能用作cache大小。
然后我們就把所有不合法的cache size標記，尋找最小的～
注意n == 0的時候輸出0,-_-bbbbbbbb
CODE
1
// ZOJ Monthly, January 2008, Cache
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <algorithm>
8
9using namespace std;
10
11const int MaxN = 1000000 + 10;
12pair<int, int> occur[1000];
13int s[MaxN], n;
14bool mark[1010];
15
16void init();
17void work();
18void mark_factor(int x);
19
20int main() 
{
21
for (; scanf("%d", &n) != EOF; ) {
22
init();
23 work();
24
}
25
26 return 0;
27
}
28
29void init() {
30 fill(occur, occur + 1000, make_pair(n + 1, -1));
31 for (int i = 0; i < n; ++i) {
32 scanf("%d", &s[i]);
33 occur[s[i]].first <?= i;
34 occur[s[i]].second >?= i;
35 }
36}
37
38void work() {
39 if (n == 0) {
40 cout << 0 << endl; return;
41 }
42
43 fill(mark, mark + 1010, false);
44 for (int i = 0; i < 1000; ++i)
45 for (int j = i + 1; j < 1000; ++j) {
46 if (occur[i].second < occur[j].first || occur[j].second < occur[i].first) continue;
47
48 mark[1] = true; mark_factor(j - i);
49 }
50
51 int ans = 1;
52 for (; mark[ans]; ) ++ans;
53 cout << ans << endl;
54}
55
56void mark_factor(int x) {
57 if (mark[x]) return;
58 mark[x] = true;
59 for (int i = 2; i * i <= x; ++i) {
60 if (x % i) continue;
61 mark_factor(i); mark_factor(x / i);
62 }
63}
64
65
662896 Common Factor
Recommended在一個素數域上考慮這個問題，那么他們的Common Factor可以通過GCD求出來。
然后測試一些大素數，如果都通過了就可以認為他們存在Common Factor了。
2897 Desmond's Ambition
Recommended首先求出所有的橋，如果將那些block視為一個點那么圖就成為一棵樹。
接下來分為4部分求:（建議自己想想，這個不太容易描述）
1. 每塊內部的距離，暴力。
2. 每個橋被使用的次數，其實就是橋左邊的頂點數*橋右邊的頂點數，在DFS的時候順便計算即可，參考
Bridges 3. 每塊內部的點對的最短路被經過的次數，對(u, v)點對來說，就是f(u)*f(v)*dist(u,v)
f(u)定義為，列舉出所有一個頂點在u上的橋，在橋的令一端的頂點個數和。
4. 每塊內部點通過某個點和外界聯系的距離和。f(u) * sum_dist(u)，sum_dist(u)是u到同一塊內的其他所有點的最短距離和。
CODE
1// ZOJ Monthly, January 2008, Desmond's Ambition
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <vector>
8
9using namespace std;
10
11const int MaxN = 10000 + 10, MaxEN = 100000 + 10;
12struct EdgeNode {
13 int p, len, id;
14};
15vector<EdgeNode> g[MaxN];
16vector<EdgeNode> tree[MaxN];
17vector<int> block[MaxN];
18int n, m, color[MaxN], sum[MaxN], block_cnt;
19long long ans;
20long long f1[MaxN], f2[MaxN];
21bool vis[MaxN], is_bridge[MaxEN];
22int bridge[MaxEN], bridge_cnt;
23int edge[MaxEN][3];
24int low[MaxN], depth[MaxN], dfs_color[MaxN];
25
26void init();
27void work();
28void dfs_bridge(int u, int fa, int deep);
29void dfs_tree(int u, int fa);
30void dfs_block(int u, int fa, int block_id);
31void generate_block_dist(int idx);
32long long gcd(long long a, long long b);
33
34int main() {
35 for (; scanf("%d%d", &n, &m) != EOF; ) {
36 init();
37 work();
38 }
39 return 0;
40}
41
42void init() {
43 for (int i = 0; i < n; ++i) {
44 g[i].clear(); tree[i].clear(); block[i].clear();
45 }
46 for (int i = 0; i < m; ++i) {
47 int a, b, c;
48 scanf("%d%d%d", &a, &b, &c);
49 --a; --b;
50 EdgeNode tmp;
51 tmp.p = b; tmp.len = c; tmp.id = i;
52 g[a].push_back(tmp);
53 tmp.p = a;
54 g[b].push_back(tmp);
55 edge[i][0] = a; edge[i][1] = b; edge[i][2] = c;
56 }
57}
58
59void work() {
60 // Generate all the bridges
61 fill(is_bridge, is_bridge + m, false);
62 fill(dfs_color, dfs_color + n, 0);
63 bridge_cnt = 0;
64 dfs_bridge(0, -1, 0);
65
66 // Generate all the blocks
67 fill(vis, vis + n, false);
68 block_cnt = 0;
69 for (int i = 0; i < n; ++i)
70 if (!vis[i]) {
71 dfs_block(i, -1, block_cnt);
72 ++block_cnt;
73 }
74
75 // Generate the Tree
76 fill(f1, f1 + n, 0); fill(f2, f2 + n, 0);
77 for (int i = 0; i < bridge_cnt; ++i) {
78 int eid = bridge[i];
79 int a = edge[eid][0], b = edge[eid][1], c = edge[eid][2];
80 int aa = color[a], bb = color[b];
81 EdgeNode tmp;
82 tmp.p = bb; tmp.len = c; tmp.id = eid;
83 tree[aa].push_back(tmp);
84 tmp.p = aa;
85 tree[bb].push_back(tmp);
86
87 // f1[a] += block[bb].size(); f1[b] += block[aa].size();
88 }
89
90 ans = 0;
91 // Part1, all the routes in the tree
92 dfs_tree(0, -1);
93
94 // Part2, all the internal routes
95 for (int i = 0; i < block_cnt; ++i)
96 generate_block_dist(i);
97
98 // Part3, merge
99 for (int i = 0; i < n; ++i)
100 ans += f1[i] * f2[i];
101
102 long long t1 = ans, t2 = n * (n - 1) / 2, d = gcd(t1, t2);
103 cout << t1 / d << "/" << t2 / d << endl;
104}
105
106void dfs_bridge(int u, int fa, int deep) {
107 dfs_color[u] = 1;
108 depth[u] = deep; low[u] = deep;
109
110 for (vector<EdgeNode>::iterator it = g[u].begin(); it != g[u].end(); ++it) {
111 if (it->p == fa) continue;
112 if (dfs_color[it->p] == 1) {
113 low[u] <?= depth[it->p];
114 }
115 else if (dfs_color[it->p] == 0) {
116 dfs_bridge(it->p, u, deep + 1);
117 low[u] <?= low[it->p];
118 if (low[it->p] > depth[u]) {
119 is_bridge[it->id] = true;
120 bridge[bridge_cnt++] = it->id;
121 }
122 }
123 }
124
125 dfs_color[u] = 2;
126}
127
128void dfs_tree(int u, int fa) {
129 sum[u] = block[u].size();
130
131 for (vector<EdgeNode>::iterator it = tree[u].begin(); it != tree[u].end(); ++it) {
132 if (it->p == fa) continue;
133 dfs_tree(it->p, u);
134 sum[u] += sum[it->p];
135 ans += static_cast<long long>(sum[it->p]) * (n - sum[it->p]) * it->len;
136
137 int eid = it->id;
138 int a = edge[eid][0], b = edge[eid][1];
139 int aa = color[a], bb = color[b];
140 if (aa == u) {
141 f1[a] += sum[it->p]; f1[b] += n - sum[it->p];
142 }
143 else {
144 f1[b] += sum[it->p]; f1[a] += n - sum[it->p];
145 }
146
147
148 }
149}
150
151void generate_block_dist(int idx) {
152 int gg[30][30];
153 fill(gg[0], gg[block[idx].size()], 1000000000);
154
155 for (vector<int>::iterator it = block[idx].begin(); it != block[idx].end(); ++it) {
156 int u = *it;
157 int uu = it - block[idx].begin();
158 for (vector<EdgeNode>::iterator eit = g[u].begin(); eit != g[u].end(); ++eit) {
159 int v = eit->p;
160 if (color[v] != idx) continue;
161 int vv = find(block[idx].begin(), block[idx].end(), v) - block[idx].begin();
162 gg[uu][vv] = eit->len;
163 }
164 }
165
166 int n = block[idx].size();
167 for (int j = 0; j < n; ++j)
168 for (int i = 0; i < n; ++i)
169 for (int k = 0; k < n; ++k)
170 gg[i][k] <?= gg[i][j] + gg[j][k];
171 for (int i = 0; i < n; ++i) {
172 long long &val = f2[block[idx][i]];
173 val = 0;
174 for (int j = 0; j < n; ++j)
175 if (j != i) val += gg[i][j];
176 }
177
178 for (int i = 0; i < n; ++i)
179 for (int j = i + 1; j < n; ++j) {
180 ans += gg[i][j];
181 ans += static_cast<long long>(gg[i][j]) * f1[block[idx][i]] * f1[block[idx][j]];
182 }
183
184}
185
186void dfs_block(int u, int fa, int block_id) {
187 color[u] = block_id; block[block_id].push_back(u);
188 vis[u] = true;
189
190 for (vector<EdgeNode>::iterator it = g[u].begin(); it != g[u].end(); ++it) {
191 if ((!is_bridge[it->id]) && (!vis[it->p]))
192 dfs_block(it->p, u, block_id);
193 }
194}
195
196long long gcd(long long a, long long b) {
197 return b == 0 ? a : gcd(b, a % b);
198}
199
2898 Greedy Grave Robber
24個寶藏，搜12個，把他們的機關觸發情況存入hash or map，然后搜右邊12個，查表。
很經典的想法了。
2899 Hangzhou Tour
狀態f[st][i][j], st表示已訪問的頂點，i表示目前位置，j表示自行車位置，dp。
注意f[st][i][j]只可能轉移到>=st的狀態。有序性存在。
對相同的st的那些狀態使用dijstra or SPFA.
2900 Icecream
dp, f[i][j][k] = 使用前i個icecream, 組成長度為j, 最后一個元素值為k的方案數。
復雜度2000 * 2000 * 100...10s夠了。
2901 MV Maker
Recommendedf[p][a][b] = 長度為2^p + 1, 第一個是a, 最后一個是b的最大value.
然后拼接～，復雜度O(n^3*logL)
CODE
1// ZOJ Monthly, January 2008, MV Maker
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7
8using namespace std;
9
10const int MaxN = 100 + 10;
11const long long INF = 1000000000000000LL;
12long long f[20][MaxN][MaxN], g[2][MaxN];
13
14int main() {
15 int t;
16 cin >> t;
17 for (; t > 0; --t) {
18 int n, l;
19 cin >> n >> l;
20 for (int i = 0; i < n; ++i)
21 for (int j = 0; j < n; ++j)
22 cin >> f[0][i][j];
23
24 --l;
25
26 int lev = 0;
27 for (int i = 0; (1 << (i + 1)) <= l; ++i) {
28 for (int j = 0; j < n; ++j)
29 for (int k = 0; k < n; ++k) {
30 f[i + 1][j][k] = -INF;
31 for (int x = 0; x < n; ++x)
32 f[i + 1][j][k] >?= f[i][j][x] + f[i][x][k];
33 }
34 ++lev;
35 }
36
37 int cur = 0;
38 fill(g[cur], g[cur] + n, 0);
39 for (int i = lev; i >= 0; --i) {
40 if (l < (1 << i)) continue;
41 l -= (1 << i);
42
43 cur = 1 - cur;
44 fill(g[cur], g[cur] + n, -INF);
45 for (int j = 0; j < n; ++j)
46 for (int k = 0; k < n; ++k)
47 g[cur][k] >?= g[1 - cur][j] + f[i][j][k];
48 }
49
50 cout << *max_element(g[cur], g[cur] + n) << endl;
51 }
52 return 0;
53}
54
2902 Ten drops
模擬，注意這句
Of cause, a left click in grid without blob should be ignored because it's meaningless.