Shen Huang's Blog
0%

Posted on Edited on

二分图最大匹配的匈牙利算法

二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。</span>

最大匹配：图中包含边数最多的匹配称为图的最大匹配。

完美匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。

最小覆盖： 最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数

最小路径覆盖：

用尽量少的不相交简单路径覆盖有向无环图Ｇ的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m。</span>

最大独立集问题：

在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．</span>

如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数</span>

一、匈牙利算法

设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。</span>

v 给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。</span>

v 选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)</span>

v 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。</span>

最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。

匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。</span>

由增广路径的定义可以推出下述三个结论：

v 1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。</span>

v 2. P经过取反操作（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。</span>

v 3. M为G的最大匹配当且仅当不存在相对于M的增广路径。</span>

从而可以得到求解最大匹配的匈牙利算法：

v (1)置M为空</span>

v (2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M</span>

v (3)重复(2)操作直到找不出增广路径为止</span>

二、KM算法：</span>

二分图最优匹配：对于二分图的每条边都有一个权（非负），要求一种完备匹配方案，使得所有匹配边的权和最大，记做最优完备匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题）</span>

解二分图最优匹配问题可用穷举的方法，但穷举的效率=n！，所以我们需要更加优秀的算法。</span>

先说一个定理：设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最优匹配。</span>

Kuhn－Munkras算法（即KM算法）流程：</span>

v (1)初始化可行顶标的值</span>

v (2)用匈牙利算法寻找完备匹配</span>

v (3)若未找到完备匹配则修改可行顶标的值</span>

v (4)重复(2)(3)直到找到相等子图的完备匹配为止</span>

KM算法主要就是控制怎样修改可行顶标的策略使得最终可以达到一个完美匹配，首先任意设置可行顶标（如每个X节点的可行顶标设为它出发的所有弧的最大权，Y节点的可行顶标设为0），然后在相等子图中寻找增广路，找到增广路就沿着增广路增广。而如果没有找到增广路呢，那么就考虑所有现在在匈牙利树中的X节点（记为S集合），所有现在在匈牙利树中的Y节点（记为T集合），考察所有一段在S集合，一段在not T集合中的弧，取 delta = min {l(xi)+l(yj)-w(xi,yj) , | xi in S, yj in not T} 。明显的，当我们把所有S集合中的l(xi)减少delta之后，一定会有至少一条属于(S, not T)的边进入相等子图，进而可以继续扩展匈牙利树，为了保证原来属于(S,T )的边不退出相等子图，把所有在T集合中的点的可行顶标增加delta。随后匈牙利树继续扩展，如果新加入匈牙利树的Y节点是未盖点，那么找到增广路，否则把该节点的对应的X匹配点加入匈牙利树继续尝试增广。</span>

复杂度分析：由于在不扩大匹配的情况下每次匈牙利树做如上调整之后至少增加一个元素，因此最多执行n次就可以找到一条增广路，最多需要找n条增广路，故最多执行n^2次修改顶标的操作，而每次修改顶标需要扫描所有弧，这样修改顶标的复杂度就是O(n^2)的，总的复杂度是O(n^4)的。</span>

对于not T的每个元素yj，定义松弛变量slack(yj) =min{l(xi)+l(yj)-w(xi,yj), | xi in S}，很明显每次的delta = min{slack(yj), | yj in not T}，每次增广之后用O(n^2)的时间计算所有点的初始slack，由于生长匈牙利树的时候每条弧的顶标增量相同，因此修改每个slack需要常数时间（注意在修改顶标后和把已盖Y节点对应的X节点加入匈牙利树的时候是需要修改slack的）。这样修改所有slack值时间是O(n)的，每次增广后最多修改n次顶标，那么修改顶标的总时间降为O(n^2)，n次增广的总时间复杂度降为O(n^3)。事实上这样实现之后对于大部分的数据可以比O(n^4)的算法快一倍左右。</span>

利用二分图匹配的匈牙利算法和KM算法，我们可以求解大部分的关于二分图的问题，它们提供了求解最大匹配和最优匹配的有效算法，在具体编程时我们只要多注意优化，我们就可以得出求解这类问题的有效方法，从而可以对这类实际问题进行有效合理的解决。</span>

另一种说法：

KM算法(转)

KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B [i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终 成立。KM算法的正确性基于以下定理：</span>

　　若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。</span>

　　这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。

　　初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。</span>

　　我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：</span>

两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。</span>

两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。</span>

X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。</span>

X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。</span>

　　现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}。</span>

　　以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶 标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个"松弛量"函数 slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A [i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改 顶标后，要把所有的slack值都减去d。</span>

原文:http://www.360doc.com/content/11/0718/14/3701281_134273282.shtml

Posted on Edited on

[二分图带权匹配与最佳匹配]

什么是二分图的带权匹配？二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小。而二分图的最佳匹配则一定为完备匹配，在此基础上，才要求匹配的边权值之和最大或最小。二分图的带权匹配与最佳匹配不等价，也不互相包含。

我们可以使用KM算法实现求二分图的最佳匹配。方法我不再赘述，可以参考tianyi的讲解。KM算法可以实现为O(N^3)。

[KM算法的几种转化]

KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。

KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。

KM算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a就是最大积匹配。至于精度问题则没有更好的办法了。

以上转自:https://www.byvoid.com/blog/match-km

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/* From: Lich_Amnesia
 * Time: 2014-01-25 17:00:42
 *
 * POJ 2195 KM 算法
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define INT_MAX 1000000000
#define maxn 150
int w[maxn][maxn],n,m; //边集
int lenx,leny; // X顶点个数
int lx[maxn],ly[maxn]; //顶标
int slack[maxn]; //松弛操作
int le[maxn]; // Y集合点所匹配的X顶点标号
char maps[maxn][maxn];
bool S[maxn],T[maxn];// S集合 T集合

bool match(int u){
	S[u] = 1;
	for (int i = 1; i <= leny; i ++){
		if (!T[i] && lx[u] + ly[i] == w[u][i]){
			//找到相等子图
			T[i] = 1;
			if (!le[i] || match(le[i])){
				le[i] = u;
				return true;
			}
		}else if (slack[i] > lx[u] + ly[i] - w[u][i]){
			slack[i] = lx[u] + ly[i] - w[u][i];
		} //修改松弛值
	}
	return false;
}

void update(){ // 根据Delta修改顶标集合
	int d = INT_MAX;
	for (int j = 1; j <= leny; j ++)
		if (!T[j]) d = min(d,slack[j]);
	for (int j = 1; j <= lenx; j ++)
		if (S[j]) lx[j] -= d;
	for (int j = 1; j <= leny; j ++)
		if (T[j]) ly[j] += d;
}

int KM(){
	int ans = 0;
	for (int i = 1; i <= lenx; i ++) {
		lx[i] = -INT_MAX;
		for (int j = 1; j <= leny; j ++){
			lx[i] = max(lx[i],w[i][j]);
		}
	}
	memset(ly,0,sizeof(ly));
	memset(le,0,sizeof(le));

	//搜索增广路
	for (int i = 1;i <= lenx; i ++){
		for (int j = 1; j <= leny; j ++)
			slack[j] = INT_MAX;
		while (1){
			memset(S,0,sizeof(S));memset(T,0,sizeof(T));
			//找到I对应的增广路,找到便不再找
			//未找到便修正
			if (match(i)) break;
			else update();
		}
	}

	for (int i = 1; i <= leny; i ++)
		if (le[i]) ans += w[le[i]][i];
	return -ans;
}

int main(){
	while (~scanf("%d%d", &n, &m) && (n + m)){
		lenx = 0,leny = 0;
		for (int i = 0; i < n; i ++){
			scanf("%s", maps[i]);
			for (int j = 0; j < m; j ++){
				if (maps[i][j] == &#39;H&#39;){
					lx[++ lenx] = i,slack[lenx] = j;	
				}else if (maps[i][j] == &#39;m&#39;){
					ly[++ leny] = i,le[leny] = j;
				}
			}
		}
		for (int i = 1;i <= lenx; i ++){
			for (int j = 1; j <= leny; j ++){
				w[i][j] = -iabs(lx[i] - ly[j]) 
					- iabs(slack[i] - le[j]);
			}
		}

		printf("%dn",KM());
	}
	return 0;
}

Posted on Edited on

求最大独立集转化为求最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/* From: Lich_Amnesia
 * Time: 2014-01-24 21:10:12
 * 
 * ZOJ 1654 匹配
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 55

int x[maxn * maxn],y[maxn * maxn];//x匹配的y顶点
int xs[maxn][maxn],ys[maxn][maxn];//横的坐标x的取值
int xnu,ynu;
char s[maxn][maxn];
bool g[maxn * maxn][maxn * maxn];
bool vis[maxn * maxn]; //DFS算法中记录顶点访问状态

bool path(int u){
	for (int v = 1; v <= ynu; v ++){
		if (g[u][v] && !vis[v]){
			vis[v] = 1;
			//如果v没有匹配
			//或者v已经匹配了,但是从y[v]出发能找到一条增广路

			if (!y[v] || path(y[v])) {
				x[u] = v;
				y[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

void MaxMatch(){
	int ans = 0;
	memset(x,0,sizeof(x));
	memset(y,0,sizeof(y));
	for (int i = 1;i <= xnu; i ++){
		if (!x[i]) {
			memset(vis,0,sizeof(vis));
			if (path(i)){
				ans ++;
			}
		}
	}

	printf("%dn", ans);
}

int main(){
	int T,t = 0,m,n;
	cin >> T;
	while (t++ < T){
		printf("Case :%dn", t);
		scanf("%d%d", &m, &n);
		for (int i = 0; i < m; i ++){
			scanf("%s", s[i]);
		}
		memset(xs,0,sizeof(xs));
		memset(ys,0,sizeof(ys));
		int number = 0;
		for (int i = 0; i < m; i ++){
			int flag = 1;
			for (int j = 0; j < n; j ++){
				if (s[i][j] == &#39;o&#39;) {
					if (flag) number ++,flag = 0;
					xs[i][j] = number;
				}
				if (s[i][j] == &#39;#&#39;) flag = 1;
			}
		}
		xnu = number,number = 0;
		for (int j = 0; j < n; j ++){
			int flag = 1;
			for (int i = 0; i < m; i ++){
				if (s[i][j] == &#39;o&#39;) {
					if (flag) number ++,flag = 0;
					ys[i][j] = number;
				}
				if (s[i][j] == &#39;#&#39;) flag = 1;
			}
		}
		ynu = number;

		memset(g,0,sizeof(g));
		for (int i = 0; i < m; i ++){
			for (int j = 0; j < n; j ++){
				if(xs[i][j]) g[xs[i][j]][ys[i][j]] = 1;
			}
		}

		MaxMatch();
	}
	return 0;
}

Posted on Edited on

Let's consider substring of s s[i… j], that all characters from i to j are palindrome centers, and i - 1, j + 1 are not. Every such substring can be treated independently from the others, and as we don't need to know it'sstructure let's consider only it length len. Let's calculategrundy[len] — Grundy function. If we want to cut character at position i 0 ≤ i < len then our game splits in to independent ones: first will have length i - 1, second — len - i - 2, as s[i - 1] and s[i + 1] are not centers of palindrome any more.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <memory.h>
#include <cstring>

inline int max(int a, int b) { if (a >= b) return a; return b; }

const int N = 5005;
char s[N];
int grundy[N], mex[N], n, totalXor;

int main(){
	gets(s);
	for(int i = 1; i < N; i++) {
		memset(mex, 0, sizeof mex);
		for(int j = 0; j < i; j++) {
			int left = max(0, j - 1);
			int right = max(0, i - j - 2);
			int tXor = grundy[left] ^ grundy[right];
			if (tXor < N) mex[tXor]++;
		}
		for(int j = 0; ; j++) {
			if (!mex[j]) {
				grundy[i] = j;
				break;
			}
		}
	}
	n = strlen(s);
	for(int i = 1; i < n - 1; i++) {
		if (s[i-1] == s[i + 1]) {
			int j = i;
			while (j + 2 < n && s[j] == s[j + 2]) j++;
			totalXor ^= grundy[j - i + 1];
			i = j + 1;
		}
	}
	if (totalXor != 0) {
		puts("First");
		for(int i = 1; i < n - 1; i++) {
			if (s[i-1] == s[i+1]) {
				int j = i;
				while (j + 2 < n && s[j] == s[j + 2]) j++;
				int len = j - i + 1;
				int nowXor = totalXor ^ grundy[len];
				for(int k = 0; k < len; k++) {
					int left = max(0, k - 1);
					int right = max(0, len - k - 2);
					int resXor = nowXor ^ grundy[left] ^ grundy[right];
					if (resXor == 0) {
						printf("%dn", i + k + 1);
						return 0;
					}
				}
				i = j + 1;
			}
		}
	}
	puts("Second");
}

Posted on Edited on

First of all, let's carry over all powers of two in the following way: if we have ai = aj</span>, i ≠ j, carry 1 to ai + 1</span>. Now as all of ai</span> are distinct, the answer is max(ai)</span> — cnt(ai)</span> + 1, where max(ai)</span> — maximal value of ai</span>,cnt(ai)</span> — size of a

因为从小到大输入SET所以能够保证总是distinct。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* From: Lich_Amnesia
 * Time: 2014-01-24 14:23:29
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

set<int>Set;
int main(){
	int n,cnt,Max = 0;
	cin >> n;
	for (int i = 0; i < n; i ++){
		cin >> cnt;
		while (Set.count(cnt)) Set.erase(cnt),cnt++;
		Set.insert(cnt);
		Max = max(Max,cnt);
	}
	cout << Max - Set.size() + 1 << endl;
	return 0;
}

Posted on Edited on

http://codeforces.com/blog/entry/7497

借用一下,组合数学的乘法逆元的求法,先记一下，以后可能会用到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/* From: Lich_Amnesia
 * Time: 2014-01-21 14:32:49
 *
 * CF 300C Round181_div2 
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;
const ll MOD = 1000000007;

bool check(int a, int b,int x){
	while (x){
		if (x % 10 != a && x % 10 != b) return false;
		x /= 10;
	}
	return true;
}

ll Pow_mod(ll a,ll n){
	ll ret = 1;
	while (n){
		if (n & 1) ret = ret * a % MOD;
		a = a * a % MOD;
		n >>= 1;
	}
	return ret;
}

int main(){
	int a,b,n;
	cin >> a >> b >> n;	
	int sum = 0;
	ll ret = 1;
	ll ans = 0;
	for (int i = 0; i <= n; i ++){
		sum = a * i + b * (n - i);
		if (check(a,b,sum)){
			ans = (ans + ret) % MOD;
		}
		ret = ret * (n - i) % MOD;
		ret = ret * Pow_mod(i + 1, MOD - 2) % MOD; 
	} 
	cout << ans << endl;
	return 0;
}

Posted on Edited on

在 http://www.cnblogs.com/youxin/p/3219622.html 上看到转过来

各种被整除的数的特征（放在这里以备以后查阅方便）

（1）被2整除的数的特征：一个整数的末位是偶数（0、2、4、6、8）的数能被2整除。

（2）被3整除的数的特征：一个整数的数字和能被3整除，则这个数能被3整除。

（3）被4整除的数的特征：一个整数的末尾两位数能被4整除则这个数能被4整除。可以这样快速判断：最后两位数，要是十位是单数，个位就是2或6，要是十位是双数，个位就是0、4、8。

（4）被5整除的数的特征：一个整数的末位是0或者5的数能被5整除。

（5）被6整除的数的特征：一个整数能被2和3整除，则这个数能被6整除。

（6）被7整除的数的特征：”割减法”。若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，这样，一次次下去，直到能清楚判断为止，如果差是7的倍数（包括0），则这个数能被7整除。过程为：截尾、倍大、相减、验差。

例如，判断133是否7的倍数的过程如下：13－32＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－92＝595 ， 59－5*2＝49，所以6139是7的倍数，余类推。

（7）被8整除的数的特征：一个整数的未尾三位数能被8整除，则这个数能被8整除。

（8）被9整除的数的特征：一个整数的数字和能被9整除，则这个数能被9整除。

（9）被10整除的数的特征：一个整数的末位是0，则这个数能被10整除。

（10）被11整除的数的特征：”奇偶位差法”。一个整数的奇位数字之和与偶位数字之和的差是11的倍数（包括0），则这个数能被11整除。（隔位和相减）

例如，判断491678能不能被11整除的过程如下：奇位数字的和9+6+8=23，偶位数位的和4+1+7=12。23-12=11。因此491678能被11整除。

（11）被12整除的数的特征：一个整数能被3和4整除，则这个数能被12整除。

（12）被13整除的数的特征：若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，这样，一次次下去，直到能清楚判断为止，如果是13的倍数（包括0），则这个数能被13整除。过程为：截尾、倍大、相加、验差。

（13）被17整除的数的特征：若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，这样，一次次下去，直到能清楚判断为止，如果差是17的倍数（包括0），则这个数能被17整除。过程为：截尾、倍大、相减、验差。

（14）被19整除的数的特征：若一个整数的个位数字截去，再从余下的数中，加上个位数的2倍，这样，一次次下去，直到能清楚判断为止，如果是19的倍数（包括0），则这个数能被19整除。过程为：截尾、倍大、相加、验差。

（15）被7、11、13 整除的数的共同特征：若一个整数的末3位与末3位以前的数字所组成的数之差（以大减小）能被7、11、13 整除，则这个数能被7、11、13 整除。

例如：128114，由于128-114=14，14是7的倍数，所以128114能被7整除。64152，由于152-64=88，88是11的倍数，所以64152能被11整除。94146，由于146-94=52，52是13的倍数，所以94146能被13整除。

另外一篇：

整除原理

一、数的整除的特征

（1）1与0的特性：

1是任何整数的约数，即对于任何整数a，总有1|a.

0是任何非零整数的倍数，,a为整数，则a|0.

（2）若一个整数的末位是0、2、4、6或8，则这个数能被2整除。

（3）若一个整数的数字和能被3整除，则这个整数能被3整除。

(4) 若一个整数的末尾两位数能被4整除，则这个数能被4整除。

（5）若一个整数的末位是0或5，则这个数能被5整除。

（6）若一个整数能被2和3整除，则这个数能被6整除。

（7）若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5*2＝49，所以6139是7的倍数，余类推。

（8）若一个整数的未尾三位数能被8整除，则这个数能被8整除。

（9）若一个整数的数字和能被9整除，则这个整数能被9整除。

（10）若一个整数的末位是0，则这个数能被10整除。

（11）若一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除。11的倍数检验法也可用上述检查7的「割尾法」处理！过程唯一不同的是：倍数不是2而是1！

（12）若一个整数能被3和4整除，则这个数能被12整除。

（13）若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，如果差是13的倍数，则原数能被13整除。如果差太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。

（14）若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，如果差是17的倍数，则原数能被17整除。如果差太大或心算不易看出是否17的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。

（15）若一个整数的个位数字截去，再从余下的数中，加上个位数的2倍，如果差是19的倍数，则原数能被19整除。如果差太大或心算不易看出是否19的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。

（16）若一个整数的末三位与3倍的前面的隔出数的差能被17整除，则这个数能被17整除。

（17）若一个整数的末三位与7倍的前面的隔出数的差能被19整除，则这个数能被19整除。

（18）若一个整数的末四位与前面5倍的隔出数的差能被23(或29)整除，则这个数能被23整除

（19）最末两位是25的倍数（00、25、50、75）
任何一个正整数都具有100A+b的形式，其中A是自然数、b是两位的自然数。
因为100A+b=254A+b.254A是25的倍数，如果b是25的倍数，它们的和（原数）就是25的倍数。如果不是25的倍数，那么两项的和（原数），就不是25的倍数。而两位数中只且只有00、25、50、75是25的倍数。

二、判断一个数能否被7整除，有两种方法：

①割尾法：

若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－32＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－92＝595 ， 59－5*2＝49，所以6139是7的倍数，余类推。

割尾法：

证明过程：

又因为21=7*3，所以若p是7的倍数,那么可以得到q是7的倍数

②末三法：

这个数的末三位数与末三位以前的数字所组成的数之差（反过来也行）能被7、11、13整除。这个数就能被7、11、13整除。

例如：1005928

末三位数：928，末三位之前：1005 1005-928=77

因为7 | 77，所以7|1005928

末三法，简略证明：

设一个数为ABCDEF=ABC1000+DEF=ABC1001-ABC+DEF=ABC713*11-(ABC-DEF),由此可见只要ABC-DEF能被7整除，则ABCDEF能被7整除。

三、能被11整除的数的特征

把一个数由右边向左边数,将奇位上的数字与偶位上的数字分别加起来,再求它们的差,如果这个差是11的倍数(包括0),那么,原来这个数就一定能被11整除.

例如:判断491678能不能被11整除.

奇位数字的和9+6+8=23

偶位数位的和4+1+7=12 23-12=11

因此,491678能被11整除.

这种方法叫”奇偶位差法”.

除上述方法外,还可以用割减法进行判断.即:从一个数里减去11的10倍,20倍,30倍.到余下一个100以内的数为止.如果余数能被11整除,那么,原来这个数就一定能被11整除.

又如:判断583能不能被11整除.

用583减去11的50倍(583-11*50=33)余数是33, 33能被11整除,583也一定能被11整除.

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info

Posted on Edited on

带权中位数，百度百科可以看http://baike.baidu.com/view/1209446.htm

/* From: Lich_Amnesia
 * Time: 2014-01-06 20:04:54
 *
 * SGU 114 带权中位数
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"&mdash;&mdash;&ndash;"<<endl

#define maxn 15100
struct node{
    double pos;
    int num;
}p[maxn];
bool cmp(node a,node b){
    return a.pos < b.pos;
}

int main(){
    int n;
    int tot = 0;
    cin >> n;
    for (int i = 0; i < n; i ++){
        scanf("%lf%d",&p[i].pos, &p[i].num);
        tot += p[i].num;
    }
    sort(p, p + n, cmp);
    ++tot /= 2;
    int t = 0;
    for (int i = 0; i < n; i ++){
        t += p[i].num;
        if (t >= tot) {
            printf("%.5fn", p[i].pos);
            break;
        } 
    }
    return 0;
}

Posted on Edited on

主类名必须为Solution，SGU的FAQ里面有写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Solution{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		BigInteger A = BigInteger.valueOf(a);	
		A = A.pow(b);
		BigInteger B = BigInteger.valueOf(b);
		B = B.pow(a);
		System.out.println(A.subtract(B));
	}
}

Posted on Edited on

求出最小的匹配的个数，然后找到需要加多少个，

dp[i,j] 表示着从i到j最少要加多少个，并且path[i,j]表示这个在哪里进行分段。

dp[i,j] = min(dp[i,k] + dp[k+1,j]) k是i到j的遍历，并且要判断i和j是否两个正好匹配，否则dp[i,j]得出来的值需要和dp[i+1,j-1]进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/* From: Lich_Amnesia
 * Time: 2014-01-01 00:03:17
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = 0x7fffffff;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

char str[300];
int dp[300][300];
int path[300][300];

void oprint(int i, int j){
	if (i > j) return;
	if (i == j){
		if (str[i] == '[' || str[i] == ']&#39;){
			printf("[]");
		}else printf("()");
	}else if (path[i][j] == -1) {
		printf("%c", str[i]);
		oprint(i + 1,j - 1);
		printf("%c", str[j]);
	}else {
		oprint(i, path[i][j]);
		oprint(path[i][j] + 1, j);
	}
}

int main(){
	while (gets(str)){
		int n = strlen(str);
		if (n == 0) {printf("n");continue;}
		memset(dp,0,sizeof(dp));
		memset(path,-1,sizeof(path));
		for (int i = 0; i < n; i ++)
			dp[i][i] = 1;
		for (int len = 1; len < n; len ++){
			for (int i = 0; i < n - len; i ++){
				int	j = i + len;//末尾
				dp[i][j] = INF;
				if ((str[i] == '(' && str[j] == &#39;)&#39;) || 
						(str[i] == '[' &&str[j] == ']&#39;)){
					dp[i][j] = dp[i + 1][j - 1];
					path[i][j] = -1;
				}
					for (int k = i; k < j; k++){
						if (dp[i][j] > dp[i][k] + dp[k + 1][j]){
							path[i][j] = k;
							dp[i][j] = dp[i][k] + dp[k + 1][j];
						}
					}  

			}
		}
		oprint(0,n - 1);
		printf("n");
	}
	return 0;
}