题解 | #大连大学2023年11月程序设计竞赛（同步赛）#

加训时间！

https://ac.nowcoder.com/acm/contest/69510/A

A.加训时间！

根据题意,求出数组的最大值x，再*n即可。(第二次每个人都需要补x道题)

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
    }
    std::cout << n * *std::max_element(a.begin(), a.end()) << "\n";
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

B.爆wa种子!

由于a >= 0,那么抛物线的开口向上，最小值为(4 * a * c - b * b )/ 4 / a;
若a = 0,b != 0,则方程变为直线，因此最小值为负无穷
若a = 0,b = 0,则方程变成平行于x轴的直线

因此只有2才能取到负无穷

注意取最小值时不要忘记与3取min,赛时忘了这个条件狂WA┭┮﹏┭┮

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

std::string inf = "-1000000000";

void solve() {
    int n;
    std::cin >> n;

    std::cout << std::fixed << std::setprecision(9);

    double min = 1e18;
    

    double ans = 1e9;
    for (int i = 1; i <= n; i ++) {
        int a, b, c;
        std::cin >> a >> b >> c;

        if (a == 0 and b != 0) {
            std::cout << inf << "\n";
            return;
        } else {
            double y = (4 * a * c * 1.0 - b * b) / (4 * a);
            ans = std::min(ans,y);
        }
        ans = std::min(ans,c * 1.0);
    }   

    std::cout << std::fixed << std::setprecision(9) << ans << "\n";
    
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

C. 晚上不睡觉

输出a*b的错误答案即可

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int a, b;
    std::cin >> a >> b;

    std::cout << a + b << "\n";
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

D. 书生的负数

贪心思考,操作不会时数组和增大或减少,那么我们可以将前n - 1个数通过操作全部变为负数,然后判断最后一个是否为负数即可

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int n;
    std::cin >> n;

    int a = 0;
    for (int i = 1; i <= n; i ++) {
        int x;
        std::cin >> x;
        a += x;
    }
    a += n - 1;
    int c = n - 1;
    if (a < 0) {
        c ++;
    }
    std::cout << c << "\n";
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

E.明天

字符串查找,使用string的API即可

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "yes\n";
#define no std::cout << "no\n";

void solve() {
    std::string s;
    std::cin >> s;

    std::string str = "tomorrow";

    if (s == str) {
        no
        return;
    }

    if (str.find(s) != -1) {
        yes
    } else {
        no
    }
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

F.跳棋

通过观察可以发现，只要有两个格子上都有棋子，并且棋子的左边后者右边有空位,那么棋子就可以跳到所有位置上.

分别进行前后遍历,判断是否有满足上述条件的棋子，若没有，则输出棋子的数量

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    s = " " + s;

    for (int i = 1; i <= n - 1; i ++) {
        if (s[i] == 'X' and s[i + 1] == 'X') {
            std::cout << n << "\n";
            return;
        }
    }

    for (int i = n; i >= 2; i --) {
        if (s[i] == 'X' and s[i - 1] == 'X') {
            std::cout << n << "\n";
            return;
        }
    }
    std::cout << std::count(s.begin(), s.end(),'X') << "\n";

    

}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

G.河流管理

(刚开始写了个线段树丢上去了,后来发现是并查集O(∩_∩)O) 由于每一次打开挡板，都会将这之间的河流合并，所以用并查集进行祖先的修改即可。

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

struct DSU {
    std::vector<int> pre, f, v;//f -> number

    DSU(int n) : pre(n), f(n, 1), v(n + 1) { std::iota(pre.begin(), pre.end(), 0); }
    DSU(std::vector<i64> init) : DSU(init.size()) {
        for (int i = 0; i < init.size(); i ++) {
            f.push_back(init[i]);
        }
    }
    int find(int x) {
        while (x != pre[x]) x = pre[x] = pre[pre[x]];
        return x;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        f[y] += f[x];
        v[y] = std::max(v[y],v[x]);
        pre[x] = y;
        return true;
    }
    int size(int x) { return f[find(x)]; }
};
//DSU dsu(n + 1);

void solve() {
    int n, m;
    std::cin >> n >> m;

    DSU dsu(n + 1);
    for (int i = 1; i <= n; i ++) {
        std::cin >> dsu.v[i];
    }

    while (m -- ) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int l, r;
            std::cin >> l >> r;

            for (int i = dsu.find(l); i < dsu.find(r); i ++) {
                dsu.merge(i,i + 1);
            }

        } else {
            int x;
            std::cin >> x;

            std::cout << dsu.v[dsu.find(x)] << "\n";
        }

    }
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

H. 冒险

以为是背包问题,实则不是

由于每次装进背包后体积会*2,所以我们先拿体积小的即可

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    int v = 0,c = 0;
    for (int i = 0; i < n; i ++) {
        if (v * 2 + a[i] <= m) {
            v *= 2;
            v += a[i];
            c ++;
        }
    }
    std::cout << c << "\n";
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

I. 妙wa种子！

跟之前写过的一道题很像由于要划分k段,所以一定有一种方案,能把数组中前k大的数全部包含进去,所以直接取前k大值即可

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end(),std::greater());

    std::cout << std::accumulate(a.begin(), a.begin() + m,0ll) << "\n";

}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

J. 货币系统

显然，只要a,b,c三者互质，即可凑出

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;

    int d = std::gcd(a,b);
    d = std::gcd(d,c);

    if (d == 1) {
        yes
    } else {
        no
    }
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

K.从南到北II

字符串的删除，模拟即可

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    if (n < 3) {
        std::cout << s << "\n";
        return;
    }

    if (n == 3) {
        if (s == "hui" or s == "hen") {
            s = " ";
        }
        std::cout << s << "\n";
        return;
    }

    std::string ans = "";
    int i;
    for (i = 0; i < n - 2; i ++) {
        if (s[i] == 'h' and s[i + 1] == 'u' and s[i + 2] == 'i') {
            i += 2;
            continue;
        }
        if (s[i] == 'h' and s[i + 1] == 'e' and s[i + 2] == 'n') {
            i += 2;
            continue;
        }
        ans += s[i];
    }
    if (i != n) {
        while (i < n) {
            ans += s[i];
            i ++;
        }
    }
    if (ans.size() == 0) {
        std::cout << " " << "\n";
        return;
    }
    
    std::cout << ans << "\n";

}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

L. 选拔

排序

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n + 1);
    std::vector<std::vector<int>> adj(n + 1);

    std::vector<int> v;
    for (int i = 1; i <= n; i ++) {
        int k;
        std::cin >> k;
        for (int j = 1; j <= k; j ++) {
            int x;
            std::cin >> x;
            adj[i].push_back(x);
        }
        std::sort(adj[i].begin(), adj[i].end(),std::greater());
        a[i] = adj[i][0];
    }

    std::sort(a.begin() + 1, a.end(),std::greater());

    if (m <= n) {
        std::cout << std::accumulate(a.begin() + 1, a.begin() + 1 + m,0ll);
    } else {
        int ans = std::accumulate(a.begin() + 1, a.end(),0ll);
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j < adj[i].size(); j ++) {
                v.push_back(adj[i][j]);
            }
        }        
        std::sort(v.begin(), v.end(),std::greater());
        m -= n;
        ans += std::accumulate(v.begin(), v.begin() + m,0ll);

        std::cout << ans << "\n";
    }

}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}

M.远方

只要没有>=x 的建筑即可

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "yes\n";
#define no std::cout << "no\n";

void solve() {
    int n, x;
    std::cin >> n >> x;

    bool ok = true;
    for (int i = 0; i < n; i ++) {
        int y;
        std::cin >> y;
        if (y >= x) {
            ok = false;
        }
    }
    if (ok) {
        yes
    } else {
        no
    }
}       

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 
    
    int T = 1;
    
    // std::cin >> T;

    while (T -- ) {
        solve();
    }
    return 0;
}