GoPoux4

未归档

题解(2)

/ 注册

全部文章 / 未归档（共36篇）

题解「Luogu4228 [清华集训2017] 榕树之心」

转载注明来源：https://www.cnblogs.com/syc233/p/13606704.html 题意给一棵树和一个动点，最初树只有根结点，动点在根节点。每次在已有的结点处向外扩展出一个结点，并且动点沿着新结点到动点的最短路径移动一步。必须保证在任意时刻，树的点集和边集是原树点集...

题解动态规划

2020-09-03

0 412

题解「AT4995 [AGC034E] Complete Compress」

转载注明来源：https://www.cnblogs.com/syc233/p/13603919.html 注意到数据范围很小，所以我们可以枚举一个根，尽量让所有点移动到这个点上。将两颗距离至少为 \(2\) 的棋子向中间移动一步，可能会出现两种情况：它们的LCA为它们共同的祖先...

题解动态规划

2020-09-02

0 450

题解「Luogu6189 [NOI Online #1 入门组]跑步」

整数拆分问题。首先有一个dp的方法：设 \(f_{i,j}\) 表示用小于等于 \(i\) 的正整数组合成 \(j\) 的方案数，则有转移： \[f_{i,j}=f_{i-1,j}+f_{i,j-i} \] 前一项相当于不用 \(i\) 组成 \(j\) ，后一项表示使用了 ...

根号分治动态规划题解

2020-09-01

0 484

题解「Luogu6156 简单题」

简单题（确信）不难发现： \[f(n)=\mu^2(n) \] 把这个代进原式，然后开始推式子： \[\begin{aligned} \text{Ans}&=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2({\rm{gcd}}(i,j))...

题解数学

2020-08-27

0 391

题解「Luogu5221 Product」

题意求这个东西： \[\prod_{i=1}^N\prod_{j=1}^N\frac{{\rm{lcm}}(i,j)}{{\rm{gcd}}(i,j)} \ ({\rm{mod}} \ 104857601) \] 题解根据 \[{\rm{lcm}}(i,j)=\frac{...

题解数学

2020-08-25

0 398

题解「Luogu2839 [国家集训队]middle」

题面给一个序列 \(s\) ，回答 \(Q\) 个这样的询问：\(s\) 的左端点在 \([a,b]\) 中，右端点在 \([c,d]\) 中的子区间的最大中位数。题解首先要知道中位数怎么求：二分出一个 \(mid\) ，判断中位数 \(m\) 与 \(mid\) 的大小关系。将询问...

题解数据结构二分

2020-08-25

0 387

总结「积性函数和筛法」

定义若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y \in {\Bbb{N}}_{+},{\rm{gcd}}(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\) ，则 \(f\) 为积性函数。若函数 \(f(n)\) 满足 \(f(1)=1\)...

数学总结

2020-08-23

0 369

题解「Luogu6055 [RC-02] GCD」

题目要求： \[\text{Ans}=\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[{\rm{gcd}}(i,j)=1][{\rm{gc...

题解数学

2020-08-22

0 407

题解「Luogu1587 [NOI2016]循环之美」

题意求满足 \(1 \leq x \leq n,1 \leq y \leq m\) 的在 \(k\) 进制下能写成纯循环小数的最简分数 \(\frac{x}{y}\) 的个数。题解证明： \[\text{Ans}=\sum_{x=1}^{n}\sum_{y=1}^{m}[x ...

数学题解

2020-08-21

0 430

题解「Luogu3327 [SDOI2015]约数个数和」

首先有个东西是这题解题的关键： \[{\rm{d}}(ij)=\sum_{x|i}\sum_{y|i}[{\rm{gcd}}(x,y)=1] \] 有位dalao的题解证明了这个式子，可以去看看。然后就可以开始推式子了： \[\sum_{i=1}^n\sum_{j=1}^...

数学题解

2020-08-20

0 437