yzmduncan
- 浏览: 326938 次
- 性别:
- 来自: 武汉
-
最新评论
-
di1984HIT：
学习了～
Spring scope="prototype" -
netkiller.github.com：
路还很长看看我的博客 http://netkiller.git ...
写博客是个好习惯 -
ooo456mmm：
JAVA 设计模式之——动态代理 -
hanmiao：
问题是这么问的：请使用 Java 的基本数据类型表示壹下单链表 ...
JAVA数据结构之——单链表的逆序 -
hanmiao：
谢谢，今天刚好有人问我这个问题，结果没有答上来，看了你这篇文章 ...
JAVA数据结构之——单链表的逆序
文章列表
欧几里得定理
对任意的非负整数a和和任意正整数b，有gcd(a, b) = gcd(b, a%b)
这个定理可以用来求a和b的最大公约数，假设a>b，时间复杂度为O(logb)。
扩展欧几里得
它是欧几里得算法的推广，使它能计算出满足下列条件的整数系数x和y：
ax + by = gcd(a, b)
注意，x和y可能为0或负数，用它来计算模乘法的逆元也很有效。
根据gcd(a,b)=gcd(b,a%b)
ax + by = d ...
容斥原理是计数中常用的一种方法。在讨论容斥原理的过程中，要用到以下集合论的基本性质。
德摩根(De Morgan)定理
若A和B是集合U的子集，则
例题
HDU4059 The Boss on Mars
题意：给一个数n(n=10^8)，求X1^4+X2^4+..Xk^4的和模1,000,000,007，其中1<=Xi<n，且Xi与n互素。
解：
四次方求和公式为：n*(n+1)*(2*n+1)*(3*n*n+3*n-1)/30
将n分解素因子为p1^e1*p2^e2*..*pk^ek，设集合Ai为pi的整数倍的数的集合。则答案 ...
一个正整数n的欧拉函数定义为：在1到n-1之间和n互素的数的个数。
欧拉函数公式：
phi(n)=n(1-1/p1)(1-1/p2)(1-1/p3)...(1-1/pk)，其中pi为n的素因子。
例如，phi(12)=12(1-1/2)(1-1/3)=12*1/2*2/3=4。
相关定理
欧拉定理
...
筛选法
求出n以内的素数，最快的应该是筛选法。
筛选法的思路是：
要求10000以内的素数，把1-10000都列出来，1不是素数，划掉；2是素数，所有2的倍数都不是素数，划掉；取出下一个幸存的数，划掉它的 ...
初学者关于AC自动机的疑问：什么是AC自动机？为什么要学习AC自动机？学习AC自动机需要哪些知识？如何构造AC自动机及其应用？
1. 什么是AC自动机
AC的意思和KMP相似，是由Aho-Corasick这两个人创造的，用于多字符串匹配问题的算法。比如给你一个文本文件，再给你k个目标串，让你寻找这k个目标串是否存在在这个文件中。
2. 为什么要学习AC自动机
相信大家都了解KMP算法，它是用于单模式串的线性匹配算法。它的主要思想是当主串和模式串匹配不成功时，模式串不用从头开始匹配，而是回退到tk处，其中k为满足T0T1..Tk-1=Tj-k+1.. ...
题意：有n个(n<=1000)城市，坐标都告诉你了，并且每个城市都有人居住，现在要修路n-1条路，使得每个城市都连通。显然，这就是一颗树。当然，边的权值就是两点的距离。条件：有一条边可以不用任何花费。问这条边的两端点的总人数/(包含这条边的最小生成树的总权值-这条边的权值)最大是多少。即(Wa+Wb)/(mst-w(a,b))最大。
解：其实这题是次小生成树的变形。首先可以想到最小生成树。但最小生成树的边集中的不一定是最大的。考虑n只有10^3，可以枚举两点再求。
枚举的时候，判断这条边在不在MST上，若在，直接求。若不在呢？是不是类似于次小生成树了？是的。添加 ...
在上一篇中已经介绍了一种利用网络流求解竞赛问题的解法，构图共有n^2个点。但当比赛队伍逐渐增大时，比如n=60，就会有3600个点，采用网络流显然效率不高。这里再介绍一种更简单的建模方式。
解：
1. 还是假设DD赢下剩下的所有比赛，最高得分为high。
2. 对于剩下的比赛，随意定胜负。记录每位选手的得分score[i]，用champ[i][j]表示i赢j的次数。
3. 增设源点和汇点，三类边：
边(s,i,score[i])，表示选手i有score[i]次胜利(比赛)要分配。
边(i,sink,high-1)，表 ...
停摆？？停摆你妹啊！！2011-2012NBA赛季开已经打啦！你OUT了。
有n支队伍比赛，n<=20。已经打了一些比赛，并且知道了A赛区的队伍的目前得分。队伍i的目前得分为score[i]，剩余比赛场次为remain[i]，剩余场次包括同赛区和异赛区的比赛。用match[i][j]表示A区队伍的剩余的比赛情况，i和j剩余的比赛场数。当然，remain[i]>=sigma{match[i][k],1<=k<=n}。要知道，篮球比赛是没有平局的，问队伍1可不可能在赛季末获得A区的第一名(可以并列第一)？
解：
1. 显然，有种情况是：当 ...
模型：
有n个牛棚和连接n个牛棚的m条路径，n<=200,m<=1500。每到下雨天，牛都很讨厌自己的蹄子被打湿，所以在下雨前都要躲进牛棚里。当然，每个牛棚能容纳的牛的数量有限。现在每个棚内有若干只牛，问最短需要多少时间，使得所有牛都能躲到牛棚里去。
解：求最短时间，可以想到二分，然后判断可行性。
首先在原图上求floyd，得到每两个棚之间的最短距离。拆点：将每个棚拆为i和i'(流进的点和流出的点)，添边(i,i',INF)。增加源点s和汇点t，从s连边到i，容量为该棚现在的牛的数量，i'连边到t，容量为该棚的容量。接下来最关键的地方：若棚i和棚j之间的 ...
裸的DLX，比一般的数独酷稍微复杂点的就是处理输入，先dfs一下，然后建十字链表。
直接上代码了，跑得比较慢。
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int NN = 350;
const int MM = 750;
int n,m; //列，行
int cntc[NN];
int L[NN*MM],R[NN*MM],U[NN*MM],D[NN*MM];
int C[NN*MM]; ...
最长上升子序列是一个经典问题，可以用O(n^2)的dp解决。给出一个串，求出最长上升子序列的长度为多少？假设长度为s，现在问题是，有多少个长度为s的上升子序列，满足每个子序列所包含的元素均不相同(即一个数只能选一次)。
建模：
第一问直接用dp求解，dp[i]表示以i为结尾的最长递增子序列的长度，最后取dp[1~n]的最大值，即为s。
第二问可以利用上一问求出来的dp数组，用网络流求解。
1. 拆点，将每个点拆成两点，容量为1，保证每个点只取一次。
2. 增加源点s和汇点t，s和dp[i]=1的点相连，dp[i]=s的点和t相连，容量均为 ...
无向(有向)图G中，给定源点s和终点t，至少要删去多少个点(具体一点，删哪些点)，使得s和t不连通。这个问题就是点连通度，也叫最小点割集。
一般最小点割转化到最小边割上，将原图中的点v拆成v'和v''，且w(v,v'')=1。对于原图中的有向边(u,v)，则有w(u'',v')=INF；若是无向边，则还要加上边：w(v'',v')=INF。然后求以s''为源点，t'为汇点的最大流。maxflow即为最少需要删的点数，割边集对应了具体删的点的一组解。
值得注意的是最小点割的解有很多，如下图：
最小点割的方案有4种：(4,3)，(4,1 ...
关键割边就是增加某条边的容量，使得网络的最大流增加。
步骤：
1. 求最大流，得到残余网络。
2. 在残余图上从s点出发dfs，得到割边(a,b)。
3. 从t点出发反向dfs，得到所有能到达t的点。
4. 对于某条割边(a,b)，若b能到达t，则该边为关键割边。(因为从s到t的路径上只有这一条割边，增加这条割边，肯定可以增加流量)。
例：POJ3024
题意：找关键割边数量。
#include <iostream>
#include <cstdio>
#include <cst ...
所谓K短路，就是从s到t的第K短的路，第1短就是最短路。
如何求第K短呢？有一种简单的方法是广度优先搜索，记录t出队列的次数，当t第k次出队列时，就是第k短路了。但点数过大时，入队列的节点过多，时间和空间 ...
在一棵生成树中，某个顶点v0的度数<=k称作度限制条件，把满足这一条件的生成树称为度限制生成树，把权值和最小的度限制生成树称为最小度限制生成树。
如果撇开度限制条件，那么就是最小生成树问题。首先， ...