UVA294 - Divisors
Divisors 题意是说算一个区间内的因子数最大的数。网上题解大都是用的dfs，但我又不想写dfs······然后看了一下，区间长度最长才1e4，用质因数分解求出区间内每一个数的因子数然后用最朴素的方法找出答案应该也能过吧······事实证明真的可以，而且只用了40ms 2333333。 这里做个笔记，所谓质因数分解求因子数，指的是，对于一个数x,必定存在以下式子: x = (a1^p1)*(a2^p2)*(a3^p3)*(a4^p4)*···*(an^pn)(其中,a1,a2,···，an均为质数) 那么,x的因子个数则为: sum(x) = (1+p1)*(1+p2)*(1+p3)*(1+p4)*···*(1+pn)..
Read morePOJ2891 - Strange Way to Express Integers
Strange Way to Express Integers 拓展中国剩余定理的模板题，但我并看不懂模板OTZ(过段时间会补上个人理解，先把代码放这)
Read more欧拉路、欧拉回路与Fleury算法
一、概念解释 欧拉路：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。 欧拉路的存在条件：没有孤立结点，同时奇数度数的点只有2个或0个。 欧拉回路：若一个连通图中没有奇数度数的点，则该图中一定存在一条起点与终点重合的欧拉路，称为欧拉回路。 通俗地讲，欧拉路就是一笔画游戏，每条边只能走一次，问怎么画才能把所有边都画出来。欧拉回路就是在此基础上，不仅要把所有边都画出来，还要求起点和终点要是同一个地方。 二、判断欧拉路是否存在 要判断欧拉路是否存在，只需要判断奇数度数的个数即可。一般使用并查集来实现。代码如下： //判断欧拉路是否存在 #include <iostream> #include <cstdio> #include <cstrin..
Read morePOJ2236 - Wireless Network
Wireless Network 一道并查集模板题。
Read moreHDU1301 - Jungle Roads
Jungle Roads 套用Kruskal或Prim的模板即可。这里我用的时Kruskal。
Read more【求最小生成树】Prim算法&Kruskal算法
一、概念解释 首先解释几个概念： 连通图：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。 强连通图：在有向图中，若任意两个顶点vi与vj都有路径相通，则称该有向图为强连通图。 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。 (转自勿在浮沙筑高台) 简单来说，最小生成树就是在连通图中找出一颗树，这棵树满足这样的要求：1、可以..
Read moreUVA - 12563 Jin Ge Jin Qu hao
Jin Ge Jin Qu hao 一道01背包，虽然t<=1e9，但实际上t不会超过180 * n + 678。
Read moreCodeForces - 1095B Array Stabilization
Array Stabilization 题意是要求最大值和最小值的差值的最小值。容易想到，对于一个有序序列，最可能得到这个最小值的是删去这个序列的最大值或最小值，因为删去除最大值和最小值外的数并不会改变差值的最小值。因此，我们只需要比较一下删去最大值和最小值后得到的差值，然后挑小的那个即可。
Read moreCodeForces - 1095A Repeating Cipher
Repeating Cipher emmmmmm感觉没什么好说的hhhhh
Read more
HDU2067 - 小兔的棋盘
小兔的棋盘 这道题有两种方法，一是dp，二是用卡特兰数(事实上我觉得dp是很自然的想法) 先说dp。对于棋盘的第0行(从下往上、从左往右数),除了(0,0)外，所有的点都只能由左边走来；对于棋盘的第0列，除了(0,0)外，所有的点都只能由左边走来。而对于对角线上的点，因为不能跨越对角线，所以这些点都只能由下边走来。而以上三种情况都不符合的点，则可以由左边或下边的点走来。故有一下dp代码：
Read more