2016 CCPC Final

字数统计: 3.2k字   |   阅读时长: 17分
训练题解
solved A B C D E F G H I J K L
6 / 12 O Ø · · · · Ø Ø · O · O
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

比赛链接

A.The Third Cup is Free

Solved by Tryna.00:06:25(+)

题意： 每3杯咖啡有一杯免费，sort一下。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;    
const double pi = acos((double)(-1));
#define inf 0x3f3f3f3f
#define ll long long
#define eps 1e-8
const int maxn = 1010;
const int mod = 1e9 + 7;
#define endl "\n"
int moven1[10][5] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}; 
int moven2[10][5] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int t, n, a[100010];
int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
	scanf("%d",&t);
	int ans = 0;
	while(t--){
		ans++;
		scanf("%d",&n);
		for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
		sort(a + 1 , a + 1 + n);
		int sum = 0;
		int cnt = 0;
		for(int i = n; i >= 1; i--){
			if(cnt == 2){
				cnt = 0;
				continue;
			}
			sum += a[i];
			cnt++;
		}
		printf("Case #%d: ",ans);
		printf("%d\n",sum);
	}
	return 0;
}

B.wash

Solved by lllllan.(-)

题意： L件衣服，N台洗衣机和M台烘干机，一台机器每次工作只能处理一件衣服，并且都有分别的清洗/烘干时间，问先清洗再烘干，最少需要多少时间洗完并烘干所有的衣服。

思路：

贪心是显而易见的，但是又需要清洗又需要烘干，并且有先后顺序。然后就需要想，可以分别贪心吗？ 答案是可以的，先只考虑清洗，列出洗i件衣服分别需要多少时间，然后倒过来将最后清洗的衣服使用用时最短的烘干机，清洗时间短的和烘干时间长的去匹配，其中出现的最大值就是需要的答案。

思考：

为什么可以分开贪心： 烘干机的选择，受清洗机选择的影响是肯定的，但是清洗机的选择，并不受烘干机选择的影响，所以可以先对清洗贪心，列出最优选择之后，再去匹配烘干机。
为什么清洗时间短的去匹配烘干时间长的： 首先如果一件衣服同时选择了清洗时间最短和烘干时间最少的机器，那留给最后一件衣服的就是清洗时间和烘干时间都很长的机器，那时间就边长了。那反向匹配就一定正确吗？ （我发现我语言解释不了，读者可以自己想一下，确实是这样的）

具体做法： 将pair<int, int> 插入优先队列，first表示可以用这台机器的时间（若是多次使用，则要等之前使用完成才能再次使用），second表机器工作一次的时间。按从小到达的顺序排好，依次取出清洗第i件衣服。记录下时间，倒序之后，相同操作去处理干燥机。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

#define fi first
#define se second
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef pair<ll, ll> pll;

ll Time[N];
void run(int cnt) {
	ll ans = 0;
	memset(Time, 0, sizeof Time);
	priority_queue<pll, vector<pll>, greater<pll> > w, d;
	
	int l = read(), n = read(), m = read();
	for(int i = 1; i <= n; i++)	{
		int x = read();
		w.push(pll(x, x));
	}
	for(int i = 1; i <= m; i++) {
		int x = read();
		d.push(pll(x, x));
	}
	
	for(int i = 1; i <= l; i++) {
		pll tem = w.top(); w.pop();
		Time[i] = tem.fi;
		w.push(pll(tem.fi + tem.se, tem.se));
	}
	for(int i = l; i > 0; i--) {
		pll tem = d.top(); d.pop();
		Time[i] += tem.fi;
		ans = max(ans, Time[i]);
		d.push(pll(tem.fi + tem.se, tem.se));
	}

	printf("Case #%d: %lld\n", cnt, ans);
}

int main() {
	int _T = read();
	for(int cnt = 1; cnt <= _T; cnt++)	run(cnt);
	return 0;
}

G.Pandaland

Solved by lllllan.(-)

题意： 给定一个无向图，求出其中的最小环。

题解： 之前做到过一次最小环的问题，所以留着了Floyd求最小环的模板，但是报MLE了，反正Floyd的复杂度是不能接受的。办法就是换乘Dijstra，暴力枚举，删除i-j的边，然后求i到j的最短路。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define endl "\n"
#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

const int N = 8e3 + 10;
int id, ans;
int cnt, head[N];
int dis[N], vis[N];
map<pair<int, int>, int> mp;

struct node{
	int id, w;
	node(int id, int w): id(id), w(w) {}
	bool operator<(const node &A)const{
		return A.w < w;}
};
struct edge{	int to, w, next;} e[N];
void add(int u, int v, int w) {	e[cnt].to = v, e[cnt].w = w, e[cnt].next = head[u], head[u] = cnt++;}
void addedge(int u, int v, int w) {	add(u, v, w); add(v, u, w);}

void init() {
	id = cnt = 0;
	mp.clear();
	for(int i = 0; i < N; i++)	head[i] = -1;
}
void clear_set() {	for(int i = 0; i < N; i++)	dis[i] = inf, vis[i] = 0;}

void dijkstra(int s, int t, int cost) {
	clear_set();
	priority_queue<node> Q;
	Q.push(node(s, 0));
	dis[s] = 0;
	while(!Q.empty()) {
		node u = Q.top(); Q.pop();
		if(u.id == t) { ans = min(ans, u.w + cost); return;}
		if(u.w > ans)	return;
		if(vis[u.id])	continue;
		vis[u.id] = 1;
		for(int i = head[u.id]; ~i; i = e[i].next) {
			int v = e[i].to, w = e[i].w;
			if(vis[v])	continue;
			if(dis[v] > u.w + w) {
				dis[v] = u.w + w;
				Q.push(node(v, dis[v]));
			}
		}
	}
}

void run(int tot) {
	init();
	int m = read();
	while(m--) {
		int a = read(), b = read(), c = read(), d = read(), w = read();
		if(!mp[{a, b}])	mp[{a, b}] = ++id;
		if(!mp[{c, d}])	mp[{c, d}] = ++id;
		int u = mp[{a, b}], v = mp[{c, d}];
		addedge(u, v, w);
	}
	
	ans = inf;
	for(int i = 0; i < cnt; i += 2) {
		int u = e[i].to, v = e[i + 1].to, w = e[i].w;
		e[i].w = e[i + 1].w = inf;
		dijkstra(u, v, w);
		e[i].w = e[i + 1].w = w;
	}
	
	printf("Case #%d: %d\n", tot, ans == inf ? 0 : ans);
}

int main() {
	int _T = read();
	for(int i = 1; i <= _T; i++)	run(i);
	return 0;
}

H.Engineer Assignment

Solved by Sstee1XD. (-)

题意：有nn个任务，完成这些任务需要一些领域的知识。有mm个工程师，每个工程师都有一些自己会的领域。每个工程师只能选择一个任务，若参与这项任务的工程师具备了完成所需的所有知识，这项任务则被完成。问最多能完成几个任务。

题解：题目给的nn和mm都很小，所以想到了状压dpdp去实现dp[i][j]dp[i][j]表示前ii个任务在使用工程师jj状态下最多能完成的任务个数。在维护dpdp状态之前，要额外跑一遍来确定能完成第ii个任务的方案，用于最后的状态转移。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int dp[15][1 << 11], c[15], d[15], a[15][15], b[15][15], vis[150];
int n, m, cas;
vector<int> G[15];

void solve() {
    memset(dp, 0, sizeof(dp));
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        G[i].clear();
        for (int j = 1; j <= c[i]; ++j) cin >> a[i][j];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> d[i];
        for (int j = 1; j <= d[i]; ++j) cin >> b[i][j];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 1 << m; ++j) {
            memset(vis, 0, sizeof(vis));
            for (int k = 0; k < m; ++k) {
                if ((1 << k) & j) {
                    for (int q = 1; q <= d[k + 1]; ++q) {
                        vis[b[k + 1][q]] = 1;
                    }
                }
            }
            for (int q = 1; q <= c[i]; ++q) {
                if (!vis[a[i][q]]) break;
                if (q == c[i]) G[i].push_back(j);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 1 << m; ++j) {
            dp[i][j] = dp[i - 1][j];//注意这步状态转移
            for (auto v : G[i]) {
                if ((v & j) != v) continue;
                dp[i][j] = max(dp[i - 1][j - v] + 1, dp[i][j]);
            }
        }
    }
    cout << "Case #" << ++cas << ": " << dp[n][(1 << m) - 1] << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _T;
    cin >> _T;
    while (_T--) solve();
    return 0;
}

J.Worried School

Solved by Sstee1XD. 2:37(+5)

题意：给你一个学校名，再给你五场区域赛的前2020名，再给你一场ec−finalec-final的前2020名，现在要给他们发一定数量的入围WFWF的资格。区域赛以名次优先，名次相同时看它给你的区域赛的顺序，先打的优先获得资格。获得过资格的队伍不会再获得，但仍占排名。分配完区域赛之后，再给ec−finalec-final剩下的资格。现在只知道总资格数量，不知道怎么分配，问你给你的学校能否进入WFWF，不能则输出最小的分配给ec−finalec-final的资格数量，使得该学校无法进入。
题意：给的数据范围很小，读懂题目了就能暴力循环。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
map<string, int> mp, got;
int go, cas;
string t[7][30], s;

void solve() {
	cin >> go >> s;
	int ans = go + 1;
	for (int i = 1; i <= 6; ++i) {
		for (int j = 1; j <= 20; ++j) {
			cin >> t[i][j];
		}
	}
	for (int g = go; g >= 0; --g) {
		int ec = 0, site = 0;
		int flag = 0;
		mp.clear();
		got.clear();
		for (int j = 1; j <= 20; ++j) {
			if (site >= g) {
				flag = -1;
				break;
			}
			for (int i = 1; i <= 5; ++i) {
				if (!got[t[i][j]]) {
					site++;
					got[t[i][j]] = 1;
					if (t[i][j] == s) {
						flag = site;
						break;
					}
					if (site >= g) {
						flag = -1;
						break;
					}
				}
			}
			if (flag) break;
		}
		if (flag > 0) {
			continue;
		}
		
		for (int i = 1; i <= 20; ++i) {
			if (ec >= go - g) {
				flag = -1;
				break;
			}
			if (!got[t[6][i]] || t[6][i] == s) {
				ec++;
				if (t[6][i] == s) {
					flag = ec;
					break;
				}
				if (ec >= go - g) break;
			}
		}
		if (flag > 0) {
			continue;
		}
		ans = go - g;
		break;
	}
	cout << "Case #" << ++cas << ": ";
	if (ans == go + 1) {
		cout << "ADVANCED!" << endl;
		return;
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int _T;
	cin >> _T;
	while (_T--) solve();
	return 0;
}

L.Daylight Saving Time

Solved by Tryna. 03:18:10(+)

题解： 打表打出每年三月第二个周日和十一月第一个周日

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int a[500] = {0,11,4,9,2,8,1,14,7,13,6,11,4,10,3,9,2,8,1,13,6,12,5,11,4,10,3,8,1,14,7,13,6,12,5,10,3,9,2,8,1,14,7,12,5,11,4,10,3,9,2,14,7,13,6,12,5,11,4,9,2,8,1,14,7,13,6,11,4,10,3,9,2,8,1,13,6,12,5,11,4,10,3,8,1,14,7,13,6,12,5,10,3,9,2,8,1,14,7,12,5,11,4,10,3,9,2,14,7,13,6,12,5,11,4,9,2,8,1,14,7,13,6,11,4,10,3,9,2,8,1,13,6,12,5,11,4,10,3,8,1,14,7,13,6,12,5,10,3,9,2,8,1,14,7,12,5,11,4,10,3,9,2,14,7,13,6,12,5,11,4,9,2,8,1,14,7,13,6,11,4,10,3,9,2,8,1,14,7};
int t, m, d, h, m1, sec, y;
int main() {
	scanf("%d",&t);
	for(int k = 1; k <= t; k++){
		scanf("%d-%d-%d %d:%d:%d", &y, &m, &d, &h, &m1, &sec);
//		printf("%d-%d-%d %d:%d:%d\n", y, &m, &d, &h, &m1, &sec);
		int cnt = 2 * (y - 2007);
		printf("Case #%d: ",k);
		if(m < 3) printf("PST\n");
		else if(m == 12) printf("PST\n");
		else if(m >= 4 && m <= 10) printf("PDT\n");
		else if(m == 3){
			if(d < a[cnt + 1]) printf("PST\n");
			else if(d > a[cnt + 1]) printf("PDT\n");
			else{
				if(h == 2) printf("Neither\n");
				else if(h < 2) printf("PST\n");
				else printf("PDT\n");
			}
		}
		else if(m == 11){
			if(d < a[cnt + 2]) printf("PDT\n");
			else if(d > a[cnt + 2]) printf("PST\n");
			else{
				if(h == 1) printf("Both\n");
				else if (h < 1) printf("PDT\n");
				else printf("PST\n");
			}
		}
	}		

	return 0;
}
文章目录
  1. A.The Third Cup is Free
  2. B.wash
  3. G.Pandaland
  4. H.Engineer Assignment
  5. J.Worried School
  6. L.Daylight Saving Time
|