codeforces：Codeforces Round #821 (Div. 2) 【思维 + 贪心分贡献的dp】

B. Rule of League

分析

根据题意要么赢x次要么赢y次，有n - 1场比赛
那么必定x和y中有一个是0
然后就是1连赢多少场…next连赢多少场下去，也就是说对于非0的xy设为z，有z | n - 1
特别地，我们要对z = 1特殊处理，不能1234…要2345…

ac code

import sys
input = sys.stdin.readline

def solve():
    n, x, y = list(map(int, input().split()))
    if x * y != 0:
        print(-1)
        return
    if x == 0 and y == 0:
        print(-1)
        return
    z = 0
    if x == 0:
        z = y
    elif y == 0:
        z = x
    if (n - 1) % z != 0:
        print(-1)
        return

    if z == 1:
        ans = []
        for i in range(2, n + 1):
            ans.append(i)
        print(*ans)
        return

    ans = [1]
    pre = 1
    for i in range(2, n):
        if i % z == 1:
            pre = i + 1
            ans.append(pre)
        else:
            ans.append(pre)
    print(*ans)





if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

C. Parity Shuffle Sorting

分析

思维题，只能按照和为奇偶的方式变换
可以发现如果固定某一个数，只能变左边或右边的奇数或者偶数
所以我们让一头一尾一样，这样可以把所有数变成同一个即可

ac code

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    flag = True
    for i in range(1, n):
        if a[i] < a[i - 1]:
            flag = False
            break
    if flag:
        print(0)
        return

    # head and tail
    # all the same
    ans = []
    res = -1
    if a[0] == a[-1]:
        res = a[0]
    elif (a[0] + a[-1]) % 2 == 1:
        ans.append([1, n])
        res = a[0]
    else:
        ans.append([1, n])
        res = a[-1]

    for i in range(2, n):
        if (a[i - 1] + res) % 2 == 0:
            ans.append([i, n])
        else:
            ans.append([1, i])

    print(len(ans))
    for l, r in ans:
        print(l, r)





if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

D2. Zero-One (Hard Version)

分析

x相邻cost，y不相邻cost
对于简单版本而言 x >= y
由于不同的位置数必定是偶数
所以如果大于两个的话，必定可以找到全部不相邻的匹配（分两组即可）
对于两个的情况如果不相邻直接y
如果相邻考虑2 * x和y的最小值即可

对于hard version：
easy version解答了一半
那么对于x 和 y的另一种情况
我们使用dp考虑，由于y是不相邻的，所以每个idx其实的贡献是y / 2
dp = [0, y / 2]
i记录第i个不相同的位置
我们如果知道dp[i] dp[i - 1] 怎么求dp[i + 1]呢
dp[i + 1] = min(dp[i] + y / 2, dp[i - 1] + gap * x)
第一项就是把当前作为单独的
第二项就是把i + 1和i使用gap次x连起来（这里其实是贪心）
gap就是实际第i + 1个位置和第i个位置的间距
这个公式可以保证偶数项一定是整数，奇数项一定包含y / 2
但这个贡献平分的思维确实比较难想
我们的dp思路就是：一个错位的idx要么就是使用临近对换，要么就是非临近对换
对于临近对换，我们要跟最近的（也就是左右邻居）进行对换，这样才是最贪心的
对于非临近对换，我们只需要它的贡献是y / 2即可

ac code

import sys
input = sys.stdin.readline

def solve():
    n, x, y = list(map(int, input().split()))
    a = input().strip()
    b = input().strip()
    diff = 0
    lst = []
    for i in range(n):
        if a[i] != b[i]:
            diff += 1
            lst.append(i)
    if diff % 2 == 1:
        print(-1)
        return
    if diff == 0:
        print(0)
        return

    # l + 1 = r => x
    # other => y

    # case D1:
    if x >= y:
        if diff > 2:
            print((diff // 2) * y)
        else:
            if lst[0] + 1 == lst[1]:
                print(min(2 * y, x))
            else:
                print(y)
    # case D2
    else:
        # dp: choose x or y
        dp = [0, y / 2]
        # dp[2n] must integer, dp[2n+1] must contains y / 2
        for i in range(1, diff):
            gap = lst[i] - lst[i - 1]
            # choose to be y or to be x
            # each y has a contribution of y / 2
            # greedy x use neighbour
            tmp = min(dp[i] + y / 2, dp[i - 1] + gap * x)
            dp.append(tmp)
        print(int(dp[-1]))



if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

总结

这场主要就是思维题
然后最后这个dp有点另类，将贡献均摊之后，分两种情况考虑