1k 1 分钟

# [题解] 2023 杭电多校 Many Topological Problems [树计数] # 题目大意 # Topological Problem 给定一个nnn 个节点的有标号有根树和整数kkk,称一个长度为 n 的排列aaa 为好的,当且仅当∀i,1≤i≤n\forall i,1\le i\le n∀i,1≤i≤n, 满足afa[i]<ai≤afa[i]+ka_{fa[i]} \lt a_i \le a_{fa[i]}+kafa[i]​<ai​≤afa[i]​+k,fa[i]fa[i]fa[i] 表示iii...
1.7k 2 分钟

# [题解] 2023 CCPC 华为云计算挑战赛 博弈,启动! [BFS] # 题目大意 给定一个有向二分图,分为GGG 部分和YYY 部分,有一个棋子位于图上任意一节点。当棋子在GGG 部分时,玩家GGGGGG 沿节点出边操作棋子;当棋子在YYY 部分时,玩家YYYYYY 沿出边操作棋子。循环往复该过程,直至棋子到达的节点没有出边。GGGGGG 的目标是让棋子在图上每个节点经过无穷次,YYYYYY 的目标与之相反。两人均采取最优策略,问GGGGGG 是否有必胜策略。 # 题解 先来剖析一下题目的意思,GGGGGG...
1.5k 1 分钟

# [题解] 2023 杭电多校 Rikka with Square Numbers [数论] 哎,数学! # 题目大意 每次操作可以加或者减一个完全平方数,问至少多少次可以把aaa 变成bbb。 1≤a,b≤1091 \le a,b\le 10^91≤a,b≤109。 # 题解 看到这个题面首先想了dpdpdp 或者搜索的做法。 发现这里的加减两个方向的转移其实没办法很好地dpdpdp。而且并没有找到合理的操作策略,不像是直接能递推出来的。 所以大概率是个结论题。然而我对数学不那么敏感,也推不出来什么式子。 如果当初先暴力打个表说不定就有思路了,那就能看到答案其实只有111...
1.6k 1 分钟

# [题解] 2023 杭电多校 Expectation of Rank [计数 dp] # 题目大意 矩阵A∈Fpn×nA\in \Bbb{F}_p^{n\times n}A∈Fpn×n​,其中的每个元素取值为Fp\Bbb{F}_pFp​ 的均匀随机变量。 Fp\Bbb{F}_pFp​ 为ppp 阶有限域,其中ppp 为质数。 求矩阵AAA 的秩的期望E(rank A)\Bbb{E}(rank\ A)E(rank A)。 # 题解 题目有点唬人的,但实际上只用到了一个关键点: ppp 阶有限域下,秩为kkk 的向量组可以确定一个kkk...
2.2k 2 分钟

# CF890 E PermuTree 题解 [背包 dp][二进制拆分] # 题目大意 给出一个以111 为根节点大小为NNN 的树。 给这个数确定一个长度为NNN 的排列ppp,分配给各节点作为权值。对于一个点对(u,v)(u,v)(u,v),若满足au<alca(u,v)<ava_u\lt a_{lca(u,v)} \lt a_vau​<alca(u,v)​<av​,则产生111 个贡献。 求总贡献的最大值。 # 题解 首先对一个排列计算贡献的过程,实际上就是对于每一个点xxx,从它的一个子树中选一个点uuu...
1.9k 2 分钟

# 点到线段的距离 # 两种情况 首先要判断点PPP 到直线ABABAB 的投影是否落在线段ABABAB 上。 若落在线段内,即∠A\angle A∠A 和∠B\angle B∠B 为锐角,则距离为点到直线ABABAB 的距离 若落在线段外,即∠A\angle A∠A 或∠B\angle B∠B 为钝角,则距离为点到线段ABABAB 的最近端点的距离 # 如何判断垂足是否落在线段上? 有两种做法。 第一种根据角度判断,若∠A\angle A∠A、∠B\angle B∠B...