题解 - Vijos

0

Ice_Msk LV 3 @ 2007-10-06 16:51:18

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

orz M67强！

0

lijian LV 5 @ 2007-09-15 23:36:49

向Matrix67、疾风剑客两位大牛致敬！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

youarefouled LV 3 @ 2007-08-27 19:48:29

编译通过...

├ 测试数据 01：答案正确... 119ms

├ 测试数据 02：答案正确... 134ms

├ 测试数据 03：答案正确... 119ms

├ 测试数据 04：答案正确... 103ms

├ 测试数据 05：答案正确... 88ms

├ 测试数据 06：答案正确... 103ms

├ 测试数据 07：答案正确... 134ms

├ 测试数据 08：答案正确... 103ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1141ms

热烈庆祝自己一次AC第五十道题，两颗星了！！！

0

turtlemax LV 4 @ 2007-07-31 10:26:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

感谢matrix67大牛

0

老孙头 LV 9 @ 2007-07-24 14:36:49

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

连交三次,都不过,一把数据类型开大就AC。

0

zjshark LV 6 @ 2007-07-20 22:08:57

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

楼下的楼下的楼下，牛！！！

0

INFINITE_Li LV 3 @ 2007-06-22 11:44:07

和我手机上的某个游戏很像!

0

为什么封我号？ LV 3 @ 2007-06-10 21:36:29

模拟同楼下

0

Star_Gym LV 3 @ 2007-04-05 17:06:30

作为第100个通过者,有必要将0Ms方法解释清楚...(事实上是从oibh直接将matrix解题报告的补充copy过来...那里的才看得懂...)

Matrix67:

补充疾风剑客提供了一个相当快的算法，它的算法能在相当短的时间里算出给定状态到最终状态所需要的步数：对于每个状态，算法只需要枚举第一行改变哪些灯的状态，只要第一行的状态固定了，接下来的状态改变方法都是唯一的：每一行需要改变状态的位置都在上一行中不亮的灯的正下面，因为只有这样才能使上一行的灯全亮。我们枚举第一行的状态改变方法（共2^5种），对于每种方法都依次改变下面几行的状态使上面一行灯全亮。到最后一行我们需要判断是否最后一行也恰好全亮，并更新最小步数。好像这个算法能在0ms内出结果。

0

nicolas LV 3 @ 2006-11-03 08:12:12

从一大牛处打听到的做法

不要搜全部。

只搜第一行的32种状态。

之后根据某个不亮的灯能，且只能被它下面一行同列处的操作点燃向下推。

这样可以保证最下面一行外所有行都亮起来，只需再检查那一行是不是也都亮着就行了。

推的途中用《=6为条件剪枝。

这样全部数据0MS就AC

0

flyfox LV 4 @ 2006-10-28 22:27:24

我用了双向广搜加Hash判重，将每一个状态用十进制数表示。

爽死啦。。。。这题作了三天三夜。。。

先是用广搜，在状态的改变上错了几次，后来该用深搜作了一天，超时（不知道能不能用深搜作出来）25^6+...+25^1太大了，所以又改用广搜,当时错了一个小细节就是在算2的几次方时没把它记录下来，所以每次都去算指数运算，浪费了大量的时间。后来就想从目标和初始状态一起搜，这样才过得这道题。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 103ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 103ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 119ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：800ms

0

DCAM-000 LV 3 @ 2006-10-26 22:18:04

第2个样例，先拉掉（2，5）的灯，再拉（1，5）的灯

0

pengfukai LV 3 @ 2006-10-24 19:05:06

示例的第二个怎么变啊?

0

yaonie LV 3 @ 2006-11-08 14:09:56

我想的是把矩阵看作一列01串。。

入队的时候把二进制转换成十进制再入队，，判重就用位运算(n>>k)&1

0

zouxun LV 9 @ 2006-08-21 16:27:45

疾风剑客的算法,只搜第一行,其他推

0

there LV 3 @ 2006-08-20 12:38:59

广搜超时呀！

不是必须要A*吧？

0

luziying LV 6 @ 2006-08-20 10:33:09

从目标状态开始广搜6层

-1

TenderRun LV 10 @ 2015-10-18 17:50:22

借鉴了Naylon大牛的思路，学习了！

但时间耗得比他多很多啊

记录信息
评测状态 Accepted
题目 P1197 费解的开关
递交时间 2015-10-18 17:48:16
代码语言 C++
评测机 VijosEx
消耗时间 2871 ms
消耗内存 263188 KiB
评测时间 2015-10-18 17:48:18
评测结果
编译成功

测试数据 #0: Accepted, time = 296 ms, mem = 263184 KiB, score = 10
测试数据 #1: Accepted, time = 281 ms, mem = 263184 KiB, score = 10
测试数据 #2: Accepted, time = 281 ms, mem = 263184 KiB, score = 10
测试数据 #3: Accepted, time = 234 ms, mem = 263184 KiB, score = 10
测试数据 #4: Accepted, time = 359 ms, mem = 263180 KiB, score = 10
测试数据 #5: Accepted, time = 375 ms, mem = 263188 KiB, score = 10
测试数据 #6: Accepted, time = 281 ms, mem = 263184 KiB, score = 10
测试数据 #7: Accepted, time = 296 ms, mem = 263180 KiB, score = 10
测试数据 #8: Accepted, time = 187 ms, mem = 263184 KiB, score = 10
测试数据 #9: Accepted, time = 281 ms, mem = 263184 KiB, score = 10
Accepted, time = 2871 ms, mem = 263188 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int beg=62,maxstep=6,begform=33554431;
int nf[10][10],form[(1<<26)+10],Q;
void work(int step)
{
int code=0;
for(int i=1;i<=5;i++)
code^=((nf[step][i]&beg)>>1)<<(5*(5-i));
int nowstep=maxstep-step;
if(form[code]==-1||form[code]>nowstep)form[code]=nowstep;
else return;
if(step==0)return;
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
{
memcpy(nf[step-1],nf[step],sizeof(nf[step]));
nf[step-1][i]^=1<<j;
nf[step-1][i]^=1<<(j+1);
nf[step-1][i]^=1<<(j-1);
nf[step-1][i+1]^=1<<j;
nf[step-1][i-1]^=1<<j;
work(step-1);

}

}
int init()
{
char s[10][10];
int num[6],ans=0;
for(int i=1;i<=5;i++){
scanf("%s",s[i]+1);
num[i]=0;
for(int j=1;j<=5;j++)
num[i]=(num[i]<<1)+(s[i][j]-'0');
}
for(int i=1;i<=5;i++)
ans=(ans<<5)^num[i];
return ans;

}
int main()
{
for(int i=1;i<=5;i++) nf[maxstep][i]=beg;
memset(form,-1,sizeof(form));
form[beg]=0;
work(maxstep);
scanf("%d",&Q);
for(;Q--;)
printf("%d\n",form[init()]);
return 0;
}

-1

Naylon LV 8 @ 2013-10-22 11:46:12

朴素DFS+二进制，初学写的不是很好
（话说怎么木有C++的题解）

编译成功

测试数据 #0: Accepted, time = 109 ms, mem = 33392 KiB, score = 10

测试数据 #1: Accepted, time = 109 ms, mem = 33396 KiB, score = 10

测试数据 #2: Accepted, time = 109 ms, mem = 33396 KiB, score = 10

测试数据 #3: Accepted, time = 93 ms, mem = 33400 KiB, score = 10

测试数据 #4: Accepted, time = 125 ms, mem = 33400 KiB, score = 10

测试数据 #5: Accepted, time = 125 ms, mem = 33396 KiB, score = 10

测试数据 #6: Accepted, time = 109 ms, mem = 33400 KiB, score = 10

测试数据 #7: Accepted, time = 109 ms, mem = 33396 KiB, score = 10

测试数据 #8: Accepted, time = 109 ms, mem = 33400 KiB, score = 10

测试数据 #9: Accepted, time = 93 ms, mem = 33400 KiB, score = 10

Accepted, time = 1090 ms, mem = 33400 KiB, score = 100

#include <iostream>
#include <vector>
#include <memory.h>
#include <string>

using namespace std;

const int MAX_DEPTH = 6; // 搜索深度
const int TARGET_STATE = 33554431; // (2)1111111111111111111111111
const int PERFECT_LINE = 62; // (2)0111110

char stateHash[TARGET_STATE + 1]; // 到达一个局面至少需要多少步，局面由5*5bit构成一个int表示
int expectState[MAX_DEPTH + 1], presentState[MAX_DEPTH + 1][7]; // 初始状态和当前Depth下的状态

void SearchSolution(int Depth)
{
int i, j;

//
// 计算当前局面的HashIndex
//
int hashIndex = 0;
for (i = 1; i <= 5; i++) {
hashIndex |= ((presentState[Depth][i] & PERFECT_LINE) >> 1) << (5 * (5 - i));
}

//
// 如果当前局面是第一次到达，或者本次搜索的层数小于之前搜到此局面时的层数，则更新步数
//
char steps = MAX_DEPTH - (char)Depth;
if (stateHash[hashIndex] == 0 || steps < stateHash[hashIndex]) {
stateHash[hashIndex] = steps;
//
// 若还未搜到第六步，继续DFS
//
if (steps != MAX_DEPTH) {
for (i = 1; i <= 5; i++) {
for (j = 1; j <= 5; j++) {
//
// 上下左右中位取反后DFS
//
memcpy(presentState[Depth - 1], presentState[Depth], 7 * sizeof(int));
presentState[Depth - 1][i - 1] ^= 1 << (6 - j);
presentState[Depth - 1][i] ^= 1 << (5 - j);
presentState[Depth - 1][i] ^= 1 << (6 - j);
presentState[Depth - 1][i] ^= 1 << (7 - j);
presentState[Depth - 1][i + 1] ^= 1 << (6 - j);
SearchSolution(Depth - 1);
}
}
}
}
}

int main()
{
int N;
int i, j;
(cin >> N).get();

//
// 从目标状态反搜
//
for (i = 0; i < 7; i++)
presentState[MAX_DEPTH][i] = PERFECT_LINE; // 11111
SearchSolution(MAX_DEPTH);

string strInput;
vector<int> vecResults;
while (N--) {
//
// 根据输入的字符串，以二进制的方式保存初始状态
//
expectState[0] = expectState[6] = 0;
for (i = 1; i <= 5; i++) {
getline(cin, strInput);
expectState[i] = 0;
for (j = 1; j <= 5; j++) {
expectState[i] |= (strInput.at(j - 1) == '0'? 0: 1) << (6 - j);
}
}
cin.get(); // 输入时的空行

//
// 计算初始状态的HashIndex
//
int hashIndex = 0;
for (i = 1; i <= 5; i++) {
hashIndex |= ((expectState[i] & PERFECT_LINE) >> 1) << (5 * (5 - i));
}

//
// 如果初始状态就是目标状态，则只需要0步
//
if (hashIndex == TARGET_STATE)
vecResults.push_back(0L);
else
vecResults.push_back((int)(stateHash[hashIndex] != 0? stateHash[hashIndex]: -1));
}

//
// 输出结果
//
for (vector<int>::iterator iter = vecResults.begin(); iter != vecResults.end(); iter++)
cout << *iter << endl;

return 0;
}

TenderRun @ 2015-10-18 14:55:52

请问PERFECT_LINE是干嘛的？
取反的那五句话为啥要那样写？
TenderRun @ 2015-10-18 16:25:25

蠢了蠢了
TenderRun @ 2015-10-18 17:50:52

赞一个

-1

jiaoyunhao LV 10 @ 2012-08-10 23:06:22

O(32*20*n组)

题解

83 条题解

费解的开关

信息

状态

开发

支持

题解

83 条题解

费解的开关

信息

状态

开发

支持

还没有账户？

登录