526互联

西南民族大学 春季 2023 训练赛 8

发布时间 2023-04-18 21:30:35作者: PHarr

L1-1 嫑废话上代码

Talk is cheap. Show me the code.

L1-2 猫是液体

a , b , c = map( int , input().split(' ') )
print( a * b * c )

L1-3 洛希极限

#include <bits/stdc++.h>

using namespace std;


int32_t main() {
    double a, c;
    int b;
    cin >> a >> b >> c;
    if (b == 0) a = a * 2.455;
    else a = a * 1.26;
    printf("%.2lf ", a);
    if (c - a > 1e-3) cout << "^_^\n";
    else cout << "T_T\n";
    return 0;
}

L1-4 调和平均

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    int n;
    cin >> n;
    double sum = 0, x;
    for (int i = 1; i <= n; i++) {
        cin >> x, sum += 1.0 / x;
    }
    printf("%.2lf\n", double(n) / sum);
    return 0;
}

L1-5 胎压监测

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    vector<int> a(4);
    int lower, diff;
    for (int &i: a) cin >> i;
    cin >> lower >> diff;
    int upper = *max_element(a.begin(), a.end());
    int t = -1;
    for (int i = 1; i <= 4; i++) {
        if (a[i - 1] < lower || upper - a[i - 1] > diff) {
            if (t == -1) t = i;
            else t = -2;
        }
    }
    if (t == -1) cout << "Normal";
    else if (t == -2) cout << "Warning: please check all the tires!";
    else cout << "Warning: please check #" << t << "!";
    return 0;
}

L1-6 吃火锅

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    int cnt = 0, t = 0, ans = 0;
    string s;
    while (true) {
        getline(cin, s);
        if (s == ".") break;
        ans++;
        if (s.find("chi1 huo3 guo1") != -1) {
            if (t == 0) t = ans;
            cnt++;
        }
    }
    cout << ans << "\n";
    if (cnt == 0) cout << "-_-#\n";
    else cout << t << " " << cnt << "\n";
    return 0;
}

L1-7 前世档案

#include <bits/stdc++.h>
using namespace std;

int32_t main(){
    int n , m , res ;
    cin >> n >> m;
    string s;
    while( m -- ){
        cin >> s;
        res = 0;
        for( auto c : s ) {
            res <<= 1;
            if( c == 'n' ) res ++;
        }
        cout << res + 1 << "\n";
    }
    return 0;
}

L1-8 刮刮彩票

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    map<int, int> ans;
    ans[6] = 10000;
    ans[7] = 36;
    ans[8] = 720;
    ans[9] = 360;
    ans[10] = 80;
    ans[11] = 252;
    ans[12] = 108;
    ans[13] = 72;
    ans[14] = 54;
    ans[15] = 180;
    ans[16] = 72;
    ans[17] = 180;
    ans[18] = 119;
    ans[19] = 36;
    ans[20] = 306;
    ans[21] = 1080;
    ans[22] = 144;
    ans[23] = 1800;
    ans[24] = 3600;

    int a[4][4];
    int st = 45;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            cin >> a[i][j], st -= a[i][j];


    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            if (a[i][j] == 0) a[i][j] = st;

    for (int i = 1, x, y; i <= 3; i++) {
        cin >> x >> y;
        cout << a[x][y] << "\n";
    }
    int t, cnt = 0;
    cin >> t;

    if (t >= 1 && t <= 3) cnt = a[t][1] + a[t][2] + a[t][3];
    else if (t >= 4 && t <= 6) cnt = a[1][t - 3] + a[2][t - 3] + a[3][t - 3];
    else if (t == 7) cnt = a[1][1] + a[2][2] + a[3][3];
    else cnt = a[1][3] + a[2][2] + a[3][1];
    cout << ans[cnt] << "\n";

    return 0;
}

L2-1 简单计算器

用栈模拟一下就好了,对于操作符可以当做字符串读入就好了

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    int n, a, b;
    string op;
    stack<int> s1;
    stack<string> s2;

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a, s1.push(a);
    for (int i = 2; i <= n; i++)
        cin >> op, s2.push(op);
    while (s1.size() >= 2) {
        b = s1.top(), s1.pop(), a = s1.top(), s1.pop(), op = s2.top(), s2.pop();
        if (op == "+") a += b;
        else if (op == "-") a -= b;
        else if (op == "*") a *= b;
        else {
            if (b == 0)
                return cout << "ERROR: " << a << "/0\n", 0;
            a /= b;
        }
        s1.push(a);
    }
    cout << s1.top() << "\n";
    return 0;
}

L2-2 口罩发放

按照题目的模拟，写一个结构体排序就好了。

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int j;
    string name, id, time, f;

    Node() {}

    bool operator<(const Node &y) const {
        if (time != y.time) return time < y.time;
        return j < y.j;
    }
} cur;

int32_t main() {
    int d, p;
    cin >> d >> p;
    map<string, int> lst;
    vector<pair<string, string>> tt;
    set<string> st;
    for (int i = 1, t, s; i <= d; i++) {
        cin >> t >> s;
        vector<Node> person;
        for (cur.j = 0; cur.j < t; cur.j++) {
            cin >> cur.name >> cur.id >> cur.f >> cur.time;
            bool f = cur.id.size() == 18;
            if (!f) continue;
            for (auto c: cur.id)
                if (c < '0' || c > '9') {
                    f = false;
                    break;
                }
            if (!f) continue;
            person.push_back(cur);
            if (cur.f == "1" && st.count(cur.id) == 0) st.insert(cur.id), tt.emplace_back(cur.name, cur.id);
        }
        sort(person.begin(), person.end());
        for (int j = 0; j < (int) person.size() && s; j++)
            if (lst[person[j].id] == 0 || i > lst[person[j].id] + p)
                cout << person[j].name << " " << person[j].id << "\n", lst[person[j].id] = i, s--;
    }
    for (auto [name, id]: tt)
        cout << name << " " << id << "\n";
    return 0;
}

L2-3 完全二叉树的层序遍历

最直接的做法肯定是把二叉树还原回来。但是因为保证了是完全二叉树，所以可以先一边 dfs 计算出每一个节点的深度，然后把点根据深度分类，最后直接输出就好了。

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> b;

void dfs(int x, int dep) {
    if (x * 2 <= n) dfs(x * 2, dep + 1);
    if (x * 2 + 1 <= n) dfs(x * 2 + 1, dep + 1);
    b.push_back(dep);
}

int32_t main() {
    cin >> n;
    dfs(1, 0);
    vector<vector<int>> f(b.front() + 1);
    for (int i = 0, x; i < n; i++)
        cin >> x, f[b[i]].push_back(x);
    cout << f[0][0];
    for (int i = 1; i < f.size(); i++)
        for (int j = 0; j < f[i].size(); j++)
            cout << " " << f[i][j];
    return 0;
}

L2-4 网红点打卡攻略

根据题目模拟一下这个操作即可，注意要保证相邻的点联通，首位和家联通，每个点只能遍历一次。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 205;
int n, dis[N][N], m, cnt, res = 1e18, ans;

int32_t main() {
    cin >> n >> m;
    for (int u, v, w; m; m--) {
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = w;
    }
    cin >> m;
    for (int k, pre, f, sum, i = 1, len; i <= m; i++) {
        cin >> k, f = 1, sum = 0, len = 0, pre = 0;
        vector<bool> vis(n + 1, false);
        for (int x; k; k--) {
            cin >> x;
            if (f && dis[pre][x] && vis[x] == false)
                sum += dis[pre][x], vis[x] = true, pre = x, len++;
            else f = 0;
        }
        if (f && dis[pre][0]) sum += dis[pre][0];
        else f = 0;

        if (f && len == n) {
            cnt++;
            if (sum < res) res = sum, ans = i;
        }
    }
    cout << cnt << "\n" << ans << " " << res << "\n";
    return 0;
}

L3-1 那就别担心了

首先题目中说的

博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。

这里的“最终命题是假的”

对于

3 2
1 2
2 3
1 2

这组数据的答案应该是1 Yes，也就是说不要求 B 没有后继。

记忆化搜索

d[x]表示x到达终点的路径数。对于搜过的点直接累加d[x]即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n, m, sta, ed, f = 1;
vector<vector<int>> e;
vector<bool> vis;
vector<int> d;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

void dfs(int u) {
    vis[u] = true;
    if (e[u].empty() && u != ed) f = 0;
    for (auto v: e[u]) {
        if (!vis[v]) dfs(v);
        d[u] += d[v];
    }
    return;
}

int32_t main() {
    n = read(), m = read();
    e = vector<vector<int>>(n + 1);
    for (int u, v; m; m--)
        u = read(), v = read(), e[u].push_back(v);
    sta = read(), ed = read();
    d = vector<int>(n + 1), vis = vector<bool>(n + 1, false);
    d[ed] = 1, vis[ed] = true;
    dfs(sta);
    cout << d[sta] << (f ? " Yes\n" : " No\n");

    return 0;
}

拓扑序+DP

首先先进行一遍 bfs，找到AB之间的联通子图，并且计算出每个从A开始的入度。

然后f[i]表示从起点到i的路径数，在联通子图上根据拓扑序进行 DP 的转移

#include <bits/stdc++.h>

using namespace std;

#define int long long

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

int32_t main() {
    int n = read(), m = read();
    vector<int> d(n + 1), f(n + 1), to(n + 1);
    vector<vector<int>> e(n + 1), g(n + 1);
    for (int u, v; m; m--)
        u = read(), v = read(), e[u].push_back(v);

    int a = read(), b = read();
    queue<int> q;
    vector<bool> vis(n + 1, false);
    q.push(a), vis[b] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int v: e[u]) {
            d[v]++, q.push(v);
        }
    }
    q.push(a), f[a] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v: e[u]) {
            f[v] += f[u], d[v]--, to[u]++;
            if (d[v] == 0) q.push(v);
        }
    }
    cout << f[b];
    bool flag = true;
    for (int i = 1; flag && i <= n; i++) {
        if (vis[i] == false || i == b) continue;
        if (to[i] == 0) flag = 0;
    }
    if (flag) cout << " Yes\n";
    else cout << " No\n";
    return 0;
}