kk Blog —— 通用基础

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

分段排序网络 Bitonic Sort

分段排序网络 Bitonic Sort

我们之前所有的排序算法都是给定了数据再进行排序，排序的效率很大程度上取决于数据的好坏。我们今天所介绍的是一个完全不同的排序方法，它可以在“暗箱”里对数据进行排序（即你不必知道实际数据是什么），换句话说这种排序方法不依赖于数据(Data-Independent)，所有比较操作都与数据无关。你甚至可以立即忘掉前面的比较结果，因为对于所有可能的数据这类排序算法都能得到正确答案并且排序步骤完全相同。本文结束后再回过头来看这段话你将有更深的认识。

我们设置一个暗箱，暗箱左边有n个输入口，暗箱右边有n个输出口。我们需要设计一个暗箱使得，任意n个数从左边输进去，右边出来的都是有序的。图1显示了有4个输入的暗箱。

暗箱里唯一允许的元件叫做“比较器”(Comparator)，每个比较器连接两个元素，当上面那个比下面那个大时它将交换两个元素的位置。也就是说，每经过一个比较器后，它的两端中较小的一个总是从上面出来，较大的总是到了下面。图2显示了一种包含4个比较器的暗箱系统。当输入数据3,1,4,2通过这个系统时，输出为1,3,2,4，如图3所示。这种暗箱结构叫做比较网络(Comparator Network)。如果对于任意一个输入数据，比较网络的输出都是有序的，那么这个比较网络就叫做排序网络(Sorting Network)。显然，我们例子中的比较网络不是一个排序网络，因为它不能通过3,1,4,2的检验。

现在，我们的第一个问题是，是否存在比较网络。就是说，有没有可能使得任意数据通过同一组比较器都能输出有序的结果。我们最初的想法当然是，把我们已知的什么排序算法改成这种形式。把原来那十种排序又翻出来看一遍，找一找哪些排序的比较操作是无条件的。运气不错，我们所学的第一个算法——冒泡排序，它的比较就是无条件的，不管数据怎样冒泡排序都是不断比较相邻元素并把较小的放到前面。冒泡排序是一个彻头彻尾的排序网络模型，我们可以立即画出冒泡排序所对应的排序网络（图4）。这是我们得到的第一个排序网络。我们通常不认为插入排序是排序网络，因为插入排序的比较次数取决于数据的有序程度。

传统的计算机一次只能处理一个比较。排序网络真正的研究价值在于，假如有机器可以同时处理多个比较器，排序的速度将大幅度提高。我们把比较器的位置稍微移动一下，把那些互不冲突（处理的元素不同）的比较器压缩到一层(Stage)（图5），这样整个排序过程压缩为了2n-3层。实现排序网络的机器可以在单位时间里并行处理同一层中所有的比较。此时，比较次数的多少对排序效率不起决定作用了，即使比较次数多一些但是排序网络的层次更少，效率也会更高一些。我们自然又想，排序网络需要的层数能否少于2n-3。我们想到，图5的左下角和右下角似乎有些空，我们期望能在这些位置加一些比较从而减少层数。图6给出了一个只有n层的排序网络，这叫做奇偶移项排序(Odd-even Transposition Sort)。我们下文将证明它确实是一个排序网络。这次的图很多，排版也很困难，累死我了。我把下面的图7也放到这里来了，不然到处都是图很难看。

给出一个比较网络，怎样判断它是不是一个排序网络？很遗憾，现在还没有找到一种好的算法。事实上，这个问题是一个NPC问题。注：这种说法是不准确的，因为目前还没有迹象表明这个问题是NP问题。准确的说法应该是，“判断某比较网络为排序网络”是Co-NP Complete，而“判断某比较网络不是排序网络”（即找到一个反例）才是NP Complete。

传统的做法是枚举所有n的排列来验证，一共要考虑n!种情况。下面我们介绍排序网络理论里最重要的结论：0-1原理(0-1 Principle)。使用这个原理来验证排序网络只需要考虑2n种情况。0-1原理告诉我们，如果所有的01序列能够通过比较网络排出顺序，那么这足以说明该网络为排序网络。证明过程很简单。为了证明这个结论，我们证明它的逆否命题（逆否命题与原命题同真假）：如果一个比较网络不是排序网络，那么至少存在一个01序列不能被排序。我们给出一种算法，这个算法可以把任何一个不能被排序的输入数据转化为一个不能被排序的01序列。

在最初的例子（图3）中，输入数据3,1,4,2的输出为1,3,2,4，没有成功地排出顺序，从而判断出该网络不是排序网络。这说明，输出结果中存在逆序对（左边某个数大于右边的某个数）。我们从输出结果中找出一个逆序对来。例子中，(3,2)就是我们要找的数。现在，我们把输入中所有小于数字3（左边那个数）的数都变成0，把所有大于等于3的数都变成1。这样，3,1,4,2就变成了1,0,1,0。显然，把得到的这个01序列输入进去，原来曾经发生过交换的地方现在仍然会交换，原来不曾交换的地方现在也同样不会发生交换（当两个0或两个1进行比较时，我们既可以认为它们不交换，也可以看成它们要互相交换，反正都一样）。最后，该01序列输出的结果中，本来3的位置现在还是1，原来2的位置现在仍然是0，逆序对仍然存在。因此，只要一个比较网络不是排序网络，那么总可以找到一个01序列不能被排序。等价地，如果所有的01序列都能被排序了，这个比较网络也就是排序网络了。

我们用0-1原理来证明奇偶移项排序的正确性。我们对n进行数学归纳证明。n=2时（一个“工”字）显然是排序网络。

图中是n=8的情况。我们假设对于所有n<=7，奇偶移项排序网络都是正确的。我们同时假定所有输入数字非0即1，下面我们说明n=8时所有的01序列都能被正确排序。

假设最后一个数是1（图7，在前面的），那么这个1将始终排在最后不参与任何交换操作，对前面7个数没有任何影响。除去无用的灰色部分，剩下的就是n=7这一规模较小的子排序网络，由归纳假设则n=8也是排序网络；

假设最后一个数是0（图8），那么在每一次比较中这个0都会被提到前面去（前面说过，两个0之间交不交换是一回事）。蓝色的箭头表示每个数跑到了什么位置。你会发现除最后一个数以外前7个数之间的比较器又构成了n=7的情况。

接下来，我们提出一些比较器个数为O(nlognlogn)的排序网络。其中一种就是之前提到过的2p3q增量Shell排序。这种增量排序的特点是每一趟排序中的每个数只与前面的数比较一次，因此它可以非常方便地转化为排序网络。图9就是一个n=8的Shell排序网络。Bitonic排序也可以做到O(nlogn*logn)的比较器个数，今天不介绍它。下面详细介绍奇偶归并排序网络。

奇偶归并排序网络也是一种比较器个数为O(nlognlogn)的排序网络。它和归并排序几乎相同，不同的只是合并的过程。普通归并排序的O(n)合并过程显然是依赖于数据的，奇偶归并排序可以把这个合并过程改成非数据依赖型，但复杂度将变高。这个合并过程本身也是递归的。我们假设n是2的幂（不是的话可以在前面添0补足，这对复杂度的计算没有影响），算法首先把n个数中所有的奇数项和偶数项分别递归地合并，然后在排序后的第i个偶数项和第i+1个奇数项之间设立比较器。

假如1,4,6,8和2,3,7,9是两段已经有序的子序列，合并过程首先递归地合并1,6,2,7和4,8,3,9，这样原数列就变成了1,3,2,4,6,8,7,9。然后分别把(3,2),(4,6),(8,7)三对相邻元素中各自较小的那个交换到前面，完成合并操作。使用0-1原理证明这个结论出乎意料的简单：图10显示了n=16的情况，白色的方格代表一个0，灰色方格代表1。奇偶项分别排序后，偶数项1的个数最多比奇数项多出2个，我们设立的比较器可以考虑到所有的情况，不管什么情况都能让它最终变得有序。

由前面说过的结论，合并过程总共需要比较O(nlogn)次。归并排序递归一共有O(logn)层，每一层总的比较器个数不超过O(nlogn)，因此总共O(nlognlogn)。一个n=8的完整的奇偶归并排序网络如图11所示。

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

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
int M;

void BitonicMerge(int* data, int s, int len, int sta)
{
	if(len < 2) return;
	int k;
	for(k=1;k<len;k=k<<1); k>>=1;
	int i;
	int tmp;
	for(i=s;i<s+len-k;i++)
	    if(sta == data[i]>data[i+k])
	    {
	        tmp = data[i];
	        data[i] = data[i+k];
	        data[i+k] = tmp;
	    }
	BitonicMerge(data, s, k, sta);
	BitonicMerge(data, s+k, len-k, sta);
}

void BitonicSort(int* data, int s, int len, int sta)
{
	if(len>1)
	{
	    int mid=len/2;
	    BitonicSort(data, s, mid, 1-sta);
	    BitonicSort(data, s+mid, len-mid, sta);
	    BitonicMerge(data, s, len, sta);
	}
}

void BitonicSort_(int* data, int n)
{
	int i,j,k,l,len,flag,sta,ll,kk,cou;
	int tmp;

	for(flag = 0, len=1;len<n;len<<=1) flag = 1-flag; // flag == 1 ascending
	for(len=1;len<n;len<<=1)
	{
	    cou = 0;
	    for(i=0;i<n;i+=len*2)
	    {
	        sta = flag; for(ll=0;(1<<ll)<=cou;ll++) if((cou&(1<<ll)) != 0) sta = 1-sta;
	        for(ll=len;ll>=1;ll>>=1)
	        {
	            for(j=i;j+ll<i+len*2; j+=ll*2)
	            {
	                kk = ll*2; if(i+len*2-j < kk) kk = i+len*2-j; if(n-j < kk) kk = n-j;
	                for(k=j;k<j+kk-ll;k++)
	                    if(sta == (data[k] > data[k+ll]))
	                    {
	                        tmp = data[k];
	                        data[k] = data[k+ll];
	                        data[k+ll] = tmp;
	                    }
	            }
	        }
	        cou++;
	    }
	    flag = 1-flag;
	}
}

int main()
{
	for(M = 1;M<=100;M++)
	{
	    int i,j,k,l,tim=1000;

	    int n=M;
	    int m;

	    int a[M],data[M],b[M];
	    int seg_id[M];
	    int seg_start[2]={0,M};

	    int no = 0;

	    while(tim--)
	    {
	        for(i=0;i<n;i++) data[i] = a[i] = b[i] = rand()%100;

	        for(i=0;i<n;i++) seg_id[i] = 0;
	        seg_start[0] = 0;
	        seg_start[1] = M;
	        m = 1;
	        
	        BitonicSort_(data, n);   // 非递归
	        BitonicSort(b, 0, n, 1); // 递归
	        sort(a, a+n);
	        
	        // for(i=0;i<n;i++) printf("%.0f ",b[i]); printf("\n");
	        // for(i=0;i<n;i++) printf("%.0f ",a[i]); printf("\n");
	        
	
	        k = 1;
	        for(i=0;i<n;i++) if(a[i] != data[i] || b[i] != a[i]) k = 0;
	        if(k == 0) no++;
	        // if(k == 1) printf("YES\n"); else  printf("NO\n");
	    }
	    printf(" M = %d  NO = %d\n",M,no);
	}
	return 0;
}
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

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

#define M 10000

void BitonicMerge(int* data, int s, int len, int sta)
{
	if(len < 2) return;
	int k;
	for(k=1;k<len;k=k<<1); k>>=1;
	int i;
	int tmp;
	for(i=s;i<s+len-k;i++)
	    if(sta == data[i]>data[i+k])
	    {
	        tmp = data[i];
	        data[i] = data[i+k];
	        data[i+k] = tmp;
	    }
	BitonicMerge(data, s, k, sta);
	BitonicMerge(data, s+k, len-k, sta);
}

void BitonicSort(int* data, int s, int len, int sta) // 递归
{
	if(len>1)
	{
	    int mid=len/2;
	    BitonicSort(data, s, mid, 1-sta);
	    BitonicSort(data, s+mid, len-mid, sta);
	    BitonicMerge(data, s, len, sta);
	}
}

void BitonicSort_(int* data, int n) // 非递归
{
	int i,j,k,l,len,flag,sta,ll,kk,cou;
	int tmp;

	for(flag = 0, len=1;len<n;len<<=1) flag = 1-flag; // flag == 1 ascending
	for(len=1;len<n;len<<=1)
	{
	    cou = 0;
	    for(i=0;i<n;i+=len*2)
	    {
	        sta = flag; for(ll=0;(1<<ll)<=cou;ll++) if((cou&(1<<ll)) != 0) sta = 1-sta;
	        for(ll=len;ll>=1;ll>>=1)
	        {
	            for(j=i;j+ll<i+len*2; j+=ll*2)
	            {
	                kk = ll*2; if(i+len*2-j < kk) kk = i+len*2-j; if(n-j < kk) kk = n-j;
	                for(k=j;k<j+kk-ll;k++)
	                    if(sta == (data[k] > data[k+ll]))
	                    {
	                        tmp = data[k];
	                        data[k] = data[k+ll];
	                        data[k+ll] = tmp;
	                    }
	            }
	        }
	        cou++;
	    }
	    flag = 1-flag;
	}
}

int main()
{
	int i, n;
	int data[M];
	int seg_id[M];
	int seg_start[2];

	// 输入
	scanf("%d", &n);
	for(i=0;i<n;i++) scanf("%d", &data[i]);
	
	// 只分一段
	for(i=0;i<n;i++) seg_id[i] = 0;
	seg_start[0] = 0;
	seg_start[1] = n;
	
	//BitonicSort_(data, n);   // 非递归
	BitonicSort(data, 0, n, 1); // 递归

	for(i=0;i<n;i++) printf("%d%c", data[i], i==n-1?'\n':' ');
	return 0;
}

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