__故人__

分类

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20) 题解(117)

/ 注册

TA的专栏 52篇文章 0人订阅

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

任意模数多项式乘法来自专栏

任意模数多项式乘法 NTT 因为任意模数多项式乘法的系数可能超过了所以一般的就做不了。所以对于的做法是找到个模数，最后使用合并一下，但是这里的合并中的答案可能超过的值域，所以要用快速乘实现。 FFT 任意模数多项式乘法用实现的问题主要是因为精度问题，这里使用了次变化的...

2020-10-31

3 984

2020牛客NOIP赛前集训营-普及组（第六场）来自专栏

2020牛客NOIP赛前集训营-普及组（第六场） A 七七七七分析由于每次的答案的增长是以指数增长的，所以直接枚举日期的复杂度为。那就直接暴力枚举就可以了。总的复杂度为。代码 #include<bits/stdc++.h> using namespace std; int...

2020-10-31

2 701

2020牛客NOIP赛前集训营-普及组（第五场）来自专栏

2020牛客NOIP赛前集训营-普及组（第五场） A T1 购物分析由于是买送一，所以我们考虑买只需要次花钱的购买。那么可以把个物品分成很多段，每段的长度为，然后处理一下边角就好了。代码 #include<bits/stdc++.h> using namespa...

2020-10-29

5 650

2020牛客国庆集训派对day5 D 来自专栏

分析可以观察到，如果一个数的最小位数没法精准划分，那么再多的大位也不可能表达出这个数字。所以我们考虑从低位到高位依次贪心。对一位的答案可以贪心考虑。如果，那么在同一位上的我们显然是考虑是要比更优的，那么当我们可以得到一个值而且可以得到那么我们是可以确定这一位的。那么由小...

2020-10-29

8 614

k阶差分与前缀和来自专栏

K阶前缀和这是我们对前缀和的定义。而阶前缀和就是把这个过程进行次。那么考虑卷积。其实可以看作而。是一个所有项都为的函数。那么。由于卷积是有结合率的，所有阶前缀和等同于。而对于的计算，可以采用多项式快速幂，但没必要。我们有生成函数，那么的生成函数...

2020-10-29

5 1707

点分治

写在前面的一起对于简单点分治的题都是用解决的，结果遇到点分树，哦吼，做不来了。这才打算学一下点分治，我检讨。点分治引入给你个询问，询问一个树上是否有长度为的路径。要求在时间复杂度内解决。如果学习过的同学，这个就是个模板。但是这里还是考虑使用点分治解决。其实这两个算法我...

2020-10-28

1 764

2020牛客NOIP赛前集训营-提高组（第五场）来自专栏

2020牛客NOIP赛前集训营-提高组（第五场） A 三元组计数分析我们对于三元组的考虑，有一个套路，枚举二元组然后再考虑贡献。那么我们先找到有多少个二元组满足。那么这个根据调和级数可以得到。那么我们就可以直接枚举每个元素的倍数就好了。最后再考虑每个二元组的贡献就好了。总的复杂度为 ...

2020-10-28

7 756

[APIO2014]连珠线

写在前面的这是我不想做第二次的题目。分析我们什么都不说了，直接定义状态表示节点是否作为蓝线的中点的最优解。那么我们通过分析，一条蓝边一定是的路径。所以先考虑的暴力树形。和，然后就写好了。 #include<bits/stdc++.h> int re...

2020-10-26

5 680

01 Trie 解决异或小专题

说在前面的我希望以后的每日一题也是以小专题出现的，我觉得这样的练习效果才好。而且题有点少，并且有很多重复。例如解决异或和，权值，合并没有出现，有点小伤心。牛客工作人员找了这么多的例题真的很辛苦。感谢牛客。异或异或是一种位运算。满足。这个比较好理解，大概就是两个数异或，那么在一位...

2020-10-25

8 1064

CF1408G

写在前面的，一道非常好的题，思路很顺滑（是这样用的吧），考察的数据结构也很巧妙。分析首先从小到大把边加进来，那么，一个连通块是满足条件的当且仅当在加完某条边之后这个连通块是一个团。所以我们就有了个，指数级别的。那么如何去掉连通块的问题。其实我们如果按照边的长度排序。构建一棵重构树。那么我们发...

2020-10-24

4 562