kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

MySQL 最常用命令

登录到mysql中,然后在mysql的提示符下运行命令,每个命令以分号(;)结束。

一:mysql服务的启动和停止
1
2
sudo /etc/init.d/mysql stop   // net stop mysql
sudo /etc/init.d/mysql start   // net start mysql
二:登陆mysql

语法如下: mysql -u用户名 -p用户密码
命令 mysql -uroot -p , 回车后提示你输入密码,输入12345,然后回车即可进入到mysql中了,mysql的提示符是:
mysql>
注意,如果是连接到另外的机器上,则需要加入一个参数-h机器IP

三:增加新用户

格式:grant 权限 on 数据库.* to 用户名@登录主机 identified by “密码” 如,增加一个用户user1密码为password1,让其可以在本机上登录, 并对所有数据库有所有的权限。首先用以root用户连入mysql,然后键入以下命令:

1
grant all privileges on *.* to user1@localhost Identified by "password1";

如,增加一个用户user1密码为password1,让其可以在本机上登录, 并对abc数据库有查询、插入、修改、删除的权限。首先用以root用户连入mysql,然后键入以下命令:

1
grant select,insert,update,delete on abc.* to user1@localhost Identified by "password1";

如果希望该用户能够在任何机器上登陆mysql,则将localhost改为"%“。 如果你不想user1有密码,可以再打一个命令将密码去掉。

1
grant select,insert,update,delete on abc.* to user1@localhost dentified by "";
四:显示数据库列表。
1
show databases;  

缺省数据库:mysql。 mysql库存放着mysql的系统和用户权限信息,我们改密码和新增用户,实际上就是对这个库进行操作。

五:建库与删库:
1
2
create database 库名;
drop database 库名;
六:显示库中的数据表:
1
2
use abc;
show tables;
七:显示数据表的结构:
1
describe 表名;
八:建表与删表:
1
2
3
4
use abc;
create table 表名(字段列表);
drop table 表名;
如:create table imformation(name varchar(11), age int(5));
九:清空表中记录:
1
delete from 表名;
十:显示表中的记录:
1
select * from 表名;
十一:增加一个字段:
1
2
3
4
5
6
7
8
alter table table_name add column <字段名><字段选项>
alter table imformation add phone varchar(5);
觉得5太小,修改为15
修改字段:   
alter table table_name change <旧字段名> <新字段名><选项>
alter table imformation change phone phone varchar(15);
增加几个字段:
alter table imformation add authors varchar(100),add category varchar(20);
十二:删除一个字段:
1
2
alter table table_name drop column <字段名>
alter table imformation drop authors;
十三:插入记录:
1
2
insert into 表名称(字段名1,字段名2…) values (字段1的值,字段2 的值,…);
insert into imformation(name,phone) values('a1','123456789');
十四:修改记录:
1
2
update imformation set column_name1="" where column_name2="";
update imformation set phone="987654321" where name="a1";
十五:删除记录:
1
2
delete from 表名称 where 条件表达式;
delete from imformation where name="a2";
十六:查看建表信息:
1
show create table imformation\G;  大写G
十七:某个字段不同值的数目:
1
SELECT tid,count(tid) as tnum FROM TABLE group by tid order by tnum DESC;   DESC降序,ASC升序。
十八:不同id的status=0的数目:
1
SELECT id,count(*) AS tnum FROM TABLE WHERE id IN (id1, id2, id3, ...) AND status=0 GROUP BY id;
十九:替换函数
1
UPDATE `table_name` SET `field_name` = replace (`field_name`,'from_str','to_str') WHERE `field_name` LIKE '%from_str%'
二十:如何清除输入过的mysql命令

清空用户目录下的.mysql_history

平衡二叉树

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;
}