POJ1052

一开始看到题目，发现40%多的通过率，应该是挺简单的题目

然后看题目发现表述挺复杂的……一开始没理解透，胡乱写了个程序，WA地毫无悬念

仔细看了一下题目终于搞清楚，原来题目的意思是给三视图，然后问你能不能有一个cube满足这个三视图- -

然后搞了半天，终于想到办法……

先枚举三个视图的方向，然后把每个视图空的地方对应的方块全部抠掉

然后得到的是一个被镂空的方块体，而且可能还有不连通的

接着把所有连通的整个大块都找出来，做个标记，然后再判断投影……

写出来挺长的，不过大部分都是复制粘贴- -

话说写的时候有个小笔误……搞了半天，在数据的帮助下才调试出来……大悲剧的……

状态不行啊这样子……+U！

阅读全文

POJ1049

十分模拟的一道题目……纯模拟不解释……

刚刚看到这道题目，20+%的通过率，在POJ应该算比较麻烦的题目了，于是打开题目一看，别说，虽说模拟看起来挺烦的，其实也不麻烦，程序写出来短短的80行，没啥说的

然后写好了，发现样例都不能AC，于是改啊改，发现了几个小错误……模拟题就是这种麻烦- -代码质量下降了- -

提交，WA

悲剧……

找了半天找不到错误的地方，发现变量初始化有点小问题，改，继续WA

看比较迟了，于是进Discuss，第一个人说到忽略参数啥的- -一开始还以为自己理解错了，想都不想，直接改了提交，TLE- -

于是继续看Discuss，终于发现居然题目有问题……样例不对的，文件结束条件是一个第一个字符就是8的字符串而不是EOF……悲剧的POJ……改之，AC之……

怪不得通过率这么低……原来样例有问题的……

阅读全文

POJ3074&3076

搞了三天的DLX了- -

话说最开始听说DLX就是听说DLX做数独很快的，所以肯定要找几道数独做做- -

3074是最普通的那种数独3076是16*16的数独

在写3074的时候抱着尝试一下Eclipse的心情用Eclipse写出来，然后调试的时候感觉实在是……太不习惯了……

最后切回Netbeans下面，发现在Netbeans下面调试器居然乱显示……

然后又跑到VS下面去搞……最后发现了各种莫名其妙的错误……最后干脆直接把DLX部分删除重写，终于搞定了……话说搞了N久才搞定……哎……敲代码的状态不在啊……

然后又搞3076，直接改了一下数据范围，又小改了几个地方，样例直接过了，然后就提交，WA,懵了……

后来发现原来是有多组数据的，而且两组数据之间要加空行，于是改程序，提交，继续WA- -

改啊改的，终于发现问题之所在了……原来是再输入的时候……由于莫名其妙的原因搞得WA了……

只能说明一个问题……敲代码的状态完全不在啊……

另外3074的速度倒还行，3076的速度很悲剧……500+MS，而且发现这道题目不像N皇后，用<的时候反而更加快一些，不过两个都能AC，倒还好- -看来那个果然是模型的个别现象- -

大概估计一下为什么我的那么慢，是由于建模的效率问题吧，我是把模型弄好然后再删除，看了别人的都是直接建模的时候就考虑到那些已经写进去的数字了- -也可能是我的DLX太慢了- -不应该啊……不管了- -DLX算是告一段落了吧- -

撒花，庆祝~~~~

阅读全文

再说SPOJ1771

纠结于为什么顺着TLE,倒着就能AC……突然想起在看DLX的时候看到一个ZOJ3209里面也有类似的情况，顺着TLE倒着AC的情况- -找来那篇文章，复制代码，提交，顺利的TLE，然后找到他的比较部分，把<改成<=,顺利的AC了……

看来这不是N皇后的个别现象……其他问题构造的精确覆盖也会出现这问题……

到底是什么呢……

一不做，二不休，我干脆直接把两种不同程序的N皇后的搜索树都打印出来，在N=11的时候出现了不同，然后仔细比较那个搜索树，终于发现了问题！

话说在DLX里面有两层循环，第一层外循环是确定列，确定了列之后再枚举行

然后如果列是优先左边的话，枚举行的时候从下往上枚举就会更快的得到第一个解

而如果列优先右边的话，枚举行就是在从上往下枚举比较快

这样子也就解释了如果需要搜索到全部的解速度是一样的

另外一个很神奇的是在选择列的时候如果只选前N列而不是2N列的话，反而会比较快……

我估计这是由于问题的特殊性导致的模型的特点，也就说如果是一个随机的01矩阵进行DLX的话不会出现这种问题

先说为什么只枚举到N而不是2N会比较快，相当于在摆放旗子的时候每一步都先盯着每一行都只能摆放一个棋子，确定了这个条件再去看其他条件，这样子随着摆放的增加，约束会越来越强，而不容易出现放了一大堆棋子之后发现不对又都拿掉的情况，但是总体来看，如果需要全部的答案，需要枚举的次数还是不变的，测试数据也说明了这点。

再说外循环从左到右，内循环从下到上要快一些的情况……

话说N皇后问题建模出来的矩阵，对于行约束，是大量相邻的行都一样的，而列约束是相邻的列都不一样的，这个是显而易见的。

外循环从左到右循环在搜索树的上层取到的大都是行约束，但是到了中层开始取到列约束，取到列约束之后，再枚举的行实际上都是在这个列约束的基础上的，然后就鬼使神差的出现了大量的无效枚举……丫的鬼知道为什么……

再来看看拼图问题……大概情况是选择了一块位置，然后放上一块图片，如果两者方向一样，就会出现大量的由于遇到同一块图片而达到的冲突……

由枚举全部则速度相同可以看出，这其实是一个概率问题，方向反掉之后出现大量冲突的概率变小了，但是总体来看，花费是一样的，而搜索这种东西本身很靠RP的……尤其是只需要一个答案的情况下……之所以随机化搜索……也是有一定道理……随机化就不容易出现大规模冲突的情况……总体趋向于平衡……

感觉自己都搞不清楚在说什么了……结论是DLX很神奇……枚举行的时候还是跟选择列反过来稍微好一些……

阅读全文

N皇后问题，SPOJ1771

话说昨儿个写了个DLX，今天准备用DLX写个N皇后问题

一开始在POJ找到个300皇后问题，直接就写了，然后悲剧了……无限TLE

后来发现这道题目是要用构造法的……

写了的程序不能浪费，在SPOJ上面找到一个50皇后问题，稍微小改了一下就提交了

然后TLE了……悲剧的……话说本地都不会TLE……

于是百度……找到一个代码，那个代码很顺利的过了……

百思不得其解，除了代码风格，感觉两个人的代码没什么差别

一开始我以为是由于回溯的时候恢复链表的顺序导致出现错误，但是仔细一想发现即使按照顺序恢复也是能够正确还原的

为了验证，特意改了个程序，最后发现没有问题……

但是实在没办法，就把我的N皇后还是改成first do ，last undo的结构，再次提交，再次TLE……

悲剧的啊……

仔细看了一下百度到的代码，发现百度到那个代码输出的结果字典序明显偏大，而我输出来的头几位尤其是第一位几乎都是1，难道问题在这里？仔细看了一下代码，发现那个代码在sum相同时优先取后面的点，而我的是优先取前面的点，灵机一动，把我的<改成了<=，发现速度居然飙升！提交，直接居然就过了……

回过头，把最初那个TLE的程序拿出来，把<改成<=，还是AC，而且速度比改过这个还快！

于是很奇怪为什么会有这种情况……

决定测试一下

设置了一个全局变量g_op，记录cover的次数来估计搜索树的大小。

在题目的要求下，即只输出一个解的条件下，对于，测试了下面一串N的cover次数

10 11 12 13 14 15 25 31 32 33 34 35 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
，在<的情况下，程序运行结果是
110 245 290 422 238 125 196 2250 328 267 355 657 441 652 5261 570 632 613 274 10 783 633 234 3276 147849 7378 97766 955
而<=的情况下，结果是
110 191 325 429 379 125 734 556 3672 670 165 366 325 2309 651 296 634 887 11073 629 982 946 930 9164 1179 1342 371
并且跟百度到的程序一模一样！
可以发现，其实两种情况下大部分的cover次数都比较接近，但是在<=的时候最大的只是1W多，总体相对于<的时候平缓许多，在<的时候出现了10W多的情况，估计就是这几个情况导致了TLE
接着我在想到底是为什么呢？
突然想到测试算出所有解的情况
于是小改一下程序，分别测试N为下列值时，算出所有解需要的次数
4 5 6 7 8 9 10 11 <的时候，结果为
59 191 403 1383 4447 17376 61048 258523
<=的时候，结果为
59 191 403 1383 4447 17376 61048 258523
两者一模一样！
突然又想到如果不管大于小于的情况，直接取最前面一个跟最后面一个会是怎样的情况，说干就干，再改一下程序，还是测试求出所有解的情况
还是那些n，取最前面一个的时候结果为
59 199 559 2011 7489 30637 129379 606625
取最后面一个，结果为
59 199 559 2011 7489 30637 129379 606625
居然一模一样！
现在凭我的感觉分析一下
取所有解的时候出现了两次一模一样，应该是由于棋盘的对称性
但是直接取第一个跟取sum最小相比还是慢很多，说明DLX的剪枝还是比较暴力的，基本上剪掉了2/3
最搞不懂的就是第一组比较数据了
为什么优先取后面的会快那么多呢
如果用对称性来说明的话后面的点跟前面的点应该是完全对称的啊
我感觉我想不到了……
求大牛解释……

阅读全文

POJ3740

就是一个精确覆盖问题- -

主要是想练练DLX，由于第一次写，不想搞麻烦的，先找了一个纯的DLX练手

于是乎……

一开始写出来程序是错的

对DLX理解有问题

于是改啊改的……

最后改出来无限TLE……

然后又不知道改什么……

然后经过几次提交发现……

居然AC了……然后看了一下时间……960+ms……

大悲剧……

再提交

1000MS……整……

看来程序太慢了……但是又不知道哪里有得优化的……

PS：然后稍微改了一下程序，把数组开小一点……居然到300MS了……memset500次……太花时间了……

再次PS：之后在本机做了一下性能测试，发现90%以上的时间花费在Init（）函数里面，而且几乎全部是花费在scanf里面的……瓶颈在输入输出了……DLX果然暴力啊……十分快……

阅读全文

POJ1077，八数码……

POJ1077，经典的八数码问题，百度到一个地方说是不做这道题目人生是不完整的- -然后我做了三天……貌似还不止三天……

找这道题目完全是为了练A*。

一开始我不知死活的先写了一个限制深度的DFS……结果……无限TLE中- -

然后写了个BFS，网上有说BFS能够AC的，但是我写出来的TLE不解释……代码质量不太好估计……（后来发现其实hash方式影响很大）

于是再写一个双向BFS，华丽的60MS，这道题目算是过了……60MS这个里面用了大量的STL，MAP啥的，看来双向宽搜果然是很暴力的啊……貌似这是这辈子写的第二个双向宽搜，上一个大概- -4年前刚学搜索的时候吧- -

写了这么多都还没有涉及A，回头，写A去了。

一开始用自己写的100多行的一个堆，然后大量STL写了个A，结果TLE了……备受打击啊……ATLE了……

一不做，二不休，干脆把所有的map全部改成了哈希表，900多MS……泪奔……

无限百度各种八数码代码，找到这么个地方

http://www.cnblogs.com/liyongmou/archive/2010/07/19/1780861.html

里面写着，BFS500多MS,A30+，IDA10+MS……感觉很不可思议……

于是乎把代码复制下来在POJ提交了一下……确认了……确实有这么快……泪奔……

于是开始研究那代码……

发现A*里面有个地方利用priority_queue的时候的技巧是错误的，于是找CFY讨论- -又找作者讨论- -最后发现确实有点问题……难道还是得用自己的那个恶心的堆吗……这时候那个网页的作者告诉了我一个冗余的办法……确实很漂亮……很好的解决了那个办法- -

重写不解释，然后发现我那个哈希表也花费了大量的时间，于是更改编码方式，用变进制数（刚学的- -）来搞，搞出来,AC了，不过时间还是有点悲剧，200+MS

然后又用IDA写了一个，话说IDA好东西啊，代码只有A*长度的一半- -速度还一点都不含糊，100+MS……

不过感觉跟30+，10+还是差很多啊，于是各种想办法改，先是发现以一些无关痛痒的地方，最后发现启发函数有点问题，于是改了一下启发函数，瞬间飙到60MS,40MS……还是有点差距……不过……感觉差不多了……不写了……三天了……哥累了……

总结一下收获- -

1、利用冗余法从而可以直接用STL的堆，降低A*的编写复杂度- -

2、启发函数很重要啊很重要啊很重要！

3、IDA*很欢乐啊很欢乐啊很欢乐

4、STL的速度……有时候挺快的，有时候还真挺蛋疼……终于体会到为什么要慎用了……常数是大了点- -

5、看别人代码收获很大啊……

贴下代码吧……把A的贴上……至少用了冗余法……IDA那个……算了……

#include #include #include #include

const int MAXN = 362880 + 100;

using namespace std;

struct CStatus
{
int a[9];
int zero_pos;
};

int Encode(CStatus &sts)
{
int a[9];
for(int i=0; i<9; ++i){
a[i] = 0;
for(int j=i+1; j<9; ++j)
if(sts.a[i] > sts.a[j])
++a[i];
}
int k = 0;
for(int i=0; i<9; ++i){
k = k*(9-i)+a[i];
}
return k;
}

void Decode(int k, CStatus &sts)
{
int a[9];
a[8] = 0;
for(int i=2; i<=9; ++i){
a[9-i] = k % i;
k /= i;
}
for(int i=0; i<9; ++i)
sts.a[i] = 10;
for(int i=0; i<9; ++i){
int nb = 0;
for(int j=0; j<9; ++j){
if(sts.a[j] < i)
nb++;
else if(a[j] + nb == i){
sts.a[j] = i;
break;
}
}
}
for(int i=0; i<9; ++i)
if(sts.a[i] == 0){
sts.zero_pos = i;
return;
}
}

struct CNode{
int key, val;
CNode(int _k, int _v):key(_k), val(_v){}
};

inline bool operator < (CNode const &n1, CNode const &n2)
{
return n1.val > n2.val;
}

CStatus stsStart, stsGoal;
priority_queue open; int start, goal, g[MAXN], f[MAXN], h[MAXN], pre[MAXN]; char step[MAXN]; int sx[] = {0, 0, 1, -1}, sy[] ={1, -1, 0, 0}; char step_char[] = {'r', 'l', 'd', 'u'};

inline int abs(int a)
{
return a >= 0?a:-a;
}

/int CalcH(CStatus &sts)
{
int k = 0;
for(int i=0; i<8; ++i)
k += abs(sts.a[i]/3 - (i+1)/3) + abs(sts.a[i] %3-(i+1)%3);
return k;
}/
int CalcH(CStatus &sts)
{
int k = 0;
for(int i=0; i<9; ++i){
//if(sts.a[i] != i+1)
//k++;
if(sts.a[i] == 0)
continue;
k += abs(sts.a[i]/3 - (i+1)/3) + abs(sts.a[i] %3-(i+1)%3);
}
return k;
}

bool AStar()
{
for(int i=0; i<MAXN; ++i){
f[i] = g[i] = h[i] = -1;
}
h[start] = CalcH(stsStart);
g[start] = 0;
f[start] = g[start] = h[start];
open.push(CNode(start, f[start]));
while(!open.empty()){
CNode now = open.top();
open.pop();
if(now.key == goal)
return true;
if(f[now.key] != now.val)
continue;
CStatus stsNow;
Decode(now.key, stsNow);
int x = stsNow.zero_pos / 3;
int y = stsNow.zero_po s % 3;
for (int i = 0; i < 4; ++i) {
int xx = x + sx[i], yy = y + sy[i];
if (xx <= 2 && xx >= 0 && yy <= 2 && yy >= 0) {
stsNow.a[x * 3 + y] = stsNow.a[xx * 3 + yy];
stsNow.a[xx * 3 + yy] = 0;
int hash = Encode(stsNow);
//没有出现过，说明不在open表也不在Close表
if (g[hash] == -1) {
g[hash] = g[now.key] + 1;
h[hash] = CalcH(stsNow);
f[hash] = g[hash] + h[hash];
open.push(CNode(hash, f[hash]));
pre[hash] = now.key;
step[hash] = i;
//出现过，说明在open表或者close表，直接更新
} else if (g[hash] > g[now.key] + 1) {
g[hash] = g[now.key] + 1;
f[hash] = g[hash] + h[hash];
open.push(CNode(hash, f[hash]));
pre[hash] = now.key;
step[hash] = i;
}
stsNow.a[xx * 3 + yy] = stsNow.a[x * 3 + y];
stsNow.a[x * 3 + y] = 0;
}

}
}
return false;
}

void print_ans()
{
string ans;
int k = goal;
while(k != start){
ans = step_char[step[k]] + ans;
k = pre[k];
}
printf(“%s\n”, ans.c_str());
}

int main()
{
char s[10];
stsGoal.a[8] = 0;
stsGoal.zero_pos = 8;
for(int i=0; i<8; ++i)
stsGoal.a[i] = i+1;
goal = Encode(stsGoal);
for(int i=0; i<9; ++i){
scanf(“%s”, s);
if(s[0] == ‘x’){
stsStart.zero_pos = i;
stsStart.a[i] = 0;
}else{
stsStart.a[i] = s[0]-‘0’;
}
}
start = Encode(stsStart);
if(AStar()){
print_ans();
}else{
printf(“unsolvable”);
};
return 0;
}

阅读全文

POJ2908

本来想找道A的题目的，发现这题目直接不用A就OK了，不过还是能够用上写的那个A*的类，干脆就做了，做出来结论是不能迷恋STL啊……

先上题目

Quantum

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 2057		Accepted: 631

Description

At the Institution for Bits and Bytes at University of Ramville, Prof. Jeremy Longword and his eight graduate students are investigating a brand new way of storing and manipulating data on magnetic disks for use in hard drives. The method is based on letting quasimagnetic quantum operations operate on the sectors on the disk, and is, of course, safer andmore reliable than any earlier invented storage method. The use of each quantum operation costs a certain amount of energy, and the more energy the storage unit consumes, the warmer it will get. Therefore, you and your research team, are assigned the task of writing a program that, given sets of possible quantum operations and their costs, can calculate the lowest possible total cost for transforming a set of data to the wanted result.

On the disk, binary words of length 1 ≤ L ≤ 20 are treated. The quantum operations are defined by strings of the same length as the binary words, and are built from the four letters N (does nothing), F (inverts one bit), S (sets a bit to 1), and C (resets a bit to 0). Each letter in the string corresponds to an operation on the bit in the binary word at the same position. The binary words are transformed one by one and the total energy cost for the transformation is calculated as the sum of the costs for the performed quantum operations.

Input

The input starts with a single positive integer N ≤ 20 on a row, deciding the number of test cases that will follow. Then, for each of the test cases:

One line containing three integers: L, nop and nw separated by one space.
L indicates the length of the binary words and the quantum operations.
nop (≤ 32) is the number of quantum operations that are available for use when transforming the binary words.
nw (≤ 20) is the number of binary words that are to be transformed in the current test case.

After this, nop rows follows, each of them containing the definition of a quantum operation followed by the energy cost 0 ≤ ci 1000 of carrying out the quantum operation. The definition and the cost are separated by a single space.

Finally, there are nw rows, each containing two binary words separated by a single space. The first of these words should, when possible, be transformed to the second using the quantum operations. The binary words are expressed as sequences of 1’ s and 0’s. After these rows, the next test case follows, if there is any.

Output

Each test case should produce a row containing a list of the energy costs of transforming each of the binary words. The costs should be separated by a single space and presented in the same order as the corresponding input. When there is no successful way of transforming a binary word, “NP”, meaning not possible should be printed instead.

Sample Input

2<br></br>4 3 3<br></br>NFFN 1<br></br>NFNF 2<br></br>NNFN 4<br></br>0010 0100<br></br>0001 0010<br></br>0100 1000<br></br>4 4 5<br></br>CFSF 4<br></br>NNSS 3<br></br>FFFF 5<br></br>FNFN 6<br></br>1111 0000<br></br>1001 0110<br></br>0101 1000<br></br>1000 0011<br></br>0000 1001

Sample Output

1 3 NP<br></br>5 4 8 9 9<br></br><br></br>题目意思挺简单的，具体做的时候为了方便直接把一个操作分解为三步，根据位运算来搞，开三个数组分别记录and，or，xor，分别表示三中操作<br></br>然后搞的时候直接int t = (((now & opAnd[i]) ^ opXor[i]) | opOr[i]);<br></br>虽然没有估价函数，不过该有的CloseTable，OpenTable貌似还是用上了（PS：好像我这个程序里面把两个表的名字搞反了……）<br></br>做的时候OpenTable用了自己写的类，然后CloseTable开了一个map，然后TLE了……<br></br>大悲剧……<br></br>于是乎把CloseTable的map改成数组，继续TLE……<br></br>丫的，把Opentable里面的map也改成数组，然后AC了……396MS……速度还行- -<br></br>一不做二不休，干脆直接把OpenTable里面的Vector也改成数组，结果时间没变- -，内存也没变，效率基本一样……<br></br>仔细想想也是，vector是线性复杂度，map是log复杂度，改成数组就是线性复杂度了，规模在100W的时候加上常数比较大log是不行，不过线性复杂度影响就不大了- -<br></br>结论是规模大还是得写个哈希表啥的……map靠不住啊……<br></br>在想这题目能不能搞个估价函数提高下速度的……<br></br>贴代码先……<br></br>/*<br></br> * File:   main.cpp<br></br> * Author: Universe<br></br> *<br></br> * Created on 2010年7月25日, 下午6:32<br></br> */<br></br><br></br>#include <cstdlib><br></br>#include <map><br></br>#include <queue><br></br>#include <iostream><br></br>#include <vector><br></br>#include <functional><br></br>#include <cstdio><br></br><br></br>using namespace std;<br></br><br></br>class CCloseTable<br></br>{<br></br>int* keys;<br></br>int* vals;<br></br>int *map_kp;//key->pos<br></br>int size;<br></br>void adjust_up(int pos);<br></br>void adjust_down(int pos);<br></br>public:<br></br>void push(int key, int val);<br></br>//void modify(int key, int val);<br></br>void pop();<br></br>int top_key(){return keys[0];};<br></br>int top_val(){return vals[0];};<br></br>bool empty(){return size == 0;};<br></br>CCloseTable();<br></br>~CCloseTable();<br></br>};<br></br><br></br>CCloseTable::~CCloseTable()<br></br>{<br></br>delete map_kp;<br></br>delete keys;<br></br>delete vals;<br></br>}<br></br><br></br>CCloseTable::CCloseTable()<br></br>{<br></br>size = 0;<br></br>map_kp = new int[1100000];<br></br>keys = new int[1100000];<br></br>vals = new int[1100000];<br></br>for(int i=0; i<1100000; ++i)<br></br>map_kp[i] = -1;<br></br>}<br></br><br></br>void CCloseTable::push(int key, int val)<br></br>{<br></br>if(map_kp[key] == -1){<br></br>map_kp[key] = size;<br></br>keys[size] = key;<br></br>vals[size] = val;<br></br>size++;<br></br>adjust_up(size-1);<br></br>}else{<br></br>if(vals[map_kp[key]] <= val)<br></br>return;<br></br>vals[map_kp[key]] = val;<br></br>adjust_up(map_kp[key]);<br></br>}<br></br>}<br></br><br></br>void CCloseTable::pop()<br></br>{<br></br>size --;<br></br>//map_kp.erase(keys[0]);<br></br>map_kp[keys[0]] = -1;<br></br>keys[0] = keys[size];<br></br>vals[0] = vals[size];<br></br>map_kp[keys[0]] = 0;<br></br>adjust_down(0);<br></br>}<br></br><br></br>void CCloseTable::adjust_up(int pos)<br></br>{<br></br>int val = vals[pos];<br></br>int key = keys[pos];<br></br>int fa = (pos-1)/2;<br></br>while(pos > 0 && vals[fa] > val){<br></br>vals[pos] = vals[fa];<br></br>keys[pos] = keys[fa];<br></br>map_kp[keys[pos]] = pos;<br></br>pos = fa;<br></br>fa = (pos-1)/2;<br></br>}<br></br>vals[pos] = val;<br></br>keys[pos] = key;<br></br>map_kp[key] = pos;<br></br>}<br></br><br></br>void CCloseTable::adjust_down(int pos)<br></br>{<br></br>int val = vals[pos];<br></br>int key = keys[pos];<br></br>int rChild = (pos+1)*2;<br></br>while(rChild <= size){<br></br>if(rChild == size){<br></br>rChild --;<br></br>}else if(vals[rChild] > vals[rChild-1])<br></br>rChild --;<br></br>if(val <= vals[rChild])<br></br>break;<br></br>vals[pos] = vals[rChild];<br></br>keys[pos] = keys[rChild];<br></br>map_kp[keys[pos]] = pos;<br></br>pos = rChild;<br></br>rChild = (pos+1)*2;<br></br>}<br></br>vals[pos] = val;<br></br>keys[pos] = key;<br></br>map_kp[key] = pos;<br></br>}<br></br><br></br>int l, n, m, start, goal;<br></br>char s[30];<br></br>unsigned int opXor[31], opAnd[31], opOr[31], cost[31];<br></br>int ot[1100000];<br></br><br></br>void DoIt()<br></br>{<br></br>CCloseTable ct;<br></br>for(int i=0; i<1100000; ++i)<br></br>ot[i] = -1;<br></br>ct.push(start, 0);<br></br>while(!ct.empty() && ot[goal] == -1){<br></br>int now = ct.top_key();<br></br>int costNow = ct.top_val();<br></br>ct.pop();<br></br>ot[now] = costNow;<br></br>for(int i=0; i<n; ++i){<br></br>int t = (((now & opAnd[i]) ^ opXor[i]) | opOr[i]);<br></br>if(ot[t] != -1)<br></br>continue;<br></br>ct.push(t, costNow + cost[i]);<br></br>}<br></br>}<br></br>if(ot[goal] == -1)<br></br>printf("NP");<br></br>else<br></br>printf("%d", ot[goal]);<br></br>}<br></br><br></br>void Solve()<br></br>{<br></br>scanf("%d%d%d", &l, &n, &m);<br></br>for(int i=0; i<n; ++i){<br></br>scanf("%s%d", s, &cost[i]);<br></br>opXor[i] = opOr[i] = 0;<br></br>opAnd[i] = 0xffffffff;<br></br>for(int j=0; j<l; ++j){<br></br>opXor[i] <<=1;<br></br>opAnd[i] <<=1;<br></br>opOr[i] <<=1;<br></br>if(s[j] == 'F')<br></br>opXor[i] |= 1;<br></br>if(s[j] == 'S')<br></br>opOr[i] |= 1;<br></br>if(s[j] != 'C')<br></br>opAnd[i] |= 1;<br></br>}<br></br>}<br></br>for(int i=0; i<m; ++i){<br></br>scanf("%s", s);<br></br>start = 0;<br></br>for(int j=0; j<l; ++j)<br></br>start = (start << 1)|(s[j]-'0');<br></br>scanf("%s", s);<br></br>goal = 0;<br></br>for(int j=0; j<l; ++j)<br></br>goal = (goal << 1)|(s[j]-'0');<br></br>DoIt();<br></br>if(i == m-1)<br></br>printf("\n");<br></br>else<br></br>printf(" ");<br></br>}<br></br>}<br></br><br></br>int main(int argc, char** argv)<br></br>{<br></br>int nCase;<br></br>scanf("%d", &nCase);<br></br>while(nCase --){<br></br>Solve();<br></br>}<br></br>}<br></br><br></br><br></br>

阅读全文

POJ1184

NOI的题目，历经千辛万苦终于AC了……完全不在状态，今天下午写了一个下午写出来N多bug……各种悲剧……终于过了……写篇日志留念一下……上题目先- -

聪明的打字员

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3232		Accepted: 662

Description

阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。

不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right，为了说明这6个键的作用，我们先定义录入区的6个位置的编号，从左至右依次为1，2，3，4，5，6。下面列出每个键的作用：

Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按Swap0键之后，录入区的数字不变；

Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按Swap1键之后，录入区的数字不变；

Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是9）。例如，如果光标所在位置的数字为2，按Up之后，该处的数字变为3；如果该处数字为9，则按Up之后，数字不变，光标位置也不变；

Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字是0），如果该处数字为0，则按Down之后，数字不变，光标位置也不变；

Left：按Left，光标左移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上，则光标不动；

Right：按Right，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上，则光标不动。

当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。

现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。

Input

仅一行，含有两个长度为6的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。

Output

仅一行，含有一个正整数，为最少需要的击键次数。

Sample Input

123456 654321

Sample Output

题目的意思其实很简单- -而且是中文的- - 这道题目其实是很久以前看英文吐血然后就找中文题做，一开始以为这道题目比较简单，是个软柿子，拿过来捏的，然后放了很久都没做出来……前天发现有一道题目没AC的，本着不留Faild的精神，决定A掉一开始拿到题目，想着算上光标位置的话，总共只有6000000种状态，然后就想直接BFS……然后果断TLE了……看了Discuss里面各种说法，A啊，优化啊啥的试着优化了一下感觉搞不定。于是决定趁机学一下A……然后完全不知道咋下手…… 突然发现了一个好的优化办法，把数字增减跟移动分开考虑，先算出把当前排列变成所有其他排列需要的步数，然后再算出把那个状态变到需要的状态的加减的步数写了个累死累活，终于写出来了- -由于移动也需要步数，一开始想的是把能够移动到的最右边的那个位置记下来，这样子有6！66个情况，能够接受后来发现有个bug，999999到999998这种情况就没法过了……大悲剧…… 后来想到把能够改的每一位都做一个标记，然后具体写的时候由于是在刚才那个基础上面改，所以就搞了很别扭的位运算- -，把二进制高6位用于记录移动过程中有没有经过某位，然后低24位当10进制记录状态……混合进制……最后终于艰难的AC了…… 途中中bug无数，没想到一个80多行的程序能有这么多bug…… 其中由于位运算优先级导致的bug和重写一大堆由于思路不清晰导致的数字写错bug一大堆手误bug一大堆思路错误小bug一大堆算法错误大bug一大堆…… 好TM悲剧的一道题目…… 不过也算是AC了…… 另外左移操作是不能少的，比如下面这个数据 000159 000591 贴上代码……

#include <stdio.h>
#include <queue>
#include <set>
#include <map>
#include <stdlib.h>

using namespace std;

unsigned int mask[] = {100000, 10000, 1000, 100, 10, 1, 1000000, 10000000};
unsigned int couldMask[] = {0x80000000, 0x40000000, 0x20000000, 0x10000000, 0x8000000, 0x4000000};

map<unsigned int, unsigned int> Status;//值表示花费的步数，不存在表示未搜索到
queue<unsigned int> bfs_queue;
unsigned int ans, start, goal;

inline int Getpos(unsigned int status, unsigned int pos)
{
	return ((status & 0xffffff) / mask[pos]) % 10;
}

unsigned int CheckAns(unsigned int status)
{
	unsigned int total;
	total = Status[status];
	for(unsigned int i=0; i<6; ++i)
	if(status & couldMask[i]){
		total += abs(Getpos(status, i)- Getpos(goal, i));
	}else if(Getpos(status, i)!= Getpos(goal, i))
	return false;
	if(total < ans)
	ans = total;
}

unsigned int swap(unsigned int status, unsigned int p1, unsigned int p2)
{
	return status + Getpos(status, p1)*(mask[p2]-mask[p1])
	+ Getpos(status, p2)*(mask[p1]-mask[p2]);
}

void Add(unsigned int k, unsigned int step)
{
	if(Status.find(k) == Status.end()){
		Status[k] = step;
		bfs_queue.push(k);
		CheckAns(k);
	}
}

int main()
{
	unsigned int t;
	scanf("%d%d", &start, &goal);
	Status[start] = 0;
	start |= couldMask[0];
	bfs_queue.push(start);
	ans = 100000000;
	CheckAns(start);

	while(!bfs_queue.empty()){
		unsigned int now = bfs_queue.front();
		bfs_queue.pop();
		unsigned int step = Status[now]+1;
		if(step > ans)
		break;
		if(Getpos(now, 6) > 0){
			t = now - mask[6];
			Add(t, step);
			t = swap(now, 0, Getpos(now, 6));
			t |= couldMask[0];
			Add(t, step);
		}
		if(Getpos(now, 6) < 5){
			t = now + mask[6];
			t |= couldMask[Getpos(t, 6)];
			Add(t, step);
			t = swap(now, 5, Getpos(now, 6));
			t |= couldMask[5];
			Add(t, step);
		}
	}
	printf("%d\n", ans);
}

阅读全文

POJ1048

昨天连续用JavaA了两道水题，感觉Java手感比较在了，然后打开这道POJ1048,一看数据就囧到了- -强悍的模拟题……估计Java写出来的话Java也已经很熟了- -，最后写出来确实发现了Java的一个问题，多维数组不能直接Clone……

先上题目：

Follow My Logic

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 1384		Accepted: 400

Description

For this problem you will determine the output of a logic circuit composed of one or more inputs, zero or more dual-input AND/OR gates, and one output. The input circuits are drawn with standard ASCII characters. Circuit paths are represented using horizontal and vertical lines, and junctions. Horizontal lines are represented with dash characters (ASCII code 45 decimal), vertical lines with vertical bar characters (ASCII code 124 decimal), and junctions with plus characters (ASCII code 43 decimal). Inputs are represented using the capital letters A through Z, and the output is represented by a question mark. AND and OR gates are represented as shown in the leftmost entries in the figure below, and their orientation will always be exactly as shown. The location of the gate inputs and output is shown by the middle figure below. Finally, gate inputs or its output can be inverted, represented by a lowercase “oh”character (ASCII code 111 decimal) at the input or output location. The figure on the right below shows a simple but complete logic circuit.

        :\               :\                 -:\                 -o:\                       A-o:\

        : )              : >                 : )-                 : )o-                       : )o-?

        :/               :/                 -:/                 --:/                       B--:/

     AND gate          OR gate       Gate with inputs    An inverted top input          Two logic inputs

                                                 and an inverted output         and the output

Input

Circuits in the input will obey the following guidelines:

1. The maximum size of the circuit picture is 100 by 100 characters.

2. A path always travels in a straight line unless altered by a junction. At a junction, the path can and will make a ninety degree turn. Two junctions will not be horizontally or vertically adjacent.

3. No paths will be “broken” That is, every path character is guaranteed to be adjacent on both sides to either another path character of the same type, a junction, a gate input, a gate output, a logic input, or the logic output.

4. Circuit paths do not cross or intersect other paths.

5. Gate inputs always approach horizontally from the left as shown above. Gate outputs always leave horizontally to the right as shown above.

6. Inversions may only appear immediately adjacent to a gate input or output, and will always be preceded (in the case of an input) or followed (in the case of an output) by at least one dash as shown above.

The end of a logic diagram in the input is indicated by line containing only a single asterisk in the first column. Following this are several lines which indicate the state of the inputs in the logic diagram. Each of these lines is a string of twenty-six “0”(zero) or “1”characters, with the first position representing the state of input A, the second position representing the state of input B, etc. Note that input values which are not actually used in the circuit may simply be ignored. The list of input states is terminated by a line containing only a single asterisk character in the first column.

Following the asterisk which terminates the list of input states is another circuit diagram followed by a list of input states, which is then followed by another circuit diagram and list of input states, and so on until the end of the file. The file will always contain at least one circuit and one set of inputs for that circuit.

Output

The program is to report the value of the output (0 or 1) of each logic circuit, one value per line, for each set of input values in the list which follows the circuit. The list of outputs for each circuit should be separated by a single blank line.

Sample Input

A---:\
    : )---?
B---:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
A---+
    |
    +---:\
        : >o---:\
    +---:/     : )---?
    |      C--o:/
B---+
*
00000000000000000000000000
11100000000000000000000000
*

Sample Output

0

0

0

1
 


1

0


题目是一个计算逻辑电路的结果……字符画……

各种悲剧……

具体写的时候出了几次错，主要还是因为题目理解有问题，英语悲剧……

先是没有理解o，然后就是输入的时候可能出现

A

|

|

+--....

这样子，悲剧的……

最后还是AC了，Java写了140行，感觉还不错，200多MS,速度感觉有点慢




import java.util.*;

public class Main {
	static char a[][] = new char[110][110];
	static char value[] = new char[30];
	static final int xx[] = {0, 1, 0, -1};
	static final int yy[] = {1, 0, -1, 0};
	static final char cc[] = {'-', '|', '-', '|'};

	static void scan(int x, int y){
		int d = 0;
		for(int i=0; i<4; ++i){
			if(a[x + xx[i]][y + yy[i]] == cc[i]){
				d = i;
				break;
			}
		}
		while (true) {
			while (a[x + xx[d]][y + yy[d]] == cc[d]) {
				a[x + xx[d]][y + yy[d]] = a[x][y];
				x += xx[d];
				y += yy[d];
			}
			if(a[x + xx[d]][y + yy[d]] == 'o'){
				a[x + xx[d]][y + yy[d]] = (char)(a[x][y] == 0?1:0);
				x += xx[d];
				y += yy[d];
				d = 0;
			}
			if(a[x + xx[d]][y + yy[d]] == ':'){
				break;
			}
			if(a[x + xx[d]][y + yy[d]] == '?' ){
				a[x + xx[d]][y + yy[d]] = a[x][y];
				break;
			}
			if(a[x + xx[d]][y + yy[d]] == '+'){
				a[x + xx[d]][y + yy[d]] = a[x][y];
				x += xx[d];
				y += yy[d];
				d = (d+1)%4;
				if(a[x + xx[d]][y + yy[d]] == cc[d]){
					a[x + xx[d]][y + yy[d]] = a[x][y];
					x += xx[d];
					y += yy[d];
					continue;
				}
				d = (d+2)%4;
				if(a[x + xx[d]][y + yy[d]] == cc[d]){
					a[x + xx[d]][y + yy[d]] = a[x][y];
					x += xx[d];
					y += yy[d];
					continue;
				}
			}
		}

	}

	static void Solve()
	{
		int ansx = 0, ansy = 0;
		for (int i = 0; i < a.length; ++i) {
			for (int j = 0; j < a[i].length; ++j) {
				if (a[i][j] == '?') {
					ansx = i;
					ansy = j;
				}
			}
		}
		for (int i = 0; i < a.length; ++i) {
			for (int j = 0; j < a[i].length; ++j) {
				if (a[i][j] >= 'A' && a[i][j] <= 'Z') {
					a[i][j] = (char) (value[a[i][j] - 'A'] - '0');
					scan(i, j);
				}
			}
		}
		while (a[ansx][ansy] == '?') {
			for (int i = 0; i < a.length; ++i) {
				for (int j = 0; j < a[i].length; ++j) {
					if ((a[i][j] == '>') && a[i - 1][j - 3] < 2 && a[i + 1][j - 3] < 2) {
						a[i][j] = (char) (a[i - 1][j - 3] | a[i + 1][j - 3]);
						if(a[ansx][ansy] != '?')
						break;
						scan(i, j);
					}
					if ((a[i][j] == ')') && a[i - 1][j - 3] < 2 && a[i + 1][j - 3] < 2) {
						a[i][j] = (char) (a[i - 1][j - 3] & a[i + 1][j - 3]);
						if(a[ansx][ansy] != '?')
						break;
						scan(i, j);
					}
				}
				if(a[ansx][ansy] != '?')
				break;
			}
		}
		System.out.println((int)(a[ansx][ansy]));
	}

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		boolean first = true;
		while (in.hasNext()) {
			if(first)
			first = false;
			else
			System.out.println();
			for (int i = 0; i < 110; ++i)
			for (int j = 0; j < 110; ++j)
			a[i][j] = ' ';
			String tmp;
			int n = 0;
			while (true) {
				tmp = in.nextLine();
				if (tmp.startsWith("*"))
				break;
				++n;
				for(int i=1; i<=tmp.length(); ++i)
				a[n][i] = tmp.charAt(i-1);

			}
			char bak[][] = new char[110][110];
			for(int i=0; i<a.length; ++i)
			bak[i] = a[i].clone();
			while (true) {
				for(int i=0; i<a.length; ++i)
				a[i] = bak[i].clone();
				tmp = in.nextLine();
				if (tmp.startsWith("*"))
				break;
				value = tmp.toCharArray();
				Solve();
			}
		}
	}
}

阅读全文

Newer Page: 7 of 9 Older

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 2057		Accepted: 631

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3232		Accepted: 662

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 1384		Accepted: 400

Recent Posts