算法竞赛进阶指南-0x02-费解的开关(Advanced Guide to algorithm competition – 0x02 – puzzling switch)-其他

算法竞赛进阶指南-0x02-费解的开关(Advanced Guide to algorithm competition – 0x02 – puzzling switch)

http://noi-test.zzstep.com/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0201%20%E8%B4%B9%E8%A7%A3%E7%9A%84%E5%BC%80%E5%85%B3

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
struct nd
{
int a[6][6], sum;
} node[10000005];
int a[6][6], tot, ax[6][6];
const int oprx[] = {0, 0, 0, 1, -1}, opry[] = {0, 1, -1, 0, 0};
void gn(int sum)
{
int i, j;
for (i = 1; i <= 2; i++)
for (j = 1; j < 6; j++)
node[tot].a[i][j] = ax[i][j];
node[tot].sum = sum;
tot++;
if (sum == 6)
return;
for (i = 1; i < 6; i++)
{
for (j = 0; j < 5; j++)
ax[1 + oprx[j]][i + opry[j]] ^= 1;
gn(sum + 1);
for (j = 0; j < 5; j++)
ax[1 + oprx[j]][i + opry[j]] ^= 1;
}
}
inline int res(int x)
{
int i, j;
for (i = 1; i < 3; i++)
for (j = 1; j < 6; j++)
ax[i][j] = node[x].a[i][j];
for (i = 3; i < 6; i++)
for (j = 1; j < 6; j++)
ax[i][j] = a[i][j];
int ret = node[x].sum;
for (i = 2; i < 6; i++)
{
for (j = 1; j < 6; j++)
{
if (!ax[i - 1][j])
{
for (int k = 0; k < 5; k++)
ax[i + oprx[k]][j + opry[k]] ^= 1; //这里的ax写成了a...离谱的是上面的if里面的ax原本也是没错的...
ret++;
if (ret > 6)
return -1;
}
}
}
for (i = 1; i < 6; i++)
{
if (!ax[5][i])
return -1;
}
return ret;
}
int main()
{
int _, i, j;
scanf("%d", &_);
while (_--)
{
for (i = 1; i <= 5; i++)
for (j = 1; j <= 5; j++)
scanf("%1d", &a[i][j]);
for (i = 1; i < 3; i++)
for (j = 1; j <= 5; j++)
ax[i][j] = a[i][j];
tot = 1;
gn(0);
int ans = -1;
for (i = 1; i < tot; i++)
{
int t = res(i);
if (t >= 0 && (ans > t || ans < 0))
ans = t;
}
printf("%d\n", ans);
}
return 0;
}``````

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int dp[1 << 25];
struct node
{
int sta, sum;
node(int s = 0, int su = 0)
{
sta = s;
sum = su; //原本写成su=sum了
}
};
void bfs()
{
queue<node> q;
int i, t;
q.push(node((1 << 25) - 1, 0));
while (!q.empty())
{
int sta = q.front().sta, sum = q.front().sum;
q.pop();
if (dp[sta] >= 0 && dp[sta] < sum)
continue;
dp[sta] = sum;
if (sum > 5)
continue;
for (i = 0; i < 25; i++)
{
t = sta ^ (1 << i);
if (i - 5 >= 0)
t ^= (1 << (i - 5));
if (i + 5 < 25)
t ^= (1 << (i + 5));
if (i % 5)
t ^= (1 << (i - 1));
if (i % 5 != 4)
t ^= (1 << (i + 1));
if (dp[t] < 0 || dp[t] > sum + 1)
{
dp[t] = sum + 1; //最开始没写这个导致死循环
q.push(node(t, sum + 1));
}
}
}
}
int main()
{
int _, i, j, t, x;
memset(dp, -1, sizeof(dp));
bfs();
scanf("%d", &_);
while (_--)
{
x = 0;
for (i = 1; i <= 5; i++)
{
for (j = 1; j <= 5; j++)
{
scanf("%1d", &t);
x <<= 1;
x ^= t;
}
}
printf("%d\n", dp[x]);
}
return 0;
}``````
————————

http://noi-test.zzstep.com/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0201%20%E8%B4%B9%E8%A7%A3%E7%9A%84%E5%BC%80%E5%85%B3

Because this question is the first question (not the first question in fact), I think it is relatively simple, a glance of violence, 256. When calculating, one person was omitted, thinking that the scale was 1E7, which led to the slow calculation of samples, so slow that I thought it was a dead cycle. After looking for a long dead cycle, I found that this code can actually produce results

Then it is handled line by line according to the ordinary flipping problem. The code stinks, and there is a wrong variable name, which has been checked for more than half an hour. Mark the mistakes below

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
struct nd
{
int a[6][6], sum;
} node[10000005];
int a[6][6], tot, ax[6][6];
const int oprx[] = {0, 0, 0, 1, -1}, opry[] = {0, 1, -1, 0, 0};
void gn(int sum)
{
int i, j;
for (i = 1; i <= 2; i++)
for (j = 1; j < 6; j++)
node[tot].a[i][j] = ax[i][j];
node[tot].sum = sum;
tot++;
if (sum == 6)
return;
for (i = 1; i < 6; i++)
{
for (j = 0; j < 5; j++)
ax[1 + oprx[j]][i + opry[j]] ^= 1;
gn(sum + 1);
for (j = 0; j < 5; j++)
ax[1 + oprx[j]][i + opry[j]] ^= 1;
}
}
inline int res(int x)
{
int i, j;
for (i = 1; i < 3; i++)
for (j = 1; j < 6; j++)
ax[i][j] = node[x].a[i][j];
for (i = 3; i < 6; i++)
for (j = 1; j < 6; j++)
ax[i][j] = a[i][j];
int ret = node[x].sum;
for (i = 2; i < 6; i++)
{
for (j = 1; j < 6; j++)
{
if (!ax[i - 1][j])
{
for (int k = 0; k < 5; k++)
ax[i + oprx[k]][j + opry[k]] ^= 1; //这里的ax写成了a...离谱的是上面的if里面的ax原本也是没错的...
ret++;
if (ret > 6)
return -1;
}
}
}
for (i = 1; i < 6; i++)
{
if (!ax[5][i])
return -1;
}
return ret;
}
int main()
{
int _, i, j;
scanf("%d", &_);
while (_--)
{
for (i = 1; i <= 5; i++)
for (j = 1; j <= 5; j++)
scanf("%1d", &a[i][j]);
for (i = 1; i < 3; i++)
for (j = 1; j <= 5; j++)
ax[i][j] = a[i][j];
tot = 1;
gn(0);
int ans = -1;
for (i = 1; i < tot; i++)
{
int t = res(i);
if (t >= 0 && (ans > t || ans < 0))
ans = t;
}
printf("%d\n", ans);
}
return 0;
}``````

The back teammates provide the idea of memory search. Roughly, the 25 elements of the matrix are divided into one bit in turn to form a binary number, which is used as the identification (state) for storing intermediate results.

The original idea was to start from 0 and calculate the number of operations required from each identification to the final answer. If it exceeds six times, it is illegal to directly record it. But teammates pointed out that this will cause a lot of unnecessary calculations. It’s better to mark all the states that can be reached within six steps from the final answer (with a BFS).

About state access, I originally wanted to be lazy. Every time I expand the state into matrix operation, I will turn to state after operation. But the teammate pointed out that the number of bits of difference between adjacent elements in the state is certain, and only the boundary value needs to be judged.

Then I wrote the code fairly smoothly. After writing, because the status is not transferred in time, repeated access to the status leads to an endless loop. Later, because the constructor in the structure was wrongly written for a long time, I was still wondering whether the input and output states were reversed. After derivation, it is indeed inverse, but because the matrix is symmetrical, it has no effect on the answer

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int dp[1 << 25];
struct node
{
int sta, sum;
node(int s = 0, int su = 0)
{
sta = s;
sum = su; //原本写成su=sum了
}
};
void bfs()
{
queue<node> q;
int i, t;
q.push(node((1 << 25) - 1, 0));
while (!q.empty())
{
int sta = q.front().sta, sum = q.front().sum;
q.pop();
if (dp[sta] >= 0 && dp[sta] < sum)
continue;
dp[sta] = sum;
if (sum > 5)
continue;
for (i = 0; i < 25; i++)
{
t = sta ^ (1 << i);
if (i - 5 >= 0)
t ^= (1 << (i - 5));
if (i + 5 < 25)
t ^= (1 << (i + 5));
if (i % 5)
t ^= (1 << (i - 1));
if (i % 5 != 4)
t ^= (1 << (i + 1));
if (dp[t] < 0 || dp[t] > sum + 1)
{
dp[t] = sum + 1; //最开始没写这个导致死循环
q.push(node(t, sum + 1));
}
}
}
}
int main()
{
int _, i, j, t, x;
memset(dp, -1, sizeof(dp));
bfs();
scanf("%d", &_);
while (_--)
{
x = 0;
for (i = 1; i <= 5; i++)
{
for (j = 1; j <= 5; j++)
{
scanf("%1d", &t);
x <<= 1;
x ^= t;
}
}
printf("%d\n", dp[x]);
}
return 0;
}``````