zxw0819-CSDN博客

原创求斐波那契数列的多种方法（有矩阵（附好模板））

f[1]=1; f[2]=2; f[n]=f[n-1]+f[n-2]; (1）递推long long fib(int n){ if(n==1) return 1; if(n==2) return 2; return fib(n-1)+fib(n-2);}(2) 循环long long fib(int n){ long long a=1,b=2,c; i

2017-08-09 21:31:53 835 1

原创 01分数规划

题套：有一堆物品，每一个物品有一个收益ai，一个代价bi，我们要求一个方案使选择的∑ai/∑bi为最值。套路解题：我们可用二分。设我们求的是最大，则我们要使∑ai/∑bi>=x ,等价于∑a[i]-x*∑b[i]>=0例一： Dropping Tests poj2976#include<cstdio>#include<algorithm>using namespace std;int

2017-08-01 16:07:12 296

原创精析背包四讲

No1. 01背包：题套：有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v

2017-07-31 11:48:14 420

原创 bzoj1007

题目描述在xoy直角坐标平面上有n条直线L1,L2,…Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的.例如,对于直线:L1:y=x; L2:y=-x; L3:y=0则L1和L2是可见的,L3是被覆盖的.给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.输入输出格式输入格式：第一行为N

2017-07-26 21:34:14 281

原创 bzoj1005(prufer序列+组合+高精)

Description 自从明明学了树的结构,就对奇怪的树产生了兴趣…… 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? Input 第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1 Output 一个整数,表示不同的满足要求的树的个数,无解输出0 Sample In

2017-07-24 15:44:21 403

原创 bzoj1004(组合+乘法逆元)（简便）

Description 　　小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案. 两种染色方法相同当且仅当其

2017-07-23 21:59:12 647 1

原创 bzoj2463（博弈）

Description小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？Input 输入文件有多组数据。输入第一行包含一个整数n，表示棋盘的规模。

2017-07-23 11:22:01 439

原创 Treap--简单的平衡二叉搜索树

它基本的支持一下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，只删除一个) 3. 查询x数的排名(若有多个相同的数，输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数) 模板如下：#include<cstdio>#include<cstdlib>//有rand()[随机函数]#inc

2017-06-19 21:36:58 295

原创排列组合

先补充一个其它的东西—–二项式定理：排列：定义：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m）表示。计算公式：此外规定0！==1其满足：A(n,m)=n×A(n-1,m-1);(编

2017-05-12 10:00:32 6403

原创生成树计数

问题即：给定一n个点的无向图，求其生成树的个数。我们需要用到Matrix-tree定理,又叫Kirchhoff矩阵定理,于1847年首次被基尔霍夫先生证明,后来被广泛应用于生成树的计数问题。定义：图G的基尔霍夫矩阵C[G]=D[G]-A[G]. 其中，D[G]为此无向图G的度数矩阵，A[G]为此图的邻接矩阵. 度数矩阵：表示的是点的度（类比有向图中的出、入度）；对于i行j列的矩阵来说

2017-05-11 21:29:55 1061

原创行列式

行列式在数学中，是由解线性方程组产生的一种算式，是取自不同行不同列的n个元素的乘积的代数和。介绍两个概念：主对角线：左上方与右下方组成的对角线。次对角线：另一条对角线。（右上到左下）介绍两个最重要的性质： 1、上三角行列式（下三角行列式）的值等于其主对角线上n个元素的乘积。 2、互换行列式的两行（列），行列式变号（正、负）。1.二阶行列式定义：由四个数排成两行两列的数表。计算：二

2017-05-11 20:46:15 2619

原创强连通分量（Tarjan、Kosaraju）

先介绍一下强连通分量：首先，强连通分量只可能存在于有向图中，无向图中是不存在强连通分量的，当然，无向图中也有对应物，被称为连通分量，求解无向图中的连通分量，根据具体要求，可以选择使用并查集或者DFS。对于一个强连通分量中的任意一对顶点(u，v)，都能够保证分量中存在路径使得u->v，v->u看图：以上用虚线围绕的部分就是一个强连通分量，因此上图中总共含有三个。上图中由a，b，e这三个顶点

2017-05-10 21:26:26 973

转载 st 表--求区间最值

（本文以最小值为例）举例：给出一数组A[0~5] = {5,4,6,10,1,12},则区间[2,5]之间的最值为1。方法：ST算法分成两部分：离线预处理（nlogn）和在线查询（O(1)）。虽然还可以使用线段树、树状链表等求解区间最值，但是ST算法要比它们更快，而且适用于在线查询。（1）离线预处理：运用DP思想，用于求解区间最值，并保存到一个二维数组中。（2）在线查询：对给定区间进行分

2017-05-10 17:25:14 378

原创网络流--平面图转换对偶图

今天所讲的一种模型，是将平面图转换为对偶图，用最短路来求最小割。它的速度比起裸最小割（Dinic）更快（但是仅适用于网格图）。平面图：可以画在平面上边不相交的图。（网格图）性质：若一个连通的平面图有n个点，m条边，f个面，则 f=m-n+2对于平面图G，可以找到它的对偶图G*: G*中的每个点对应G中的面; 即对于G中的每条边，都会“挨着”两个面，这两个面对应着G*中的两个点，那么对这两

2017-05-08 22:02:39 1333

原创网络流--最小费用最大流

还是贴代码：#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int MAXN=5005,MAXM=50005,INF=~0U>>1;int N,M,S,T;int minCost,maxFlow;struct E{int next,to,cap,cost;}

2017-05-08 20:40:05 572

原创网络流--最大流

直接贴模板：#include<cstdio>#include<cstring>#include<queue>#include<algorithm>using namespace std;const int maxm=100000+5,maxn=100000+5,inf=100000000;int head[maxm],tot=1;//因反向边用^ 所以不能是0； int n,m,s,t

2017-05-08 20:30:06 330

原创去重函数

在STL中unique函数是一个去重函数， unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除，是把重复的元素移到后面去了，然后依然保存到了原数组中，然后返回去重后最后一个元素的地址，因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。t=unique(a+1,a+n+1);

2017-05-05 21:01:14 1142

原创求一个数的所有约数

介绍一种O(sqrt(n))的算法：void pre (int x){ for(int i=1;i*i<=x;i++) { if(x%i==0) { a[++cnt]=i; if(x!=i*i) a[++cnt]=x/i; } }}即用sqrt(n)将1~n分开，我们只用求前

2017-05-04 19:11:22 6667 3

原创欧拉

诸多东西就不证明了欧拉函数：设n为正整数，以 φ(n)表示不超过n且与n互质的正整数的个数，称为n的欧拉函数值。以下代码就是求互质的个数：#include<cstdio>using namespace std;int ok(int n){ int ans=n; for(int i=2;i*i<=n;i++) { if(n%i==0)

2017-04-22 10:10:38 277

状压dp中大量用到位运算，下面就简单介绍几种常见的位运算。## 状压 ##：解法需要保存一定的状态数据，每个状态数据通常情况下是可以通过2进制来表示的。这就要求状态数据的每个单元只有两种状态，比如说棋盘上的格子，放棋子或者不放，或者是硬币的正反两面。这样就可以用0或者1来表示状态数据的每个单元，而整个状态数据就是一个0、1组成的二进制数。接下来，我们再看一道题。题目大意：输入n和m表示一个n*m的矩

2017-03-22 21:12:36 349

原创二维单调队列

二维单调队列（二维）单调队列通常解决区间最值问题。比如：有一个 a*b 的整数组成的矩阵，现请你从中找出一个 n*n 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。先介绍一下单调队列: 问题描述：用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。解法一：很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗

2017-03-08 20:47:55 2867

原创 KMP算法

KMP算法思想我们首先用一个图来描述kmp算法的思想。在字符串O中寻找f，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高。事实上，如果我们提前计算某些信息，就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。我们可以得到如下的结论： 1. A段字符

2017-03-01 20:49:17 312

原创 KMP算法（字符串匹配）

先来个理论上的分析首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。因为B与A不匹配，搜索词再往后移。就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。继续搜索，直到字符串有一个字符，与搜索词对应的字符不相同为止。这时，最自然的反应是，将搜索词整个

2017-02-20 16:57:33 238

原创封印一击

封印一击题目描述 “圣主 applepi 于公元 2011 年 9 月创造了 Nescafe，它在散发了 16 次光辉之后与公元 2011 年 11 月 12 日被封印为一颗魂珠，贮藏于 Nescafe 神塔之中。公元 2012 年 9 月，圣主带领四大护法重启了 Nescafe，如今已经是 Nescafe 之魂的第 30 次传播了。不久，它就要被第二次封印，而变成一座神杯……”appl

2017-02-07 20:51:24 398

原创能量获取

贪心法题目描述 “封印大典启动，请出 Nescafe 魂珠！”随着圣主 applepi 一声令下，圣剑护法 rainbow 和魔杖护法 freda 将 Nescafe 魂珠放置于封印台上。封印台是一个树形的结构，魂珠放置的位置就是根节点（编号为 0）。还有 n 个其它节点（编号 1~n）上放置着封印石，编号为 i 的封印石需要从魂珠上获取 Ei 的能量。能量只能沿着树边从魂珠传向封印石，每

2017-02-07 16:56:24 465

zxw0819的博客