概述中国剩余定理可以求解同余方程组，如对下列方程组：$$\begin{cases}x\equiv a_1 \ (mod \ m_1) \\ x\equiv a_2 \ (mod \ m_2) \\ x\equiv a_3 \ (mod \ m_3) \\ \ldots \\ x\equiv a_n \ (mod \ m_n) \end{cases}$$求解最小的 $x$ 。求解令：$$M=...
今天做了P1738 洛谷的文件夹。这道题本身挺水，其实map就行了，但我菜所以还用了pbds里的hash_table，这篇文章主要是记录一下hash_table的用法。hash_table食用方法先引入头文件：#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>然后是pb...
只是发个板子。虽说似乎NOIp近几年一般都是取膜而不是高精了，但我还是担心会考，所以就复习了一下。定义用struct储存整个数和位数。整个数全部倒序方便计算。struct bigint{
int s[5005],len;
bigint(){memset(s,0,sizeof(s));len=0;}
};加法inline bigint add(bigint x,bigint y...
排序希尔排序作者： dreamcatcher-cx 出处： https://www.cnblogs.com/chengxiao/本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在页面明显位置给出原文链接。我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，n/2,(n...
作为一个上个月刚学完线段树的蒟蒻，看Splay又看不懂，便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了，便去花了一天学了一个Tarjan求LCA（然而后来发现并不怎么需要），然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。准备工作链表/链式前向星线段树/树状数组/Splay等可以维护一段数据的数据结构LCA （其实只涉及到一些思想，而且几乎用不...
概念最小生成树即为无向图中结点构成的树中各边权值之和最小的树，可以有多种情况。一般用Kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。Kruskal算法方法可以将Kruskal算法理解成对边的贪心算法。1.将路径用邻接表存储，存储的值为起点、终点和权值；2.将邻接表按照权值为关键字排序；3.从最小权值的边开始循环，每连接起两个结点就把它们并到同一个集合（并查集实现），连接之前判断...