NeoRuTayE's blog

ACMC C++图论 并查集

POJ2236 - Wireless Network

2019-02-27

Wireless Network 一道并查集模板题。

ACMC C++Kruskal图论 最小生成树

HDU1301 - Jungle Roads

2019-02-27

Jungle Roads 套用Kruskal或Prim的模板即可。这里我用的时Kruskal。

ACMC C++Kruskal最小生成树Prim

一、概念解释首先解释几个概念：连通图：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。强连通图：在有向图中，若任意两个顶点vi与vj都有路径相通，则称该有向图为强连通图。连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。 (转自勿在浮沙筑高台) 简单来说，最小生成树就是在连通图中找出一颗树，这棵树满足这样的要求：1、可以..

ACMC C++DP 01背包

UVA - 12563 Jin Ge Jin Qu hao

2019-02-24

Jin Ge Jin Qu hao 一道01背包，虽然t<=1e9，但实际上t不会超过180 * n + 678。

ACMC C++

CodeForces - 1095B Array Stabilization

2019-02-24

Array Stabilization 题意是要求最大值和最小值的差值的最小值。容易想到，对于一个有序序列，最可能得到这个最小值的是删去这个序列的最大值或最小值，因为删去除最大值和最小值外的数并不会改变差值的最小值。因此，我们只需要比较一下删去最大值和最小值后得到的差值，然后挑小的那个即可。

ACMC C++

CodeForces - 1095A Repeating Cipher

2019-02-24

Repeating Cipher emmmmmm感觉没什么好说的hhhhh

ACMC C++组合数学

HDU2067 - 小兔的棋盘

2019-02-24

小兔的棋盘这道题有两种方法，一是dp，二是用卡特兰数(事实上我觉得dp是很自然的想法) 先说dp。对于棋盘的第0行(从下往上、从左往右数),除了(0,0)外，所有的点都只能由左边走来；对于棋盘的第0列，除了(0,0)外，所有的点都只能由左边走来。而对于对角线上的点，因为不能跨越对角线，所以这些点都只能由下边走来。而以上三种情况都不符合的点，则可以由左边或下边的点走来。故有一下dp代码：