非常奇怪的错误,求大佬解惑
查看原帖
非常奇怪的错误,求大佬解惑
1107998
Flaw_Owl楼主2024/5/10 15:14

如题,在这道题的提交过程中发现了非常诡异的错误。

首先给出我的 AC 代码:

#include <iostream>
#include <cctype>
#include <string.h>
#define ll long long

using namespace std;

ll read()
{
    ll x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const ll P = 299987;

ll n, m;   // 棋盘的行数和列数
ll ex, ey; // 最后一个非障碍格子的坐标
ll now, last;
ll ans;

ll a[13][13]; // 记录棋盘
ll head[300000];
ll nxt[2 << 24];
ll que[2][2 << 24];
ll val[2][2 << 24];
ll cnt[2];
ll inc[13]; // 2 的幂次方

void init()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char ch = getchar();
            while (ch != '*' && ch != '.')
                ch = getchar();
            if (ch != '.')
                a[i][j] = 0;
            else
            {
                a[i][j] = 1;
                ex = i;
                ey = j;
            }
        }
    inc[0] = 1;
    for (int i = 1; i <= 13; i++)
        inc[i] = inc[i - 1] << 2;
}

void insert(ll bit, ll num)
{
    ll u = bit % P + 1;
    for (int i = head[u]; i; i = nxt[i])
        if (que[now][i] == bit)
        {
            val[now][i] += num;
            return;
        }
    nxt[++cnt[now]] = head[u];
    head[u] = cnt[now];
    que[now][cnt[now]] = bit;
    val[now][cnt[now]] = num;
}
void solve()
{
    cnt[now] = 1;
    val[now][1] = 1;
    que[now][1] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= cnt[now]; j++)
            que[now][j] <<= 2;
        for (int j = 1; j <= m; ++j)
        {
            memset(head, 0, sizeof(head));
            last = now;
            now ^= 1;
            cnt[now] = 0;
            for (int k = 1; k <= cnt[last]; ++k)
            {
                ll bit = que[last][k], num = val[last][k];
                ll b1 = (bit >> ((j - 1) * 2)) % 4, b2 = (bit >> (j * 2)) % 4;
                if (!a[i][j])
                {
                    if (!b1 && !b2)
                        insert(bit, num);
                }
                else if (!b1 && !b2)
                {
                    if (a[i + 1][j] && a[i][j + 1])
                        insert(bit + inc[j - 1] + inc[j] * 2, num);
                }
                else if (!b1 && b2)
                {
                    if (a[i][j + 1])
                        insert(bit, num);
                    if (a[i + 1][j])
                        insert(bit - inc[j] * b2 + inc[j - 1] * b2, num);
                }
                else if (b1 && !b2)
                {
                    if (a[i + 1][j])
                        insert(bit, num);
                    if (a[i][j + 1])
                        insert(bit - inc[j - 1] * b1 + inc[j] * b1, num);
                }
                else if (b1 == 1 && b2 == 1)
                {
                    int flag = 1;
                    for (int l = j + 1; l <= m; ++l)
                    {
                        if ((bit >> (l * 2)) % 4 == 1)
                            flag++;
                        if ((bit >> (l * 2)) % 4 == 2)
                            flag--;
                        if (!flag)
                        {
                            insert(bit - inc[j] - inc[j - 1] - inc[l], num);
                            break;
                        }
                    }
                }
                else if (b1 == 2 && b2 == 2)
                {
                    int flag = 1;
                    for (int l = j - 2; l >= 0; --l)
                    {
                        if ((bit >> (l * 2)) % 4 == 1)
                            flag--;
                        if ((bit >> (l * 2)) % 4 == 2)
                            flag++;
                        if (!flag)
                        {
                            insert(bit - inc[j] * 2 - inc[j - 1] * 2 + inc[l], num);
                            break;
                        }
                    }
                }
                else if (b1 == 2 && b2 == 1)
                    insert(bit - inc[j - 1] * 2 - inc[j], num);
                else if (i == ex && j == ey)
                    ans += num;
            }
        }
    }
}
int main()
{
    init();
    solve();
    printf("%lld", ans);
    return 0;
}

这里有两个问题:

  1. 如果开 O2O_2 会氧中毒,所以只能关掉 O2O_2。这一点我无法理解。
  2. 更诡异的错误是,注意到代码中的定义部分:
ll a[13][13]; 
ll head[300000];
ll nxt[2 << 24];
ll que[2][2 << 24];
ll val[2][2 << 24];
ll cnt[2];
ll inc[13];

如果我将 ll inc[13] 往前放,即修改成

ll a[13][13];
ll inc[13];
ll head[300000];
ll nxt[2 << 24];
ll que[2][2 << 24];
ll val[2][2 << 24];
ll cnt[2];

无论开不开 O2O_2 优化都 无法通过,存在两个点 WA。

并且,第二个问题应该可以确定 不是测评机 的问题,因为在 本地/洛谷 IDE 都无法顺利通过第五组测试点。

这是我从未遇见过的问题,希望能有大佬帮我解决 QAQ。

2024/5/10 15:14
加载中...