ZZJC新生训练赛第十八场题解

链接：https://www.nowcoder.com/acm/contest/97429
密码：gar615gdsr

难度分类

• 题目分值决定

A-解题思路

除一下比较分数大小即可

A-代码实现

a, b = map(int, input().split())
x, y = map(int, input().split())
if a / b > x / y:
    print(">")
elif a / b == x / y:
    print("=")
else:
    print("<")

B-解题思路

已经固定矩阵大小，枚举分界线后遍历即可

B-代码实现

f = 1
g = []
for i in range(9):
    g.append(list(map(int, input().split())))
    if len(set(g[i])) != 9:
        f = 0
for x in [0, 3, 6]:
    for y in [0, 3, 6]:
        st = set()
        for i in range(3):
            for j in range(3):
                st.add(g[x + i][y + j])
        if len(st) != 9:
            f = 0 
if f:
    print("Valid")
else:
    print("Invalid")

C-解题思路

对n取余除3直到n是0即可

C-代码实现

n = (int(input()))
ans = ""
while n > 0:
    ans = str(n % 3) + ans
    n //= 3
print(ans)

D-解题思路

看看每一天用哪种方式更划算然后求和即可

D-代码实现

n, c = map(int, input().split())
a = list(map(int, input().split()))
dp = [a[0]] * n
for i in range(1, n):
    dp[i] = min(dp[i - 1] + c, a[i])
print(sum(dp))

E-解题思路

算一下中间过程中会扣除的最大生命值即可，注意最后要+1保证是正数

E-代码实现

n = int(input())
a = list(map(int, input().split()))
ans = pre = 0
for i in a:
    pre += i
    ans = min(ans, pre)
print(abs(ans) + 1)

F-解题思路

双指针谁小优先选谁即可

F-代码实现

s = input()
t = input()
 
i, j = 0, 0
n, m = len(s), len(t)
ans = []
 
while i < n and j < m:
    if s[i] <= t[j]:
        ans.append(s[i])
        i += 1
    else:
        ans.append(t[j])
        j += 1
 
if i < n:
    ans.append(s[i:])
if j < m:
    ans.append(t[j:])
 
print("".join(ans))

G-解题思路

按照截止排序，看完成时间会不会和开始时间有交叉

G-代码实现

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin >> n;

    std::vector<std::array<int, 2>> dt(n);
    for (int i = 0; i < n; i++) {
        std::cin >> dt[i][0] >> dt[i][1];
    }

    std::sort(dt.begin(), dt.end());

    i64 sum = 0;
    for (auto [d, t]: dt) {
        sum += t;
        if (sum > d) {
            std::cout << "No\n";
            return 0;
        }
    }
    std::cout << "Yes\n";
}

H-解题思路

中位数附近就是最小值

H-代码实现

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin >> n;

    std::vector<int> x(n);
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
    }

    std::sort(x.begin(), x.end());

    i64 ave1 = x[n / 2], ave2 = x[n / 2 + 1], ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        ans1 += abs(ave1 - x[i]);
        ans2 += abs(ave2 - x[i]);
    }

    std::cout << std::min(ans1, ans2);
}

I-解题思路

求卡特兰数

I-代码实现

#include <bits/stdc++.h>

using i64 = long long;
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;

std::vector<i64> fac(N + 1, 1), invfac(N + 1, 1);

i64 ksm(i64 a, i64 n, i64 mod) {
    i64 res = 1;
    a = (a % mod + mod) % mod;
    while (n) {
        if (n & 1) {
            res = (a * res) % mod;
        }
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    invfac[n] = ksm(fac[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) {
        invfac[i] = invfac[i + 1] * (i + 1) % MOD;
    }
}

i64 C(int n, int m) {  // 组合数
    if (m > n || m < 0) {
        return 0;
    }
    return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}

i64 A(int n, int m) {  // 排列数
    if (m > n || m < 0) {
        return 0;
    }
    return fac[n] * invfac[n - m] % MOD;
}

// n 对括号的合法匹配数，有 n 个节点的二叉树的种类数
// 从对角线下方走到对角线的路径数，栈的出栈序列数
i64 catalan(int n) {  // 卡特兰数
    if (n < 0) {
        return 0;
    }
    return C(2 * n, n) * ksm(n + 1, MOD - 2, MOD) % MOD;
}

// 将 n 个不同的元素划分到 k 个非空集合中的方案数
i64 stirling2(int n, int k) {  // 第二类斯特林数
    if (k > n || k < 0) {
        return 0;
    }
    i64 res = 0;
    for (int i = 0; i <= k; i++) {
        i64 term = C(k, i) * ksm(k - i, n, MOD) % MOD;
        if (i % 2 == 1) {
            term = (MOD - term) % MOD;
        }
        res = (res + term) % MOD;
    }
    return res * invfac[k] % MOD;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    init(N);
    int n;
    std::cin >> n;

    std::cout << catalan(n);
}

J-解题思路

nm只有16，dfs爆搜即可

J-代码实现

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> a[i][j];
        }
    }

    int ans = 0;
    std::vector<int> f(m);
    auto dfs = [&](auto &&self, int x, int cnt) -> void {
        if (x == n) {
            for (int i = 0; i < m; i++) {
                if (f[i] < 0) {
                    return;
                }
            }
            ans = std::max(ans, cnt);
            return;
        }
        self(self, x + 1, cnt);
        for (int i = 0; i < m; i++) {
            f[i] += a[x][i];
        }
        self(self, x + 1, cnt + 1);
        for (int i = 0; i < m; i++) {
            f[i] -= a[x][i];
        }
    };

    dfs(dfs, 0, 0);

    std::cout << ans;
}