CCPC 2016-2017, Finals Solution
分类:
IT文章
•
2025-01-09 09:09:26
A - The Third Cup is Free
水。
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 const int maxn = 1e5 + 10;
6
7 int n;
8 int arr[maxn];
9
10 int main()
11 {
12 int t;
13 scanf("%d", &t);
14 for(int cas = 1; cas <= t; ++cas)
15 {
16 scanf("%d", &n);
17 for(int i = 1; i <= n; ++i) scanf("%d", arr + i);
18 sort(arr + 1, arr + 1 + n);
19 int ans = 0;
20 int cnt = 0;
21 for(int i = n; i >= 1; --i)
22 {
23 cnt++;
24 if(cnt == 3)
25 {
26 arr[i] = 0;
27 cnt = 0;
28 }
29 ans += arr[i];
30 }
31 printf("Case #%d: %d
", cas, ans);
32 }
33 return 0;
34 }
View Code
B - Wash
题意：有n个洗衣机，有m个烘干机，要洗L件衣服，最后一件衣服洗完的最少时间
思路：将n个洗衣机扩展成L个洗衣机，将m个烘干机扩展成L个烘干机，那么贪心分配即可。
即用时最少的洗衣机和用时最多的烘干机配对，扩展的话，将n个洗衣机都进堆，然后依次取出，再丢进去，丢进去的时候加上它的洗衣时间即可。
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 typedef long long ll;
6 const int maxn = 1e6 + 10;
7
8 struct node{
9 ll cost, now;
10 node(){}
11 node(ll cost, ll now): cost(cost), now(now){}
12 bool operator < (const node & b) const
13 {
14 return now > b.now;
15 }
16 };
17
18 int l, n, m;
19 ll arr[maxn];
20
21 int main()
22 {
23 int t;
24 scanf("%d", &t);
25 for(int cas = 1; cas <= t; ++cas)
26 {
27 scanf("%d %d %d", &l, &n, &m);
28 priority_queue<node>q1, q2;
29 for(int i = 1; i <= n; ++i)
30 {
31 int x;
32 scanf("%d", &x);
33 q1.push(node(x, x));
34 }
35 for(int i = 1; i <= m; ++i)
36 {
37 int x;
38 scanf("%d", &x);
39 q2.push(node(x, x));
40 }
41 for(int i = 1; i <= l; ++i)
42 {
43 node tmp = q1.top();
44 q1.pop();
45 arr[i] = tmp.now;
46 tmp.now += tmp.cost;
47 q1.push(tmp);
48 }
49 ll ans = 0;
50 for(int i = l; i >= 1; --i)
51 {
52 node tmp = q2.top();
53 q2.pop();
54 ans = max(ans, tmp.now + arr[i]);
55 tmp.now += tmp.cost;
56 q2.push(tmp);
57 }
58 printf("Case #%d: %lld
", cas, ans);
59 }
60 return 0;
61 }
View Code
C - Mr.Panda and Survey
留坑。
D - Game Leader
留坑。
E - Problem Buyer
题意：出题人有n道题目，主办方需要m道不同难度题目，出题人的题目有一个难度范围，如果主办方需要买k道题目，那么出题人就从n道题目中随机选取k道给主办方，主办方要使得不论出题人如何给出k道题都能满足他的要求，求最小的k
思路：我们先考虑主办方只需要一道题的情况，答案显然是不符合那道题的其他题目个数+1
那么再考虑推广到m的情况，将区间排序，并且将题目难度也排序，从左至右用优先队列维护里面的区间是否满足，那么不满足的个数就是n - 优先队列里面的元素个数 那么显然对于这道题，至少要取 不满足个数+1 再考虑一个区间只能给一个题目，那么每次扫过去的时候pop出一个即可, $那么我们求出最大的x_i + 1 即可 x_i表示不满足第i个题目的区间有多少个$
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 const int maxn = 1e5 + 10;
6
7 struct node{
8 int l, r;
9 node(){}
10 node(int l, int r):l(l), r(r){}
11 bool operator < (const node &b)const
12 {
13 return r > b.r;
14 }
15 }arr[maxn];
16
17 int cmp(node a, node b)
18 {
19 if(a.l == b.l) return a.r > b.r;
20 else return a.l < b.l;
21 }
22
23 int n, m;
24 int brr[maxn];
25
26 int main()
27 {
28 int t;
29 scanf("%d", &t);
30 for(int cas = 1; cas <= t; ++cas)
31 {
32 scanf("%d %d", &n, &m);
33 for(int i = 1; i <= n; ++i) scanf("%d %d", &arr[i].l, &arr[i].r);
34 for(int i = 1; i <= m; ++i) scanf("%d", brr + i);
35 sort(arr + 1, arr + 1 + n, cmp);
36 sort(brr + 1, brr + 1 + m);
37 priority_queue<node>q;
38 int ans = 0;
39 int j = 1;
40 for(int i = 1; i <= m; ++i)
41 {
42 while(j <= n && arr[j].l <= brr[i]) q.push(arr[j++]);
43 while(!q.empty() && q.top().r < brr[i]) q.pop();
44 int tmp = q.size();
45 ans = max(ans, n - tmp + 1);
46 if(ans > n) break;
47 q.pop();
48 }
49 if(ans > n) printf("Case #%d: IMPOSSIBLE!
", cas);
50 else printf("Case #%d: %d
", cas, ans);
51 }
52 return 0;
53 }
View Code
F - Periodical Cicadas
留坑。
G - Pandaland
题意：给出一张图，找一个最小环（边权和最小）
思路：枚举每一条边为两个端点跑最短路，如果跑的通即存在环，更新答案即可。
但是正解应该是：
求最小生成树，每次枚举非树边，就是树上两个距离+边权
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define INFLL 0x3f3f3f3f3f3f3f3f
6 #define N 8010
7 #define pii pair <int, int>
8 int t, n, m;
9 map <pii, int> mp;
10
11 struct Edge
12 {
13 struct node
14 {
15 int to, nx, w, vis;
16 node() {}
17 node(int to, int nx, int w, int vis = 1) : to(to), nx(nx), w(w), vis(vis) {}
18 }a[N << 1];
19 int head[N], pos;
20 void init() { memset(head, 0, sizeof head); pos = -1; }
21 void add(int u, int v, int w)
22 {
23 a[++pos] = node(v, head[u], w); head[u] = pos;
24 a[++pos] = node(u, head[v], w); head[v] = pos;
25 }
26 }G;
27 #define erp(u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w)
28
29 int Hash(int x, int y)
30 {
31 if (mp.find(pii(x, y)) == mp.end()) mp[pii(x, y)] = ++n;
32 return mp[pii(x, y)];
33 }
34
35 struct node
36 {
37 int to; ll w;
38 node () {}
39 node (int to, ll w) : to(to), w(w) {}
40 bool operator < (const node &r) const
41 {
42 return w > r.w;
43 }
44 };
45
46 ll dist[N]; bool used[N];
47
48 void Dijkstra(int st, int ed)
49 {
50 for (int i = 1; i <= n; ++i) dist[i] = INFLL, used[i] = false;
51 priority_queue <node> q; q.emplace(st, 0); dist[st] = 0;
52 while (!q.empty())
53 {
54 int u = q.top().to; q.pop();
55 if(u == ed) return ;
56 if (used[u]) continue;
57 used[u] = 1;
58 erp(u) if (G.a[it].vis)
59 {
60 if (!used[v] && dist[v] > dist[u] + w)
61 {
62 dist[v] = dist[u] + w;
63 q.emplace(v, dist[v]);
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", &m);
76 mp.clear(); n = 0; G.init();
77 for (int i = 1, x[2], y[2], w, u, v; i <= m; ++i)
78 {
79 for (int j = 0; j < 2; ++j) scanf("%d%d", x + j, y + j);
80 scanf("%d", &w); u = Hash(x[0], y[0]); v = Hash(x[1], y[1]);
81 G.add(u, v, w);
82 }
83 ll res = INFLL;
84 for (int i = 0; i <= m - 1; ++i)
85 {
86 G.a[2 * i].vis = 0; G.a[2 * i + 1].vis = 0;
87 int u = G.a[2 * i].to, v = G.a[2 * i + 1].to;
88 Dijkstra(u, v);
89 res = min(res, G.a[2 * i].w + dist[v]);
90 G.a[2 * i].vis = 1; G.a[2 * i + 1].vis = 1;
91 }
92 if (res == INFLL) res = 0;
93 printf("%lld
", res);
94 }
95 return 0;
96 }
View Code
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define INFLL 0x3f3f3f3f3f3f3f3f
6 #define N 8010
7 #define pii pair <int, int>
8 int t, n, m;
9 map <pii, int> mp;
10
11 struct Gragh
12 {
13 struct node
14 {
15 int to, nx, w;
16 node() {}
17 node(int to, int nx, int w) : to(to), nx(nx), w(w){}
18 }a[N << 1];
19 int head[N], pos;
20 void init() { memset(head, 0, sizeof head); pos = 0; }
21 void add(int u, int v, int w)
22 {
23 a[++pos] = node(v, head[u], w); head[u] = pos;
24 a[++pos] = node(u, head[v], w); head[v] = pos;
25 }
26 }G;
27 #define erp(u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w)
28
29 struct Edge
30 {
31 int u, v, vis; ll w;
32 Edge() {}
33 Edge(int u, int v, ll w, int vis = 0) : u(u), v(v), w(w), vis(vis) {}
34 bool operator < (const Edge &r) const { return w < r.w; }
35 }edge[N];
36
37 int Hash(int x, int y)
38 {
39 if (mp.find(pii(x, y)) == mp.end()) mp[pii(x, y)] = ++n;
40 return mp[pii(x, y)];
41 }
42
43 int pre[N];
44 int find(int x) { return pre[x] == 0 ? x : pre[x] = find(pre[x]); }
45
46 void Kruskal()
47 {
48 sort(edge + 1, edge + 1 + m);
49 for (int i = 1; i <= m; ++i)
50 {
51 int u = edge[i].u, v = edge[i].v; ll w = edge[i].w;
52 int fu = find(u), fv = find(v);
53 if (fu == fv) continue;
54 pre[fu] = fv;
55 G.add(u, v, w);
56 edge[i].vis = 1;
57 }
58 }
59
60 int fa[N], sze[N], son[N], top[N], deep[N], rt[N]; ll dis[N];
61 void DFS(int u, int root)
62 {
63 sze[u] = 1;
64 rt[u] = root;
65 erp(u) if (v != fa[u])
66 {
67 fa[v] = u;
68 deep[v] = deep[u] + 1;
69 dis[v] = dis[u] + w;
70 DFS(v, root); sze[u] += sze[v];
71 if (!son[u] || sze[v] > sze[son[u]]) son[u] = v;
72 }
73 }
74
75 void getpos(int u, int sp)
76 {
77 top[u] = sp;
78 if (!son[u]) return;
79 getpos(son[u], sp);
80 erp(u) if (v != fa[u] && v != son[u])
81 getpos(v, v);
82 }
83
84 int lca(int u, int v)
85 {
86 while (top[u] != top[v])
87 {
88 if (deep[top[u]] < deep[top[v]]) swap(u, v);
89 u = fa[top[u]];
90 }
91 if (deep[u] > deep[v]) swap(u, v);
92 return u;
93 }
94
95 void Init()
96 {
97 mp.clear(); n = 0; G.init();
98 memset(pre, 0, sizeof pre);
99 memset(son, 0, sizeof son);
100 memset(fa, 0, sizeof fa);
101 }
102
103 int main()
104 {
105 scanf("%d", &t);
106 for (int kase = 1; kase <= t; ++kase)
107 {
108 Init();
109 printf("Case #%d: ", kase);
110 scanf("%d", &m);
111 for (int i = 1, x[2], y[2], w, u, v; i <= m; ++i)
112 {
113 for (int j = 0; j < 2; ++j) scanf("%d%d", x + j, y + j);
114 scanf("%d", &w); u = Hash(x[0], y[0]); v = Hash(x[1], y[1]);
115 edge[i] = Edge(u, v, w);
116 } Kruskal();
117 for (int i = 1; i <= n; ++i) if (!fa[i])
118 {
119 fa[i] = i; dis[i] = 0; deep[i] = 0;
120 DFS(i, i); getpos(i, i);
121 }
122 ll res = INFLL;
123 for (int i = 1, u, v, w; i <= m; ++i) if (!edge[i].vis)
124 {
125 u = edge[i].u, v = edge[i].v, w = edge[i].w;
126 if (rt[u] != rt[v]) continue;
127 res = min(res, dis[u] + dis[v] - 2 * dis[lca(u, v)] + w);
128 }
129 if (res == INFLL) res = 0;
130 printf("%lld
", res);
131 }
132 return 0;
133 }
