头像

trudbot

$\href{http://trudbot.cn/}{{点击进入我的个人网站}}$




离线:42分钟前


最近来访(262)
用户头像
情断青丝
用户头像
Sufferingcreatinglife
用户头像
要好好学习鸭
用户头像
_Zhou_Bo_
用户头像
khalil
用户头像
浮尘_9999
用户头像
杨淇
用户头像
Weather
用户头像
木讷2.0
用户头像
天元之弈
用户头像
逆夏
用户头像
人生如戏ba
用户头像
滑雪
用户头像
凌乱之风
用户头像
再躺平是狗
用户头像
AuJinn
用户头像
Autonomy
用户头像
懒得理你
用户头像
Murphy_
用户头像
贾淏文


trudbot
22小时前

区间递推以i结束/开头的连续序列最大和, 在此过程中记录i之前/之后的最大和。最后枚举分界线。

#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int a[N], mx[N], mxt[N];

int main () {
    int T; cin >> T;
    while (T --) {
        int n; cin >> n;
        for (int i = 1; i <= n; i ++) {
            cin >> a[i];
        }
        mx[0] = mxt[n + 1] = -1e9;
        int lt = 0, ltt = 0;
        for (int i = 1, j = n; j >= 1; i ++, j --) {
            int f = a[i] + (lt < 0 ? 0 : lt);
            int ft = a[j] + (ltt < 0 ? 0 : ltt);
            mx[i] = max(mx[i-1], f);
            mxt[j] = max(mxt[j + 1], ft);
            lt = f, ltt = ft;
        }

        int ans = -1e9;
        for (int i = 1; i <= n; i ++) {
            ans = max(ans, mx[i] + mxt[i + 1]);
        }
        cout << ans << endl;
    }
    return 0;
}


题目讨论 AcWing 4676. 退退退

trudbot
1天前

为什么字符串哈希过不了, 难道是常数太大吗😥




trudbot
2天前

很显然如果存在长度为k的最长公共子字符串,那么长度为k-1的公共子字符串也必定存在。因此我们可以二分最长公共子字符串的长度, 求右边界。假设现在的长度为k,check(k) 的逻辑为我们将所有所有字符串的长度为k的子串分别进行哈希,将哈希值放入n个哈希表中存储。之后求交集即可。

#include <bits/stdc++.h>
using namespace std;

class HashString {
private:
    typedef unsigned long long ull;
    const int P = 131;
    vector<ull> p;
    vector<ull> prefix;
    int n;
public:
    HashString(string s) {
        n = s.size();
        s.insert(0, "0");
        p.resize(n + 1), p[0] = 1;
        prefix.resize(n + 1, 0);
        for(int i=1; i<=n; i++) {
            p[i] = p[i-1] * P;
            prefix[i] = prefix[i - 1] * P + s[i];
        }
    }

    ull get(int l, int r) {
        l++, r++;
        return prefix[r] - prefix[l - 1] * p[r - l + 1];
    }
};

int main () {
    int T; cin >> T;
    while (T --) {
        int n; cin >> n;
        string ss[n];
        vector<HashString> hss;
        for (int i = 0; i < n; i ++) {
            cin >> ss[i];
            hss.push_back(HashString(ss[i]));
        }
        int l = 1, r = 60;

        set<unsigned long long> hashCode;//保存最后一次求交集产生的哈希值
        auto check = [&] (int m) -> bool {
            set<unsigned long long> sets[n];
            for (int i = 0; i < n; i ++) {
                for (int j = 0; j + m - 1 < 60; j ++) {
                    sets[i].insert(hss[i].get(j, j + m - 1));
                }
            }
            map<unsigned long long, int> cnt;//用哈希表统计出现次数求交集
            for (int i = 0; i < n; i ++) {
                for (auto v : sets[i]) {
                    cnt[v]++;
                }
            }
            set<unsigned long long> t;//保存交集中的元素
            for (auto p : cnt) {
                if (p.second == n) {
                    t.insert(p.first);
                }
            }
            if (t.empty()) {
                return false;
            }
            hashCode = t;
            return true;
        };

        while (l < r) {
            int m = (l + r + 1) >> 1;
            if (check(m)) {
                l = m;
            } else {
                r = m - 1;
            }
        }

        if (r < 3) {
            cout << "no significant commonalities" << endl;
            continue;
        }
        vector<string> ans;//保存所有符合题意的子串
        for (l = 0; l + r - 1 < 60; l++) {
            if (hashCode.count(hss[0].get(l, l + r - 1))) {
                ans.push_back(ss[0].substr(l, r));
            }
        }
        sort(ans.begin(), ans.end());
        cout << ans[0] << endl;
    }
    return 0;
}




trudbot
2天前

字符串哈希
$O(n)$

# include <bits/stdc++.h>
using namespace std;

class HashString {
private:
    typedef unsigned long long ull;
    const int P = 131;
    vector<ull> p;
    vector<ull> prefix;
    int n;
public:
    HashString(string s) {
        n = s.size();
        s.insert(0, "0");
        p.resize(n + 1), p[0] = 1;
        prefix.resize(n + 1, 0);
        for(int i=1; i<=n; i++) {
            p[i] = p[i-1] * P;
            prefix[i] = prefix[i - 1] * P + s[i];
        }
    }

    ull get(int l, int r) {
        l++, r++;
        return prefix[r] - prefix[l - 1] * p[r - l + 1];
    }
};


int main () {
    int n; cin >> n;
    while (n -- ) {
        string w, t; cin >> w >> t;
        auto hsw = HashString(w), hst = HashString(t);
        int len = (int) w.size(), ans = 0;
        for (int i = 0; i + len <= t.size(); i++) {
            if (hsw.get(0, len - 1) == hst.get(i, i + len - 1)) {
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}



trudbot
2天前

本题和4679几乎相同

#include <bits/stdc++.h>
using namespace std;

class HashString {
private:
    typedef unsigned long long ull;
    const int P = 131;
    vector<ull> p;
    vector<ull> prefix;
    int n;
public:
    HashString (string s) {
        n = s.size();
        s.insert(0, "0");
        p.resize(n + 1), p[0] = 1;
        prefix.resize(n + 1, 0);
        for(int i=1; i<=n; i++) {
            p[i] = p[i-1] * P;
            prefix[i] = prefix[i - 1] * P + s[i];
        }
    }

    ull get (int l, int r) {
        l++, r++;
        return prefix[r] - prefix[l - 1] * p[r - l + 1];
    }
};

int find (string s) {
    int n = (int) s.size();
    auto hs = HashString(s);
    for (int i = 1; i < n; i++) {
        auto v = hs.get(0, i-1);
        int j = i, flag = 1;
        for (; j + i - 1 < n; j += i) {
            if (! (v == hs.get(j, j + i - 1))) {
                flag = 0;
                break;
            }
        }
        if (flag ) {
            if (j == n) {
                return 0;
            } else if (hs.get(j, n - 1) == hs.get(0, n - j - 1)) {
                return i - (n - j);
            }
        }
    }
    return n;
}

int main () {
    int n; cin >> n;
    while (n -- ) {
        string s; cin >> s;
        cout << find(s) << endl;
    }
    return 0;
} 



trudbot
2天前

字符串哈希板子。

#include <bits/stdc++.h>
using namespace std;

class HashString {
private:
    typedef unsigned long long ull;
    const int P = 131;
    vector<ull> p;
    vector<ull> prefix;
    int n;
public:
    HashString(string s) {
        n = s.size();
        s.insert(0, "0");
        p.resize(n + 1), p[0] = 1;
        prefix.resize(n + 1, 0);
        for(int i=1; i<=n; i++) {
            p[i] = p[i-1] * P;
            prefix[i] = prefix[i - 1] * P + s[i];
        }
    }

    ull get(int l, int r) {
        l++, r++;
        return prefix[r] - prefix[l - 1] * p[r - l + 1];
    }
};

int main () {
    string s;
    while (cin >> s) {
        int n = (int) s.size();
        auto hs = HashString(s);
        for (int i = 1; i <= n; i ++) {
            if (hs.get(0, i - 1) == hs.get(n - i, n - 1)) {
                cout << i << " ";
            }
        }
        cout << endl;
    }
    return 0;
}




trudbot
2天前

字符串哈希。
不难发现, 该题题意为:
对于字符串s, 求出最短的字符串a满足: s由若干个a以及一个任意长度的a的前缀拼接而成。

#include <bits/stdc++.h>
using namespace std;

class HashString {
private:
    typedef unsigned long long ull;
    const int P = 131;
    vector<ull> p;
    vector<ull> prefix;
    int n;
public:
    HashString(string s) {
        n = s.size();
        s.insert(0, "0");
        p.resize(n + 1), p[0] = 1;
        prefix.resize(n + 1, 0);
        for(int i=1; i<=n; i++) {
            p[i] = p[i-1] * P;
            prefix[i] = prefix[i - 1] * P + s[i];
        }
    }

    ull get(int l, int r) {
        l++, r++;
        return prefix[r] - prefix[l - 1] * p[r - l + 1];
    }
};

int find (string s) {
    int n = (int) s.size();
    auto hs = HashString(s);
    for (int i = 1; i <= n; i++) {
        auto v = hs.get(0, i-1);
        int j = i, flag = 1;
        for (; j + i - 1 < n; j += i) {
            if (! (v == hs.get(j, j + i - 1))) {
                flag = 0;
                break;
            }
        }
        if (flag && (j == n || hs.get(j, n - 1) == hs.get(0, n - j - 1))) {
            return i;
        }
    }
}

int main () {
    string s;
    while (cin >> s) {
        cout << find(s) << endl;
    }
    return 0;
} 



trudbot
2天前

字符串哈希水过

题意字符串s由n个字符串a拼接而成, 求最大的n。

算法:从小到大枚举每一个能被s长度整除的数i,将s分成i快判断是否相等, 用字符串哈希优化此过程。

#include <bits/stdc++.h>
using namespace std;

class HashString {
private:
    typedef unsigned long long ull;
    const int P = 131;
    vector<ull> p;
    vector<ull> prefix;
    int n;
public:
    HashString(string s) {
        n = s.size();
        s.insert(0, "0");
        p.resize(n + 1), p[0] = 1;
        prefix.resize(n + 1, 0);
        for(int i=1; i<=n; i++) {
            p[i] = p[i-1] * P;
            prefix[i] = prefix[i - 1] * P + s[i];
        }
    }

    ull get(int l, int r) {
        l++, r++;
        return prefix[r] - prefix[l - 1] * p[r - l + 1];
    }
};

int find (string s) {
    int n = (int)s.size();
    auto hs = HashString(s);
    for (int i = 1; i <= n; i ++) {
        if (n % i) {
            continue;
        }
        bool flag = true;
        auto v = hs.get(0, i - 1);
        for (int j = i; j < n; j += i) {
            if (! (hs.get(j, j + i - 1) == v)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return n / i;
        }
    }
    return 1;
}

int main () {
    string s;
    getline(cin, s);
    while (s != ".") {
        cout << find(s) << endl;
        getline(cin, s);
    }
    return 0;
}



trudbot
2天前

字符串哈希, 从大到小枚举长度

#include <bits/stdc++.h>
using namespace std;

class HashString {
private:
    typedef unsigned long long ull;
    const int P = 131;
    vector<ull> p;
    vector<ull> prefix;
    int n;
public:
    HashString(string s) {
        n = s.size();
        s.insert(0, "0");
        p.resize(n + 1), p[0] = 1;
        prefix.resize(n + 1, 0);
        for(int i=1; i<=n; i++) {
            p[i] = p[i-1] * P;
            prefix[i] = prefix[i - 1] * P + s[i];
        }
    }

    ull get(int l, int r) {
        return prefix[r] - prefix[l - 1] * p[r - l + 1];
    }
};

int main () {
    string s1, s2;
    while (cin >> s1 >> s2) {
        int len = min(s1.size(), s2.size());
        int r = s2.size();
        auto hs1 = HashString(s1), hs2 = HashString(s2);
        while (len > 0) {
            if (hs1.get(1, len) == hs2.get(r - len + 1, r)) {
                break;
            }
            len --;
        }
        if (len) {
            cout << s1.substr(0, len) << " ";
        }
        cout << len << endl;
    }
    return 0;
}


活动打卡代码 AcWing 901. 滑雪

trudbot
2天前
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int a[N][N], mx[N][N];
int n, m;
pair<int, int> dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int dfs(int r, int c) {
    if (mx[r][c] == -1) {
        mx[r][c] = 1;
        for (int i = 0; i < 4; i++) {
            int r1 = r + dir[i].first, c1 = c + dir[i].second;
            if (a[r][c] > a[r1][c1]) {
                mx[r][c] = max(mx[r][c], 1 + dfs(r1, c1));
            }
        }
    }
    return mx[r][c];
}

int main () {
    cin >> n >> m;
    memset(a, 0x3f, sizeof a);
    memset(mx, -1, sizeof mx);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mx[i][j] == -1) {
                ans = max(ans, dfs(i, j));
            }
        }
    }
    cout << ans << endl;
    return 0;
}