2014亚洲区鞍山H题研究
作者: | 更新日期:
亚洲区比赛又开始了，于是看了看鞍山现场赛的题，发现 H题挺有意思的，于是研究了一番。
本文首发于公众号：天空的代码世界，微信号：tiankonguse
题目
题目具体看 
简单的说就是告诉你三个01数对应的答案表, 让你求最少的步骤来得到这个答案表.
每个步骤只能使用 NAND(a,b) 操作.
NAND(a,b) 操作代表 !(b&&c) 运算.
问题转换
我们单独一位一位的看, 看不出眉目来. 但是整体来看, 即传入的三个数不是01数字, 而是三个8位01的数字, 那么经过 NAND(a,b) 操作, 返回8位要求的答案表即可.
这时 NAND(a,b) 操作 操作就 ~(b&c) 了.
开始搜索
问题转化后, 发现使用一个优先队列搜索就行了.
8位整数类型
但是第一步是定义一个8位的数字.
typedef unsigned char uchar;
结构体封装
然后定义结构体如下
struct T {
vector<uchar>str;
int n;//起初用的 int[]数组
int ans;
bool operator<(const T t)const {
return ans > t.ans;
}
};
字符串转化8位整数
//00010011 => 19
uchar toUchar(const char* str) {
uchar ans = 0;
while(*str) {
ans = (ans<<1) | (*str++ -'0');
}
return ans;
}
NAND 运算
inline uchar NAND(uchar a, uchar b) {
return ~(a&b);
}
初始化
有了这些准备, 我们就可以开始搜索了.
不过搜索前需要准备一下初始条件.
由于 NAND 可以有常量, 即0与1, 转化为整数也就是0 与255了. 再加上a,b,c三个常量, 我们共有5个常量.
int a,b,c, zero, one;
a = toUchar("00001111");
b = toUchar("00110011");
c = toUchar("01010101");
zero = toUchar("00000000");
one = toUchar("11111111");
另外队列的第一个元素需要有上面5个常量, 于是把他们加进去.
我把这个初始化封装在 T 中了, 虽然只能初始化一次.
另外还封装了一个动态添加元素的 add 函数.
struct T {
void init() {
str.clear();
n = 0;
ans = 1;
add(a);
add(b);
add(c);
add(one);
add(zero);
}
void add(uchar a) {
str.push_back(a);
n++;
}
};
直观优化
have 优化
当一个元素出队时, 假设有n个不同的数字, 则会搜出 C(n,2) 个数字, 我们需要加入不在n个数字中的数字.
于是我在 T 中加入一个 have 数组.
struct T {
bool have[N];
};
但是后来发现内存不够, 于是把 have 数字提取出来, 每次出队时生成 have 数组.
now = que.top();
que.pop();
tmpn = now.n;
memset(have, false, sizeof(have));
for(int i=0; i<now.n; i++) {
have[now.str[i]] = 1;
}
这样, 循环的得到新的数字后只需要判断一下是否重复已经存在即可.
for(int i=0; i<tmpn; i++) {
for(int j=i+1; j<tmpn; j++) {
tmpNAND = NAND(now.str[i], now.str[j]);
if(have[tmpNAND]) {
continue;
}
have[tmpNAND] = true;
//其他代码...
}
}
map 优化
后来发现, 得到数字 a1,a2 和得到数字 a2,a1 是等价的, 但是由于在不同的分支中, 我们不能直接去重, 所以我加了一个map来判断.
数字范围为0~255,一字节可以储存8位, 所以需要 256/8 = 32 字节的字符串来保存.
又由于字符串以0为结尾, 所以我们不能有0这个字节, 所以我采用一个字节用7位来保存信息，最高位至1, 这样有 256/7 = 37 字节.
map<string,bool>bit;
void toString(const T&t, char* str) {
int now;
for(int i=0; i<t.n; i++) {
now = t.str[i];
str[now/7] |= 1<<(now % 7);
}
}
bool haveString(const T& t) {
char str[50];
memset(str, 0, sizeof(str));
toString(t, str);
for(int i=0; i<38; i++) {
str[i] |= (1<<7);
}
if(bit.find(str) == bit.end()) {
bit[str] = 1;
return false;
} else {
return true;
}
}
for(int i=0; i<tmpn; i++) {
for(int j=i+1; j<tmpn; j++) {
tmpNAND = NAND(now.str[i], now.str[j]);
if(have[tmpNAND]) {
continue;
}
have[tmpNAND] = true;
newT = now;
newT.add(tmpNAND);
if(haveString(newT)) {
continue;
}
}
}
时间上的一个小优化
上面的have 数组从结构体中提取出来, 然后又加了map后, 发现跑的挺慢的, 于是向能不能提高速度, 发现有个地方可以优化.
放出队后, 我们又n个数字, 然后会双层循环去得到所有的合法值.
其实这n个值中, 假设标号为0到n-1,只有第n-1个数字数新加进入的.
也就是说前面的n-1个数字可能已经两两运算过了.
所以我加了一个直接从起始位置开始循环的优化
struct T {
int start;//默认值0
}
for(int i=now.start; i<tmpn; i++) {
for(int j=i+1; j<tmpn; j++) {
tmpNAND = NAND(now.str[i], now.str[j]);
if(have[tmpNAND]) {
continue;
}
have[tmpNAND] = true;
newT = now;
newT.add(tmpNAND);
newT.start = now.start+1;
if(haveString(newT)) {
continue;
}
if(tmpNAND == d) {
return now.ans;
}
que.push(newT);
}
}
但是得到的答案是错误的, 经过分析发现循环内, 对于新加入队列的值来说, 只新增了一个值.
意思也就是虽然依旧有n-1个旧值, 对应着 C(n-1, 2) 可能值, 但是产生新值时还有很多是没有遍历的, 即有些值被遗漏了.
那怎么做才能做到 now.start 之前的值全部已访问过, 或者不遗漏未访问的呢？
发现调整一下循环, 就可以做到了.
for(int i=now.start; i<tmpn; i++) {
for(int j=0; j<i; j++) {
tmpNAND = NAND(now.str[i], now.str[j]);
if(have[tmpNAND]) {
continue;
}
have[tmpNAND] = true;
newT = now;
newT.add(tmpNAND);
newT.start = i;
if(haveString(newT)) {
continue;
}
if(tmpNAND == d) {
return now.ans;
}
que.push(newT);
}
}
我们对于now.start之前的都遍历过了, 所以没必要再次对now.start之前的遍历了, 而对于没有遍历的和新增的, 之后还会遍历.
这样优化后复杂度有 O(n\^3) 降为 O(n\^2) 了.
不过综合复杂度还是很大很大. 这个只算是常数优化, 因为 n 目前最大是10.
目前的结果
经过上面的优化, 对于0到255这些值, 只有104不能跑出来, 其他的全部可以跑出来了.
数据可以参考这里 打表数据 .
ps: 2014-10-20 19:48:00 已经把所有结果跑出来了，详见这里 完整数据1
还可以做得优化
其实还可以做得优化还有几个地方.
优先队列优化
后来发现先进入的一定比后进入的ans小，所以使用队列就行了。
map 优化
第一个是那个 map, 我们使用的内存是 38 * 2\^256, 我们可以优化为 tire(字典树), 这样内存变为 2\^256/8 ,算是节省100倍内存吧.
实际上我们需要的内存远远小于, 而且字典树也不容易做到压位, 所以实际节省内存大概是4~6倍.
错误的优化map
由于map最坏情况下空间也是指数级的，所以我就想着能不能优化这个map。
然后还真想出一个方法来。
用一个256位的数据结构来保存某个数字是否出现过。
const int bitLen=4;
ULL bit[bitLen];
void toBit(const T&t, ULL* bit) {
int now;
ULL one = 1;
for(int i=0; i<t.n; i++) {
now = t.str[i];
bit[now>>6] |= (one<<(now & 63));
}
}
void initBit(ULL* bit) {
for(int i=0; i<bitLen; i++) {
bit[i] = 0;
}
}
void setBit(const T&t, ULL* bit) {
ULL str[bitLen];
initBit(str);
toBit(t, str);
for(int i=0; i<bitLen; i++) {
bit[i] |= str[i];
}
}
bool haveString(const T& t) {
ULL str[bitLen];
initBit(str);
toBit(t, str);
for(int i=0; i<bitLen; i++) {
if((bit[i] & str[i]) != str[i]) {
bit[i] |= str[i];
return false;
}
}
return true;
}
主要是上面的 haveString 函数，用于判断这个 T 是否出现过，如果出现过，应该和 bit 位运算 与 之后的0.
如果是新增的 T, 则应该只有一位和 bit 不同，把新增的那一位加入到bit即可。
但是悲剧是发现跑出的答案和以前的答案不同。
分析后发现这个方案完全不行，假设在第n层可以得到a和b,我们会把a和b标志位出现过，然后到a的n+1层了，假设又出现b了，对于a这个分支，b是未出现的，但是我们已经把b标记为出现了，所以问题就来了。
tire 树优化 这个map 也不一定可行，或者实现比较复杂。
因为来一个 a,b 和来一个 b,a 实际上是等价的，但是我们的 tire 是不等价的。
所以这里就需要给 tire 树排序了，这就需要在新增数据的时候，对树进行调整。
也可以实现，还是log 级，但是常数大了点。
原来写个 tire 树来优化 map 也是不容易的呀。
数组优化
我们看到, T 中使用的 vector, 实际上我们新增一个 T 后, 相对于父节点, 我们只是新增了一个数值, 所以也可以作为 tire(字典树)优化.
这里节省内存大概节省几倍倍内存.
这个 tire 树倒是可行，实际上也不能称为 tire 树，我们新增一个节点的复杂度不是 log 级，而是 O(1) 级，只需要指定父节点即可。
要得到当时数组的所有数字，需要从叶子顺着去头部，这更像链表。
偷懒的做法
实际上我们只剩下一个没有打表计算出来, 而那个值大概也就可能是9或10, 最坏情况下是11.
我们可以尝试提交三次, 谁ac了, 答案就是谁, 这样就知道答案是几了.
另一个优化
实际上上面两个优化节省十几倍的内存, 应该可以跑出最后那个答案了, 但是为了可靠, 我们可以使用 IDA* 来优化.
因为我们现在只剩下一个了, 其他的最大在9层, 所以这个最后的答案应该也在9或者10层.
而一层我们只增加一个数组, 所以大概有15个数字, 暴力递归来找的话, 也没多少.
但是说到这里, 一种新的做法出来了 IDA* .
质的变化
上面虽然在各种优化，但还是 bfs 搜索。
但是最后发现可以递归若干层来找答案，这就转向了另一个算法:启发式搜索。
IDA* 算法
上面使用 IDA* 的思想来解决内存不足的问题, 这次就完全使用IDA*的算法来打整张表.
噢, 说错了, 我们使用的还不是 IDA* , 而是 迭代加深搜索. 我们没有一个良好的估价函数, 所以估价函数就是一个常数了.
迭代加深搜索
看看自己的模板，上面记录着这样一句话
对于一般的搜索，复杂度是O(2\^n)的复杂度。
对于不知道比较好的算法时，只有进行暴力搜索了。
但是DFS 可能进去出不来，对于BFS 又可能爆栈。这是就要进行迭代搜索了。
每当加深一层深度时，次层的搜索的时间可以忽略不计了，因为相差一个数量级。
这些优化和 迭代加深算法的代码就交给我的学弟李淼洋吧.
PS: 2014-10-20 19:52 自己在当天晚上已经跑出了结果。
目前的方法
之前使用队列加各种优化把255个数字跑出来，而只剩下一个104没有跑出来。
后来，加了一个 dfs 优化：当bfs 搜索到第9 层的时候，开始 dfs 搜索，最深搜不超过11层。
struct T {
void pop(){
str.pop_back();
n--;
}
};
int dfs(T& now, int lev, int d, int& ans) {
if(ans != -1 && ans <= now.ans+lev) {
now.pop();
return -1;
}
if(now.ans+lev > 11) {
now.pop();
return -1;
}
bool have[N];
memset(have, false, sizeof(have));
for(int i=0; i<now.n; i++) {
have[now.str[i]] = 1;
}
int tmpNAND;
int tmpAns;
for(int i=now.start; i<now.n; i++) {
for(int j=0; j<i; j++) {
tmpNAND = NAND(now.str[i], now.str[j]);
if(tmpNAND == d) {
now.pop();
return now.ans + lev;
}
if(have[tmpNAND]) {
continue;
}
have[tmpNAND] = true;
now.add(tmpNAND);
now.start = i;
tmpAns = dfs(now, lev+1,d, ans);
if(tmpAns != -1) {
if(ans == -1) {
ans = tmpAns;
} else {
ans = min(ans,tmpAns);
}
}
}
}
now.pop();
return ans;
}
for(int i=now.start; i<tmpn; i++) {
for(int j=0; j<i; j++) {
tmpNAND = NAND(now.str[i], now.str[j]);
if(have[tmpNAND]) {
continue;
}
have[tmpNAND] = true;
newT = now;
newT.add(tmpNAND);
newT.start = i;
if(haveString(newT)) {
continue;
}
if(tmpNAND == d) {
return now.ans;
}
if(newT.ans > MIN_LEV) {
tmpAns = dfs(newT, 1, d, ans);
if(tmpAns != -1) {
if(ans == -1) {
ans = tmpAns;
} else {
ans = min(ans, tmpAns);
}
}
} else {
que.push(newT);
}
}
}
完整数据见这里 完整数据
最终版本的代码参见这里 .
AC代码
AC 代码见这里 这里
本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。
