Atcoder Beginner Contest 257 Ex 发表于 2022-07-14 更新于 2022-07-15 题目大意给定 N 个 6 面色子,价值为 Ci,每一面的概率均为 16,且有不同的权值 Ai,j。 从中选 K 个色子,使得期望权值和的平方减去所选色子价值和最大。 阅读全文 »
BZOJ3309 Solution 发表于 2022-07-14 题目大意对于 n 的唯一分解 n=∏pc,定义 f(n)=max{c}。 T 组询问,给定 n,m,求∑i=1n∑i=1mf(gcd(i,j))T≤104,n,m≤107 阅读全文 »
Luogu 7526 发表于 2022-04-11 更新于 2022-07-10 题目大意给定 n 个数 ai,对于每一个 i∈[0,K−1],求选出 m 个数使得异或和为 i 的方案数。 m≤n≤1.3×105,ai<K≤217。 阅读全文 »
CodeForces Global Round 2 H 发表于 2022-04-06 题目大意给定 n 个可重集 Si 及 x,y,z,k,每个可重集仅包含三种元素 ai,bi,ci,且它们的个数分别为 x,y,z。对于每个 t∈[0,2k−1] 求∑p1∈S1∑p2∈S2⋯∑pn∈Sn[p1⊕p2⊕⋯⊕pn=t]其中 ⊕ 表示按位异或。 n≤105,ai,bi,ci<2k,k≤17。 阅读全文 »
PKUSC & PKUWC 2018 选解 发表于 2022-03-03 Winter Camp Min-Max题目大意给定 n 个节点的二叉树,给定叶节点的权值,非叶节点的权值有 p 的概率为子节点的最大值,否则为子节点的最小值。 求根节点取到任意值的概率。 1≤n≤3×105。 阅读全文 »
Codeforces Educational Round 123 发表于 2022-03-01 A题目大意给定包含 RGBrgb 各一次的字符串,判断 r,g,b 是否分别在 R,G,B 之前。 阅读全文 »
从多项式乘法到快速傅里叶变换 发表于 2022-02-10 快速傅里叶变换点值表示法在做多项式乘法时, 类似于竖式乘法, 一个朴素的想法是将一个多项式的每一项与另一个多项式的每一项相乘, 得到新的多项式, 时间复杂度 Θ(n2)。 我们考虑对多项式看作向量, 对其做线性变换, 其和系数表达是一一对应的, 从而可以在其变换上考虑。因此, 我们引入了点值表示。 阅读全文 »
Codeforces Round 770 发表于 2022-02-10 A题目大意给定字符串 S,一次操作为 S←rev(S)+S 或 S←S+rev(S),求 k 次操作后可以得到的字符串种数。 阅读全文 »
CCPC 2021 Harbin G Damaged Bicycle 发表于 2022-02-10 更新于 2022-02-21 题目大意给定 n 个点 m 条边的带权(长度)无向图,图中有 k 个点,其中第 i 个点有一辆自行车,有 pi 的概率损坏,只有到达该点才知道自行车是否损坏。 已知 Bessie 的步行速度为 t,骑车速度为 r,现在她从 1 号点出发,求出一种路径方案,使得期望时间最短。 1≤n,m≤105,k≤18。 阅读全文 »