22.4.5天梯训练

发表于 分类于 ，

校内训练赛，非本校同学可能打不开。

L1-1 拉格朗日中值定理 (5 分)

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    printf("%.1f\n", (1.0 * pow(b, 2) - pow(a, 2)) / (2 * 1.0 * (b - a)));
    return 0;
}

L1-2 h0053. 游戏时间 (5 分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

int a, b, c, d;
int main() {
    cin >> a >> b >> c >> d;
    int t1 = a * 60 + b;
    int t2 = c * 60 + d;
    if (t2 < t1) t2 += 24 * 60;
    int h = (t2 - t1) / 60, m = (t2 - t1) % 60;
    if (h == 0 && m == 0)
        cout << "O JOGO DUROU 24 HORA(S) E 0 MINUTO(S)" << endl;
    else
        printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)\n", h, m);
    return 0;
}

L1-3 h0079. 循环相克令 (10 分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    string a, b;
    for (int i = 0; i < t; i++) {
        cin >> a >> b;
        if (a == b) cout << "Repetition" << endl;
        if (a == "Scissors" && b == "Paper") cout << "Player1" << endl;
        if (a == "Scissors" && b == "Rock") cout << "Player2" << endl;
        if (a == "Paper" && b == "Rock") cout << "Player1" << endl;
        if (a == "Paper" && b == "Scissors") cout << "Player2" << endl;
        if (a == "Rock" && b == "Scissors") cout << "Player1" << endl;
        if (a == "Rock" && b == "Paper") cout << "Player2" << endl;
    }
    return 0;
}

L1-4 明天几号？ (10 分)

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
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int y, m, d;
    scanf("%d/%d/%d", &y, &m, &d);
    // 输出下一天
    if (d == months[m]) {
        if (m == 12) {
            y++;
            m = 1;
            d = 1;
        } else if (m == 2 && y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)) {
            d++;

        } else {
            m++;
            d = 1;
        }
    } else {
        if (m == 2 && d == 29) {
            m++;
            d = 1;
        } else {
            d++;
        }
    }

    cout << y << "/" << m << "/" << d << endl;
    return 0;
}

L1-5 15道题你能爆0我？？ (15 分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int scores[] = {0, 5, 5, 10, 10, 15, 15, 20, 20, 25, 25, 25, 25, 30, 30, 30};
int main() {
    int n;
    cin >> n;
    while (n--) {
        int ans = 0, x;
        for (int j = 1; j <= 15; j++) {
            cin >> x;
            if (scores[j] == x) ans++;
        }
        if (ans == 15) {
            cout << "xuan ak la!" << endl;
        } else if (ans > 7) {
            cout << "xuan hai xing ba!" << endl;
        } else if (ans > 0) {
            cout << "xuan jia you ba!" << endl;
        } else if (ans == 0) {
            cout << "xuan bao ling la!" << endl;
        }
    }
    return 0;
}

L1-6 烤地瓜 (15 分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;
int n;
int res;
bool isprime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++)
        if (n % i == 0 && !isprime(i)) res += i;
    cout << res << endl;
    return 0;
}

L1-7 红包 (20 分)

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
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int n;
// 记录结果位数
int res = -1;
// 记录本次位数
int cnt;
// 记录结果的开头数组
int rs;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    int ts;
    int a0 = -1, a1, num = 0;
    for (int i = 0; i < n; i++) {
        cin >> a1;
        // 如果是连续的
        if (a0 + 1 == a1) {
            a0 = a1, num++;
        } else {
            // 如果不连续，就判断是不是比之前所记录的大
            if (num > res) rs = ts, res = num;
            if (num >= 10) cnt ++;
		// 替换开头
            ts = a1;
            a0 = a1;
            num = 1;
        }
    }
    if (num > res) rs = ts, res = num;
    if (num >= 10) cnt ++;
    cout << cnt << endl;
    for (int i = 0; i < res; i++) {
        cout << rs + i;
        if (i != res - 1) cout << ' ';
    }
    return 0;
}

L1-8 挑单词 (20 分)

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
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
vector<string> v;
int n;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    while (n--) {
        string tw;
        cin >> tw;
        // 找超过3个字符的单词，双指针
        for (int i = 0; i < tw.size(); i++) {
            int j = i;
            while (isalpha(tw[j])) j++;
            if (j - i >= 3) {
                string t = tw.substr(i, j - i);
                t[0] = toupper(t[0]);
                v.push_back(t);
            }
            i = j;
        }
    }
    sort(v.begin(), v.end(), greater<string>());
    v.erase(unique(v.begin(), v.end()), v.end());
    if (v.size() != 0)
        for (int i = 0; i < v.size(); i++) {
            cout << v[i];
            if (i != v.size() - 1) cout << " ";
        }
    else
        cout << "no word" << endl;
    return 0;
}

L2-1 后缀表达式 (25 分)

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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
stack<ll> st;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    while (cin >> s) {
        if (s[0] != '+' && s[0] != '-' && s[0] != '*' && s[0] != '/') {
            st.push(stoll(s));
        } else {
            auto a = st.top();
            st.pop();
            auto b = st.top();
            st.pop();
            //  cout << a << " " << b << endl;
            if (s[0] == '+') {
                st.push((b % mod + a % mod) % mod);
            } else if (s[0] == '-') {
                st.push((b % mod - a % mod) % mod);
            } else if (s[0] == '*') {
                st.push(((b % mod) * (a % mod)) % mod);
            } else if (s[0] == '/') {
                st.push((b % mod) / (a % mod));
            }
        }
    }
    cout << st.top() % mod;
    return 0;
}

L2-4 航空公司VIP客户查询 (25 分)

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
#pragma GCC optimize(2)
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
int n, k;
map<string, int> m;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        string id;
        int mile = 0;
        cin >> id >> mile;
        if (mile < k) mile = k;
        m[id] += mile;
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        string id;
        cin >> id;
        if (m.count(id) != 0)
            cout << m[id] << endl;
        else
            cout << "No Info" << endl;
    }
    return 0;
}

L3-1 扫雷游戏 (30 分)

扫了一个小时还是只能过样例…

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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
// 存雷，true 表示有雷
bool mp[N][N];
// 是否已经打开
int st[N][N];
// row col 雷数量
int n, m, k, l;

int bx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, by[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// 算一算八个方向有几个雷
void count(int x, int y) {
    st[x][y] = 0;
    for (int i = 0; i < 8; i++) {
        int nx = x + bx[i], ny = y + by[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (mp[nx][ny]) st[x][y]++;
    }
}

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
// bfs 打开周围没雷的格子
void bfs(int x, int y) {
    queue<PII> q;
    q.push({x, y});
    count(x, y);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (!mp[nx][ny] && st[nx][ny] == -1) {
                count(nx, ny);
                q.push({nx, ny});
            }
        }
    }
}

bool tap(int x, int y) {
    // 越界
    if (x < 0 || x >= m || y < 0 || y >= n) return false;
    // 如果开过了
    if (st[x][y] != -1) return false;
    // 如果这里是雷，那么就是死亡
    if (mp[x][y]) return true;
    // 把旁边点开
    bfs(x, y);
    return false;
}
bool flag = false;
int main() {
    cin >> n >> m >> k >> l;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        mp[x][y] = true;
    }
    memset(st, -1, sizeof(st));
    for (int i = 0; i < l; i++) {
        int x, y;
        cin >> x >> y;
        if (tap(x, y)) {
            cout << "You lose" << endl;
            flag = true;
            break;
        } else {
            for (int ii = 0; ii < n; ii++) {
                for (int jj = 0; jj < m; jj++) printf("%d ", st[ii][jj]);
                cout << endl;
            }
        }
        if (i != l - 1) cout << endl;
    }
    int cnt = 0;
    if (!flag) {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (st[i][j] == -1) cnt++;
        // cout << cnt << endl;
        if (cnt == k) cout << "You win" << endl;
    }
    return 0;
}