2015ACM/ICPC亚洲区沈阳站 Solution
分类:
IT文章
•
2025-01-09 09:13:43
A - Pattern String
留坑。
B - Bazinga
题意：找一个最大的i，使得前i - 1个字符串中至少不是它的子串
思路：暴力找，如果有一个串已经符合条件，就不用往上更新
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 510
5
6 int t, n;
7 int vis[N];
8 string s[N];
9
10 int main()
11 {
12 ios::sync_with_stdio(false);
13 int t;
14 cin >> t;
15 for(int cas = 1; cas <= t; ++cas)
16 {
17 cin >> n;
18 memset(vis, 0, sizeof vis);
19 for(int i = 1; i <= n; ++i) cin >> s[i];
20 int ans = -1;
21 for(int i = 1; i <= n; ++i)
22 {
23 for(int j = i + 1; j <= n; ++j)
24 {
25 if(!vis[j])
26 {
27 int tmp = s[j].find(s[i]);
28 if(tmp == -1)
29 {
30 vis[j] = 1;
31 ans = max(ans, j);
32 }
33 else break;
34 }
35 }
36 }
37 cout << "Case #" << cas << ": " << ans << endl;
38 }
39 return 0;
40 }
View Code
C - Minimum Cut-Cut
留坑。
D - Pagodas
题意：刚开始集合里有a, b 两个数，每次能从集合中选出 x + y 或者 x - y 放进集合中，并且放过的不能放，不能放的输游戏
思路：考虑$gcd(x, y), 每次产生的新数肯定是gcd(x, y)的倍数$ 所以能放的数总数只有 gcd(x, y) 的倍数的个数
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 int gcd(int a, int b)
6 {
7 return b == 0 ? a : gcd(b, a % b);
8 }
9
10 int n, a, b;
11
12 int main()
13 {
14 int t;
15 scanf("%d", &t);
16 for(int cas = 1; cas <= t; ++cas)
17 {
18 scanf("%d %d %d", &n, &a, &b);
19 int g = gcd(a, b);
20 int tmp = n / g;
21 printf("Case #%d: ", cas);
22 puts(tmp & 1 ? "Yuwgna" : "Iaka");
23 }
24 return 0;
25 }
View Code
E - Efficient Tree
留坑。
F - Frogs
题意：有n只青蛙，长度为m的环，每只青蛙固定步数往前跳，跳到一个点标记一下，求最后有多少点被标记
思路：先将m分解因子，对于每一个arr[i]都和m求gcd，然后将gcd的倍数标记一次，代表需要统计一次它的倍数。最后遍历一边每个因子，求出它被多用几次或者少用几次的和即可。
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 #define ll long long
6 #define N 10010
7
8 ll gcd(ll a, ll b)
9 {
10 return b == 0 ? a : gcd(b, a % b);
11 }
12
13 int n, m;
14 int vis[N], used[N];
15 ll arr[N];
16 vector<int>vec;
17
18 int main()
19 {
20 int t;
21 scanf("%d", &t);
22 for(int cas = 1; cas <= t; ++cas)
23 {
24 scanf("%d %d", &n, &m);
25 memset(vis, 0, sizeof vis);
26 memset(used, 0, sizeof used);
27 vec.clear();
28 for(int i = 1; i * i <= m; ++i)
29 {
30 if(m % i == 0)
31 {
32 vec.push_back(i);
33 if(i * i != m) vec.push_back(m / i);
34 }
35 }
36 sort(vec.begin(), vec.end());
37 int tot = vec.size();
38 tot--;
39 for(int i = 1; i <= n; ++i)
40 {
41 scanf("%lld", arr + i);
42 ll x = gcd(arr[i], m);
43 for(int j = 0; j < tot; ++j)
44 {
45 if(vec[j] % x == 0) vis[j] = 1;
46 }
47 }
48 ll ans = 0;
49 for(int i = 0; i < tot; ++i)
50 {
51 if(vis[i] != used[i])
52 {
53 ll tmp = (m - 1) / vec[i];
54 ans += tmp * (tmp + 1) / 2 * vec[i] * (vis[i] - used[i]);
55 for(int j = i + 1; j < tot; ++j)
56 {
57 if(vec[j] % vec[i] == 0)
58 {
59 used[j] += vis[i] - used[i];
60 }
61 }
62 }
63 }
64 printf("Case #%d: %lld
", cas, ans);
65 }
66 return 0;
67 }
View Code
G - Game of Flying Circus
题意：翻译啊翻译
思路：分类讨论
1)在1-2相遇 即v1=v2 输出Yes
2)在2-3相遇，利用二分计算出相遇点，算一下到4的时间，判断
3)在3-4相遇，利用二分计算出相遇点，算一下到1的时间，判断
4)一定No
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 const double eps = 1e-8;
6
7 double T, v1, v2;
8
9 int sgn(double x)
10 {
11 if(fabs(x) < eps) return 0;
12 else return x > 0 ? 1 : -1;
13 }
14
15 int main()
16 {
17 int t;
18 scanf("%d", &t);
19 for(int cas = 1; cas <= t; ++cas)
20 {
21 scanf("%lf %lf %lf", &T, &v1, &v2);
22 printf("Case #%d: ", cas);
23 if(sgn(v1 - v2) == 0) puts("Yes");
24 else if(sgn(2 * v1 * v1 - v2 * v2) > 0)//2-3
25 {
26 double l = 0, r = 300.0;
27 while(r - l > eps)
28 {
29 double mid = (l + r) / 2.0;
30 double dis1 = sqrt(mid * mid + 300.0 * 300.0);
31 double t1 = dis1 / v1;
32 double dis2 = mid + 300.0;
33 double t2 = dis2 / v2;
34 if(sgn(t1 - t2) > 0)
35 {
36 l = mid;
37 }
38 else
39 {
40 r = mid;
41 }
42 }
43 double x = (l + r) / 2.0;
44 double dis1 = x + 600.0;
45 double t1 = dis1 / v1;
46 double dis2 = 600.0 - x;
47 double t2 = dis2 / v2 + T;
48 puts(sgn(t1 - t2) <= 0 ? "Yes" : "No");
49 }
50 else if(sgn(3 * v1 - v2) > 0)//3-4
51 {
52 double l = 0, r = 300.0;
53 while(r - l > eps)
54 {
55 double mid = (l + r) / 2.0;
56 double dis1 = sqrt(mid * mid + 300.0 * 300.0);
57 double t1 = dis1 / v1;
58 double dis2 = 900.0 - mid;
59 double t2 = dis2 / v2;
60 if(sgn(t1 - t2) > 0)
61 {
62 r = mid;
63 }
64 else
65 {
66 l = mid;
67 }
68 }
69 double y = (l + r) / 2.0;
70 double dis1 = sqrt((300.0 - y) * (300.0 - y) + 300.0 * 300.0) + 900.0;
71 double t1 = dis1 / v1;
72 double dis2 = y + 300.0;
73 double t2 = dis2 / v2 + T;
74 puts(sgn(t1 - t2) <= 0 ? "Yes" : "No");
75 }
76 else puts("No");
77 }
78 return 0;
79 }
View Code
H - Chessboard
留坑。
I - Triple
题意：二元组$A<a, b>$ 三元组 $B<c, d, e> A * B = {<a, c, d> | <a, b> in A , <c, d, e> in B and b = e}$ 求有多少集合满足TOP(C)
思路：枚举B，对于每个B，我们考虑符合条件的最高的a, 因为有多个a，那么小的a肯定不会放到集合里面，
对于最大的a，我们判断二维BIT中右下角有的最大值，是否大于它本身，不是的话它就应该放进TOP(C)
要多考虑一下当前的(c, d) 有多个点的情况
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 100010
5 #define pii pair <int, int>
6 #define ll long long
7
8 int t, n, m;
9 struct A
10 {
11 int a, b;
12 void scan()
13 {
14 scanf("%d%d", &a, &b);
15 }
16 bool operator < (const A &r) const
17 {
18 return b == r.b ? a < r.a : b < r.b;
19 }
20 }a[N];
21
22 struct B
23 {
24 int c, d, e;
25 void scan()
26 {
27 scanf("%d%d%d", &c, &d, &e);
28 }
29 }b[N];
30
31 pii pos[N];
32
33 struct BIT
34 {
35 int a[1010][1010];
36
37 void Init()
38 {
39 memset(a, 0, sizeof a);
40 }
41
42 void update(int x, int y, int val)
43 {
44 for (int i = x; i; i -= i & -i)
45 for (int j = y; j; j -= j & -j)
46 a[i][j] = max(a[i][j], val);
47 }
48
49 int query(int x, int y)
50 {
51 int res = 0;
52 for (int i = x; i < 1010; i += i & -i)
53 for (int j = y; j < 1010; j += j & -j)
54 res = max(res, a[i][j]);
55 return res;
56 }
57 }bit;
58
59 int main()
60 {
61 scanf("%d", &t);
62 for (int kase = 1; kase <= t; ++kase)
63 {
64 printf("Case #%d: ", kase);
65 scanf("%d%d", &n, &m);
66 for (int i = 1; i <= n; ++i) a[i].scan();
67 for (int i = 1; i <= m; ++i) b[i].scan();
68 sort(a + 1, a + 1 + n);
69 memset(pos, 0, sizeof pos);
70 for (int i = n; i >= 1; --i)
71 {
72 int b = a[i].b;
73 if (!pos[b].first)
74 {
75 pos[b].first = a[i].a, ++pos[b].second;
76 continue;
77 }
78 if (i != n)
79 {
80 if (b == a[i + 1].b && a[i].a == pos[b].first)
81 ++pos[b].second;
82 }
83 }
84 bit.Init();
85 for (int i = 1; i <= m; ++i)
86 {
87 if (pos[b[i].e].first == 0) continue;
88 bit.update(b[i].c, b[i].d, pos[b[i].e].first);
89 }
90 ll res = 0;
91 for (int i = 1; i <= m; ++i)
92 {
93 int x = b[i].c, y = b[i].d;
94 if(!pos[b[i].e].first) continue;
95 int Max = max(bit.query(x, y + 1), bit.query(x + 1, y));
96 bool flag = true;
97 if (Max >= pos[b[i].e].first) flag = false;
98 Max = bit.query(x, y); if (Max != pos[b[i].e].first) flag = false;
99 if (flag) res += pos[b[i].e].second;
100 }
101 printf("%lld
", res);
102 }
103 return 0;
104 }
View Code
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 2000010
5 #define ll long long
6 #define INFLL 0x3f3f3f3f3f3f3f3f
7
8 int t, n, m;
9 int arr[N];
10
11 struct Edge
12 {
13 int to, nx; ll w;
14 Edge() {}
15 Edge(int to, int nx, ll w) : to(to), nx(nx), w(w) {}
16 }edge[N << 1];
17
18 int head[N], pos;
19
20 void Init()
21 {
22 memset(head, -1, sizeof head);
23 pos = 0;
24 }
25
26 void addedge(int u, int v, int w)
27 {
28 edge[++pos] = Edge(v, head[u], w); head[u] = pos;
29 }
30
31 struct node
32 {
33 int u; ll w;
34 node () {}
35 node (int u, ll w) : u(u), w(w) {}
36 bool operator < (const node &r) const
37 {
38 return w > r.w;
39 }
40 };
41
42 ll dist[2][N];
43 bool used[N];
44
45 void Dijkstra(int st, int id)
46 {
47 for (int i = 1; i <= n + m; ++i) dist[id][i] = INFLL, used[i] = 0;
48 priority_queue <node> q;
49 q.emplace(st, 0);
50 dist[id][st] = 0;
51 while (!q.empty())
52 {
53 int u = q.top().u; q.pop();
54 if (used[u]) continue;
55 used[u] = 1;
56 for (int it = head[u]; ~it; it = edge[it].nx)
57 {
58 int v = edge[it].to;
59 if (!used[v] && dist[id][v] > dist[id][u] + edge[it].w)
60 {
61 dist[id][v] = dist[id][u] + edge[it].w;
62 q.emplace(v, dist[id][v]);
63 }
64 }
65 }
66 }
67
68
69 int main()
70 {
71 scanf("%d", &t);
72 for (int kase = 1; kase <= t; ++kase)
73 {
74 printf("Case #%d: ", kase);
75 scanf("%d%d", &n, &m);
76 Init();
77 for (int i = 1, tot, w; i <= m; ++i)
78 {
79 scanf("%d%d", &w, &tot);
80 for (int j = 1; j <= tot; ++j) scanf("%d", arr + j);
81 for (int j = 1; j <= tot; ++j) addedge(arr[j], i + n, w);
82 for (int j = 1; j <= tot; ++j) addedge(i + n, arr[j], 0);
83 }
84 Dijkstra(1, 0);
85 Dijkstra(n, 1);
86 vector <int> v;
87 ll Min = INFLL;
88 // for (int i = 1; i <= n; ++i) cout << dist[0][i] << " " << dist[1][i] << endl;
89 for (int i = 1; i <= n; ++i) Min = min(Min, max(dist[0][i], dist[1][i]));
90 if (Min == INFLL) puts("Evil John");
91 else
92 {
93 for (int i = 1; i <= n; ++i) if (max(dist[0][i], dist[1][i]) == Min)
94 v.push_back(i);
95 printf("%lld
", Min);
96 for (int i = 0, len = v.size(); i < len; ++i) printf("%d%c", v[i], "
"[i == len - 1]);
97 }
98 }
99 return 0;
100 }
