注：由于2023ICPC杭州站题目会作为Ucup上的一场比赛，所以这份补题将在Ucup 2月10号比完赛后更新（预计补题 M J D G H 五题）暂时已更新 G、H

[TOC]

Problem - G - Codeforces

python实现的怎么改都 了这里给出 的python实现QAQ。

code 1

import sys
from heapq import heappush,heappop
input = sys.stdin.readline
inf = float("inf")
mod = 18446744073709551616

dx = [0,1,0,-1]
dy = [1,0,-1,0]
n,m,k = map(int, input().split())
g = [[] for i in range(n*m+1)]
dic = {}
root = 1
for i in range(1,k+1):
    x,y = map(int, input().split())
    tmp = (x-1)*m + y
    dic[tmp] = i
    if i == 1: root = tmp
ls = [input().strip() for _ in range(n)]
for i in range(n):
    for j in range(m):
        if ls[i][j] == '.':
            for t in range(4):
                x,y = i + dx[t], j + dy[t]
                if x < 0 or x >= n or y < 0 or y >= m or ls[x][y] == '#':continue
                g[i*m+j+1].append(x*m+y+1)
dist = [inf]*(n*m+1)
vis = [0]*(n*m+1)
def dijkstra(r):
    dist[r] = 0
    q = []
    heappush(q, (0,r))
    while q:
        _,x = heappop(q)
        if vis[x]: continue
        vis[x] = 1
        for y in g[x]:
            if y in dic:
                if dist[y] > max(dist[x] + 1, k - dic[y]+1):
                    dist[y] = max(dist[x] + 1, k - dic[y]+1)
                    heappush(q, (dist[y],y))
            else:
                if dist[y] > dist[x] + 1:
                    dist[y] = dist[x] + 1
                    heappush(q, (dist[y], y))

ans = 0
dijkstra(root)
for i in range(1,n+1):
    for j in range(1,m+1):
        idx = (i-1)*m+j
        if dist[idx] != inf:
            ans = (ans + dist[idx]**2) % mod
print(ans)
# print(dist)
# print(dic)
# print(n,m,k)

code 2

import sys
from collections import deque
input = sys.stdin.readline
inf = float("inf")
mod = 18446744073709551616

def bfs(x,y):
    q = deque()
    dq = deque()
    dist[x][y] = 0
    q.append((x,y))
    vis[x][y] = 1
    while q:
        x,y = q.popleft()
        for t in range(4):
            nx,ny = x+dx[t],y+dy[t]
            if nx<0 or nx>=n or ny<0 or ny>=m or ls[nx][ny] == '#' or vis[nx][ny]: continue
            vis[nx][ny] = 1
            if dic[nx][ny]:
                if dist[x][y] + 1 >= k - dic[nx][ny] + 1:
                    dist[nx][ny] = dist[x][y]+1
                    q.append((nx,ny))
                else:
                    dist[nx][ny] = k - dic[nx][ny] + 1
                    dq.append((nx,ny))
            else:
                dist[nx][ny] = dist[x][y]+1
                q.append((nx,ny))
        while dq and dist[dq[0][0]][dq[0][1]] == dist[x][y]+1:
            q.append((dq[0][0],dq[0][1]))
            dq.popleft()

dx = [0,1,0,-1]
dy = [1,0,-1,0]
n,m,k = map(int, input().split())
dist = [[inf]*m for _ in range(n)]
vis = [[0]*m for _ in range(n)]
dic = [[0]*m for _ in range(n)]
for i in range(1,k+1):
    x,y = map(int, input().split())
    dic[x-1][y-1] = i
    if i == 1: rx,ry = x-1,y-1

ls = [input().strip() for _ in range(n)]
bfs(rx,ry)
ans = 0
for i in range(n):
    for j in range(m):
        if dist[i][j] != inf:
            ans = (ans + dist[i][j]*dist[i][j]) % mod
print(ans)

Problem - H - Codeforces

题目分析

​ 要求的就是每个事件发生的概率。事件的依赖关系构成一棵基环树。 如果 ，则事件 必然发生。若 ，则事件 必然不发 生。否则，事件 发生当且仅当事件 在事件 之前发生。 则对这样子的事件而言，其发生的概率为 ，其中 为基环树上 到最近的，必定发生的祖先事件的概率。如果离 最近的是一个必定不发生的事件，则事件 发生的概率为 . 使用任何 或者 的算法处理出 即可。

​ 上面是官方题解给出的，那么为什么这么算呢， 其实就是 ，即假如 必定发生， 且 依赖 且 依赖 （更具分析C必须在B前发生，B才能发生，B必须在A前发生，A才能发生），对于A，如果其发生，那么在最终发生的时间排列中一定存在形如的子序列，所以我们在算概率时要除以 的全排列。

python ac code

# Created by iN_siDious.
# Copyright © 2024 iN_siDious. All rights reserved.
import sys,os
import random
from math import inf,ceil,sqrt
from string import ascii_lowercase,ascii_uppercase
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import heappushpop, heapify, heappop, heappush
from bisect import bisect_left,bisect_right
from types import GeneratorType
from random import randint
RANDOM = randint(1, 10 ** 10)
class op(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(op, self).__hash__() ^ RANDOM
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
input = lambda: sys.stdin.buffer.readline().decode().strip()
out = sys.stdout.write
def S():
    return input()
def I():
    return int(input())
def MI():
    return map(int, input().split())
def MF():
    return map(float, input().split())
def MS():
    return input().split()
def LS():
    return list(input().split())
def LI():
    return list(map(int,input().split()))
def print1(x):
    return out(str(x)+"\n")
def print2(x,y):
    return out(str(x)+" "+str(y)+"\n")
def print3(x,y,z):
    return out(str(x)+" "+str(y)+" "+str(z)+"\n")
def Query(i,j):
    print3('?', i, j)
    sys.stdout.flush()
    qi=I()
    return qi
def print_arr(arr):
    out(' '.join(map(str,arr)))
    out(str("\n"))

# ----------------------------- # ----------------------------- #

mod = 10**9 + 7
N = 5*(10**5)+1
inv = lambda x:pow(x,mod-2,mod)
jc = [1]*N
jc[0] = 0
for i in range(2,N):
    jc[i] = i*jc[i-1] % mod

def solve():
    n = I()
    a = [0]+LI()
    b = [0]+LI()
    w = [0]+LI()
    g = [[] for _ in range(n+1)]
    li = [0]*(n+1)
    deg = [0]*(n+1)
    for i in range(1,n+1):
        if a[i] >= a[b[i]] and a[i] < a[b[i]] + w[b[i]]:
            g[b[i]].append(i)
            deg[i] += 1
        if a[i] < a[b[i]]:
            li[i] = 1
    q = deque()
    for i in range(1,n+1):
        if deg[i] == 0: q.append(i)
    while q:
        x = q.popleft()
        if li[x] == 0: continue
        for y in g[x]:
            li[y] += li[x]+1
            deg[y] -= 1
            if deg[y] == 0: q.append(y)

    for i in range(1,n+1):
        a[i] = (a[i] + w[i]*inv(jc[li[i]])) % mod
    print_arr(a[1:])

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