11月26, 2016

代码捉鬼

日常刷题,这道题本来思路清晰,简单 dfs 很快解决了,样例通过,交 wa。 代码如下

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mem[21][11][156];
bool vis[21];
ll dfs(int n, int k, int s) {
    if (k * n < s) {
        return 0;
    } else if (k == 1 && s <= n) {
        if (vis[s] || !s) {
            return 0;
        }
        return 1;
    }
    ll ans = 0;
    for (int i = n; i >= 1; i--) {
        if (vis[i]) continue;
        vis[i] = true;
        ans += dfs(i - 1, k - 1, s - i);
        vis[i] = false;
    }
    return ans;
}
int main() {
    memset(mem, -1, sizeof(mem));
    int n, k, s;
    while(cin >> n >> k >> s) {
        if (n == 0 && k == 0 && s == 0) break;
        memset(vis, false, sizeof(vis));
        int ans = dfs(n, k, s);
        cout << ans << endl;
    }
}

20 10 105 这组数据测试,可以获得正确结果5448 。 此时,我们可以看到代码中有一个从未使用过的数组mem[] ,如果去掉数组的初始化memset(vis, false, sizeof(vis)) ,诡异的现象发生了,输出结果改变了。 此时,如果你去掉数组mem[] 的声明,输出结果会再次发生改变。把声明和初始化加回,结果也相应恢复正常。 Debug 许久,无果,向大神求救。 在大神敏锐的观察力下,代码中的鬼无处可藏。我们发现如果将mem[] 的声明和vis[] 的声明的次序调换,那无论有没有初始化mem[] ,结果都是错的。由此推测,可能是vis[] 数组越界了。 于是我们回头在代码中仔细搜索对vis[] 的访问,果然因为 s 可能存在负值,vis[s] 是存在越界可能的。而负向越界指向的内存正是mem[] 的领地,如果读到的是-1,则不会影响程序的输出结果,而如果是其他的数值,结果必然出错。显然这个 OJ 的内存管理方式和我的本机不同,但不知道为什么不报 RE。 修改代码后问题解决。想起以前见到的一些无能为力的闹鬼代码,感慨颇多。从今往后遇到这样的事情,一定要仔细分析,至少留有记录。

感谢大神。

本文链接:https://sxing.xyz/post/代码捉鬼.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。