A. 战争会议

题意：给一个N 和 一个X，X的两倍有没有大于N

代码：

for _ in range(int(input())):
    n, x = list(map(int, input().split()))
    print("YES" if 2 * x >= n else "NO")

B 魔法力量[Easy]

题意：给一个数组，可以从数组任意位置向后取，取的下一个数严格大于之前的数，问最大取值是多少。

定义a为数组，i为当前位置。

考虑以i结尾前面最大取到多少

所以dp[i]表示以i为结尾的数组取到的最大值是多少，递推式如下： $dp[i]＝\begin{cases} max(dp[j]) + a[i],1 <= j < i \end{cases}$ 最后输出$max(dp)$

py代码如下：

n = int(input())
a = list(map(int, input().split()))
f = [0] * (n + 1)
for i in range(n):
    f[i] = a[i]
    for j in range(i):
        if a[j] < a[i]:
            f[i] = max(f[i], f[j] + a[i])
print(max(f))

C 魔法力量[Hard]

通过B可以发现第二层循环主要找的是之前小于数字a[i]的f数组的最大值，可以用值域线段树查找区间最大值优化dp。

import sys


class Tree:
    left = None
    right = None
    val = 0
    start = 0
    end = 0

    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end


def query(root: Tree, l: int, r: int, L: int, R: int) -> int:
    if root == None: return 0
    if l >= L and r <= R:
        return root.val
    m = (l + r) // 2
    ans = 0
    if m >= L:
        ans = query(root.left, l, m, L, R)
    if m < R:
        ans = max(ans, query(root.right, m + 1, r, L, R))
    return ans


def update(root: Tree, l: int, r: int, idx: int, v: int) -> None:
    if l == r:
        root.val = v
        return
    m = (r - l) // 2 + l
    if root.left == None: root.left = Tree(l, m)
    if root.right == None: root.right = Tree(m + 1, r)
    if m >= idx:
        update(root.left, l, m, idx, v)
    elif m < idx:
        update(root.right, m + 1, r, idx, v)
    root.val = max(root.left.val, root.right.val)


n = int(input())
a = list(map(int, input().split()))
f = [0] * (n + 1)
inf = 10 ** 9
root = Tree(1, inf)
ans = 0
for i in range(1, n + 1):
    if i == 1:
        f[i] = a[i - 1]
    else:
        f[i] = a[i - 1] + query(root, 1, inf, 1, a[i - 1] - 1)
    ans = max(ans, f[i])
    update(root, 1, inf, a[i - 1], f[i])
print(ans)

D 银行开锁[Easy]

题意：选$N$个数，数字范围在$1-M$之间，数字的绝对值差必须 $\geq$ k，问有几种方式。

此题 N <= 100，有个 $N^3$ 的dp解法 首先上最直觉的记忆化搜索 代码如下：

from functools import cache

n, m, k = list(map(int, input().split()))
MOD = 998244353

# i表示当前位，pre表示上一个选的数
@cache
def dfs(i: int, pre: int) -> int:
    if i >= n:
        return 1
    ans = 0
    # 选择1 - m之间的数
    for num in range(1, m + 1):
        if abs(num - pre) >= k:
            ans += dfs(i + 1, num)
            ans %= MOD

    return ans


print(dfs(0, -k))

E. 银行开锁[Hard]

N = 1000 必须考虑优化 当前选的数字$v$，之前就选择1 ~ v-k 和 v + k ~ M 可以用前缀和优化掉这一层累加的代码

dp[i][j]表示前i位，当前位选数字j的方案数

n, m, k = list(map(int, input().split()))
MOD = 998244353
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
pre_sum = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if i == 1:
            dp[i][j] = 1
        else:
            if k == 0:
                # 差值为0 加上上一次所有的方案数
                dp[i][j] += pre_sum[i - 1][m]
                dp[i][j] %= MOD
            else:
                if j - k > 0:
                    dp[i][j] += pre_sum[i - 1][j - k]
                    dp[i][j] %= MOD
                if j + k <= m:
                    dp[i][j] += pre_sum[i - 1][m] - pre_sum[i - 1][j + k - 1]
                    dp[i][j] %= MOD
    # 计算前缀和
    for j in range(1, m + 1):
        pre_sum[i][j] = (pre_sum[i][j - 1] + dp[i][j]) % MOD

ans = 0
for i in range(1, m + 1):
    ans += dp[n][i]
    ans %= MOD
print(ans)

F. 谎言

题意：选择多个谎言，让谎言总可行度达到m，每个谎言之间可能存在排斥。

思路：用并查集维护哪些谎言是一组的，即一组的谎言只能选择一个，并且维护这一组的可信度最大值。 最后遍历每一组，把最大值加上，先加最大的可信度，再依次加小的，达不到m就输出you will die

代码：

class DSU:
    __slot__ = "fa", "val"

    def __init__(self, n: int):
        self.fa = [i for i in range(n + 1)]
        self.val = [0 for _ in range(n + 1)]

    def find(self, x: int):
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def merge(self, x: int, y: int, v: int):
        if y == b:
            self.val[x] = v
            return
        fx = self.find(x)
        fy = self.find(y)
        self.fa[fx] = self.fa[fy]
        self.val[fy] = max(self.val[fy], self.val[fx], v)


n, m = list(map(int, input().split()))
dsu = DSU(n)
for i in range(1, n + 1):
    a, b = list(map(int, input().split()))
    dsu.merge(i, b, a)
l = []
for i in range(1, n + 1):
    if i == dsu.find(i):
        l.append(dsu.val[i])
l.sort(reverse=True)
cnt = 0
total = 0
for v in l:
    total += v
    cnt += 1
    if total >= m:
        break
print("you will die" if total < m else cnt)

G. 操作整数

题意：给一个数组，可以使任意数加上任意个k，问最大让多少个数相等。

假设a = 6,b = 100,k = 2，这样一定会使a = b 假设a = 8,b = 17,k = 3,这样一定会使a = b 推出结论：a % k == b % k 必定可以得到a = b 因为同余，a和b一定相等

代码：

from collections import Counter

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
c = Counter()
for v in a:
    c[v % k] += 1
ans = 0
for v in c.values():
    ans = max(ans, v)
print(ans)

H. 数圈圈

题意：0 6 9加1，8加2

数字很大用字符串读入。

代码：

x = input()
ans = 0
for c in x:
    if c == '0' or c == '6' or c == '9':
        ans += 1
    if c == '8':
        ans += 2
print(ans)

I. 字符的数量

题意：给一个字符串s，有多个提问，问l，r之间有多少个字母c。

思路：为每一个字母创建一个前缀和，用于快速求区间数量

代码：

s = input()
n = len(s)
pre_sum = [[0 for _ in range(26)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(26):
        pre_sum[i][j] = pre_sum[i - 1][j] + (1 if ord(s[i - 1]) - 97 == j else 0)
for _ in range(int(input())):
    tmp = list(map(str, input().split()))
    l, r = int(tmp[0]), int(tmp[1])
    c = tmp[2]
    v = ord(c) - 97
    print(pre_sum[r][v] - pre_sum[l - 1][v])

J. 运营商

按照题目模拟就行，注意开大变量

代码：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double num = sc.nextDouble();
        int v = sc.nextInt();
        double ans = 0;
        if(v == 1){
            ans = 30 + Math.max(0,(num - 20));
        }else if (v == 2){
            ans = (double) (1.5 * num);
        }else{
            ans = 40 + Math.max(0,(num - 15) * 0.5f);
        }
        System.out.printf("%.2f",ans);
    }
}