北京林业大学“计蒜客”杯程序设计竞赛

Contents
  1. 1. A.喝酒
  2. 2. B.大钉骑马走江湖
  3. 3. C. Candy
  4. 4. D. A letter from Chensg
  5. 5. E. delightful world
  6. 6. G. 易彰彪的一张表
  7. 7. H. Ivan 的等待焦虑症发作了

zz选手只做了7个题
$A、B、C、D、E、G、H$

A.喝酒

题意:

$N瓶酒,3个盖子或者4个空瓶可以换1瓶酒,问能喝几瓶$

分析:

$直接模拟一下,别忘记换的酒也有盖子和瓶子$

代码:

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
//
// Created by TaoSama on 2016-04-24
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n;
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int ans = n, a = n, b = n;
while(a >= 3 || b >= 4) {
int delta = a / 3 + b / 4;
a = a % 3 + delta;
b = b % 4 + delta;
ans += delta;
}
printf("%d\n", ans);
}
return 0;
}

B.大钉骑马走江湖

题意:

$N*M的图,马走日,问到终点要几步$

分析:

$打个方向表和蹩马腿的表,然后直接bfs就好$

代码:

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
//
// Created by TaoSama on 2016-04-24
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
char s[105][105];
int f[105][105];
int sx, sy, tx, ty;
int d[][2] = {{1, 2}, {1, -2}, { -1, 2}, { -1, -2}, {2, 1}, {2, -1}, { -2, 1}, { -2, -1}};
int no[][2] = {0, 1, 0, -1, 0, 1, 0, -1, 1, 0, 1, 0, -1, 0, -1, 0};
int bfs() {
queue<int> q; q.push(sx * m + sy);
memset(f, -1, sizeof f);
f[sx][sy] = 0;
while(q.size()) {
int u = q.front(); q.pop();
int x = u / m, y = u % m;
for(int i = 0; i < 8; ++i) {
int nx = x + d[i][0], ny = y + d[i][1];
int kx = x + no[i][0], ky = y + no[i][1];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(kx < 0 || kx >= n || ky < 0 || ky >= m) continue;
if(s[nx][ny] == '#' || s[kx][ky] == '#') continue;
if(f[nx][ny] == -1) {
f[nx][ny] = f[x][y] + 1;
q.push(nx * m + ny);
}
}
}
return f[tx][ty];
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d%d", &n, &m) == 2) {
for(int i = 0; i < n; ++i) {
scanf("%s", s[i]);
for(int j = 0; j < m; ++j) {
if(s[i][j] == 's') sx = i, sy = j;
if(s[i][j] == 'e') tx = i, ty = j;
}
}
printf("%d\n", bfs());
}
return 0;
}

C. Candy

题意:

$N\le10^5个人,每个人有个权,现开始发糖,至少1个$
$要求权比旁边2个人大的,必须糖比他多$
$问最少需要发多少糖$

分析:

$暴力,先给每个人发一个,然后正着补一遍,倒着补一遍就好了$

代码:

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
//
// Created by TaoSama on 2016-04-24
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, a[N];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d", &n) == 1) {
vector<int> v(n + 1, 1);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
for(int i = 1; i <= n; ++i) {
if(i > 1 && a[i] > a[i - 1]) v[i] = max(v[i], v[i - 1] + 1);
if(i < n && a[i] > a[i + 1]) v[i] = max(v[i], v[i + 1] + 1);
}
for(int i = n; i; --i) {
if(i > 1 && a[i] > a[i - 1]) v[i] = max(v[i], v[i - 1] + 1);
if(i < n && a[i] > a[i + 1]) v[i] = max(v[i], v[i + 1] + 1);
}
// for(int x : v) printf("%d ", x); puts("");
int ans = accumulate(v.begin() + 1, v.end(), 0);
printf("%d\n", ans);
}
return 0;
}

D. A letter from Chensg

题意:

$求N个串的字典序最小的最长公共子串$
$我很喜欢这封love letter啊$

分析:

$数据非常小,直接从长到短的暴力就好了,正解当然是sa啦$

代码:

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
//
// Created by TaoSama on 2015-10-30
// Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n;
string s[15];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; ++i) cin >> s[i];
string ans;
for(int sz = 60; sz >= 3; --sz) {
for(int st = 0; st + sz - 1 < 60; ++st) {
bool ok = true;
string cur = s[1].substr(st, sz);
for(int i = 2; i <= n; ++i) {
if(s[i].find(cur) == string::npos) {
ok = false;
break;
}
}
if(!ok) continue;
if(!ans.size() || cur < ans) ans = cur;
}
if(ans.size()) break;
}
if(ans.size()) cout << ans << '\n';
else cout << "No significant commonalities\n";
}
return 0;
}

E. delightful world

题意:

$猜1个01串,先现给出N\le 35次猜想,以及对应的猜对的个数\le 5$
$问符合要求的串有几个$

分析:

$meet in middle辣,二进制枚举前半部分,然后哈希这个串的匹配情况成数字,因为猜对个数小嘛$
$然后从另一半计数就好了$

代码:

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
//
// Created by TaoSama on 2016-04-24
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
typedef long long LL;
int n, m;
char s[15][40];
int a[15];
LL ten[20];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
ten[0] = 1;
for(int i = 1; i < 20; ++i) ten[i] = ten[i - 1] * 10;
while(scanf("%d%d", &n, &m) == 2) {
for(int i = 0; i < m; ++i) scanf("%s%d", s[i], a + i);
map<LL, int> mp;
int half = n >> 1, lft = n - half;
for(int i = 0; i < 1 << half; ++i) {
bool ok = true;
LL sum = 0;
for(int j = 0; j < m; ++j) {
int cnt = 0;
for(int k = 0; k < half; ++k)
if(s[j][k] - '0' == (i >> k & 1)) ++cnt;
if(cnt <= a[j]) sum += cnt * ten[j];
else {
ok = false;
break;
}
}
if(ok) ++mp[sum];
}
LL ans = 0;
for(int i = 0; i < 1 << lft; ++i) {
bool ok = true;
LL sum = 0;
for(int j = 0; j < m; ++j) {
int cnt = 0;
for(int k = 0; k < lft; ++k)
if(s[j][half + k] - '0' == (i >> k & 1)) ++cnt;
if(cnt <= a[j]) sum += (a[j] - cnt) * ten[j];
else {
ok = false;
break;
}
}
if(ok) ans += mp[sum];
}
printf("%lld\n", ans);
}
return 0;
}

G. 易彰彪的一张表

题意:

$N个长度为M的字符串,如果他们首尾相连,问T串是否是合并串的子串$

分析:

$数据很小,直接合并到一起string::find$

代码:

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
//
// Created by TaoSama on 2016-04-24
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(cin >> n >> m) {
string s, t;
for(int i = 1; i <= n; ++i) {
cin >> t;
s += t;
}
for(int i = 0; i < s.size(); ++i) s[i] = tolower(s[i]);
cin >> t;
for(int i = 0; i < t.size(); ++i) t[i] = tolower(t[i]);
if(s.find(t) != string::npos) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}

H. Ivan 的等待焦虑症发作了

题意:

$10个电梯上下楼,会在一些层停留,问到达规定层的时间(不算这层的停留时间)$

分析:

$数据很小直接一层一层走的模拟就好了,一开始写lower_bound没看数据写了半天。$

代码:

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
//
// Created by TaoSama on 2016-04-24
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, p, wh[5];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d%d", &n, &p) == 2) {
for(int i = 1; i <= n; ++i) scanf("%d", wh + i);
bool s[5][50] = {};
for(int i = 1; i <= n; ++i) {
int cnt; scanf("%d", &cnt);
while(cnt--) {
int x; scanf("%d", &x);
s[i][x] = 1;
}
}
vector<int> ans(n + 1);
for(int i = 1; i <= n; ++i) {
if(wh[i] == p) ans[i] = 0;
else if(wh[i] > p) {
ans[i] = 5;
for(int j = wh[i] - 1; j > p; --j) {
ans[i] += 5;
if(s[i][j]) ans[i] += 15;
}
} else {
ans[i] = 5;
for(int j = wh[i] + 1; j < p; ++j) {
ans[i] += 5;
if(s[i][j]) ans[i] += 15;
}
}
}
for(int i = 1; i <= n; ++i)
printf("%d%c", ans[i], " \n"[i == n]);
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到