|
|
2009年6月4日
1 #include <iostream>
2
3 using namespace std;
4
5 int min(int a, int b, int c)
6 {
7 return min(a, min(b, c));
8 }
9
10 int n;
11 int f[255][255];
12 bool map[255][255];
13
14 int main()
15 {
16 freopen("range.in", "r", stdin);
17 freopen("range.out", "w", stdout);
18
19 cin >> n;
20 for (int i = 0; i < n; i++)
21 for (int j = 0; j < n; j++)
22 {
23 char c;
24 cin >> c;
25 map[i][j] = (c == '0' ? false : true);
26 }
27
28 for (int i = 0; i < n; i++)
29 for (int j = 0; j < n; j++)
30 if (map[i][j])
31 {
32 f[i][j] = 1;
33
34 int t = 0;
35 if (i - 1 >= 0 && map[i - 1][j] &&
36 j - 1 >= 0 && map[i][j - 1] && map[i - 1][j - 1])
37 t = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]);
38
39 f[i][j] >?= t + 1;
40 }
41
42 int cnt[255] = { 0 };
43 for (int i = 0; i < n; i++)
44 for (int j = 0; j < n; j++)
45 if (f[i][j] >= 2)
46 for (int k = 2; k <= f[i][j]; k++)
47 cnt[k]++;
48
49 for (int i = 2; i <= 250; i++)
50 if (cnt[i])
51 cout << i << ' ' << cnt[i] << endl;
52
53 return 0;
54 }
55
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 struct point {
7 int x, y;
8 point operator+(const point &p) const {
9 point np = { x + p.x, y + p.y };
10 return np;
11 }
12 } ;
13
14 int r, c, knightsNum;
15 point king, knights[30 * 26];
16
17 const point kinghtDir[8] = {
18 {-2, +1}, {-1, +2}, {+1, +2}, {+2, +1},
19 {+2, -1}, {+1, -2}, {-1, -2}, {-2, -1}
20 } ;
21
22 inline bool inside(const point &p) {
23 return p.x >= 0 && p.x < r && p.y >= 0 && p.y < c;
24 }
25
26 int dist[30][26][30][26];
27 void spfa(const point &s)
28 {
29 for (int i = 0; i < r; i++)
30 for (int j = 0; j < c; j++)
31 dist[s.x][s.y][i][j] = INT_MAX;
32 dist[s.x][s.y][s.x][s.y] = 0;
33
34 queue<point> q;
35 q.push(s);
36
37 point cp; //current point
38 point np; //next point
39 while (q.empty() == false)
40 {
41 cp = q.front(); q.pop();
42 for (int i = 0; i < 8; i++)
43 {
44 np = cp + kinghtDir[i];
45 if (inside(np) && dist[s.x][s.y][cp.x][cp.y] + 1 < dist[s.x][s.y][np.x][np.y])
46 {
47 dist[s.x][s.y][np.x][np.y] = dist[s.x][s.y][cp.x][cp.y] + 1;
48 q.push(np);
49 }
50 }
51 }
52 }
53
54 int ans = INT_MAX;
55 void gather(int tx, int ty)
56 {
57 int sum = 0;
58 for (int i = 0; i < knightsNum; i++)
59 sum += dist[knights[i].x][knights[i].y][tx][ty];
60
61 if (sum > ans)
62 return;
63
64 for (int i = max(0, king.x - 2); i <= min(r - 1, king.x + 2); i++)
65 for (int j = max(0, king.y - 2); j <= min(c - 1, king.y + 2); j++)
66 {
67 int tmp;
68 if (i == king.x && j == king.y)
69 tmp = 0;
70 else
71 {
72 if (abs(i - king.x) == 1 || abs(j - king.y == 1))
73 tmp = 1;
74 else
75 tmp = 2;
76 }
77 for (int k = 0; k < knightsNum; k++)
78 if (dist[knights[k].x][knights[k].y][i][j] != INT_MAX &&
79 dist[i][j][tx][ty] != INT_MAX)
80 ans <?= (sum - dist[knights[k].x][knights[k].y][tx][ty]
81 + tmp + dist[knights[k].x][knights[k].y][i][j] + dist[i][j][tx][ty]);
82 }
83 }
84
85 int main()
86 {
87 freopen("camelot.in", "r", stdin);
88 freopen("camelot.out", "w", stdout);
89
90 cin >> r >> c;
91
92 {
93 char a; int b;
94 cin >> a >> b;
95 king.y = a - 'A', king.x = b - 1;
96 while (cin >> a >> b)
97 {
98 knights[knightsNum].y = a - 'A';
99 knights[knightsNum].x = b - 1;
100 knightsNum++;
101 }
102 }
103
104 if (knightsNum == 0)
105 {
106 cout << 0 << endl;
107 return 0;
108 }
109
110 for (int i = 0; i < r; i++)
111 for (int j = 0; j < c; j++)
112 {
113 point cp = { i, j };
114 spfa(cp);
115 }
116
117 for (int i = 0; i < r; i++)
118 for (int j = 0; j < c; j++)
119 gather(i, j);
120
121 cout << ans << endl;
122
123 return 0;
124 }
125
2009年6月3日
1 #include <set>
2 #include <iostream>
3
4 using namespace std;
5
6 class SepcialOffer;
7 class Cart;
8
9 class SpecialOffer {
10 private:
11 int n;
12 int c[5]; //code of each product
13 int x[5]; //amount of each product needed
14 public:
15 int sp; //special price
16 public:
17 friend class Cart;
18 friend istream& operator>>(istream &is, SpecialOffer &t) {
19 is >> t.n;
20 for (int i = 0; i < t.n; i++)
21 is >> t.c[i] >> t.x[i];
22 is >> t.sp;
23 return is;
24 }
25 } so[100]; //special offers set
26
27 class Cart {
28 private:
29 int n;
30 int c[5]; //code of each product in the cart
31 int x[5]; //amount of each product int the cart
32 int p[5]; //the regular price of each product int the cart
33 public:
34 int bestp; //the best price of all products int the cart
35 public:
36 int regularPrice() {
37 int sum = 0;
38 for (int i = 0; i < n; i++)
39 sum += p[i] * x[i];
40 return sum;
41 }
42 bool couldUseSpecialOffer(const SpecialOffer &t) const {
43 for (int i = 0; i < t.n; i++) {
44 int j;
45 for (j = 0; j < n; j++)
46 if (t.c[i] == c[j] && t.x[i] <= x[j])
47 break;
48 if (j == n)
49 return false;
50 }
51 return true;
52 }
53 Cart useSpecialOffer(const SpecialOffer &t) const {
54 Cart nc = *this;
55 for (int i = 0; i < t.n; i++) {
56 int j;
57 for (j = 0; j < n; j++)
58 if (t.c[i] == c[j] && t.x[i] <= x[j]) {
59 nc.x[j] -= t.x[i];
60 break;
61 }
62 }
63 return nc;
64 }
65 bool operator<(const Cart &t) const {
66 for (int i = 0; i < n; i++)
67 if (x[i] != t.x[i])
68 return x[i] - t.x[i] < 0 ? true : false;
69 return false;
70 }
71 friend istream& operator>>(istream &is, Cart &t) {
72 is >> t.n;
73 for (int i = 0; i < t.n; i++)
74 is >> t.c[i] >> t.x[i] >> t.p[i];
75 return is;
76 }
77 } cart;
78
79 int so_num; //special offers num
80 set<Cart> cartSet;
81
82 int search(Cart cart)
83 {
84 set<Cart>::iterator it = cartSet.find(cart);
85 if (it != cartSet.end())
86 return it->bestp;
87
88
89 cart.bestp = INT_MAX;
90 for (int i = 0; i < so_num; i++)
91 if (cart.couldUseSpecialOffer(so[i]))
92 cart.bestp <?= (search(cart.useSpecialOffer(so[i])) + so[i].sp);
93
94 cart.bestp <?= cart.regularPrice();
95
96 cartSet.insert(cart);
97
98 return cart.bestp;
99 }
100
101 int main()
102 {
103 freopen("shopping.in", "r", stdin);
104 freopen("shopping.out", "w", stdout);
105
106 cin >> so_num;
107 for (int i = 0; i < so_num; i++)
108 cin >> so[i];
109 cin >> cart;
110
111 cout << search(cart) << endl;
112
113 return 0;
114 }
115
2009年5月20日
1 #include <stack>
2 #include <iostream>
3
4 using namespace std;
5
6 int n = 1024, m;
7 int deg[1024];
8 int map[1024][1024];
9
10 stack<int> ans_st;
11
12 void search(int p)
13 {
14 for (int i = 0; i < n; i++)
15 if (map[p][i])
16 {
17 map[p][i]--, map[i][p]--;
18 search(i);
19 }
20 ans_st.push(p + 1);
21 }
22
23 int main()
24 {
25 freopen("fence.in", "r", stdin);
26 freopen("fence.out", "w", stdout);
27
28 cin >> m;
29
30 int s, t;
31 for (int i = 0; i < m; i++)
32 {
33 cin >> s >> t;
34 deg[s - 1]++; deg[t - 1]++;
35 map[s - 1][t - 1]++; map[t - 1][s - 1]++;
36 }
37
38 int i;
39 for (i = 0; i < n; i++)
40 if (deg[i] % 2 == 1)
41 {
42 search(i);
43 break;
44 }
45 if (i == n)
46 for (int j = 0; j < n; j++)
47 if (deg[j])
48 {
49 search(j);
50 break;
51 }
52
53 while (ans_st.empty() == false)
54 {
55 cout << ans_st.top() << endl;
56 ans_st.pop();
57 }
58
59 return 0;
60 }
61
2009年5月19日
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 int cowNum;
7 int pastureNum;
8 int pathNum;
9 int map[800][800];
10
11 int CowsInThePasture[800];
12
13 struct
14 {
15 int x[800][800];
16 int c[800];
17
18 } AdjList;
19
20 int main()
21 {
22 freopen("butter.in", "r", stdin);
23 freopen("butter.out", "w", stdout);
24
25 cin >> cowNum >> pastureNum >> pathNum;
26 for (int i = 0; i < cowNum; i++)
27 {
28 int t;
29 cin >> t;
30 CowsInThePasture[t - 1]++;
31 }
32
33 for (int i = 0; i < pastureNum; i++)
34 for (int j = 0; j < pastureNum; j++)
35 map[i][j] = INT_MAX;
36
37 int s, t, l;
38 for (int i = 0; i < pathNum; i++)
39 {
40 cin >> s >> t >> l;
41 map[s - 1][t - 1] <?= l;
42 map[t - 1][s - 1] <?= l;
43 }
44
45 for (int i = 0; i < pastureNum; i++)
46 for (int j = 0; j < pastureNum; j++)
47 if (map[i][j] != INT_MAX)
48 AdjList.x[i][AdjList.c[i]++] = j;
49
50 int ans = INT_MAX;
51 for (int k = 0; k < pastureNum; k++)
52 {
53 int d[800];
54 for (int i = 0; i < pastureNum; i++)
55 d[i] = INT_MAX;
56 d[k] = 0;
57
58 queue<int> q;
59 q.push(k);
60
61 bool inqueue[800] = { false };
62 inqueue[k] = true;
63
64 while (q.empty() == false)
65 {
66 int s = q.front(); q.pop();
67
68 for (int i = 0; i < AdjList.c[s]; i++)
69 {
70 int t = AdjList.x[s][i];
71 if (map[s][t] != INT_MAX && d[s] + map[s][t] < d[t])
72 {
73 d[t] = d[s] + map[s][t];
74 if (inqueue[t] == false)
75 {
76 inqueue[t] = true;
77 q.push(t);
78 }
79 }
80 }
81
82 inqueue[s] = false;
83 }
84
85 int sum = 0;
86 for (int i = 0; i < pastureNum; i++)
87 if (CowsInThePasture[i])
88 sum += d[i] * CowsInThePasture[i];
89
90 ans <?= sum;
91 }
92
93 cout << ans << endl;
94
95 return 0;
96 }
97
2009年5月18日
1 #include <map>
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 int init_state, target_state;
8
9 void get_init_and_target_state()
10 {
11 init_state = 12345678;
12 for (int i = 0, x, t = 10000000; i < 8; i++, t /= 10)
13 {
14 cin >> x;
15 target_state += x * t;
16 }
17 }
18
19 map<int, string> stateMap;
20
21 int main()
22 {
23 freopen("msquare.in", "r", stdin);
24 freopen("msquare.out", "w", stdout);
25
26 get_init_and_target_state();
27
28 queue<int> q;
29 q.push(init_state);
30 stateMap.insert(make_pair(init_state, ""));
31
32 while (q.empty() == false)
33 {
34 int cur = q.front(); q.pop();
35
36 if (cur == target_state)
37 {
38 cout << stateMap.find(cur)->second.size() << endl;
39 cout << stateMap.find(cur)->second << endl;
40 return 0;
41 }
42
43 int x[10] = { 0 };
44 for (int i = 8, t = cur; t; i--, t /= 10)
45 x[i] = t % 10;
46
47 int na = x[8] * 10000000 + x[7] * 1000000 + x[6] * 100000 +
48 x[5] * 10000 + x[4] * 1000 + x[3] * 100 + x[2] * 10 + x[1];
49
50 int nb = x[4] * 10000000 + x[1] * 1000000 + x[2] * 100000 +
51 x[3] * 10000 + x[6] * 1000 + x[7] * 100 + x[8] * 10 + x[5];
52
53 int nc = x[1] * 10000000 + x[7] * 1000000 + x[2] * 100000 +
54 x[4] * 10000 + x[5] * 1000 + x[3] * 100 + x[6] * 10 + x[8];
55
56 map<int, string>::iterator it;
57 if ((it = stateMap.find(na)) == stateMap.end())
58 {
59 it = stateMap.find(cur);
60 stateMap.insert(make_pair(na, it->second + 'A'));
61 q.push(na);
62 }
63 if ((it = stateMap.find(nb)) == stateMap.end())
64 {
65 it = stateMap.find(cur);
66 stateMap.insert(make_pair(nb, it->second + 'B'));
67 q.push(nb);
68 }
69 if ((it = stateMap.find(nc)) == stateMap.end())
70 {
71 it = stateMap.find(cur);
72 stateMap.insert(make_pair(nc, it->second + 'C'));
73 q.push(nc);
74 }
75 }
76
77 return 0;
78 }
79
2009年5月16日
摘要: 1 #include <iostream> 2 3 using namespace std; 4 5 int gcd(const int a, cons... 閱讀全文
2009年5月13日
1 #include <iostream>
2
3 using namespace std;
4
5 class Wheel
6 {
7 public:
8 void rotate()
9 {
10 for (int i = 0; i < wedge_num; i++)
11 {
12 wedges_start_angle[i] += rotation_speed;
13 wedges_start_angle[i] %= 360;
14 }
15 }
16
17 int rotation_speed;
18 int wedge_num;
19 int wedges_start_angle[5];
20 int wedges_extent[5];
21 } wheels[5];
22
23 bool light_can_pass_all_wheels()
24 {
25 int c[360] = { 0 };
26 for (int i = 0; i < 5; i++)
27 for (int j = 0; j < wheels[i].wedge_num; j++)
28 {
29 int s = wheels[i].wedges_start_angle[j];
30 for (int k = 0; k <= wheels[i].wedges_extent[j]; k++)
31 c[(s + k) % 360] += 1;
32 }
33
34 for (int i = 0; i < 360; i++)
35 if (c[i] == 5)
36 return true;
37 return false;
38 }
39
40 int main()
41 {
42 freopen("spin.in", "r", stdin);
43 freopen("spin.out", "w", stdout);
44
45 for (int i = 0; i < 5; i++)
46 {
47 cin >> wheels[i].rotation_speed >> wheels[i].wedge_num;
48 for (int j = 0; j < wheels[i].wedge_num; j++)
49 cin >> wheels[i].wedges_start_angle[j] >> wheels[i].wedges_extent[j];
50 }
51
52 if (light_can_pass_all_wheels())
53 {
54 cout << 0 << endl;
55 return 0;
56 }
57 for (int t = 1; t < 360; t++)
58 {
59 for (int i = 0; i < 5; i++)
60 wheels[i].rotate();
61 if (light_can_pass_all_wheels())
62 {
63 cout << t << endl;
64 return 0;
65 }
66 }
67
68 cout << "none" << endl;
69
70 return 0;
71 }
72
2009年5月11日
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("kimbits.in", "r", stdin);
8 freopen("kimbits.out", "w", stdout);
9
10 int n, m; unsigned t;
11
12 cin >> n >> m >> t;
13
14 unsigned f[32][32] = { 0 };
15
16 for (int i = 0; i <= m; i++)
17 f[0][i] = 1;
18 for (int i = 0; i <= n; i++)
19 f[i][0] = 1;
20
21 for (int i = 1; i <= n; i++)
22 for (int j = 1; j <= m; j++)
23 f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
24
25 for (int i = n - 1, j = m; i >= 0; i--)
26 {
27 if (t > f[i][j])
28 {
29 cout << 1;
30 t -= f[i][j];
31 j--;
32 }
33 else
34 cout << 0;
35 }
36 cout << endl;
37
38 return 0;
39 }
40
2009年4月29日
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("fact4.in", "r", stdin);
8 freopen("fact4.out", "w", stdout);
9
10 int n, c2 = 0, c5 = 0, cr = 1;
11
12 cin >> n;
13
14 for (int i = 2; i <= n; i++)
15 {
16 int t = i;
17
18 while (t && t % 2 == 0) c2++, t /= 2;
19 while (t && t % 5 == 0) c5++, t /= 5;
20
21 cr *= t, cr %= 10;
22 }
23
24 for (int i = 0; i < c2 - c5; i++)
25 cr *= 2, cr %= 10;
26
27 cout << cr << endl;
28
29 return 0;
30 }
31
|