算法竞赛进阶指南-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

因为这题是第一题(其实不是第一题),以为比较简单,一眼暴力,256。算的时候少算了一位,以为规模是1e7,导致样例都算很慢,慢到我以为是死循环。找了半天死循环才发现这个代码其实能出结果…

然后就按照普通的翻转问题一行一行处理。代码恶臭,而且有一处变量名写错查了半个多小时。下面标出错误的地方

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

后面队友提供了记忆化搜索的思路。大致是给矩阵的25个元素依次分一个位,形成一个二进制数,以这个二进制数作为存储中间结果的标识(状态)。

原本的思路是从0开始,求出每个标识到最终答案所需操作次数,超过六次的直接记非法。但队友指出,这样会造成大量不必要的计算,不如从最终答案开始,(用一个bfs)把所有从最终答案开始六步之内能到的状态标上。

有关状态的存取,原本想偷懒,每一次将状态展开为矩阵操作,操作完再转为状态。但还是那个队友,指出:相邻元素在状态中相差的位数是一定的,只需要判断边界值就可以。

然后就还算顺利地写出了代码。写完因为状态没及时转移,状态重复访问导致死循环。后面因为结构体中构造函数写错卡了半天,期间还在想是不是输入和输出的状态反了。经过推导,确实是反了,但因为矩阵是对称的,其实反不反对答案没有影响

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