最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球聚焦：找段错误找了一个小时，纪念一下

来源：博客园


【资料图】

题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805344776077312

你猜怎么着，我把M看成了N,N<300，我数组就开了1000，我甚至觉得很够了已经，结果人家M的范围压根没给，后来算算大概有5万。抛了个段错误我还一直以为是测试数据有问题，蠢死我了！！

这题我一开始按照dfs的套路去做了，但是最后一个节点超时了我靠：

#include#include#include#include#include#includeusing namespace std;#define inf 0x3f3f3f3f struct edge {    string to;    int next;} g[50000];int head[301], cnt;string s, t;unordered_map M;vector > res;vector path;int vis[301], gender[301];void dfs(string cur, int cur_step) {    if (cur_step == 4) {        // 找到        res.push_back(path);        return ;    }    if (cur_step == 1) {        // 找和A同性的        for (int i = head[M[cur]]; i; i = g[i].next) {            string to = g[i].to;            if (!vis[M[to]] && gender[M[to]] == gender[M[s]] && to != t) {                vis[M[to]] = 1;                path.push_back(to[0] == "-" ? to.substr(1, to.size() - 1) : to);                dfs(to, cur_step + 1);                path.pop_back();                vis[M[to]] = 0;            }        }    } else if (cur_step == 2){        // 找和B同性的        for (int i = head[M[cur]]; i; i = g[i].next) {            string to = g[i].to;            if (!vis[M[to]] && gender[M[to]] == gender[M[t]] && to != t) {                vis[M[to]] = 1;                path.push_back(to[0] == "-" ? to.substr(1, to.size() - 1) : to);                dfs(to, cur_step + 1);                path.pop_back();                vis[M[to]] = 0;            }        }    } else if (cur_step == 3) {        // 找B        for (int i = head[M[cur]]; i; i = g[i].next) {            string to = g[i].to;            if (!vis[M[to]] && to == t) {                vis[M[to]] = 1;                dfs(to, cur_step + 1);                vis[M[to]] = 0;            }        }    }}bool cmp(vector &a, vector &b) {    return (a[0] < b[0]) || (a[0] == b[0] && a[1] < b[1]);}void output() {    for (int i = 0; i < res.size(); i++) {        cout << res[i][0] << " " << res[i][1] << endl;    }}int n, m, k, num;int main() {    cin >> n>> m;    for (int i = 0; i < m; i++) {        string a, b;        cin >> a >> b;        if (M.find(a) == M.end()) {            M[a] = ++num;        }        if (M.find(b) == M.end()) {            M[b] = ++num;        }        g[++cnt] = edge{b, head[M[a]]};        head[M[a]] = cnt;        g[++cnt] = edge{a, head[M[b]]};        head[M[b]] = cnt;        gender[M[b]] = (b[0] != "-");        gender[M[a]] = (a[0] != "-");    }    cin >> k;    for (int i = 0; i < k; i++) {        cin >> s >> t;        if (M.find(s) == M.end()) {            cout << 0 << endl;            continue;        }        memset(vis, 0, sizeof(vis));        vis[M[s]] = 1;        path.clear();        res.clear();        dfs(s, 1);        sort(res.begin(), res.end(), cmp);        printf("%d\n", res.size());        output();    }    return 0;}

没办法，两个半小时的苦苦挣扎之后再叫我再去优化代码，我可不干了。换个思路吧，看看柳神的代码：

#include #include #include #include #include using namespace std;unordered_map arr;struct node { // vector + 结构体就好了，妈的，我在搞什么二维的vector，多捞啊    int a, b;};bool cmp(node x, node y) {    return x.a != y.a ? x.a < y.a : x.b < y.b; // 三元表达式的写法，嘿嘿，学到了}int main() {    int n, m, k;    scanf("%d%d", &n, &m);    vector v[10000];    for (int i = 0; i < m; i++) {        string a, b;        cin >> a >> b;        if (a.length() == b.length()) { // 邻接表记录同性朋友，思路是真的清晰！            v[abs(stoi(a))].push_back(abs(stoi(b))); // stoi() 这玩意为啥总是记不住？有前导零也不怕，照样盘它！            v[abs(stoi(b))].push_back(abs(stoi(a)));        }        arr[abs(stoi(a)) * 10000 + abs(stoi(b))] = arr[abs(stoi(b)) * 10000 + abs(stoi(a))] = true; // 邻接矩阵一维化，有效地节省了空间，秀我一脸。。。        // 连等是个技巧    }    scanf("%d", &k);    for (int i = 0; i < k; i++) {        int c, d;        cin >> c >> d;        vector ans;        for (int j = 0; j < v[abs(c)].size(); j++) {            for (int k = 0; k < v[abs(d)].size(); k++) {                if (v[abs(c)][j] == abs(d) || abs(c) == v[abs(d)][k]) continue; // 朋友总不能直接是对象吧，也不能是自己吧，PASS PASS                if (arr[v[abs(c)][j] * 10000 + v[abs(d)][k]] == true)                    ans.push_back(node{v[abs(c)][j], v[abs(d)][k]});  // 我的朋友和你的朋友是不是朋友呢？两个for循环 woc 多么省力啊，我还搁那 dfs 半天写不清楚            }        }        sort(ans.begin(), ans.end(), cmp); // 排完序就出来了，over！！        printf("%d\n", int(ans.size()));        for(int j = 0; j < ans.size(); j++)            printf("%04d %04d\n", ans[j].a, ans[j].b); // 千万记得格式 %04d 上一题我就栽在这里了，耗了半个小时才发现    }    return 0;}

关键词：