1 条题解

  • 0
    @ 2025-4-16 12:59:22

    手写哈希表

    vector 写法

    #include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, m;
int len[212345];
int nxt[212345];
int pre[212345];
const int SZ = 3123456;
struct hash_map
{ // 哈希表模板
    vector<pair<unsigned long long, int>> data[SZ];
    int hash(unsigned long long u) { return u % SZ; }
    int &operator[](unsigned long long u)
    {
        int hu = hash(u); // 获取头指针
        for (int i = 0; i < data[hu].size(); i++)
            if (data[hu][i].first == u)
                return data[hu][i].second;
        data[hu].push_back({u, 0});
        return data[hu].back().second;
    }
} hm;
unsigned long long B[105];
int now[105];
unsigned long long nowH[105];
unsigned long long sH[10000005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    B[0] = 1;
    for (int i = 1; i <= 100; i++)
        B[i] = B[i - 1] * 137;
    for (int i = 1; i <= n; i++)
    {
        cin >> len[i];
        nxt[i] = pre[i] = -1;
        hm[len[i]]++;
    }
    for (int T = 1; T <= m; T++)
    {
        int op, x, y, k;
        string S;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            // 合并
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 1; i <= 50; i++)
                if (now[i] != 0)
                    for (int j = 51; j <= i + 50 - 1; j++)
                        if (now[j] != 0)
                        {
                            unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                            hm[h]++;
                        }
            nxt[x] = y;
            pre[y] = x;
        }
        else if (op == 2)
        {
            cin >> x;
            y = nxt[x];
            // 分裂
            pre[y] = -1;
            nxt[x] = -1;
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 1; i <= 50; i++)
                if (now[i] != 0)
                    for (int j = 51; j <= i + 50 - 1; j++)
                        if (now[j] != 0)
                        {
                            unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                            hm[h]--;
                        }
        }
        else if (op == 3)
        {
            cin >> S >> k;
            for (int i = 1; i <= S.length(); i++)
                sH[i] = sH[i - 1] * 137 + S[i - 1] - '0';
            // mul(f(t))
            int ans = 1;
            bool flag = false;
            for (int i = 1; i + k - 1 <= S.length(); i++)
            {
                unsigned long long h = sH[i + k - 1] - sH[i - 1] * B[k];
                int cnt = hm[h];
                ans = (long long)ans * cnt % MOD;
                flag = true;
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

    链式前向星写法

    #include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, m;
int len[212345];
int nxt[212345];
int pre[212345];
const int SZ = 3123456;
struct hash_map
{ // 哈希表模板
    struct data
    {
        unsigned long long u;
        int v, nex;
    };               // 前向星结构
    data e[SZ << 1]; // SZ 是 const int 表示大小
    int h[SZ], cnt;
    int hash(unsigned long long u) { return u % SZ; }
    int &operator[](unsigned long long u)
    {
        int hu = hash(u); // 获取头指针
        for (int i = h[hu]; i; i = e[i].nex)
            if (e[i].u == u)
                return e[i].v;
        return e[++cnt] = (data){u, 0, h[hu]}, h[hu] = cnt, e[cnt].v;
    }
    hash_map()
    {
        cnt = 0;
        memset(h, 0, sizeof(h));
    }
} hm;
unsigned long long B[105];
int now[105];
unsigned long long nowH[105];
unsigned long long sH[10000005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    B[0] = 1;
    for (int i = 1; i <= 100; i++)
        B[i] = B[i - 1] * 137;
    for (int i = 1; i <= n; i++)
    {
        cin >> len[i];
        nxt[i] = pre[i] = -1;
        hm[len[i]]++;
    }
    for (int T = 1; T <= m; T++)
    {
        int op, x, y, k;
        string S;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            //合并
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 1; i <= 50; i++)
                if (now[i] != 0)
                    for (int j = 51; j <= i + 50 - 1; j++)
                        if (now[j] != 0)
                        {
                            unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                            hm[h]++;
                        }
            nxt[x] = y;
            pre[y] = x;
        }
        else if (op == 2)
        {
            cin >> x;
            y = nxt[x];
            //分裂
            pre[y] = -1;
            nxt[x] = -1;
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 1; i <= 50; i++)
                if (now[i] != 0)
                    for (int j = 51; j <= i + 50 - 1; j++)
                        if (now[j] != 0)
                        {
                            unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                            hm[h]--;
                        }
        }
        else if (op == 3)
        {
            cin >> S >> k;
            for (int i = 1; i <= S.length(); i++)
                sH[i] = sH[i - 1] * 137 + S[i - 1] - '0';
            // mul(f(t))
            int ans = 1;
            bool flag = false;
            for (int i = 1; i + k - 1 <= S.length(); i++)
            {
                unsigned long long h = sH[i + k - 1] - sH[i - 1] * B[k];
                int cnt = hm[h];
                ans = (long long)ans * cnt % MOD;
                flag = true;
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

    自带 unordered_map 的超时 92 分

    #include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, m;
int len[212345];
int nxt[212345];
int pre[212345];
const int SZ = 3123456;
unordered_map<unsigned long long, int> hm;
unsigned long long B[105];
int now[105];
unsigned long long nowH[105];
unsigned long long sH[10000005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    B[0] = 1;
    for (int i = 1; i <= 100; i++)
        B[i] = B[i - 1] * 137;
    for (int i = 1; i <= n; i++)
    {
        cin >> len[i];
        nxt[i] = pre[i] = -1;
        hm[len[i]]++;
    }
    for (int T = 1; T <= m; T++)
    {
        int op, x, y, k;
        string S;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            // 合并
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 50; i >= 1; i--)
            {
                if (now[i] == 0)
                    break;
                for (int j = 51; j <= i + 50 - 1; j++)
                {
                    if (now[j] == 0)
                        break;
                    unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                    hm[h]++;
                }
            }
            nxt[x] = y;
            pre[y] = x;
        }
        else if (op == 2)
        {
            cin >> x;
            y = nxt[x];
            // 分裂
            pre[y] = -1;
            nxt[x] = -1;
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 50; i >= 1; i--)
            {
                if (now[i] == 0)
                    break;
                for (int j = 51; j <= i + 50 - 1; j++)
                {
                    if (now[j] == 0)
                        break;
                    unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                    hm[h]--;
                }
            }
        }
        else if (op == 3)
        {
            cin >> S >> k;
            for (int i = 1; i <= S.length(); i++)
                sH[i] = sH[i - 1] * 137 + S[i - 1] - '0';
            // mul(f(t))
            int ans = 1;
            bool flag = false;
            for (int i = 1; i + k - 1 <= S.length(); i++)
            {
                unsigned long long h = sH[i + k - 1] - sH[i - 1] * B[k];
                int cnt = hm[h];
                ans = (long long)ans * cnt % MOD;
                flag = true;
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

    map 的超时 60 分

    #include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, m;
int len[212345];
int nxt[212345];
int pre[212345];
const int SZ = 3123456;
map<unsigned long long, int> hm;
unsigned long long B[105];
int now[105];
unsigned long long nowH[105];
unsigned long long sH[10000005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    B[0] = 1;
    for (int i = 1; i <= 100; i++)
        B[i] = B[i - 1] * 137;
    for (int i = 1; i <= n; i++)
    {
        cin >> len[i];
        nxt[i] = pre[i] = -1;
        hm[len[i]]++;
    }
    for (int T = 1; T <= m; T++)
    {
        int op, x, y, k;
        string S;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            // 合并
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 1; i <= 50; i++)
                if (now[i] != 0)
                    for (int j = 51; j <= i + 50 - 1; j++)
                        if (now[j] != 0)
                        {
                            unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                            hm[h]++;
                        }
            nxt[x] = y;
            pre[y] = x;
        }
        else if (op == 2)
        {
            cin >> x;
            y = nxt[x];
            // 分裂
            pre[y] = -1;
            nxt[x] = -1;
            for (int i = 1; i <= 100; i++)
                now[i] = nowH[i] = 0;
            for (int i = x, cnt = 50; i != -1 && cnt >= 1; i = pre[i], cnt--)
                now[cnt] = len[i];
            for (int i = y, cnt = 51; i != -1 && cnt <= 100; i = nxt[i], cnt++)
                now[cnt] = len[i];
            for (int i = 1; i <= 100; i++)
                nowH[i] = nowH[i - 1] * 137 + now[i];
            for (int i = 1; i <= 50; i++)
                if (now[i] != 0)
                    for (int j = 51; j <= i + 50 - 1; j++)
                        if (now[j] != 0)
                        {
                            unsigned long long h = nowH[j] - nowH[i - 1] * B[j - i + 1];
                            hm[h]--;
                        }
        }
        else if (op == 3)
        {
            cin >> S >> k;
            for (int i = 1; i <= S.length(); i++)
                sH[i] = sH[i - 1] * 137 + S[i - 1] - '0';
            // mul(f(t))
            int ans = 1;
            bool flag = false;
            for (int i = 1; i + k - 1 <= S.length(); i++)
            {
                unsigned long long h = sH[i + k - 1] - sH[i - 1] * B[k];
                int cnt = hm[h];
                ans = (long long)ans * cnt % MOD;
                flag = true;
            }
            cout << ans << "\n";
        }
    }
    return 0;
}
    • 1

    [NOI2017] 蚯蚓排队

    信息

    ID
    1361
    时间
    3000ms
    内存
    1250MiB
    难度
    6
    标签
    递交数
    31
    已通过
    5
    上传者
    1. 评测队列
    2. 服务状态
    3. 兼容模式
    4. 主题
    2. 陕ICP备2024054233号
    3. Worker 0, 53ms
    4. Powered by Hydro v4.19.1 Community, Modified by 33DAI