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...