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

Author Avatar
TaoSama Apr 25, 2016

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

A.喝酒

题意：

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

分析：

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

代码：

//
//  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就好$

代码：

//
//  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个人大的，必须糖比他多$
$问最少需要发多少糖$

分析：

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

代码：

//
//  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啦$

代码：

//
//  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辣，二进制枚举前半部分，然后哈希这个串的匹配情况成数字，因为猜对个数小嘛$
$然后从另一半计数就好了$

代码：

//
//  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$

代码：

//
//  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没看数据写了半天。$

代码：

//
//  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;
}