题解 | #A~F#

快快乐乐剪羊毛

https://ac.nowcoder.com/acm/contest/81126#questionhttps://ac.nowcoder.com/acm/contest/81126/F

A 获得木头

乘4再除2再乘4

input = lambda: sys.stdin.readline().rstrip("\r\n")
ii = lambda: int(input())

x = ii()
print(x * 4 // 2 * 4)

B 采矿时间到！

遍历每个位置的左右两侧统计拓宽1次就可得到的矿石数量cnt1和必须拓宽两次才能得到的矿石数量cnt2

如果cnt1大于体力值则每消耗一点体力就得到一个矿石；否则先把拓宽一次就能得到的矿石挖了，剩下的体力再去挖拓宽两次才能得到的矿石。当然最后体力可能有剩余，所以要将剩下的体力能挖的矿石与cnt2比较一下。

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
mii = lambda: map(int, input().split())

n, h = mii()
g = [input() for _ in range(5)]
cnt1 = cnt2 = 0
for i in range(n):
    if g[1][i] == '*':
        if g[0][i] == '*': cnt1 += 2
        else: cnt1 += 1
    else:
        if g[0][i] == '*': cnt2 += 1
            
    if g[3][i] == '*':
        if g[4][i] == '*': cnt1 += 2
        else: cnt1 += 1
    else:
        if g[4][i] == '*': cnt2 += 1
if cnt1 >= h: print(h)
else: print(cnt1 + min(cnt2, (h - cnt1) // 2))

C 耕种时间到！

其实是个很简单的模拟题，赛时习惯性地猜了一些乱七八糟的规律才反应过来。。

用字典cnt统计用不同收割次数后变为x的初始小麦种子数量，即若a[i]在被收割t次后等级变为x，则cnt[t] += 1 那么我们只需要遍历刚开始的每个小麦种子，判断它的等级能否变为x以及需要收割几次，这个过程是log的复杂度所以直接模拟上取整的过程即可（x / y上取整 = (x - 1) // y + 1)

如果一个小麦种子需要t次收割将等级变为x，那么变为x时该小麦种子的数量分裂为了2^t个，所以对于每种收割次数t，得到的等级x的小麦种子为cnt[t] * (1 << t)，最后比较一下每种收割次数即可。

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip("\r\n")
ii = lambda: int(input())
lmii = lambda: list(map(int, input().split()))

n = ii()
a = lmii()
x = ii()
cnt = Counter()

for i in range(n):
    if a[i] < x: continue
    else:
        cur = a[i]
        t = 0
        while cur > x:
            cur = (cur - 1) // 3 + 1
            t += 1
        if cur == x:
            cnt[t] += 1

ans = 0
for i in cnt:
    ans = max(ans, cnt[i] * (1 << i))
print(ans)

D 探索的时光

由题意要求的是（+号打不出来了用@代替）

$\sum_{i=1}^{n}{(x - i)^2 * a_i} = \sum_{i=1}^{n}{(x^2 * a_i - 2*x*i*a_i @ i^2 * a_i)}$

$= x^2*\sum_{i=1}^{n}{a_i} - 2 * x*\sum_{i=1}^{n}{i * a_i} @ \sum_{i=1}^{n}{i^2 * a_i}$

将式子中除了x以外的部分求出来，再遍历每一个编号作为x比较大小即可

import sys
INF = float('inf')
input = lambda: sys.stdin.readline().rstrip("\r\n")
ii = lambda: int(input())
lmii = lambda: list(map(int, input().split()))

n = ii()
a = [0] + lmii()
s = sum(a)
b = c = 0
for i in range(1, n + 1):
    b += i * a[i]
    c += i * i * a[i]

ans = INF
for i in range(1, n + 1):
    ans = min(ans, i * i * s - 2 * i * b + c)
print(ans)

E 来硬的

非常典的01背包，可以用二维的 $dp[i][0/1], 0 <= i <= m$ 表示烧炼i单位的铁矿石并且用了或没用（1或0）魔法消耗的时间，然后根据题意转移即可

注意可能当前煤炭能烧炼的铁矿石单位可能大于需要烧炼的铁矿石单位，所以要避免负数出现

import sys
INF = float('inf')
input = lambda: sys.stdin.readline().rstrip("\r\n")
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))

n, m = mii()
a = [lmii() for _ in range(n)]
dp = [[INF] * 2 for _ in range(m + 1)]
dp[0][0] = dp[0][1] = 0
for i in range(n):
    x, y = a[i]
    for j in range(m, 0, -1):
        dp[j][0] = min(dp[j][0], dp[max(j - x, 0)][0] + y)
        dp[j][1] = min(dp[j][1], dp[max(j - x, 0)][1] + y, dp[max(j - 2 * x, 0)][0] + y // 2)
        
print(min(dp[m][0], dp[m][1]))

F 快快乐乐剪羊毛

赛时脑子一团浆糊写了一堆屎山代码，可能比较适合和我一样思维能力不强的选手

首先用每块草的宽度前缀和求一下每块草皮右端点的位置

先根据每只羊的位置确定当前在第id块草皮上，记录该羊的初始价值，然后用字典差分地记录移动的距离对应的总价值变化,la表示上一个位置的价值，la初始化为v[id]

1.羊从id相对草皮向左移动，羊的价值每次变化是在刚到第i块草皮的右端点，即羊移动了w[i] - id，差分地记录总价值改变量v[i] - la，并更新la为v[i]。注意移动到最左侧草皮后还要继续向左移动到没有草的部分即位置为0。

2.羊从id相对草皮向右移动，羊的价值每次变化是在刚到第i块草皮的左端点 + 1(左闭右开区间)，即羊移动了w[i - 1] + 1 - id，差分地记录总价值改变量v[i] - la，并更新la为v[i]。注意移动到最右侧草皮后还要继续向右移动到没有草的部分即位置为w[n] + 1。

最后将对总价值做出改变的向左和向右的移动距离分开，因为之前是以差分的方式记录的总价值变化量，所以现在初始化res为草皮没有移动时的总价值，然后分别向左右两侧对记录下的总价值的变化量求和，每次求和结果放入set中去重，答案为set的长度。

import sys
from bisect import bisect_left, bisect_right
from collections import Counter
INF = float('inf')
input = lambda: sys.stdin.readline().rstrip("\r\n")
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))

n, m = mii()
w = [0] + lmii()
v = [0] + lmii()
X = [0] + lmii()

for i in range(1, n + 1):
    w[i] += w[i - 1]
    
sm = Counter()
for i in range(1, m + 1):
    x = X[i]
    id = bisect_left(w, x)
    sm[0] += v[id]
    la = v[id]
    cur = x
    for i in range(id - 1, -1, -1):
        if i == 0:
            sm[0 - x] += 0 - la
        else:
            sm[w[i] - x] += v[i] - la
            la = v[i]

    la = v[id]
    cur = x
    for i in range(id + 1, n + 2):
        if i == n + 1:
            sm[w[i - 1] + 1 - x] += 0 - la
        else:
            sm[w[i - 1] + 1 - x] += v[i] - la
            la = v[i]
            
idx1 = [i for i in sm if i < 0]
idx2 = [i for i in sm if i > 0]
idx1.sort(reverse = True)
idx2.sort()

res = sm[0]
s = {res}
for i in idx1:
    res += sm[i]
    s.add(res)
res = sm[0]
for i in idx2:
    res += sm[i]
    s.add(res)
print(len(s))

事实上并不需要把左右两个方向分开，可以参考hls代码

hls代码