|
|
1 /* Accepted 1141 C++ 00:03.20 5904K */
2 #include <iostream>
3
4 using namespace std;
5 const int maxn = 800;
6
7 struct { int cnt, son[maxn]; } Tree[maxn + 1];
8 struct { int cnt, x[maxn]; } Query[maxn + 1];
9
10 class DisjointSet
11 {
12 private:
13 int p[maxn + 1], rank[maxn + 1];
14 public:
15 void reset()
16 {
17 memset(p, 0, sizeof(p));
18 memset(rank, 0, sizeof(rank));
19 }
20 void make(const int x)
21 {
22 p[x] = x;
23 rank[x] = 0;
24 }
25 void link(const int x, const int y)
26 {
27 if(rank[x] > rank[y])
28 p[y] = x;
29 else
30 {
31 p[x] = y;
32 if(rank[x] == rank[y])
33 rank[y]++;
34 }
35 }
36 int find(const int x)
37 {
38 if(x != p[x])
39 p[x] = find(p[x]);
40 return p[x];
41 }
42 }set;
43
44 int ancestor[maxn + 1], cnt[maxn + 1];
45 bool black[maxn + 1];
46
47 void LCA(int u)
48 {
49 set.make(u);
50 ancestor[set.find(u)] = u;
51 for(int i = 0; i < Tree[u].cnt; i++)
52 {
53 LCA(Tree[u].son[i]);
54 set.link(u, Tree[u].son[i]);
55 ancestor[set.find(u)] = u;
56 }
57 black[u] = true;
58 for(int i = 0; i < Query[u].cnt; i++)
59 if(black[Query[u].x[i]])
60 cnt[ancestor[set.find(Query[u].x[i])]]++;
61 }
62
63 int main()
64 {
65 int n;
66 while(cin >> n)
67 {
68 memset(cnt, 0, sizeof(cnt));
69 memset(Tree, 0, sizeof(Tree));
70 memset(Query, 0, sizeof(Query));
71 memset(black, false, sizeof(black));
72
73 int s, t, m;
74 bool x[maxn] = {false};
75 for(int i = 0; i < n; i++)
76 {
77 scanf("%d:(%d)", &s, &m);
78 for(int k = 0; k < m; k++)
79 {
80 cin >> t;
81 x[t] = true;
82 Tree[s].son[k] = t;
83 }
84 Tree[s].cnt = m;
85 }
86
87 int root;
88 for(int i = 1; i <= n; i++)
89 if(x[i] == false)
90 {
91 root = i;
92 break;
93 }
94
95 cin >> m;
96 char c1, c2, c3;
97 for(int i = 0; i < m; i++)
98 {
99 cin >> c1 >> s >> c2 >> t >> c3;
100 Query[s].x[Query[s].cnt++] = t;
101 Query[t].x[Query[t].cnt++] = s;
102 }
103
104 set.reset();
105 LCA(root);
106
107 for(int i = 1; i <= n; i++)
108 if(cnt[i])
109 cout << i << ':' << cnt[i] << endl;
110 }
111
112 return 0;
113 }
114
1 /* Accepted 1140 C++ 00:07.18 928K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, match[301];
7 bool map[301][301], visited[301];
8
9 bool dfs(int p)
10 {
11 for(int i = 1; i <= m; i++)
12 if(map[p][i] && visited[i] == false)
13 {
14 visited[i] = true;
15 if(match[i] == 0 || dfs(match[i]))
16 {
17 match[i] = p;
18 return true;
19 }
20 }
21 return false;
22 }
23
24 int main()
25 {
26 int cases; cin >> cases;
27 while(cases--)
28 {
29 memset(map, false, sizeof(map));
30 memset(visited, false, sizeof(visited));
31 memset(match, 0, sizeof(match));
32
33 cin >> n >> m;
34
35 int cnt, t;
36 for(int s = 1; s <= n; s++)
37 {
38 cin >> cnt;
39 while(cnt--)
40 {
41 cin >> t;
42 map[s][t] = true;
43 }
44 }
45
46 cnt = 0;
47 for(int i = 1; i <= n; i++)
48 {
49 memset(visited, false, sizeof(visited));
50 cnt += dfs(i);
51 }
52 cout << (cnt == n ? "YES" : "NO") << endl;
53 }
54
55 return 0;
56 }
57
1 /* Accepted 1127 C++ 00:00.00 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m;
7 int len[26][26];
8 bool map[26][26], visited[26];
9
10 void dfs(int s, int p, int cnt)
11 {
12 visited[p] = true;
13 for(int i = 0; i < n; i++)
14 if(map[p][i] && visited[i] == false)
15 {
16 len[s][i] = cnt + 1;
17 dfs(s, i, cnt + 1);
18 }
19 }
20
21 int main()
22 {
23 char source;
24 cin >> n >> source >> m;
25
26 char s, t;
27 while(cin >> s >> t)
28 s -= 'A', t -= 'A', map[s][t] = map[t][s] = true;
29
30 for(int i = 0; i < n; i++)
31 {
32 memset(visited, false, sizeof(visited));
33 dfs(i, i, 0);
34 }
35
36 m--;
37 cout << "Program 8 by team X" << endl;
38 cout << source; source -= 'A';
39
40 bool fortified[26] = {false};
41 fortified[source] = true;
42
43 while(m--)
44 {
45 int max = 0, idx;
46 for(int i = 0; i < n; i++)
47 if(fortified[i] == false)
48 {
49 int minDist = INT_MAX;
50
51 for(int j = 0; j < n; j++)
52 if(fortified[j])
53 minDist <?= len[i][j];
54 if(max < minDist)
55 {
56 max = minDist;
57 idx = i;
58 }
59 }
60 fortified[idx] = true;
61 cout << ' ' << char(idx + 'A');
62 }
63 cout << endl << "End of program 8 by team X" << endl;
64
65 return 0;
66 }
67
1 /* Accepted 1181 C++ 00:00.00 848K */
2 #include <string>
3 #include <iostream>
4 #include <algorithm>
5
6 using namespace std;
7
8 int main()
9 {
10 string s, dict[100];
11 int n = 0, cnt[100][26] = {0};
12
13 while( (cin >> s) && s != "XXXXXX" )
14 dict[n++] = s;
15
16 sort( dict, dict + n );
17
18 for( int i = 0; i < n; i++ )
19 for( int j = 0; j < dict[i].size(); j++ )
20 cnt[i][dict[i][j] - 97]++;
21
22 while( (cin >> s) && s != "XXXXXX" )
23 {
24 int x[26] = {0};
25 for( int i = 0; i < s.size(); i++ )
26 x[s[i] - 97]++;
27 bool find = false;
28 for( int i = 0; i < n; i++ )
29 if( s.size() == dict[i].size() )
30 {
31 int j;
32 for( j = 0; j < 26; j++ )
33 if( cnt[i][j] != x[j] )
34 break;
35 if( j == 26 )
36 {
37 find = true;
38 cout << dict[i] << endl;
39 }
40 }
41 if( find == false )
42 cout << "NOT A VALID WORD" << endl;
43 cout << "******" << endl;
44 }
45
46 return 0;
47 }
48
set opt[i][j] for the the min time of using i lessons cover the 1..j topics.
opt[i][j] = min{ opt[i - 1][j - k] + d(j - k + 1 .. j) }
1 /* Accepted 1183 C++ 00:01.91 4760K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int N;
9 cin >> N;
10 while(N--)
11 {
12 int n, l, c, t[1001], Case = 0,;
13 cin >> n;
14 while(n)
15 {
16 cin >> l >> c;
17 for(int i = 1; i <= n; i++)
18 cin >> t[i];
19
20 int d[1001][1001];
21 for(int i = 0; i <= n; i++)
22 for(int j = 0; j <= n; j++)
23 d[i][j] = INT_MAX;
24
25 d[0][0] = 0;
26
27 int i;
28 for(i = 0; i < n; i++)
29 {
30 if(d[i][n] != INT_MAX)
31 break;
32
33 for(int j = i; j < n; j++)
34 {
35 if(d[i][j] == INT_MAX)
36 break;
37
38 int x = l;
39 for(int k = j + 1; k <= n; k++)
40 {
41 x -= t[k];
42 if(x < 0)
43 break;
44
45 if(x == 0)
46 d[i + 1][k] <?= d[i][j];
47 else if(1 <= x && x <= 10)
48 d[i + 1][k] <?= d[i][j] - c;
49 else if(x > 10)
50 d[i + 1][k] <?= d[i][j] + (x - 10) * (x - 10);
51 }
52 }
53 }
54
55 cout << "Case " << ++ Case << ':' << endl << endl;
56 cout << "Minimum number of lectures: " << i << endl;
57 cout << "Total dissatisfaction index: " << d[i][n] << endl;
58
59 cin >> n;
60 if(n)
61 cout << endl;
62 }
63 if(N)
64 cout << endl;
65 }
66
67 return 0;
68 }
69
1 /* C++ Accepted 0.015 380 KB */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct rec { int n, m; };
8
9 int main()
10 {
11 int n = 0; char c;
12 for(int i = 0; i < 16; i++)
13 {
14 cin.get(c);
15 if(c == '\n')
16 {
17 i--;
18 continue;
19 }
20 if(c == 'b')
21 n |= (1 << i);
22 }
23
24 rec cur = {n, 0};
25 queue <rec> q;
26 q.push(cur);
27
28 bool repeat[65536] = {false}, find = false;
29 while(q.empty() == false)
30 {
31 cur = q.front(); q.pop();
32
33 if(cur.n == 0 || cur.n == 65535)
34 {
35 cout << cur.m << endl;
36 find = true;
37 break;
38 }
39
40 for(int i = 0; i < 16; i++)
41 {
42 int t = cur.n;
43
44 t ^= (1 << i);
45 if(i - 4 >= 0)
46 t ^= (1 << (i - 4));
47 if(i + 4 < 16)
48 t ^= (1 << (i + 4));
49 if(i % 4 - 1 >= 0)
50 t ^= (1 << (i - 1));
51 if(i % 4 + 1 < 4)
52 t ^= (1 << (i + 1));
53
54 if(repeat[t] == false)
55 {
56 repeat[t] = true;
57 rec tmp = {t, cur.m + 1};
58 q.push(tmp);
59 }
60 }
61 }
62
63 if(find == false)
64 cout << "Impossible" << endl;
65
66 return 0;
67 }
68
1 /* Accepted 0.046 200 KB */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 struct { int x, y; } p[200];
9
10 int n;
11 cin >> n;
12 for(int i = 0; i < n; i++)
13 cin >> p[i].x >> p[i].y;
14
15 int max = 0;
16 for(int i = 0; i < n; i++)
17 for(int j = 0; j < n; j++)
18 if(i != j)
19 {
20 int x = p[j].x - p[i].x;
21 int y = p[j].y - p[i].y;
22
23 int cnt = 2;
24 for(int k = 0; k < n; k++)
25 if(k != i && k != j)
26 if(x * (p[k].y - p[i].y) == y * (p[k].x - p[i].x))
27 cnt++;
28 if(max < cnt)
29 max = cnt;
30 }
31
32 cout << max << endl;
33
34 return 0;
35 }
36
1 /* Accepted 0.39 1 200 KB */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, match[1000];
7 bool map[1000][1000], visited[1000];
8
9 bool dfs(int p)
10 {
11 for(int i = 0; i < m; i++)
12 if(map[p][i] && visited[i] == false)
13 {
14 visited[i] = true;
15 if(match[i] == -1 || dfs(match[i]))
16 {
17 match[i] = p;
18 return true;
19 }
20 }
21 return false;
22 }
23
24 int main()
25 {
26 int s, t;
27 cin >> n >> m >> s;
28 while(cin >> s >> t)
29 {
30 s--, t--;
31 map[s][t] = true;
32 }
33
34 int cnt = 0;
35 memset(match, 0XFF, sizeof(match));
36 for(int i = 0; i < n; i++)
37 {
38 memset(visited, false, sizeof(visited));
39 cnt += dfs(i);
40 }
41
42 cout << n + m - 2 * cnt + cnt << endl;
43
44 return 0;
45 }
46
1 /* Accepted 1171 C++ 00:00.40 488K */
2 #include <stdio.h>
3
4 int main()
5 {
6 int n, N;
7 char p[100000];
8
9 scanf("%d", &N);
10 while(N--)
11 {
12 scanf("%d", &n);
13 for(int i = 0; i < n; )
14 {
15 scanf("%c", p + i);
16 if(p[i] == 'U' || p[i] == 'D')
17 i++;
18 }
19
20 int ans = 0, pos = 0;
21 for(int i = 1; i < n; i++)
22 if(p[i] != p[pos])
23 {
24 pos = i;
25 ans++;
26 }
27
28 printf("%d\n", ans);
29 if(N)
30 putchar('\n');
31 }
32
33 return 0;
34 }
35
1 /* Accepted 1133 C++ 00:00.04 836K */
2 #include <map>
3 #include <iostream>
4
5 using namespace std;
6
7 inline int split(int n)
8 {
9 int sum = 0;
10 while(n)
11 {
12 sum += n % 10;
13 n /= 10;
14 }
15 return sum;
16 }
17
18 inline int prime(int n) //if prime(n) == n, it's a prime number.
19 {
20 if(n % 2 == 0)
21 return 2;
22 for(int i = 3; i * i <= n; i += 2)
23 if(n % i == 0)
24 return i;
25 return n;
26 }
27
28 int main()
29 {
30 int n;
31 map <int, int> rec;
32 while((cin >> n) && n)
33 {
34 if(rec.count(n))
35 {
36 cout << rec[n] << endl;
37 continue;
38 }
39 for(int i = n + 1; true; i++)
40 {
41 if(prime(i) == i)
42 continue;
43
44 int s1 = split(i);
45
46 int s2 = 0, m = i, p;
47 while((p = prime(m)) != 1)
48 {
49 s2 += split(p);
50 m /= p;
51 }
52
53 if(s1 == s2)
54 {
55 cout << i << endl;
56 rec[n] = i;
57 break;
58 }
59 }
60 }
61
62 return 0;
63 }
64
|