|
|
1 #include <iostream>
2
3 using namespace std;
4
5 int n, m, c[50], f[2000002];
6
7 int main()
8 {
9 freopen("stamps.in", "r", stdin);
10 freopen("stamps.out", "w", stdout);
11
12 cin >> n >> m;
13 for (int i = 0; i < m; i++)
14 cin >> c[i];
15
16 sort(c, c + m);
17
18 for (int i = 1; i <= 2000000; i++)
19 {
20 f[i] = INT_MAX;
21 for (int j = 0; j < m; j++)
22 if (i - c[j] >= 0)
23 f[i] <?= f[i - c[j]] + 1;
24 if (f[i] > n)
25 {
26 cout << i - 1 << endl;
27 return 0;
28 }
29 }
30 cout << 2000000 << endl;
31
32 return 0;
33 }
34
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 int binaryStr2num(const string & str, int s, int t)
7 {
8 int n = 0;
9 for (int i = s; i < t; i++)
10 n = n * 2 + str[i] - '0';
11 return n;
12 }
13
14 string num2binaryStr(int k, int n)
15 {
16 string s;
17 while (n)
18 {
19 s += (n % 2 + '0');
20 n /= 2;
21 }
22 while (s.size() < k)
23 s += '0';
24 for (int i = 0; i < s.size() / 2; i++)
25 swap(s[i], s[s.size() - i - 1]);
26 return s;
27 }
28
29 int a, b, n, cnt[12 + 1][4096];
30 string s;
31
32 int main()
33 {
34 freopen("contact.in", "r", stdin);
35 freopen("contact.out", "w", stdout);
36
37 cin >> a >> b >> n;
38
39 string ts;
40 while (cin >> ts)
41 s += ts;
42
43 for (unsigned i = 0; i <= s.size() - a; i++)
44 {
45 int t = binaryStr2num(s, i, i + a - 1);
46 for (int j = a; j <= b; j++)
47 {
48 if (i + j - 1 >= s.size())
49 continue;
50 t = t * 2 + (s[i + j - 1] - '0');
51 cnt[j][t]++;
52 }
53 }
54
55 while (n--)
56 {
57 int Max = 0, len, num;
58 for (int i = a; i <= b; i++)
59 for (int j = 0; j < 4096; j++)
60 if (Max < cnt[i][j])
61 Max = cnt[i][j], len = i, num = j;
62
63 if (Max == 0)
64 break;
65
66 queue <string> q;
67 for (int i = a; i <= b; i++)
68 for (int j = 0; j < 4096; j++)
69 if (cnt[i][j] == Max)
70 {
71 q.push(num2binaryStr(i, j));
72 cnt[i][j] = 0;
73 }
74
75 cout << Max << endl;
76
77 int i = 0;
78 while (q.empty() == false)
79 {
80 cout << q.front();
81
82 i++;
83 if (i % 6 == 0)
84 cout << endl;
85 else
86 cout << (q.size() == 1 ? '\n' : ' ');
87
88 q.pop();
89 }
90 }
91
92 return 0;
93 }
94
1 #include <iostream>
2
3 using namespace std;
4
5 int n, m, t;
6 int sx[1001], sy[1001], tx[1001], ty[1001], col[1001], cnt[2600];
7
8 int curCol;
9 void cut(int csx, int csy, int ctx, int cty, int i)
10 {
11 while ((i <= t) && (sx[i] >= ctx || tx[i] <= csx || sy[i] >= cty || ty[i] <= csy))
12 i++;
13 if (i > t)
14 {
15 cnt[curCol] += (ctx - csx) * (cty - csy);
16 return;
17 }
18
19 if (csx < sx[i])
20 {
21 cut(csx, csy, sx[i], cty, i + 1);
22 csx = sx[i];
23 }
24 if (ctx > tx[i])
25 {
26 cut(tx[i], csy, ctx, cty, i + 1);
27 ctx = tx[i];
28 }
29 if (csy < sy[i])
30 cut(csx, csy, ctx, sy[i], i + 1);
31 if (cty > ty[i])
32 cut(csx, ty[i], ctx, cty, i + 1);
33 }
34
35 int main()
36 {
37 freopen("rect1.in", "r", stdin);
38 freopen("rect1.out", "w", stdout);
39
40 cin >> n >> m >> t;
41
42 sx[0] = 0;
43 sy[0] = 0;
44 tx[0] = n;
45 ty[0] = m;
46 col[0] = 1;
47 for (int i = 1; i <= t; i++)
48 cin >> sx[i] >> sy[i] >> tx[i] >> ty[i] >> col[i];
49
50 for (int i = t; i >= 0; i--)
51 {
52 curCol = col[i];
53 cut(sx[i], sy[i], tx[i], ty[i], i + 1);
54 }
55
56 for (int i = 1; i <= 2500; i++)
57 if (cnt[i])
58 cout << i << ' ' << cnt[i] << endl;
59
60 return 0;
61 }
62
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("humble.in", "r", stdin);
8 freopen("humble.out", "w", stdout);
9
10 int nhum = 0, neednhum, nprime;
11 int hum[100000], prime[100];
12
13 cin >> nprime >> neednhum;
14 for (int i = 0; i < nprime; i++)
15 cin >> prime[i];
16
17 hum[nhum++] = 1;
18
19 int pidx[100] = { 0 };
20
21 while (nhum < neednhum + 1)
22 {
23 int min = INT_MAX;
24 for (int i = 0; i < nprime; i++)
25 {
26 while (prime[i] * hum[pidx[i]] <= hum[nhum - 1])
27 pidx[i]++;
28 min <?= prime[i] * hum[pidx[i]];
29 }
30 hum[nhum++] = min;
31 }
32
33 cout << hum[neednhum] << endl;
34
35 return 0;
36 }
37
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("inflate.in", "r", stdin);
8 freopen("inflate.out", "w", stdout);
9
10 int n, m;
11 int w[10000];
12 int v[10000];
13 int f[10001] = { 0 };
14
15 cin >> m >> n;
16 for (int i = 0; i < n; i++)
17 cin >> v[i] >> w[i];
18
19 for (int i = 0; i < n; i++)
20 for (int j = w[i]; j <= m; j++)
21 f[j] >?= (f[j - w[i]] + v[i]);
22
23 cout << f[m] << endl;
24
25 return 0;
26 }
27
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("agrinet.in", "r", stdin);
8 freopen("agrinet.out", "w", stdout);
9
10 int n, map[100][100];
11
12 cin >> n;
13 for (int i = 0; i < n; i++)
14 for (int j = 0; j < n; j++)
15 cin >> map[i][j];
16
17 //=====prim=====
18 int lowcost[100];
19 int vset[100];
20 int ans = 0;
21
22 vset[0] = 1;
23 for (int i = 1; i < n; i++)
24 {
25 lowcost[i] = map[0][i];
26 vset[i] = 0;
27 }
28
29 for (int k = 1; k < n; k++)
30 {
31 int min = INT_MAX, p;
32 for (int i = 0; i < n; i++)
33 if (vset[i] == 0 && lowcost[i] < min)
34 {
35 min = lowcost[i];
36 p = i;
37 }
38 ans += min;
39 vset[p] = 1;
40 for (int i = 0; i < n; i++)
41 if (vset[i] == 0 && map[p][i] < lowcost[i])
42 lowcost[i] = map[p][i];
43 }
44
45 cout << ans << endl;
46
47 return 0;
48 }
49
1 #include <map>
2 #include <iostream>
3
4 using namespace std;
5
6 string int2str(int n)
7 {
8 if (n == 0)
9 return string("0");
10 string s;
11 while (n)
12 {
13 s += (n % 10 + '0');
14 n /= 10;
15 }
16 for (unsigned i = 0; i < s.size() / 2; i++)
17 swap(s[i], s[s.size() - i - 1]);
18 return s;
19 }
20
21 int main()
22 {
23 freopen("fracdec.in", "r", stdin);
24 freopen("fracdec.out", "w", stdout);
25
26 int a, b, q, r;
27 map <int, int> rRec;
28
29 while (cin >> a >> b)
30 {
31 string ans = int2str(a / b) + '.';
32
33 a = a % b;
34 rRec[a % b] = ans.size();
35
36 int cnt = ans.size() + 1;
37 while (true)
38 {
39 a = a * 10;
40 q = a / b;
41 r = a % b;
42
43 ans += (q + '0');
44
45 if (r == 0 || rRec[r])
46 break;
47
48 rRec[r] = cnt++ ;
49
50 a = r;
51 }
52
53 if (r)
54 {
55 ans += ')';
56 ans.insert(rRec[r], "(");
57 }
58
59 for (int i = 0; i < ans.size(); i++)
60 {
61 cout << ans[i];
62 if ((i + 1) % 76 == 0)
63 cout << endl;
64 }
65
66 cout << endl;
67
68 rRec.clear();
69 }
70
71 return 0;
72 }
73
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 //a..z -> 0..25
7 //A..Y -> 26..51
8
9 int main()
10 {
11 freopen("comehome.in", "r", stdin);
12 freopen("comehome.out", "w", stdout);
13
14 int n;
15 cin >> n;
16
17 int map[52][52] = { 0 };
18
19 bool x[52] = { false };
20
21 char s, t; int l;
22 for (int i = 0; i < n; i++)
23 {
24 cin >> s >> t >> l;
25
26 if (s >= 'a' && s <= 'z')
27 s -= 'a';
28 else
29 s -= 'A' - 26;
30
31 if (t >= 'a' && t <= 'z')
32 t -= 'a';
33 else
34 t -= 'A' - 26;
35
36 x[s] = x[t] = true;
37
38 int a = map[s][t];
39 int b = map[t][s];
40 int c;
41
42 if (a == 0) a = INT_MAX;
43 if (b == 0) b = INT_MAX;
44 c = min(a, b);
45
46 map[s][t] = map[t][s] = min(c, l);
47 }
48
49 //spfa
50 queue <int> q;
51 int f[52];
52
53 q.push(51);
54 f[51] = 0;
55 for (int i = 0; i < 51; i++)
56 f[i] = INT_MAX;
57
58 while (q.empty() == false)
59 {
60 int cp = q.front(); q.pop();
61
62 for (int i = 0; i < 51; i++)
63 if (x[i] && map[cp][i] && f[cp] + map[cp][i] < f[i])
64 {
65 f[i] = f[cp] + map[cp][i];
66 q.push(i);
67 }
68 }
69
70 int ans = INT_MAX;
71 char c;
72 for (int i = 26; i < 51; i++)
73 if (x[i] && f[i] < ans)
74 {
75 ans = f[i];
76 c = i - 26 + 'A';
77 }
78
79 cout << c << ' ' << ans << endl;
80
81 return 0;
82 }
83
1 #include <cmath>
2 #include <iostream>
3
4 using namespace std;
5
6 struct Point
7 {
8 int x, y;
9 } ;
10
11 int sqr(int n)
12 {
13 return n * n;
14 }
15
16 int n;
17 Point p[150];
18 bool adj[150][150];
19 double dist[150][150];
20
21 int subGraphCnt;
22
23 int visited[150];
24 void dfs(int p)
25 {
26 visited[p] = subGraphCnt;
27 for (int i = 0; i < n; i++)
28 if (adj[p][i] == true && visited[i] == false)
29 dfs(i);
30 }
31
32 int main()
33 {
34 freopen("cowtour.in", "r", stdin);
35 freopen("cowtour.out", "w", stdout);
36
37 cin >> n;
38 for (int i = 0; i < n; i++)
39 cin >> p[i].x >> p[i].y;
40
41 cin.get();
42 for (int i = 0; i < n; i++)
43 {
44 for (int j = 0; j < n; j++)
45 {
46 char c;
47 c = cin.get();
48 adj[i][j] = c - '0';
49 }
50 cin.get();
51 }
52
53 for (int i = 0; i < n; i++)
54 for (int j = i + 1; j < n; j++)
55 if (adj[i][j])
56 {
57 int tmp = sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y);
58 dist[i][j] = dist[j][i] = sqrt(tmp);
59 }
60 else
61 dist[i][j] = dist[j][i] = INT_MAX;
62
63 for (int k = 0; k < n; k++)
64 for (int i = 0; i < n; i++)
65 for (int j = 0; j < n; j++)
66 if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
67 dist[i][j] <?= (dist[i][k] + dist[k][j]);
68
69 for (int i = 0; i < n; i++)
70 if (visited[i] == 0)
71 {
72 subGraphCnt++;
73 dfs(i);
74 }
75
76 double x[150] = { 0 };
77 for (int i = 0; i < n; i++)
78 for (int j = 0; j < n; j++)
79 if (dist[i][j] != INT_MAX)
80 x[i] >?= dist[i][j];
81
82 double ans = INT_MAX;
83 for (int i = 0; i < n; i++)
84 for (int j = 0; j < n; j++)
85 if (visited[i] != visited[j])
86 {
87 double tmp = sqrt(sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y));
88 tmp += (x[i] + x[j]);
89 ans <?= tmp;
90 }
91 for (int i = 0; i < n; i++)
92 ans >?= x[i];
93
94 cout.setf(ios_base::showpoint);
95 cout.setf(ios_base::fixed);
96 cout.precision(6);
97 cout << ans << endl;
98
99 return 0;
100 }
101
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 struct Point
7 {
8 int x, y;
9 } ;
10
11 int n, m, ans;
12 int rec[100 * 2 + 1][38 * 2 + 1];
13 char map[100 * 2 + 1][38 * 2 + 1];
14
15 bool inside(int i, int j)
16 {
17 return i >= 1 && i < n - 1 && j >= 1 && j < m - 1;
18 }
19
20 void bfs(Point & cp)
21 {
22 rec[cp.x][cp.y] = 1;
23
24 queue <Point> q;
25 q.push(cp);
26
27 while (q.empty() == false)
28 {
29 Point cp = q.front(); q.pop();
30
31 if (inside(cp.x - 1, cp.y) && map[cp.x - 1][cp.y] == ' ')
32 if (rec[cp.x][cp.y] + 1 < rec[cp.x - 1][cp.y])
33 {
34 rec[cp.x - 1][cp.y] = rec[cp.x][cp.y] + 1;
35 Point np = { cp.x - 1, cp.y };
36 q.push(np);
37 }
38 if (inside(cp.x + 1, cp.y) && map[cp.x + 1][cp.y] == ' ')
39 if (rec[cp.x][cp.y] + 1 < rec[cp.x + 1][cp.y])
40 {
41 rec[cp.x + 1][cp.y] = rec[cp.x][cp.y] + 1;
42 Point np = { cp.x + 1, cp.y };
43 q.push(np);
44 }
45 if (inside(cp.x, cp.y - 1) && map[cp.x][cp.y - 1] == ' ')
46 if (rec[cp.x][cp.y] + 1 < rec[cp.x][cp.y - 1])
47 {
48 rec[cp.x][cp.y - 1] = rec[cp.x][cp.y] + 1;
49 Point np = { cp.x, cp.y - 1 };
50 q.push(np);
51 }
52 if (inside(cp.x, cp.y + 1) && map[cp.x][cp.y + 1] == ' ')
53 if (rec[cp.x][cp.y] + 1 < rec[cp.x][cp.y + 1])
54 {
55 rec[cp.x][cp.y + 1] = rec[cp.x][cp.y] + 1;
56 Point np = { cp.x, cp.y + 1 };
57 q.push(np);
58 }
59 }
60 }
61
62 int main()
63 {
64 freopen("maze1.in", "r", stdin);
65 freopen("maze1.out", "w", stdout);
66
67 cin >> m >> n;
68
69 n = 2 * n + 1;
70 m = 2 * m + 1;
71
72 cin.get();
73 for (int i = 0; i < n; i++)
74 {
75 for (int j = 0; j < m; j++)
76 map[i][j] = cin.get();
77 cin.get();
78 }
79
80 for (int i = 0; i < n; i++)
81 for (int j = 0; j < m; j++)
82 rec[i][j] = INT_MAX;
83
84 for (int i = 0, j = 0; j < m; j++)
85 if (map[i][j] == ' ')
86 {
87 Point p = { i, j };
88 bfs(p);
89 }
90 for (int i = 0, j = 0; i < n; i++)
91 if (map[i][j] == ' ')
92 {
93 Point p = { i, j };
94 bfs(p);
95 }
96 for (int i = n - 1, j = 0; j < m; j++)
97 if (map[i][j] == ' ')
98 {
99 Point p = { i, j };
100 bfs(p);
101 }
102 for (int i = 0, j = m - 1; i < n; i++)
103 if (map[i][j] == ' ')
104 {
105 Point p = { i, j };
106 bfs(p);
107 }
108
109 for (int i = 0; i < n; i++)
110 for (int j = 0; j < m; j++)
111 if (rec[i][j] != INT_MAX)
112 ans >?= rec[i][j];
113
114 cout << ans / 2 << endl;
115
116 return 0;
117 }
118
|