COCR Cup 2025 python
2025-09-07 10:10:50
发布于：北京
61阅读
0回复
0点赞
@MuktorFM，过来看看题解
A. Easy
n = float(input())
print("{0:.2f}".format(n * 2))
B. Word
n = int(input())
wd = ""
jtb = ""
gb = 0
xz_l = -1
xz_r = -1
for _ in range(n):
op = input().strip()
if op == "I":
s = input().strip()
if xz_l != -1 and xz_l <= xz_r and xz_r < len(wd):
# 先删除选中部分
wd = wd[:xz_l] + wd[xz_r+1:]
# 插入新内容
wd = wd[:xz_l] + s + wd[xz_l:]
gb = xz_l + len(s)
else:
# 在光标位置插入
wd = wd[:gb] + s + wd[gb:]
gb += len(s)
xz_l = xz_r = -1
elif op == "A":
if not wd:
xz_l = xz_r = -1
else:
xz_l = 0
xz_r = len(wd) - 1
gb = len(wd)
elif op == "C":
if xz_l != -1 and xz_l <= xz_r and xz_r < len(wd):
jtb = wd[xz_l:xz_r+1]
xz_l = xz_r = -1
elif op == "V":
if xz_l != -1 and xz_l <= xz_r and xz_r < len(wd):
# 先删除选中部分
wd = wd[:xz_l] + wd[xz_r+1:]
# 粘贴粘贴内容
wd = wd[:xz_l] + jtb + wd[xz_l:]
gb = xz_l + len(jtb)
else:
# 在光标位置粘贴
wd = wd[:gb] + jtb + wd[gb:]
gb += len(jtb)
xz_l = xz_r = -1
elif op == "P":
i = int(input())
gb = min(i, len(wd))
xz_l = xz_r = -1
elif op == "TP":
i = int(input())
if not wd:
xz_l = xz_r = -1
gb = 0
else:
i = max(1, min(i, len(wd)))
xz_l = xz_r = i - 1
gb = i
print(wd)
C. Force
import math
n = int(input())
xx = 0.0
yy = 0.0
for _ in range(n):
x, f = map(float, input().split())
# 将角度转换为弧度
k = math.radians(x)
# 累加向量分量
xx += f * math.cos(k)
yy += f * math.sin(k)
# 处理接近零的情况
if abs(xx) < 1e-12 and abs(yy) < 1e-12:
print("0 0")
else:
# 计算模长
mag = math.sqrt(xx **2 + yy** 2)
# 计算角度（弧度转度）
t = math.degrees(math.atan2(yy, xx))
# 确保角度在0-360度范围内
if t < 0:
t += 360.0
# 输出向下取整的结果
print(f"{int(math.floor(mag))} {int(math.floor(t))}")
D. Stone
T = int(input())
for _ in range(T):
n = int(input())
ans = 0
for _ in range(n):
t = int(input())
ans ^= t
if ans != 0:
print("Yes")
else:
print("No 1")
E. Farm
import sys
sys.setrecursionlimit(1 << 25) # 提高递归限制，适应深层树结构
class Node:
def __init__(self, p):
# 初始化节点属性
self.x = p[0]
self.y = p[1]
self.t = p[2]
self.minx = self.maxx = self.x
self.miny = self.maxy = self.y
self.mint = self.maxt = self.t
self.sz = 1 # 子树大小
self.vis = False # 是否被访问/处理
self.l = None # 左子树
self.r = None # 右子树
def change(self):
# 更新节点的范围信息
if self.vis:
# 已访问节点的范围设置为无效
self.minx = self.miny = self.mint = float('inf')
self.maxx = self.maxy = self.maxt = -float('inf')
self.sz = 0
else:
# 未访问节点初始范围为自身
self.minx = self.maxx = self.x
self.miny = self.maxy = self.y
self.mint = self.maxt = self.t
self.sz = 1
# 合并左子树信息
if self.l and self.l.sz > 0:
self.minx = min(self.minx, self.l.minx)
self.maxx = max(self.maxx, self.l.maxx)
self.miny = min(self.miny, self.l.miny)
self.maxy = max(self.maxy, self.l.maxy)
self.mint = min(self.mint, self.l.mint)
self.maxt = max(self.maxt, self.l.maxt)
self.sz += self.l.sz
# 合并右子树信息
if self.r and self.r.sz > 0:
self.minx = min(self.minx, self.r.minx)
self.maxx = max(self.maxx, self.r.maxx)
self.miny = min(self.miny, self.r.miny)
self.maxy = max(self.maxy, self.r.maxy)
self.mint = min(self.mint, self.r.mint)
self.maxt = max(self.maxt, self.r.maxt)
self.sz += self.r.sz
def upd(nd, p, dep=0):
# 插入新点并更新树结构
if nd is None:
return Node(p)
# 根据深度交替维度分割（偶数深度按x，奇数按y）
if dep % 2 == 0:
if p[0] < nd.x:
nd.l = upd(nd.l, p, dep + 1)
else:
nd.r = upd(nd.r, p, dep + 1)
else:
if p[1] < nd.y:
nd.l = upd(nd.l, p, dep + 1)
else:
nd.r = upd(nd.r, p, dep + 1)
# 更新节点信息
nd.change()
return nd
def query(nd, x1, x2, y1, y2, cur):
# 查询范围内符合条件的点并标记
if nd is None or nd.sz == 0:
return 0
# 剪枝：节点范围完全不匹配查询范围
if (nd.maxx < x1 or nd.minx > x2 or
nd.maxy < y1 or nd.miny > y2 or
nd.mint > cur):
return 0
cnt = 0
# 检查当前节点是否符合条件
if not nd.vis:
if (x1 <= nd.x <= x2 and
y1 <= nd.y <= y2 and
nd.t <= cur):
cnt += 1
nd.vis = True # 标记为已处理
# 递归查询左右子树
cnt += query(nd.l, x1, x2, y1, y2, cur)
cnt += query(nd.r, x1, x2, y1, y2, cur)
# 更新节点信息
nd.change()
return cnt
def main():
# 高效读取输入
import sys
input = sys.stdin.read().split()
ptr = 0
n = int(input[ptr])
ptr += 1
m = int(input[ptr])
ptr += 1
q = int(input[ptr])
ptr += 1
root = None
for i in range(1, q + 1):
op = int(input[ptr])
ptr += 1
if op == 1:
# 插入操作
x = int(input[ptr])
ptr += 1
y = int(input[ptr])
ptr += 1
k = int(input[ptr])
ptr += 1
root = upd(root, (x, y, i + k))
else:
# 查询操作
x1 = int(input[ptr])
ptr += 1
y1 = int(input[ptr])
ptr += 1
x2 = int(input[ptr])
ptr += 1
y2 = int(input[ptr])
ptr += 1
res = query(root, x1, x2, y1, y2, i)
print(res)
if __name__ == "__main__":
main()
F. Run
import sys
import math
def exgcd(a, b):
"""扩展欧几里得算法，返回(x, y)使得ax + by = gcd(a, b)"""
if b == 0:
return (1, 0)
x, y = exgcd(b, a % b)
return (y, x - (a // b) * y)
def gcd(a, b):
"""计算最大公约数"""
if b == 0:
return a
return gcd(b, a % b)
def inv(a, p):
"""求a在模p下的逆元，p可以不是质数"""
x, y = exgcd(a, p)
return (x % p + p) % p # 确保结果为正数
def lcm(a, b):
"""计算最小公倍数"""
return a // gcd(a, b) * b
def mabs(x):
"""绝对值"""
return x if x > 0 else -x
def fast_mul(a, b, p):
"""模乘法：(a * b) % p，防止溢出（Python中无需担心溢出，但保持原逻辑）"""
t = 0
a %= p
b %= p
while b:
if b & 1:
t = (t + a) % p
b >>= 1
a = (a + a) % p
return t
def fast_pow(a, b, p):
"""快速幂：(a ^ b) % p"""
t = 1
a %= p
while b:
if b & 1:
t = (t * a) % p
b >>= 1
a = (a * a) % p
return t
def read():
"""读取整数，模拟C++的快速输入"""
data = sys.stdin.read().split()
ptr = 0
def inner():
nonlocal ptr
res = int(data[ptr])
ptr += 1
return res
return inner
def F(n, P, PK):
"""计算n!中除去所有因子P后的结果 mod PK"""
if n == 0:
return 1
# 计算循环部分：1..PK中与P互质的数的乘积
rou = 1
for i in range(1, PK + 1):
if i % P != 0:
rou = rou * i % PK
# 计算循环次数的幂
rou = fast_pow(rou, n // PK, PK)
# 计算剩余部分
rem = 1
for i in range(PK * (n // PK), n + 1):
if i % P != 0:
rem = rem * (i % PK) % PK
# 递归处理n/P
return F(n // P, P, PK) * rou % PK * rem % PK
def G(n, P):
"""计算n!中包含的质因子P的个数"""
if n < P:
return 0
return G(n // P, P) + (n // P)
def C_PK(n, m, P, PK):
"""计算C(n, m) mod PK，其中PK = P^k"""
# 计算分子分母的阶乘部分（去除P因子后）
fz = F(n, P, PK)
fm1 = inv(F(m, P, PK), PK)
fm2 = inv(F(n - m, P, PK), PK)
# 计算P的幂次
power = G(n, P) - G(m, P) - G(n - m, P)
mi = fast_pow(P, power, PK)
# 组合结果
return fz * fm1 % PK * fm2 % PK * mi % PK
def ex_lucas(n, m, p):
"""扩展Lucas定理计算C(n, m) mod p"""
if m < 0 or m > n:
return 0
ljc = p
tot = 0
A = [] # 存储质因子的幂 PK
B = [] # 存储对应模PK的结果
# 分解p为质因子幂
tmp = 2
while tmp * tmp <= ljc:
if ljc % tmp == 0:
PK = 1
while ljc % tmp == 0:
PK *= tmp
ljc //= tmp
A.append(PK)
B.append(C_PK(n, m, tmp, PK))
tot += 1
tmp += 1
# 处理剩余的质因子
if ljc != 1:
A.append(ljc)
B.append(C_PK(n, m, ljc, ljc))
tot += 1
# 中国剩余定理合并结果
ans = 0
for i in range(tot):
PK = A[i]
rem = B[i]
M = p // PK
T = inv(M, PK)
ans = (ans + rem * M % p * T % p) % p
return ans
def main():
input_reader = read()
n = input_reader()
p = input_reader()
print(ex_lucas(2 * n, n, p))
if __name__ == "__main__":
main()
G. Zombie
import sys
def solve(x):
"""计算数字x各位中的最大值"""
if x == 0:
return 0
maxx = 0
while x:
maxx = max(maxx, x % 10)
x = x // 10
return maxx
def main():
input = sys.stdin.read().split()
ptr = 0
_ = int(input[ptr])
ptr += 1
for _ in range(_):
a = int(input[ptr])
ptr += 1
m = int(input[ptr])
ptr += 1
rem = int(input[ptr])
ptr += 1
rem -= 1 # 转换为0基
mm = m
# 初始化num数组(1-based)
num = [0] * 20 # num[1]到num[19]
for i in range(1, 20):
num[i] = mm % 10
mm = mm // 10
# 初始化pw数组
pw = [1] * 20
for i in range(1, 20):
pw[i] = pw[i-1] * 10
# 初始化dp1和dp2 (三维数组: [k][a][b])
# dp1[k][a][b]: 状态转移后的数字
# dp2[k][a][b]: 状态转移的步数
dp1 = [[[0]*10 for _ in range(10)] for __ in range(20)]
dp2 = [[[0]*10 for _ in range(10)] for __ in range(20)]
for a_val in range(10):
for b_val in range(10):
if a_val == 0 and b_val == 0:
dp2[1][a_val][b_val] = float('inf')
continue
# 计算dp1[1][a_val][b_val]和dp2[1][a_val][b_val]
current = b_val
steps = 0
while current <= 9:
current += max(a_val, current)
steps += 1
current -= 10
dp1[1][a_val][b_val] = current
dp2[1][a_val][b_val] = steps
# 填充dp1和dp2的更高维度
for k in range(2, 20):
for a_val in range(10):
for b_val in range(10):
if a_val == 0 and b_val == 0:
dp2[k][a_val][b_val] = float('inf')
continue
ft = b_val
gt = 0
for i in range(10):
t = ft
ft = dp1[k-1][max(a_val, i)][t]
gt = min(gt + dp2[k-1][max(a_val, i)][t], float('inf'))
dp1[k][a_val][b_val] = ft
dp2[k][a_val][b_val] = gt
# 初始化fr和to数组
fr = [[0]*10 for _ in range(70)]
to = [[0]*10 for _ in range(70)]
for s in range(10):
if s == 0:
fr[0][s] = 0
to[0][s] = 1
continue
ff = s
gg = 0
maxx_val = 0
b = 0
# 处理19到2的位
for i in range(19, 1, -1):
for j in range(num[i]):
t = ff
ff = dp1[i-1][max(maxx_val, j)][t]
gg = min(gg + dp2[i-1][max(maxx_val, j)][t], float('inf'))
b = b * 10 + num[i]
maxx_val = max(maxx_val, num[i])
# 处理剩余部分
ff = b * 10 + ff
while ff < m:
ff += solve(ff)
gg += 1
fr[0][s] = ff % m
to[0][s] = gg
# 填充fr和to的更高维度
for i in range(1, 70):
for s in range(10):
t = fr[i-1][s]
fr[i][s] = fr[i-1][t]
to[i][s] = min(to[i-1][s] + to[i-1][t], float('inf'))
# 处理rem的主循环
while rem >= 100:
if a <= 9 and to[0][a] <= rem:
k = 0
while k <= 63 and (k + 1 < 70) and to[k+1][a] <= rem:
k += 1
rem -= to[k][a]
a = fr[k][a]
continue
if m - a <= 100:
a = (a + solve(a)) % m
rem -= 1
continue
# 分解a到num数组
mm = a
for i in range(1, 20):
num[i] = mm % 10
mm = mm // 10
# 计算maxx数组
maxx_arr = [0] * 20
for i in range(19, 0, -1):
if i != 19:
maxx_arr[i] = maxx_arr[i+1]
else:
maxx_arr[i] = 0
maxx_arr[i] = max(maxx_arr[i], num[i])
# 寻找k值
k = 1
t = a % 10
while (k + 1 < 20 and not num[k+1]) and \
((a // pw[k+1] + 1) * pw[k+1] + dp1[k+1][maxx_arr[k+2]][t] < m) and \
(rem >= dp2[k+1][maxx_arr[k+2]][t]):
k += 1
rem -= dp2[k][maxx_arr[k+1]][t]
num[1] = dp1[k][maxx_arr[k+1]][t]
num[k+1] += 1
# 重新计算a
a = 0
for i in range(19, 0, -1):
a = a * 10 + num[i]
# 处理剩余的rem
for _ in range(rem):
a = (a + solve(a)) % m + 1
print(a)
if __name__ == "__main__":
main()
H. Square
import bisect
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
n = int(data[idx])
idx += 1
rrx = [0] * (n + 1)
rry = [0] * (n + 1)
rrc = [0] * (n + 1)
mxx = 0
mxy = 0
for i in range(1, n + 1):
rrx[i] = int(data[idx])
idx += 1
rry[i] = int(data[idx])
idx += 1
rrc[i] = int(data[idx]) - 1 # 转换为0-based索引
idx += 1
mxx = max(mxx, rrx[i])
mxy = max(mxy, rry[i])
ans = float('inf')
x = [0] * (n + 1)
y = [0] * (n + 1)
rc = [0] * (n + 1)
rx = [0] * (n + 1)
ry = [0] * (n + 1)
px = [0] * (n + 1)
dx = [0] * (n + 1)
dy = [0] * (n + 1)
c = [0] * (n + 1)
tx, ty = 0, 0
# 树状数组实现
class SZMin:
def __init__(self, size):
self.size = size
self.c = [float('inf')] * (self.size + 2) # 1-based
def clear(self):
self.c = [float('inf')] * (self.size + 2)
def add(self, x, y_val):
while x <= self.size:
if y_val < self.c[x]:
self.c[x] = y_val
else:
break # 无需继续更新
x += x & -x
def ask(self, x):
res = float('inf')
while x > 0:
if self.c[x] < res:
res = self.c[x]
x -= x & -x
return res
# 线段树实现
class SegmentTree:
def __init__(self, size):
self.n = size
self.size_tree = 1
while self.size_tree < self.n:
self.size_tree <<= 1
self.val = [float('inf')] * (2 * self.size_tree)
self.t1 = [float('inf')] * (2 * self.size_tree) # 延迟标记1
self.t2 = [float('inf')] * (2 * self.size_tree) # 延迟标记2
def push1(self, o, x):
if x < self.t1[o]:
self.t1[o] = x
def push2(self, o, x):
if self.t1[o] + x < self.val[o]:
self.val[o] = self.t1[o] + x
if x < self.t2[o]:
self.t2[o] = x
def pushdown(self, o, l, r):
mid = (l + r) // 2
left = o << 1
right_node = left | 1
# 传递t2标记
if self.t2[o] != float('inf'):
self.push2(left, self.t2[o])
self.push2(right_node, self.t2[o])
self.t2[o] = float('inf')
# 传递t1标记
if self.t1[o] != float('inf'):
self.push1(left, self.t1[o])
self.push1(right_node, self.t1[o])
self.t1[o] = float('inf')
def update1(self, o, l, r, ul, ur, val):
if ul <= l and r <= ur:
self.push1(o, val)
return
self.pushdown(o, l, r)
mid = (l + r) // 2
if ul <= mid:
self.update1(o << 1, l, mid, ul, ur, val)
if ur > mid:
self.update1(o << 1 | 1, mid + 1, r, ul, ur, val)
def update2(self, o, l, r, ul, ur, val):
if ul <= l and r <= ur:
self.push2(o, val)
return
self.pushdown(o, l, r)
mid = (l + r) // 2
if ul <= mid:
self.update2(o << 1, l, mid, ul, ur, val)
if ur > mid:
self.update2(o << 1 | 1, mid + 1, r, ul, ur, val)
def query(self, o, l, r, qx):
if l == r:
return self.val[o]
self.pushdown(o, l, r)
mid = (l + r) // 2
if qx <= mid:
return min(self.val[o], self.query(o << 1, l, mid, qx))
else:
return min(self.val[o], self.query(o << 1 | 1, mid + 1, r, qx))
def s1():
nonlocal ans
o = SZMin(ty)
p = SZMin(ty)
for t in range(1, n + 1):
i = px[t]
if c[i] == 0:
o.add(dy[i], -x[i] - y[i])
elif c[i] == 1:
val = o.ask(dy[i])
if val != float('inf'):
p.add(dy[i], val)
elif c[i] == 2:
val = p.ask(dy[i])
if val != float('inf'):
ans = min(ans, x[i] + y[i] + val)
def s2():
nonlocal ans
if ty == 0:
return
st = SegmentTree(ty)
for t in range(1, n + 1):
i = px[t]
if c[i] == 0:
st.update1(1, 1, st.size_tree, dy[i], ty, -x[i] - y[i])
elif c[i] == 1:
st.update2(1, 1, st.size_tree, 1, dy[i], y[i])
elif c[i] == 2:
val = st.query(1, 1, st.size_tree, dy[i])
if val != float('inf'):
ans = min(ans, val + x[i])
def solve():
s1()
s2()
from itertools import permutations
def ss(tpx, tpy):
nonlocal tx, ty, ans
# 坐标转换
for i in range(1, n + 1):
if tpx == 1:
x[i] = rrx[i]
else:
x[i] = mxx - rrx[i] + 1
if tpy == 1:
y[i] = rry[i]
else:
y[i] = mxy - rry[i] + 1
rc[i] = rrc[i]
rx[i] = x[i]
ry[i] = y[i]
px[i] = i
# 离散化处理
rx_sorted = sorted(rx[1:n+1])
ry_sorted = sorted(ry[1:n+1])
tx = len(rx_sorted)
ty = len(ry_sorted)
# 去重
rx_unique = []
prev = None
for num in rx_sorted:
if num != prev:
rx_unique.append(num)
prev = num
tx = len(rx_unique)
ry_unique = []
prev = None
for num in ry_sorted:
if num != prev:
ry_unique.append(num)
prev = num
ty = len(ry_unique)
# 计算dx和dy
for i in range(1, n + 1):
dx[i] = bisect.bisect_left(rx_unique, x[i]) + 1 # 1-based
dy[i] = bisect.bisect_left(ry_unique, y[i]) + 1 # 1-based
# 排序px
def cmpx(i):
if x[i] != x[px[i+1]]:
return x[i]
return y[i]
px[1:n+1] = sorted(range(1, n+1), key=lambda i: (x[i], y[i]))
# 尝试所有排列
for perm in permutations([0, 1, 2]):
for i in range(1, n + 1):
c[i] = perm[rc[i]]
solve()
# 四种变换情况
ss(1, 1)
ss(1, 0)
ss(0, 1)
ss(0, 0)
print(ans * 2)
if __name__ == "__main__":
main()
总体来说：python写代码真的是太累了，太长了！
作者只得了342分，第18，还可以吧？
有帮助，赞一个