如何减少代码混乱和逻辑错误

文章

网上的题解代码大多写得很糟糕，并不适合学习它的风格，以下来简单介绍怎么写可以减少代码出错。

1. 减少全局变量，最好不用

这点在大家学了DP和搜索后，问题会越来越严重，全局变量最最容易导致的问题是因为忘记初始化而本地运行结果正确，但一提交就WA，尤其是网上题解99%都把数组直接写全局，这样会产生一个另类的坑让你超时。

就比如这个题目 https://vjudge.net/contest/430569#problem/K

它是多组输入，那你运用bfs时，通常要加个数组例如int vis[100010];去记录搜索过的数字。注意到，在多组输入的情况下，每次bfs前你需要对这个数组做一次清空，那么如果有10000组输入，但计算的内容很简单像1 2这类，那么你的实际的时间复杂度将变成$O(nt)$，t是组数，n是最大输入大小，很显然这个量下是会超时的，只是这个题没有这么坑你，但有的题目确实会这样卡你。

解决方法是，用std::set<int> vis;来代替原来的数组，这样初始化代价非常低，而且可以直接在bfs函数里面声明，插入时，用vis.insert(n)，判断存在性用if (vis.count(n))，这样再也不需要在bfs之前写memset了。

对于dp需要用数组的场合，如果是多组输入，通常只要一维数组，那么直接用vector<int>就行，而且它自动为你初始化为0，还不用担心太长导致栈溢出，可以很好地代替数组。而对于二维数组，你还可以

typedef int arr[1000];
std::vector<arr> dp;

这样我们就可以做出一个dp解题模板

void solve() {
    int n;
    cin >> n;
    vector<int> dp(n + 10); //初始化尺寸
    // do sth.
}
int main() {
    int t;
    cin >> t; //t组输入的模式
    while (t--) solve();
    return 0;
}

而对于搜索题也是类似，替换为set<int> vis就行。尽管它的查询速度没有数组快，但是90%以上的题目并不会因为慢个$logn$就导致超时。

void solve(int a, int b) {
    set<int> vis;
    queue<node> q;
    // do sth.
}
int main() {
    int a, b;
    while (cin >> a >> b) solve(a, b); //输入到EOF为止的模式
    return 0;
}

2. 多写函数

不要一个main函数全写完，代码写得清晰不容易出错，减少在debug上花的时间远远比少写两个函数定义来得值。

以下我们用这份求大整数阶乘的代码来做个演示

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int i,j,sum,digits=1;
        int a[10001]={1};
        for(i=2; i<=n; i++)
        {
            sum=0;
            for(j=0; j<digits; j++)
            {
                a[j]=a[j]*i+sum;
                sum=a[j]/10000;
                a[j]%=10000;
            }
            if(sum>0)
                a[digits++]=sum;
        }
        printf("%d",a[digits-1]);
        for(i=digits-2; i>=0; i--)
            printf("%04d", a[i]);
        printf("\n");
    }
    return 0;
}

改写后

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int base = 10000;
const char* out_fmt = "%04d";
int carry(int &sum, int newval) { //单个位的加法进位计算
    sum += newval;
    int ret = sum % base;
    sum /= base;
    return ret;
}
void mul(vector<int> &a, int m) { //对大整数a乘以m
    int sum = 0;
    for (int j = 0; j < a.size(); j++) {
        a[j] = carry(sum, a[j] * m);
    }
    if (sum > 0) a.push_back(sum);
}
void print(vector<int> &a) { //对大整数a输出
    printf("%d", a[a.size() - 1]);
    for (int i = a.size() - 2; i >= 0; i--)
        printf(out_fmt, a[i]);
    printf("\n");
}
void solve(int n) {
    int digits = 1;
    vector<int> a;
    a.push_back(1);
    for (int i = 2; i <= n; i++) {
        mul(a, i);
    }
    print(a);
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        solve(n);
    }
    return 0;
}

3. 多用STL，能不自己写的就不要自己写

特别是二分搜索，这东西坑很多，最好是用现成的lower_bound upper_bound，对于结构体，重载operator<就可以用了。特别地，在用到离散化的时候，直接用sort+unique比自己写来得好得多。

而要能多用STL的前提，就是你足够熟练，那就离不开平时多用了，不然在比赛中你根本没有时间去查这个怎么使用，结果就只能是不用，然后自己重新写一堆代码来实现STL中已经有的东西，而且还不一定写对，甚至效率也没有STL高。

再来看一个例子，网上的求LIS的$O(n^2)$模板代码

#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[10010];
int dp[10010];
// LIS
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            dp[i] = 1;
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

修改后

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
void solve(vector<int> &a) {
    int n = a.size();
    vector<int> dp(n, 1); //全部n个元素初始化为1
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        solve(a);
    }
    return 0;
}

再接着，优化为$O(nlogn)$的LIS实现

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
void solve(vector<int> &a) {
    int n = a.size();
    vector<int> dp;
    for (int i = 0; i < n; i++) {
        vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), a[i]);
        if (it == dp.end())
            dp.push_back(a[i]);
        else
            *it = a[i];
    }
    printf("%d\n", (int)dp.size());
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        solve(a);
    }
    return 0;
}

再看，如果改成非严格递降的最大长度，那可以改为

#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>
using namespace std;
void solve(vector<int> &a) {
    int n = a.size();
    vector<int> dp;
    for (int i = 0; i < n; i++) {
        // 非严格单调时，用的是upper_bound，从大到小比较时用到仿函数对象greater<>
        vector<int>::iterator it = upper_bound(dp.begin(), dp.end(), a[i], greater<int>());
        if (it == dp.end())
            dp.push_back(a[i]);
        else
            *it = a[i];
    }
    printf("%d\n", (int)dp.size());
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        solve(a);
    }
    return 0;
}

这样写的话，不管它要递增还是递减，严格还是非严格，都只要改查找那一行就够了，非常方便。

以下再演示LCS的实现

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void solve(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(m + 1);
    dp[0].resize(n + 1);
    for (int j = 0; j < m; j++) {
        dp[j + 1].resize(n + 1);
        for (int i = 0; i < n; i++) {
            if (b[j] == a[i]) {
                dp[j + 1][i + 1] = dp[j][i] + 1;
            } else {
                dp[j + 1][i + 1] = max(dp[j][i + 1], dp[j + 1][i]);
            }
        }
    }
    cout << dp[m][n] << endl;
}
int main() {
    string a, b;
    while (cin >> a >> b) {
        solve(a, b);
    }
    return 0;
}

以下演示n皇后实现

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
int dfs(int n, int row, vector<int> &col, vector<int> &add, vector<int> &sub) {
    if (row >= n) return 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (col[i]) continue;
        if (add[i + row]) continue;
        if (sub[n + i - row]) continue;
        sub[n + i - row] = add[i + row] = col[i] = 1;
        sum += dfs(n, row + 1, col, add, sub);
        sub[n + i - row] = add[i + row] = col[i] = 0;
    }
    return sum;
}
void solve(map<int, int> &result, int n) {
    if (result.count(n)) {
        cout << result[n] << endl;
    } else {
        vector<int> col, add, sub;
        col.resize(n);
        add.resize(n * 2);
        sub.resize(n * 2);
        cout << (result[n] = dfs(n, 0, col, add, sub)) << endl;
    }
}
int main() {
    map<int, int> result;
    int n;
    while (cin >> n && n > 0) {
        solve(result, n);
    }
    return 0;
}

4. 用自动格式化代码的工具

如果用vscode，它有自带的格式化工具，而如果是code::blocks/devcpp，那就需要自己配置cstyle，这里不介绍配置方法，网上文章有。

文章的最后

如果你有代码不知道怎么改写得漂亮优美，可以发我代码。