Educational Codeforces Round 161 (Rated for Div. 2)

注：D、E题有详细题目分析，A、B、C只提供python代码

Problem - A - Codeforces

import sys
input = sys.stdin.readline
inf = float("inf")

def solve():
    n = int(input())
    a = input().strip()
    b = input().strip()
    c = input().strip()

    for i in range(n):
        x,y,z = a[i],b[i],c[i]
        if z >= 'a' and z <= 'z':
            if x >= 'a' and x <= 'z' and x == y and x != z:
                print("YES")
                return
            if x.lower() != z and y.lower() != z:
                print("YES")
                return
        else:
            if a != z.lower() and b != z.lower():
                print("YES")
                return
    print("NO")

for _ in range(int(input())):
    solve()

Problem - B - Codeforces

import sys
input = sys.stdin.readline
inf = float("inf")


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if n < 3:
        print(0)
        return
    ls = [0]*(n+1)
    for x in a:
        ls[x] += 1
    ans = 0
    cnt = 0
    for i in range(n+1):
        if ls[i] >= 3:
            ans += (ls[i]*(ls[i]-1)*(ls[i]-2))//6
            ans += ls[i]*(ls[i]-1)//2 * cnt
        elif ls[i] >= 2:
            ans += cnt
        cnt += ls[i]
    print(ans)

for _ in range(int(input())):
    solve()

Problem - C - Codeforces

import sys
input = sys.stdin.readline
inf = float("inf")

def solve():
    n = int(input())
    a = [0] + list(map(int, input().split()))
    ls = [0]*(n+1)
    ls[2] = 1
    ls1 = [0]*(n+1)
    ls1[n-1] = 1
    for i in range(3,n+1):
        if a[i] - a[i-1] < a[i-1] - a[i-2]: ls[i] = 1 + ls[i-1]
        else: ls[i] = ls[i-1] + a[i] - a[i-1]
    for i in range(n-1,0,-1):
        if a[i] - a[i-1] < a[i+1] - a[i]: ls1[i-1] = ls1[i] + 1
        else: ls1[i-1] = ls1[i] + a[i] - a[i-1]
    # print(ls)
    # print(ls1)
    m = int(input())
    for i in range(m):
        x,y = map(int, input().split())
        if x < y:
            print(ls[y] - ls[x])
        else:
            print(ls1[y] - ls1[x])

for _ in range(int(input())):
    solve()

Problem - D - Codeforces

题目分析

• 题意其实是很容易理解的，我们首先得知道，当一轮攻击结束后，在该轮的死亡数为0的话，那么我们就可以确定之后剩下的每轮攻击死亡数都为0.
• 进一步分析我们发现我们需要记录每轮死亡的怪物的编号，因为我们需要改变已死亡编号邻居的左右邻居编号。而这种操作我们用数组模拟的话，时间复杂度过高，中间删除数据是的。
• 意识到双链表中间删除结点是的，所以我们可以用数组模拟双链表来求解。

python code

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    d = list(map(int, input().split()))
    a.append(0)
    left = [i-1 for i in range(n)]
    right = [i+1 for i in range(n)]
    die,att = [],[0]*n
    if a[1] > d[0]: die.append(0)
    att[0] = a[1]
    for i in range(1,n-1):
        att[i] = a[left[i]] + a[right[i]]
        if att[i] > d[i]:
            die.append(i)
    if a[n-2] > d[n-1]: die.append(n-1)
    att[n-1] = a[n-2]
    dead = set(die)
    ans = [len(die)]
    for i in range(n-1):
        i_die, change = [], set()
        for j in die:
            if left[j] >= 0:
                right[left[j]] = right[j]
                change.add(left[j])
            if right[j] < n:
                left[right[j]] = left[j]
                change.add(right[j])
            if 0 <= left[j] < n:
                att[left[j]] += a[right[j]] - a[j]
            if 0 <= right[j] < n:
                att[right[j]] += a[left[j]] - a[j]
        for j in change:
            if j not in dead and att[j] > d[j]:
                i_die.append(j)
                dead.add(j)
        die = i_die
        ans.append(len(die))
    print(*ans)

for _ in range(int(input())):
    solve()

Problem - E - Codeforces

题目分析

这是一道构造题，要我们构造出一个长度不大于200的数组，使得该数组的上升子序列的数量等于x， 。

• 经过分析我们可以知道，如果在我们构造的数组的末尾加一个大于最大的值的值(例如)，就能使上升子序列个数变为原来的两倍，而加上一个最小的值，上升子序列个数只会增加1.
• 既然这样，我们就可以考虑递归实现这么一个解，维护两个变量max和min即可。
• 关于如何想到这么一种构造方法 ，构造一个数组，满足个数的条件，应该是有一种递推的关系的，在这题中加1的方法个人感觉其实很容易想到，我一开始想的是数组如果都是上升子序列的话，那么总共就有种，这显然对解没什么帮助，后来想着已知这么多种，往后加数怎么变化就想到了。
• 关于答案长度不超过200的证明：如果我们从长度为1开始递推的话，我们发现奇数种肯定有得到，而偶数种，我们用得到，所以每两次规模至少变为原来的两倍，而.

python code

import sys
input = sys.stdin.readline

def solve():
    def dfs(x):
        nonlocal mn,mx
        if x == 2:
            return [0]
        if x & 1:
            ans = dfs(x-1)
            ans.append(mn)
            mn -= 1
            return ans
        else:
            ans = dfs(x//2)
            ans.append(mx)
            mx += 1
            return ans

    x = int(input())
    mx,mn = 1,-1
    ans = dfs(x)
    print(len(ans))
    print(*ans)

for i in range(int(input())):
    solve()