kk Blog —— 通用基础


date [-d @int|str] [+%s|"+%F %T"]
netstat -ltunp
sar -n DEV 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

/**
 * 平衡二叉搜索（排序）树
 *
 * 平衡二叉搜索树双称为AVL树，它也是一棵二叉搜索树，是对二叉搜索树的一种改进，或都是具有下列性质的二叉树：它
 * 的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
 *
 * 平衡因子（Balance Factor,BF）定义为该节点的左子树的深度减去其右子树的深度，则平衡二叉树上所有节点的平
 * 衡因子只可能是-1、0和1。只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的了。
 *
 * 使用二叉排序树保持平衡的基本思想是：每当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若
 * 是，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子s树中节点之间的关系，以达
 * 到新的平衡。所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
 *
 * 对于平衡二叉搜索树，保持树的平衡的基本机制就是旋转。旋转是对树的元素顺序进行调节。旋转的目的是消除由于临
 * 时插入和删除对树的平衡产生的影响。
 *
 * 有四种旋转：
 * 1)绕某元素左旋转
 *          80 ← p               90
 *         / \                   / \
 *        60 90 ← r    →         80   120
 *           /\                /\    /
 *         85 120            60 85 100
 *            /
 *          100
 *            
 * 2)绕某元素右旋转
 *      p → 100                      85
 *           /\                      / \
 *     l → 85 120          →         60   100
 *         /\                       \    /\
 *        60 90                     80  90 120
 *         \
 *         80
 *
 * 3)绕某元素的左子节点左旋转，接着再绕该元素自己右旋转。此情况下就是 左旋与右旋 的结合，具体操作时可以分
 * 解成这两种操作，只是围绕点不一样而已
 *
 * 先绕100的左子节点80左旋转，接着再绕100左旋转
 *
 *                左旋                 右旋
 *         100     →     p → 100        →         90
 *         /\                /\                 /\
 *   p → 80 120        l → 90 120            80 100
 *       /\                /                  /\   \
 *     60 90 ← r         80                 60 85  120
 *        /              / \
 *       85             60 85
 *        
 * 4)绕某元素的右子节点右旋转，接着再绕该元素自己左旋转。此情况下就是 右旋与左旋 的结合，具体操作时可以分解
 * 成这两种操作，只是围绕点不一样而已
 *
 * 先绕80的右子节点80右旋转，接着再绕80左旋转
 *                     右旋             左旋
 *          80          →      80 ← p     →       85
 *          /\                /\               /\
 *        60 100 ← p        60 85 ← r        80 100
 *           /\                  \           /    /\
 *     l → 85 120                100        60  90 120
 *          \                     /\
 *           90                 90 120
 *           
 * 平衡二叉树实现类 AVLTree 中的很多方法与排序二叉树是一新的，详细请参考 BinSearchTree 类中相应方法
 *
 * AVLTree中的Entry对象与BinSearchTree中的Entry对象是有区别的，所以AVLTree类不能是BinSearchTree的
 * 了类，虽然很多的方法是一样的（如：contains、getEntry、successor、iterator），还有一些方法（add、de
 * leteEntry）只是在操作后增加了节点平衡因子调整动作，但不能直接继承于它。
 *
 * 二叉搜索树与平衡二叉搜索树没有在Java集合框架中实现，但RED-BLACK树在TreeMap实现过，当然TreeSet也是，
 * 因为它是基于TreeMap实现的，TreeSet对象基本上就是一个忽略了每个元素值部分的TreeMap对象。
 *
 */

dancing links code 6-7

六、pku 3074
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>

using namespace std;

const int MAXN = 1005;
int L[MAXN*MAXN], R[MAXN*MAXN], U[MAXN*MAXN], D[MAXN*MAXN];
int S[MAXN];
int Col[MAXN*MAXN], Row[MAXN*MAXN],Ans[MAXN],ans,limit,up;

void Remove(int c) {
	L[R[c]] = L[c];
	R[L[c]] = R[c];
	for (int i = D[c]; i != c; i = D[i])
		for (int j = R[i]; j != i; j = R[j]) {
			U[D[j]] = U[j];
			D[U[j]] = D[j];
			-- S[Col[j]];
		}
}

void Resume(int c) {
	for (int i = U[c]; i != c; i = U[i])
		for (int j = L[i]; j != i; j = L[j]) {
			U[D[j]] = j;
			D[U[j]] = j;
			++ S[Col[j]];
		}
	L[R[c]] = c;
	R[L[c]] = c;
}

bool dfs(int depth) {
	if(R[0] == 0) { if(depth > ans)ans = depth; return true; }
	int i, j, c, minnum = 1000000000;
	for (i = R[0]; i != 0; i = R[i]) {
		if (S[i] < minnum) {
			minnum = S[i];
			c = i;
		}
	}
	Remove(c);
	for (i = U[c]; i != c; i = U[i]) {
		Ans[depth] = Row[i];
		for (j = R[i]; j != i; j = R[j]) Remove(Col[j]);
		if (dfs(depth + 1)) return true;
		for (j = L[i]; j != i; j = L[j]) Resume(Col[j]);
	}
	Resume(c);
	return false;
}

int solve(int n, int m, int DL[][MAXN]) {
	for (int i = 0; i <= m; i ++) {
		L[i] = i - 1;
		R[i] = i + 1;
		U[i] = D[i] = i;
	}
	L[0] = m;
	R[m] = 0;
	int cnt = m + 1;
	memset(S, 0, sizeof (S));
	for (int i = 1; i <= n; i ++) {
		int head = cnt, tail = cnt;
		for (int c = 1; c <= m; c ++) if (DL[i][c]) {
			S[c] ++;
			Row[cnt] = i;
			Col[cnt] = c;
			U[D[c]] = cnt;
			D[cnt] = D[c];
			U[cnt] = c;
			D[c] = cnt;
			L[cnt] = tail;
			R[tail] = cnt;
			R[cnt] = head;
			L[head] = cnt;
			tail = cnt;
			cnt ++;
		}
	}
	if (dfs(0)) return true;
	return false;
}

int mark[MAXN][MAXN],x[MAXN],y[MAXN],z[MAXN];

int main()
{
	int i,j,k,l,n,m,T,boo,row,col,a[33][33],low,ok1[13][13],ok2[13][13],ok3[13][13],x1,y1,ii,jj;
	int id1[13][13],id2[13][13],id3[13][13],ok[13][13][13];
 
	char ch[999];
	while(scanf("%s",ch) != EOF && strcmp(ch,"end") != 0)
	{
		k = 0;
		for(i=1;i<=9;i++)
			for(j=1;j<=9;j++)
			{
				if(ch[k] != '.') a[i][j] = ch[k] - '0'; else a[i][j] = -1; k++;
			}
  
  
		for(i=1;i<=9;i++)
			for(j=1;j<=9;j++)
			if(a[i][j] == -1)
				for(k=1;k<=9;k++)
				{
					boo = 1;
					for(l=1;l<=9;l++)if(a[l][j] == k)boo = 0;
					for(l=1;l<=9;l++)if(a[i][l] == k)boo = 0;
					x1 = (i-1)/3*3+1; y1 = (j-1)/3*3+1;
	 
					for(ii=x1;ii<x1+3;ii++)
						for(jj=y1;jj<y1+3;jj++)
						if(a[ii][jj] == k)boo = 0;
	 
					ok[i][j][k] = boo;
				}
  
		row = 0; col = 0;
		for(j=1;j<=9;j++)
			for(k=1;k<=9;k++)
			{
				boo = 1;
				for(i=1;i<=9;i++)if(a[i][j] == k)boo = 0;
				if(boo == 1)
				{
					col++; id1[j][k] = col;
				}
				else
					id1[j][k] = -1;
			}
  
		for(i=1;i<=9;i++)
			for(k=1;k<=9;k++)
			{
				boo = 1;
				for(j=1;j<=9;j++)if(a[i][j] == k)boo = 0;
				if(boo == 1)
				{
					col++; id2[i][k] = col;
				}
				else
					id2[i][k] = -1;
			}
   
		for(i=1;i<=9;i++)
		{
			x1 = (i-1)/3*3+1; y1 = (i-1)%3*3+1;
			for(k=1;k<=9;k++)
			{
				boo = 1;
				for(ii=x1;ii<x1+3;ii++)
					for(jj=y1;jj<y1+3;jj++)
					if(a[ii][jj] == k)boo = 0;
				if(boo == 1)
				{
					col++; id3[i][k] = col;
				}
				else id3[i][k] = -1;
			}
		}
  
		for(i=1;i<=9;i++)
			for(j=1;j<=9;j++)
			if(a[i][j] == -1)
				for(k=1;k<=9;k++)
				if(ok[i][j][k] == 1)
				{
					row++; x[row] = i-1; y[row] = j-1; z[row] = k;
					for(ii=1;ii<=col;ii++)mark[row][ii] = 0;
	 
					mark[row][id1[j][k]] = 1;
					mark[row][id2[i][k]] = 1;
					mark[row][id3[(i-1)/3*3+(j-1)/3+1][k]] = 1;
				}
  
		int rr=0;
		for(i=1;i<=9;i++)
			for(j=1;j<=9;j++)
			if(a[i][j] == -1)
			{
				col++; for(k=1;k<=row;k++)mark[k][col] = 0;
				for(k=1;k<=9;k++)
				if(ok[i][j][k] == 1)
				{
					rr++; mark[rr][col] = 1;
				}
			}
 
		ans = 0;
		k = solve(row, col, mark);
   
		for(i=0;i<ans;i++)
		{
			ch[x[Ans[i]]*9+y[Ans[i]]] = z[Ans[i]] + 48;
		}
		printf("%s\n",ch);
  
	}
	return 0;
}
七、pku 3076
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>

using namespace std;

const int MAXN = 2005;
int L[MAXN*MAXN], R[MAXN*MAXN], U[MAXN*MAXN], D[MAXN*MAXN];
int S[MAXN];
int Col[MAXN*MAXN], Row[MAXN*MAXN],Ans[MAXN],ans,limit,up;


void Remove(int c) {
	L[R[c]] = L[c];
	R[L[c]] = R[c];
	for (int i = D[c]; i != c; i = D[i])
		for (int j = R[i]; j != i; j = R[j]) {
			U[D[j]] = U[j];
			D[U[j]] = D[j];
			-- S[Col[j]];
		}
}

void Resume(int c) {
	for (int i = U[c]; i != c; i = U[i])
		for (int j = L[i]; j != i; j = L[j]) {
			U[D[j]] = j;
			D[U[j]] = j;
			++ S[Col[j]];
		}
	L[R[c]] = c;
	R[L[c]] = c;
}

bool dfs(int depth) {
	// printf("ddd = %d  R0 = %d\n",depth,R[0]);
	if(R[0] == 0) { if(depth > ans)ans = depth; return true; }
	int i, j, c, minnum = 1000000000;
	for (i = R[0]; i != 0; i = R[i]) {
		if (S[i] < minnum) {
			minnum = S[i];
			c = i;
		}
	}
	Remove(c);
	for (i = U[c]; i != c; i = U[i]) {
		Ans[depth] = Row[i];
		for (j = R[i]; j != i; j = R[j]) Remove(Col[j]);
		if (dfs(depth + 1)) return true;
		for (j = L[i]; j != i; j = L[j]) Resume(Col[j]);
	}
	Resume(c);
	return false;
}

int solve(int n, int m, int DL[][MAXN]) {
	for (int i = 0; i <= m; i ++) {
		L[i] = i - 1;
		R[i] = i + 1;
		U[i] = D[i] = i;
	}
	L[0] = m;
	R[m] = 0;
	int cnt = m + 1;
	memset(S, 0, sizeof (S));
	for (int i = 1; i <= n; i ++) {
		int head = cnt, tail = cnt;
		for (int c = 1; c <= m; c ++) if (DL[i][c]) {
			S[c] ++;
			Row[cnt] = i;
			Col[cnt] = c;
			U[D[c]] = cnt;
			D[cnt] = D[c];
			U[cnt] = c;
			D[c] = cnt;
			L[cnt] = tail;
			R[tail] = cnt;
			R[cnt] = head;
			L[head] = cnt;
			tail = cnt;
			cnt ++;
		}
	}
	if (dfs(0)) return true;
	return false;
}


int mark[MAXN][MAXN],x[MAXN],y[MAXN],z[MAXN];
int id1[33][33],id2[33][33],id3[33][33],ok[33][33][33];

int main()
{
	int i,j,k,l,n,m,T,boo,row,col,a[33][33],low,ok1[33][33],ok2[33][33],ok3[33][33],x1,y1,ii,jj;
 
	char ch[999],cas=0;
	while(scanf("%s",ch) != EOF)
	{
		cas++; if(cas > 1)printf("\n");
		k = 16;
		for(i=1;i<16;i++)
		{
			scanf("%s",ch+k);
			k += 16;
		}//printf("safdsadfsdf\n");

		k = 0;
		for(i=1;i<=16;i++)
			for(j=1;j<=16;j++)
			{
				if(ch[k] != '-') a[i][j] = ch[k] - 'A'+1; else a[i][j] = -1; k++;
			}
  
		for(i=1;i<=16;i++)
			for(j=1;j<=16;j++)
			if(a[i][j] == -1)
				for(k=1;k<=16;k++)
				{
					boo = 1;
					for(l=1;l<=16;l++)if(a[l][j] == k)boo = 0;
					for(l=1;l<=16;l++)if(a[i][l] == k)boo = 0;
					x1 = (i-1)/4*4+1; y1 = (j-1)/4*4+1;
	 
					for(ii=x1;ii<x1+4;ii++)
						for(jj=y1;jj<y1+4;jj++)
						if(a[ii][jj] == k)boo = 0;
	 
					ok[i][j][k] = boo;
				}
  
		row = 0; col = 0;
		for(j=1;j<=16;j++)
			for(k=1;k<=16;k++)
			{
				boo = 1;
				for(i=1;i<=16;i++)if(a[i][j] == k)boo = 0;
				if(boo == 1)
				{
					col++; id1[j][k] = col;
				}
				else
					id1[j][k] = -1;
			}
 
		for(i=1;i<=16;i++)
			for(k=1;k<=16;k++)
			{
				boo = 1;
				for(j=1;j<=16;j++)if(a[i][j] == k)boo = 0;
				if(boo == 1)
				{
					col++; id2[i][k] = col;
				}
				else
					id2[i][k] = -1;
			}
   
		for(i=1;i<=16;i++)
		{
			x1 = (i-1)/4*4+1; y1 = (i-1)%4*4+1;
			for(k=1;k<=16;k++)
			{
				boo = 1;
				for(ii=x1;ii<x1+4;ii++)
					for(jj=y1;jj<y1+4;jj++)
					if(a[ii][jj] == k)boo = 0;
				if(boo == 1)
				{
					col++; id3[i][k] = col;
				}
				else id3[i][k] = -1;
			}
		}
  
		for(i=1;i<=16;i++)
			for(j=1;j<=16;j++)
		if(a[i][j] == -1)
			for(k=1;k<=16;k++)
		if(ok[i][j][k] == 1)
		{
			row++; x[row] = i-1; y[row] = j-1; z[row] = k;
			//if(i == 1 && j == 7 && k == 4)printf("row ===== %d\n",row);
			for(ii=1;ii<=col;ii++)mark[row][ii] = 0;
	 
			mark[row][id1[j][k]] = 1;
			mark[row][id2[i][k]] = 1;
			mark[row][id3[(i-1)/4*4+(j-1)/4+1][k]] = 1;
		}
  
		int rr=0;
		for(i=1;i<=16;i++)
			for(j=1;j<=16;j++)
			if(a[i][j] == -1)
			{
				col++; for(k=1;k<=row;k++)mark[k][col] = 0;
				for(k=1;k<=16;k++)
				if(ok[i][j][k] == 1)
				{
					rr++; mark[rr][col] = 1;
				}
			}
  
  
		//printf("%d %d\n",row,col);
		//freopen("out.txt","w",stdout);
  
	/* for(i=1;i<=row;i++)
		{
			printf("%d %d %d   ",x[i],y[i],z[i]);
			for(j=1;j<=col;j++)
			printf("%d ",mark[i][j]);
			printf("\n");
		}*/
		//fclose(stdout);
  
		ans = 0;
		k = solve(row, col, mark);
 
	// printf("%d k = %d %d %d\n",ans,id1[7][4],id2[1][4],id3[3][4]);
  
		for(i=0;i<ans;i++)
		{
		// printf("%d   %d %d %d\n",Ans[i],x[Ans[i]],y[Ans[i]],z[Ans[i]]);
			ch[x[Ans[i]]*16+y[Ans[i]]] = z[Ans[i]] + 'A'-1;
		}
		//printf("\n");*/
  
		for(i=0;i<16*16;i++)
		{
			printf("%c",ch[i]);
			if(i!=0 && (i+1)%16 == 0)printf("\n");
		}
	}
	return 0;
}

dancing links code 4-5

四、hdu 3663
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>

using namespace std;

int n,m,DD,a[66][66],s[66],f[66],id[66][6];

const int MAXN = 1005;

int L[MAXN*MAXN], R[MAXN*MAXN], U[MAXN*MAXN], D[MAXN*MAXN];
int S[MAXN];
int Col[MAXN*MAXN], Row[MAXN*MAXN],Ans[MAXN],ans,limit,up;


void Remove(int c) {
	L[R[c]] = L[c];
	R[L[c]] = R[c];
	for (int i = D[c]; i != c; i = D[i])
	for (int j = R[i]; j != i; j = R[j]) {
	    U[D[j]] = U[j];
	    D[U[j]] = D[j];
	    -- S[Col[j]];
	}
}
void Resume(int c) {
	for (int i = U[c]; i != c; i = U[i])
	for (int j = L[i]; j != i; j = L[j]) {
	    U[D[j]] = j;
	    D[U[j]] = j;
	    ++ S[Col[j]];
	}
	L[R[c]] = c;
	R[L[c]] = c;
}

bool dfs(int depth) {
//    printf("ddd = %d  R0 = %d\n",depth,R[0]);
	if(R[0] == 0) { if(depth > ans)ans = depth; return true; }
	int i, j, c, minnum = 1000000000;
	for (i = R[0]; i != 0; i = R[i]) {
	    if (S[i] < minnum) {
	        minnum = S[i];
	        c = i;
	    }
	}
	Remove(c);
	for (i = U[c]; i != c; i = U[i]) {
	    Ans[depth] = Row[i];
	    for (j = R[i]; j != i; j = R[j]) Remove(Col[j]);
	    if (dfs(depth + 1)) return true;
	    for (j = L[i]; j != i; j = L[j]) Resume(Col[j]);
	}
	Resume(c);
	return false;
}
int solve(int n, int m, int DL[][MAXN]) {
	for (int i = 0; i <= m; i ++) {
	    L[i] = i - 1;
	    R[i] = i + 1;
	    U[i] = D[i] = i;
	}
	L[0] = m;
	R[m] = 0;
	int cnt = m + 1;
	memset(S, 0, sizeof (S));
	for (int i = 1; i <= n; i ++) {
	    int head = cnt, tail = cnt;
	    for (int c = 1; c <= m; c ++) if (DL[i][c]) {
	        S[c] ++;
	        Row[cnt] = i;
	        Col[cnt] = c;
	        U[D[c]] = cnt;
	        D[cnt] = D[c];
	        U[cnt] = c;
	        D[c] = cnt;
	        L[cnt] = tail;
	        R[tail] = cnt;
	        R[cnt] = head;
	        L[head] = cnt;
	        tail = cnt;
	        cnt ++;
	    }
	}
	if (dfs(0)) return true;
	return false;
}


int mark[MAXN][MAXN],x[MAXN],y[MAXN],z[MAXN];

int main()
{
	int i,j,k,l,row,col,g;
	while(scanf("%d %d %d",&n,&m,&DD) != EOF)
	{
	    for(i=1;i<=n;i++)
	        for(j=1;j<=n;j++)
	        {
	            a[i][j] = 0;
	            if(i == j)a[i][j] = 1;
	        }
	    while(m--) {
	        scanf("%d %d",&j,&k);
	        a[j][k] = a[k][j] = 1;
	    }
	    for(i=1;i<=n;i++)scanf("%d %d",&s[i],&f[i]);
	   
	    col = 0;
	    for(i=1;i<=n;i++)
	        for(j=1;j<=DD;j++)
	            id[i][j] = ++col;
	   
	    row = 0;
	    for(i=1;i<=n;i++)
	    {
	        for(j=s[i];j<=f[i];j++)
	            for(k=j;k<=f[i];k++)
	            {
	                row++; x[row] = j; y[row] = k; z[row] = i;
	                for(l=1;l<=col;l++)mark[row][l] = 0;
	               
	                for(l=1;l<=n;l++)if(a[i][l] == 1)
	                {
	                    for(g=j;g<=k;g++) mark[row][id[l][g]] = 1;
	                }
	            }
	    }
	   
	    int rr=0;
	   
	    for(i=1;i<=n;i++)
	    {
	        col++;
	        for(j=1;j<=row;j++)mark[j][col] = 0;
	       
	        for(j=s[i];j<=f[i];j++)
	            for(k=j;k<=f[i];k++)
	            {
	                rr++;
	                mark[rr][col] = 1;
	            }
	    }
	   
	    int TT = row;
	    for(i=1;i<=n;i++)
	    {
	        row++;
	        for(j=1;j<=col;j++)mark[row][j] = 0;
	        mark[row][col-n+i] = 1;
	    }
	   
	    ans = 0;
	   
	    k = solve(row, col, mark);
	   
	    if(k == 0)
	        printf("No solution\n");
	    else
	    {
	        for(i=1;i<=n;i++)s[i] = f[i] = 0;
	        for(i=0;i<ans;i++)
	        if(Ans[i] <= TT)
	        {
	            s[z[Ans[i]]] = x[Ans[i]];
	            f[z[Ans[i]]] = y[Ans[i]];
	        }
	        for(i=1;i<=n;i++)printf("%d %d\n",s[i],f[i]);
	    }
	    printf("\n");
	}
	return 0;
}
五、hdu 2995
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>

using namespace std;

const int MAXN = 225;
int L[MAXN*MAXN], R[MAXN*MAXN], U[MAXN*MAXN], D[MAXN*MAXN];
int S[MAXN];
int Col[MAXN*MAXN];
int limit;

void Remove(int x) {
	for (int i = D[x]; i != x; i = D[i]) {
		L[R[i]] = L[i];
		R[L[i]] = R[i];
	}
}
void Resume(int x) {
	for (int i = U[x]; i != x; i = U[i]) {
		L[R[i]] = R[L[i]] = i;
	}
}
int Hash() {
	int ans = 0;
	bool hash[MAXN] = {0};
	for (int c = R[0]; c != 0; c = R[c])
	if (! hash[c]) {
		hash[c] = true;
		ans ++;
		for (int i = D[c]; i != c; i = D[i])
			for (int j = R[i]; j != i; j = R[j])
				hash[Col[j]] = true;
	}
	return ans;
}

bool dfs(int depth) {
	if (depth + Hash() > limit) return false;
	if (R[0] == 0) return true;
	int i, j, c, minnum = 2000000000;
	for (i = R[0]; i != 0; i = R[i]) {
		if (S[i] < minnum) {
			minnum = S[i];
			c = i;
		}
	}
	for (i = U[c]; i != c; i = U[i]) {
		Remove(i);
		for (j = R[i]; j != i; j = R[j]) Remove(j);
		if (dfs(depth + 1)) {
			for (j = L[i]; j != i; j = L[j]) Resume(j);
			Resume(i);
			return true;
		}
		for (j = L[i]; j != i; j = L[j]) Resume(j);
		Resume(i);
	}
	return false;
}

int solve(int n, int m, int DL[][MAXN], int maxdepth) {
	if (maxdepth > n) maxdepth = n;
	for (int i = 0; i <= m; i ++) {
		L[i] = i - 1;
		R[i] = i + 1;
		U[i] = D[i] = i;
	}
	L[0] = m;
	R[m] = 0;
	int cnt = m + 1;
	memset(S, 0, sizeof (S));
	for (int i = 1; i <= n; i ++) {
		int head = cnt, tail = cnt;
		for (int c = 1; c <= m; c ++) if (DL[i][c]) {
			S[c] ++;
			Col[cnt] = c;
			U[D[c]] = cnt;
			D[cnt] = D[c];
			U[cnt] = c;
			D[c] = cnt;
			L[cnt] = tail;
			R[tail] = cnt;
			R[cnt] = head;
			L[head] = cnt;
			tail = cnt;
			cnt ++;
		}
	}
	int best = 0, worst = maxdepth;
	/*while (best <= worst) {
		limit = (worst + best) >> 1;
		if (dfs(0)) worst = limit - 1;
		else best = limit + 1;
	}*/
	limit = maxdepth;
	if(dfs(0))best = maxdepth;
	else
		best = maxdepth+1;
	return best;
}

int x[155],y[155];

int dij(int i, int j)
{
	int d1 = (x[i]-x[j])*(x[i]-x[j]);
	int d2 = (y[i]-y[j])*(y[i]-y[j]);
	return d1+d2;
}

int main()
{
	int i,j,k,l,row,col,n,m,low,up,mid,mark[MAXN][MAXN],d[55][55],T,b[3000],top;
 
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d %d",&n,&row,&m);

		for(i=1;i<=n+row;i++)
			scanf("%d %d",&x[i],&y[i]);
 
		low = 1; up = 1000000000;

		while(low < up)
		{
			for(i=1;i<=row;i++)
				for(j=1;j<=n;j++)mark[i][j] = 0;
   
			mid = (low + up)>>1;
			for(i=1;i<=row;i++)
				for(j=1;j<=n;j++)if(dij(i+n,j) <= mid)mark[i][j] = 1;
	
			if(solve(row, n, mark, m) > m)low = mid+1; else up = mid;
		}
		mid = (low + up)>>1;
		printf("%.6lf\n",sqrt(1.0*mid));
	}
	return 0;
}