一个无法理解的 RE 问题
  • 板块学术版
  • 楼主black_trees
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/2/2 20:49
  • 上次更新2023/10/24 01:59:47
查看原帖
一个无法理解的 RE 问题
304550
black_trees楼主2023/2/2 20:49

RT,这份代码编译过后运行会直接得到 SIGSEGV 也就是 Segmentation fault 的结果。

// author : black_trees

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

class StringWithDoubleHash {
private: 
    string s; i64 len;
    i64 h[2][si], power[2][si];
    const i64 base = 131;
    const i64 m[2] = {998244853ll, 1000000009ll};
public:
    int Size() { return len; }
    i64 Index(char ch) { return (i64)(ch - 'a'); }
    void Init(string t) {
        s = ' ' + t, len = (int)t.size();
        power[0][0] = power[1][0] = 1ll;
        for(int _ = 0; _ <= 1; ++_) {
            for(int i = 1; i <= len; ++i) {
                power[_][i] = power[_][i - 1] * base % m[_];
            }
        }
        h[0][0] = h[1][0] = 0ll;
        for(int _ = 0; _ <= 1; ++_) {
            for(int i = 1; i <= len; ++i) {
                h[_][i] = (h[_][i - 1] * base) % m[_] + Index(s[i]) % m[_];
            }
        }
    }
    i64 Query(int _, int l, int r) {
        return (h[_][r] - (h[_][l - 1] * power[_][r - l + 1] % m[_]) + m[_]) % m[_];
    }
    bool Equal(int l1, int r1, int l2, int r2) {
        bool f = true;
        for(int _ = 0; _ <= 1; ++_) {
            f &= (Query(_, l1, r1) == Query(_, l2, r2));
        }
        return f;
    }
};

using str = StringWithDoubleHash;
bool Equal(str a, str b, int l, int r) {
    if(a.Size() != b.Size()) return false;
    bool f = true;
    for(int i = 0; i <= 1; ++i) 
        f &= (a.Query(i, l, r) == b.Query(i, l, r));
    return f;
}

int Radius(str s, int l, int r, int c) {
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(c - mid + 1 >= 1 && c + mid - 1 <= s.Size() 
           && s.Equal(c - mid + 1, c, c, c + mid - 1))
            l = mid;
        else r = mid - 1;
    }
    return l;
}
int Radius_ignore(str s, int l, int r, int c, int Ra) {
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(c - mid + 1 >= 1 && c + mid - 1 <= s.Size()
        && s.Equal(c - mid + 1, c - Ra - 1, c + Ra + 1, c + mid - 1))
            l = mid;
        else r = mid - 1;
    }
    return l;
} 
str s;

int Rad[si];
int delta[si][27];
int pre[si], suf[si], cnt[si];
void fix(int a[], int l, int r, int v) {
    a[r] += v, a[l - 1] -= v;
}
void redo(int a[], int n) { 
    for(int i = 1; i <= n; ++i)
        a[i] = a[i] + a[i + 1];
} 

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    string tmp; cin >> tmp;
    string t = "#";
    for(int i = 0; i < (int)tmp.size(); ++i)
        t += tmp[i], t += '#';
    s.Init(t), t = ' ' + t;

    // cout << t << endl;

    int n = s.Size(), sum = 0;
    for(int i = 1; i <= n; ++i) {
        Rad[i] = Radius(s, 1, n, i);
        sum = sum + (Rad[i] / 2);
        int L = i - Rad[i] + 1, R = i + Rad[i] - 1;

        // loosen
        if(L - 1 >= 1 && R + 1 <= n) {
            char ch1 = t[L - 1], ch2 = t[R + 1];
            int Rr = Radius_ignore(s, Rad[i], n, i, Rad[i]);
            delta[L - 1][(int)(ch2 - 'a' + 1)] += Rr - Rad[i];
            delta[R + 1][(int)(ch1 - 'a' + 1)] += Rr - Rad[i];
        }

        // lessen
        fix(pre, L, i, L), fix(suf, i, R, R), fix(cnt, L, R, 1);
    }
    redo(pre, n), redo(suf, n), redo(cnt, n);

// for(int i = 1; i <= n; ++i) cout << Rad[i] << endl;

    int ans = -1;
    for(int i = 1; i <= n; ++i) {
        if(t[i] == '#') continue;
        for(char ch = 'a'; ch <= 'z'; ++ch) {
            int add = delta[i][(int)(ch - 'a' + 1)];
            int sub = pre[i] + suf[i] - (i * cnt[i]);
            ans = max(ans, sum + (add - sub) / 2);
        }
    }

    cout << ans << endl;

    return 0;
}

// ()()()(?

经过 gdb 调试得到了以下信息:

Reading symbols from T4...
(gdb) r
Starting program: C:\Users\Administrator\OneDrive\Workspace\Code\Mockcontests\20230201C\T4.exe
[New Thread 8836.0x23e0]
[New Thread 8836.0x2cd4]
[New Thread 8836.0x2a90]

Thread 1 received signal SIGSEGV, Segmentation fault.
0x00007ff7b6ec29c6 in ___chkstk_ms ()
(gdb)

经过各种搜索找到了这个函数的源码注释:

/* ___chkstk_ms is a *special* function call, which uses %rax as the argument.We avoid clobbering any registers.  Unlike ___chkstk, it just probes the stack and does no stack allocation.  */

功能大致是在分配一个新的栈之后进行一些检查

猜测是申请栈空间的时候触发了什么错误,但是具体并不清楚,网上也没有类似的原因。

而且因为是运行就 RE 了,我猜测大概率问题出在 class StringWithDoubleHash 当中,但是并没有看出来问题。

各种询问无果,所以发个帖看看有没有大佬能看出来/kk,万分感谢

2023/2/2 20:49
加载中...