牛客周赛 Round 50 解题报告 | 珂学家

前言

题解

数学场，对数学头痛, T_T.

A. 小红的最小最大

题型: 签到

a, b, x = list(map(int, input().split()))

if min(a, b) + x > max(a, b):
    print ("YES")
else:
    print ("NO")

B. 小红的四则运算（easy）

思路: 贪心

其实就3种情况

• 三数之和
• 两数之和 * 最大数
• 三数相乘

arr = list(map(int, input().split()))

arr.sort()
r1 = arr[0] + arr[1] + arr[2]
r2 = (arr[0] + arr[1]) * arr[2]
r3 = arr[0] * arr[1] * arr[2]

print (max(r1, r2, r3))

C. 小红的四则运算（hard）

因为只有3个数，可以枚举操作顺序

• 第一个和第二个数先操作，然后和第三个操作
• 第二个和第三个数先操作，然后和第一个操作

a, b, c = list(map(int, input().split()))

v1 = max(a+b, a * b)
r1 = max(v1 + c, v1 * c)

v2 = max(b + c, b * c)
r2 = max(a + v2, a * v2)

print (max(r1, r2))

D. 小红的因式分解

思路: 解方程

其实就是一元二次解方程

先要判定是否存在解

需要保证

$$b^2-4ac\ge 0$$

难点在于转化为整数形态

可以从整除关系出发，即每个解$x_1,x_2$的最简分母出发$d_1,d_2$，通过gcd演化得到

需要保证 $d1\ast d2|a$, 即d1*d2被a整除，就有整数解

t = int(input())

from math import gcd, sqrt

def solve():
    a, b, c = list(map(int, input().split()))
    # c = b1 * b2
    # b = a1 * b2 + a2 * b1
    # a = a1 * a2
    
    # -b +- sqrt(b^2 - 4ac)  / 2a
    if a == 0:
        return "%d %d %d %d" % (b, c, 0, 1)
    
    if b * b - 4 * a * c < 0:
        return "NO"
    z = b * b - 4 * a * c
    zr = int(sqrt(z))
    if zr * zr != z:
        return "NO"
    
    g1 = gcd(abs(-b + zr), abs(2 * a))
    g2 = gcd(abs(-b - zr), abs(2 * a))
    
    l1 = abs(2 * a) // g1
    l2 = abs(2 * a) // g2
    if abs(a) % (l1 * l2) != 0:
        return ("NO")
    
    x1 = (-b + zr) * l1 // (2 * a)
    x2 = (-b - zr) * l2 // (2 * a)
    
    l3 = a // (l1 * l2)
    
    return "%d %d %d %d" % (l1 * l3, -x1 * l3, l2, -x2)
    
for _ in range(t):
    print (solve())

E. 小红的树上移动

思路: 期望DP

期望题，核心就一句话

$$概率正推，期望倒推$$

期望公式:

$$e[u]=1/|S(h+1)|\ast (\sum _{v\in S_{h+1}}e[v])+1$$

$$u为h层节点$$

$$v为h+1层节点$$

$$|S(h+1)|为h+1层的节点个数$$

其本质是自底向上的DP

但是这个很特殊，它是分层的

所以这边采用分层BFS，然后逆序来实现

n = int(input())
g = [[] for _ in range(n)]

for _ in range(n - 1):
    u, v = list(map(int, input().split()))
    u, v = u - 1, v - 1
    g[u].append(v)
    g[v].append(u)
    

from collections import deque
from math import inf

e = [0] * n
h = [inf] * n
cs = [0] * n  # 子节点个数

layers = []

deq = deque()
h[0] = 0
deq.append(0)

# 分层bfs
while len(deq) > 0:
    tmp = []
    sz = len(deq)
    for i in range(sz):
        u = deq.popleft()
        for v in g[u]:
            if h[v] > h[u] + 1:
                h[v] = h[u] + 1
                deq.append(v)
                cs[u] += 1
        tmp.append(u)
    layers.append(tmp)
    
# 逆序求得期望
mod = 998244353
preE, preN = 0, 0
depth = len(layers)
for i in range(depth - 1, -1, -1):
    l = layers[i]
    for v in l:
        if cs[v] == 0:
            # 叶子节点为终结点，期望为0
            e[v] = 0
        else:
            # 非叶子节点，其期望由下一层的节点决定 
            e[v] = (preE + preN) * pow(preN, mod - 2, mod) % mod
    preE = sum([e[v] for v in l]) % mod
    preN = len(l)
    
print (e[0])

F. 小红的网格

后期补上

直觉感觉，需要枚举平方数，以及可行解边长的GCD有一定关系

t = int(input())

from math import gcd
def solve(x):
    i = 0
    g = 0
    d = 2
    while i * i <= x:
        y = x - i * i
        r = int(y ** 0.5)
        if r * r == y:
            g = gcd(g, i)
            g = gcd(g, r)
            if (i // g + r // g) % 2 == 1:
                d = 1
        i += 1
    if g == 0:
        return "inf"
    else:
        return d * g * g
        
for _ in range(t):
    x = int(input())
    print (solve(x))

写在最后