前言

alt

题解

数学场，感觉这几道题都挺好的。

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

A. 乐奈吃冰

题型: 签到

有两部分构成

  • 消火配对
  • 未消火（尾巴）

配对数

尾巴为

这样最终为

a, b = list(map(int, input().split()))
 
x = min(a//2, b)
 
print (a + x)

B. 素世喝茶

题型: 阅读理解题

注意: 排除的是第x天，并不是第x天的美味度

n, x = list(map(int, input().split()))
 
arr = list(map(int, input().split()))
 
mz, cnt = 0, 0
for i, v in enumerate(arr):
    if i != x - 1:
        if mz < v:
            mz = v
            cnt = 1
        elif mz == v:
            cnt += 1
             
print (cnt)

C. 爱音开灯

思路: 带限制的因子数求解

数论题，属于思维题范畴

其时间复杂度为

n, x = list(map(int, input().split()))

# 带限制的因子计算
def solve(x, n):
    r = 0
    i = 1
    while i * i <= x:
        if x % i == 0:
            if i <= n:
                r += 1
            if x // i != i and x // i <= n:
                r += 1
        i += 1
    return r % 2 == 1

print ("ON" if solve(x, n) else "OFF")

D. 小灯做题

思路: BFS

其实可以观察到，

  • 快速剪枝

  • mex收敛很快，状态数很小

因此引入BFS，状态为(a, b, c)三元组

t = int(input())

from collections import Counter
from collections import deque

def mex(a, b):
    for i in range(3):
        if i != a and i != b:
            return i
    # unreachable
    return 2

def check(a, b, c, k):
    return a == k or b == k or c == k

def bfs(a, b, c, k):
    if check(a, b, c, k):
        return 0
    st = set()
    deq = deque()
    deq.append((a, b, c, 0))
    st.add((a, b, c))
    
    while len(deq) > 0:
        a1, b1, c1, t1 = deq.popleft()
        
        c2 = mex(a1, b1)
        if (a1, b1, c2) not in st:
            if c2 == k:
                return t1 + 1
            deq.append((a1, b1, c2, t1 + 1))
            st.add((a1, b1, c2))
        
        b2 = mex(a1, c1)
        if (a1, b2, c1) not in st:
            if b2 == k:
                return t1 + 1
            deq.append((a1, b2, c1, t1 + 1))
            st.add((a1, b2, c1))      
        
        a2 = mex(b1, c1)
        if (a2, b1, c1) not in st:
            if a2 == k:
                return t1 + 1
            deq.append((a2, b1, c1, t1 + 1))
            st.add((a2, b1, c1))      
    return -1
    

for _ in range(t):
    a, b, c, k = list(map(int, input().split()))
    if not check(a, b, c, k) and k >= 3:
        print (-1)
    else:
        print (bfs(a, b, c, k))

E. 立希喂猫

思路: 离散化差分 + 离线计算

其实我觉得这题挺难，但是赛时感觉米娜桑做得都很快，T_T.

这样的时间复杂度为，由排序主导

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

# (x, y, 1) 表示差分操作
# 	x为时间点，y为价值
# (x, y, 2) 表示离线查询操作
# 	x为是时间点，y为查询对应的index
ops = []
for i in range(n):
    ops.append((1, arr[i], 1))
    ops.append((brr[i] + 1, -arr[i], 1))
    
q = int(input())
for i in range(q):
    k = int(input())
    ops.append((k, i, 2))
    
ops.sort(key=lambda x: (x[0], x[2]))

res = [0] * q

ans = 0
now = 0
pre = 0
for (x, y, op) in ops:
    if op == 1:
        ans += (x - pre) * now
        now += y
        pre = x        
    elif op == 2:
        tmp = ans + (x - pre + 1) * now
        res[y] = tmp
        
print (*res, sep='\n')

F. 祥子拆团

思路: 数学

其实就两点

  1. 不同的质因子彼此独立
  2. 相同的质因子，隔板法求得C(y + m - 1, m), 注意m很小

所以C(y+m-1, m)的计算，可以利用最原始的公式

# 快速幂
def ksm(b, v):
    r = 1
    while v > 0:
        if v % 2 == 1:
            r = r * b % mod
        v //= 2
        b = b * b % mod
    return r

def comb(n, k, mod):
    # [n-k+1, n]的累乘
    r1 = 1
    for i in range(n - k + 1, n + 1):
        r1 = r1 * i % mod
    # [1, k]的累乘
    r2 = 1
    for i in range(1, k + 1):
        r2 = r2 * i % mod
    # 费马小定律求逆元
    return r1 * ksm(r2, mod - 2)

剩下的工作就是把 x拆分 质因子乘积形态

最后的解为

t = int(input())

from math import sqrt
MX = int(sqrt(10 ** 9)) + 1
mod = 10 ** 9 + 7

vis = [False] * (MX + 1)
primes = []

for i in range(2, MX + 1):
    if not vis[i]:
        primes.append(i)
        for j in range(i * i, MX + 1, i):
            vis[j] = True

def solve(x):
    res = []
    for v in primes:
        if v > x:
            break
        if x % v == 0:
            cnt = 0
            while x % v == 0:
                x //= v
                cnt += 1
            res.append((v, cnt))
        if v * v > x:
            break
    if x > 1:
        res.append((x, 1))
    return res

# 快速幂
def ksm(b, v):
    r = 1
    while v > 0:
        if v % 2 == 1:
            r = r * b % mod
        v //= 2
        b = b * b % mod
    return r

def comb(n, k, mod):
    # [n-k+1, n]的累乘
    r1 = 1
    for i in range(n - k + 1, n + 1):
        r1 = r1 * i % mod
    # [1, k]的累乘
    r2 = 1
    for i in range(1, k + 1):
        r2 = r2 * i % mod
    # 费马小定律求逆元
    return r1 * ksm(r2, mod - 2)

for _ in range(t):
    x, y = list(map(int, input().split()))
    ls = solve(x)
    r = 1
    for (k, v) in ls:
        r = r * comb(y + v - 1, v, mod) % mod
    print (r)

写在最后

alt