70分RE求调
查看原帖
70分RE求调
1028047
ZinfI_Sh楼主2024/8/7 15:39

两个点RE,一点WA,另一个OJ全RE

#include <bits/stdc++.h>
#define int long long
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define lowbit(x) (x & -x)
using namespace std;
const int DM[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};
const int HASHMOD = 9223372036854775783;
const int HASHBASE = 131;
const int HASHITEM = 999997;
inline void read(int &res)
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    res = x * f;
}
int get_hash(string s)
{
    int res = 0;
    for (int i = 0; i < s.size(); i++)
    {
        res = (res * HASHBASE % HASHMOD + s[i] - 'a') % HASHMOD;
    }
    return res;
}
struct HashTable
{
    struct Edge
    {
        int v, c;
    };
    vector<Edge> e[HASHITEM * 2];
    void clear()
    {
        for (int i = 0; i < HASHITEM; i++)
        {
            e[i].clear();
        }
    }
    bool find(int val)
    {
        int tmp = val % HASHITEM, it = 0;
        for (auto en : e[tmp])
        {
            if (en.v == val)
            {
                e[tmp][it].c++;
                return 1;
            }
            it++;
        }
        return 0;
    }
    void erase(int val, int &chan)
    {
        int tmp = val % HASHITEM, ite = 0;
        vector<Edge>::iterator it = e[tmp].begin();
        for (auto en : e[tmp])
        {
            if (en.v == val)
            {
                e[tmp][ite].c--;
                if (e[tmp][ite].c == 0)
                {
                    e[tmp].erase(it);
                    chan--;
                }
                break;
            }
            it++;
            ite++;
        }
    }
    void insert(int val, int &chan)
    {
        if (find(val))
        {
            return;
        }
        int tmp = val % HASHITEM;
        e[tmp].push_back({val, 1});
        chan++;
    }
} ht;
int bh[1000001];
bitset<10000001> in;
signed main()
{
    int n, m, ans1 = 0, ans2 = (1 << 30);
    cin >> n;
    string s;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        ht.insert(get_hash(s), ans1);
    }
    ans1 = 0;
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> s;
        bh[i] = get_hash(s);
        if (ht.find(bh[i]))
        {
            in[i] = 1;
        }
    }
    ht.clear();
    for (int i = 1; i <= m; i++)
    {
        if (in[i])
        {
            ht.insert(bh[i], ans1);
        }
    }
    cout << ans1 << '\n';
    ht.clear();
    int now = 0;
    for (int l = 1, r = 0; l <= m; l++)
    {
        while (now < ans1 && r < m)
        {
            r++;
            if (in[r])
            {
                ht.insert(bh[r], now);
            }
        }
        if (now == ans1)
        {
            ans2 = min(ans2, r - l + 1);
        }
        if (in[l])
        {
            ht.erase(bh[l], now);
        }
    }
    cout << ans2;
    return 0;
}
2024/8/7 15:39
加载中...