2023冲刺国赛模拟 38.1

标签：__ const int h1 国赛 38.1 2023 Hash id

又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又又垫底了！

T1 智力游戏

直接暴力搜索当前移动哪个长方体，移动方向和移动步数竟然能过……

Bfs 效率比较高，迭代加深 Dfs 也可以通过。

code

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

const int base = 37, mod1 = 998244353, mod2 = 20051107;

struct Hash
{
    int h1, h2;

    Hash () {}
    Hash ( int __h1, int __h2 )
        { h1 = __h1, h2 = __h2; }
    
    Hash operator + ( const Hash &A ) const
        { return Hash((h1 + A.h1) % mod1, (h2 + A.h2) % mod2); }
    Hash operator * ( const Hash &A ) const
        { return Hash(1LL * h1 * A.h1 % mod1, 1LL * h2 * A.h2 % mod2); }
    
    bool operator < ( const Hash &A ) const
    {
        if ( h1 == A.h1 )
            return h2 < A.h2;
        return h1 < A.h1;
    }
};

struct Option
{
    int id, x;
    char way;

    Option () {}
    Option ( int __id, char __way, int __x )
        { id = __id, way = __way, x = __x; }
};

int lim;
map <Hash, int> Map;
vector <Option> ans;

struct Matrix
{
    int matrix[6][6];

    Hash Get_Hash () const
    {
        Hash val = Hash(0, 0);
        for ( int i = 0; i < 6; i ++ )
            for ( int j = 0; j < 6; j ++ )
                val = val * Hash(base, base) + Hash(matrix[i][j] + 1, matrix[i][j] + 1);
        return val;
    }
}A;

void Dfs ( const Matrix &now, int depth )
{   
    Hash h = now.Get_Hash();
    if ( Map.find(h) != Map.end() && Map[h] <= depth )
        return;
    
    Map[h] = depth;
    
    if ( now.matrix[2][4] == 1 && now.matrix[2][5] == 1 )
    {
        printf("%d\n", depth);
        for ( auto v : ans )
            printf("%d %c %d\n", v.id, v.way, v.x);
        exit(0);
    }

    if ( depth == lim )
        return;

    Matrix tmp;

    for ( int i = 0; i < 6; i ++ )
    {
        for ( int j = 0; j < 6; j ++ )
        {
            if ( !now.matrix[i][j] || (i && now.matrix[i - 1][j] == now.matrix[i][j]) || (j && now.matrix[i][j - 1] == now.matrix[i][j]) )
                continue;
            
            if ( i != 5 && now.matrix[i][j] == now.matrix[i + 1][j] )
            {
                int L = i, R = i, id = now.matrix[i][j];
                while ( R != 5 && now.matrix[L][j] == now.matrix[R + 1][j] )
                    ++R;
                
                tmp = now;
                int x = 1;
                while ( L - x >= 0 && !now.matrix[L - x][j] )
                {
                    tmp.matrix[L - x][j] = id;
                    tmp.matrix[R - x + 1][j] = 0;
                    ans.push_back(Option(id, 'U', x));
                    Dfs(tmp, depth + 1);
                    ans.pop_back();
                    ++x;
                }

                tmp = now;
                x = 1;
                while ( R + x <= 5 && !now.matrix[R + x][j] )
                {
                    tmp.matrix[L + x - 1][j] = 0;
                    tmp.matrix[R + x][j] = id;
                    ans.push_back(Option(id, 'D', x));
                    Dfs(tmp, depth + 1);
                    ans.pop_back();
                    ++x;
                }
            }

            if ( j != 5 && now.matrix[i][j] == now.matrix[i][j + 1] )
            {
                int L = j, R = j, id = now.matrix[i][j];
                while ( R != 5 && now.matrix[i][L] == now.matrix[i][R + 1] )
                    ++R;
                
                tmp = now;
                int x = 1;
                while ( L - x >= 0 && !now.matrix[i][L - x] )
                {
                    tmp.matrix[i][L - x] = id;
                    tmp.matrix[i][R - x + 1] = 0;
                    ans.push_back(Option(id, 'L', x));
                    Dfs(tmp, depth + 1);
                    ans.pop_back();
                    ++x;
                }

                tmp = now;
                x = 1;
                while ( R + x <= 5 && !now.matrix[i][R + x] )
                {
                    tmp.matrix[i][L + x - 1] = 0;
                    tmp.matrix[i][R + x] = id;
                    ans.push_back(Option(id, 'R', x));
                    Dfs(tmp, depth + 1);
                    ans.pop_back();
                    ++x;
                }
            }
        }
    }
    return;
}

int main ()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);

    for ( int i = 0; i < 6; i ++ )
        for ( int j = 0; j < 6; j ++ )
            scanf("%d", &A.matrix[i][j]);
    
    while ( true )
    {
        Map.clear();
        Dfs(A, 0);
        ++lim;
    }

    return 0;
}

T2 区域划分

比较显然的两个有解条件是相邻两点所属党派不同和所有党派均出现过。

考虑直接进行构造，如果 \(0\) 的个数为 \(1\) ，可以直接从 \(0\) 向所有不相邻的点连边，如果 \(0\) 的个数大于 \(1\) ，将整个环按照 \(1\) 的位置进行划分，对于相邻的三个点 \((a, b, c)\) ，如果满足 \(b=0, a\ne b\ne 0\) ，那么将 \(a, b\) 连边，可以得到一个规模更小的子问题。

接下来整个环满足 \(0\) 两侧所属党派相同，对于一个 \(0\) 所在的位置 \(a\) ，如果两侧所属党派为 \(1\) ，将 \(a\) 和 \(a+1\) 向 \(a\) 前面第一个 \(2\) 所在的位置连边，如果两侧所属党派为 \(2\) ，将 \(a\) 和 \(a+1\) 向 \(a\) 前面第一个 \(1\) 所在的位置连边，这相当于删去点 \(a, a-1\) 。（貌似不是很显然，建议读者手摸几个样例）

为了保证 \(a\) 前面存在可以连边的位置，我们找到一个位置 \(p\) ，满足 \(p\) 为 \(0\) ， \(p+1, p+2\) 均不为 \(0\) ，从这个位置断环为链进行上述操作，可以证明一定存在这样的位置。

之后整个序列只存在一个 \(0\) ，直接简单构造即可。

code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

const int max1 = 1e5;

int n, a[max1 + 5], cnt[3], pos[3];
int id[max1 + 5], len;
bool vis[max1 + 5];

vector <pair <int, int>> ans;

int main ()
{
    freopen("divide.in", "r", stdin);
    freopen("divide.out", "w", stdout);

    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]), ++cnt[a[i]];
    
    bool flag = false;
    for ( int i = 1; i <= n - 1; i ++ )
        flag |= a[i] == a[i + 1];
    flag |= a[n] == a[1];

    for ( int i = 0; i < 3; i ++ )
        flag |= !cnt[i];
    
    if ( flag )
        puts("No");
    else
    {
        puts("Yes");
        for ( int i = 1; i <= n; i ++ )
        {
            int Prev = i - 1 == 0 ? n : i - 1;
            int Next = i + 1 == n + 1 ? 1 : i + 1;

            if ( cnt[0] > 1 && !a[i] && ((a[Prev] == 1 && a[Next] == 2) || (a[Prev] == 2 && a[Next] == 1)) )
            {
                vis[i] = true;
                ans.push_back(make_pair(Prev, Next));
                --cnt[0];
            }
        }

        if ( cnt[0] > 1 )
        {
            for ( int i = 1; i <= n; i ++ )
                if ( !vis[i] )
                    id[++len] = i;

            int start = 0;
            for ( int i = 1; i <= len; i ++ )
            {
                int p = i + 1 == len + 1 ? 1 : i + 1;
                int q = p + 1 == len + 1 ? 1 : p + 1;

                if ( !a[id[i]] && a[id[q]] && a[id[p]] != a[id[q]] )
                    { start = i; break; }
            }

            rotate(id + 1, id + start, id + 1 + len);

            for ( int i = 2; i <= len; i ++ )
            {
                if ( !a[id[i]] )
                {
                    if ( a[id[i - 1]] == 1 )
                    {
                        ans.push_back(make_pair(pos[2], id[i]));
                        ans.push_back(make_pair(pos[2], id[i + 1]));
                        vis[id[i - 1]] = vis[id[i]] = true;
                    }
                    else
                    {
                        ans.push_back(make_pair(pos[1], id[i]));
                        ans.push_back(make_pair(pos[1], id[i + 1]));
                        vis[id[i - 1]] = vis[id[i]] = true;
                    }
                }
                else
                    pos[a[id[i]]] = id[i];
            }
        }

        len = 0;
        for ( int i = 1; i <= n; i ++ )
            if ( !vis[i] )
                id[++len] = i;
        
        int start = 0;
        for ( int i = 1; i <= len; i ++ )
            if ( !a[id[i]] )
                { start = i; break; }
        
        rotate(id + 1, id + start, id + 1 + len);

        for ( int i = 3; i <= len - 1; i ++ )
            ans.push_back(make_pair(id[1], id[i]));
        
        for ( auto v : ans )
            printf("%d %d\n", v.first, v.second);
    }

    return 0;
}

T3 基因识别

让我们考虑一种纯正的根号做法。

首先建出所有文本串的 SA ，对于一个询问串，我们在 SA 上二分找到其对应的匹配一段区间，实际上求解的是这段区间中所有颜色去重后的权值和。

考虑操作分块，我们将询问所在块内涉及到的颜色单独处理，也就是求解一个区间内是否存在一种特定的颜色，将这个颜色所有出现的位置与询问涉及区间的左右端点取出，使用双指针求解。

考虑剩余颜色，一种比较套路的思路是对于每个位置找到前面第一个和其颜色相同的位置 \(pre\) ，实际上我们统计的是 \(pre<L\) 的位于区间 \([L, R]\) 内所有点的权值和，按照 \(pre\) 排序做扫描线即可，由于插入总数为 \(O(n\sqrt{n})\) ，询问总数为 \(O(n)\) ，可以使用分块平衡复杂度。

code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;

const int max1 = 3e5, B = 1500;
const int base = 29, mod1 = 998244353, mod2 = 20051107;

int n, m;
long long val[max1 + 5];

struct Hash_Value
{
    int h1, h2;

    Hash_Value () {}
    Hash_Value ( int __h1, int __h2 )
        { h1 = __h1, h2 = __h2; }
    
    Hash_Value operator + ( const Hash_Value &A ) const
        { return Hash_Value((h1 + A.h1) % mod1, (h2 + A.h2) % mod2); }
    Hash_Value operator - ( const Hash_Value &A ) const
        { return Hash_Value((h1 - A.h1 + mod1) % mod1, (h2 - A.h2 + mod2) % mod2); }
    Hash_Value operator * ( const Hash_Value &A ) const
        { return Hash_Value(1LL * h1 * A.h1 % mod1, 1LL * h2 * A.h2 % mod2); }
    bool operator == ( const Hash_Value &A ) const
        { return h1 == A.h1 && h2 == A.h2; }
};

Hash_Value power[max1 + 5];

struct Hash
{
    vector <Hash_Value> h; int len;

    void Build ( const char *s, int n )
    {
        len = n; h.resize(n + 1); h[0] = Hash_Value(0, 0);
        for ( int i = 1; i <= n; i ++ )
            h[i] = h[i - 1] * Hash_Value(base, base) + Hash_Value(s[i] - 'a' + 1, s[i] - 'a' + 1);
        return;
    }

    Hash_Value Query ( int L, int R ) const
    {
        return h[R] - h[L - 1] * power[R - L + 1];
    }
}H[max1 + 5], tmp;

char s[max1 + 5];

pair <int, int> id[max1 + 5]; int cnt;
vector <int> pos[max1 + 5];
int bin[max1 + 5], suffix[max1 + 5];

int Match ( const Hash &A, const Hash &B, const int &x, const int &y )
{
    int L = 0, R = min(A.len - x + 1, B.len - y + 1), match = 0;

    while ( L <= R )
    {
        int mid = (L + R) >> 1;

        if ( A.Query(x, x + mid - 1) == B.Query(y, y + mid - 1) )
            match = mid, L = mid + 1;
        else
            R = mid - 1;
    }
    return match;
}

bool Cmp ( const Hash &A, const Hash &B, const int &x, const int &y )
{
    int match = Match(A, B, x, y);

    if ( match == min(A.len - x + 1, B.len - y + 1) )
        return A.len - x < B.len - y;
    
    return A.Query(x + match, x + match).h1 < B.Query(y + match, y + match).h1;
}

struct ST_List
{
    int list[max1 + 5][20];

    void Build ()
    {
        list[1][0] = 0;
        for ( int i = 2; i <= cnt; i ++ )
            list[i][0] = Match(H[id[i - 1].first], H[id[i].first], id[i - 1].second, id[i].second);
        
        for ( int k = 1; (1 << k) <= cnt; k ++ )
            for ( int i = 1; i + (1 << k) - 1 <= cnt; i ++ )
                list[i][k] = min(list[i][k - 1], list[i + (1 << (k - 1))][k - 1]);
        return;
    }

    int Query_Prev ( int now, int x )
    {
        for ( int i = 19; i >= 0; i -- )
            if ( now - (1 << i) + 1 >= 1 && list[now - (1 << i) + 1][i] >= x )
                now -= 1 << i;
        return now;
    }
    int Query_Next ( int now, int x )
    {
        for ( int i = 19; i >= 0; i -- )
            if ( now + (1 << i) - 1 <= cnt && list[now][i] >= x )
                now += 1 << i;
        return now;
    }
}ST;

struct Question
{
    int opt, id, x, y;

    Question () {}
    Question ( int __opt, int __id, int __x, int __y )
        { opt = __opt, id = __id, x = __x, y = __y; }
};
vector <Question> qus;

bool vis[max1 + 5];

struct Question1
{
    int pos, id;

    Question1 () {}
    Question1 ( int __pos, int __id )
        { pos = __pos, id = __id; }
    
    bool operator < ( const Question1 &A ) const
        { return pos < A.pos; }
};

vector <Question1> qus1;

struct Question2
{
    int id, L, R;

    Question2 () {}
    Question2 ( int __id, int __L, int __R )
        { id = __id, L = __L, R = __R; }
};

vector <Question2> qus2[max1 + 5];

struct Part
{
    int len, block, st[max1 + 5], ed[max1 + 5], belong[max1 + 5];
    long long sum1[max1 + 5], sum2[max1 + 5];

    void Build ()
    {
        len = B; block = max(1, n / len);
        memset(st, 0, sizeof(int) * (block + 1));
        memset(ed, 0, sizeof(int) * (block + 1));
        for ( int i = 1; i <= block; i ++ )
        {
            st[i] = ed[i - 1] + 1;
            ed[i] = i * len;
        }
        ed[block] = cnt;

        for ( int i = 1; i <= block; i ++ )
            for ( int j = st[i]; j <= ed[i]; j ++ )
                belong[j] = i;
        return;
    }

    void Clear ()
    {
        memset(sum1 + 1, 0, sizeof(long long) * cnt);
        memset(sum2 + 1, 0, sizeof(long long) * block);
        return;
    }

    void Insert ( int now, long long x )
    {
        sum1[now] += x;
        sum2[belong[now]] += x;
        return;
    }

    long long Query ( int L, int R )
    {
        if ( L > R )
            return 0;

        long long ans = 0;
        if ( belong[L] == belong[R] )
        {
            for ( int i = L; i <= R; i ++ )
                ans += sum1[i];
        }
        else
        {
            ans = Query(L, ed[belong[L]]) + Query(st[belong[R]], R);
            for ( int i = belong[L] + 1; i <= belong[R] - 1; i ++ )
                ans += sum2[i];
        }
        return ans;
    }
}part;

int color[max1 + 5];

long long ans[max1 + 5];

void Solve ()
{
    bool flag = false;

    for ( const auto &v : qus )
        flag |= v.opt == 1;
    
    if ( !flag )
    {
        for ( const auto &v : qus )
            val[v.x] += v.y;
    }
    else
    {
        memset(vis + 1, 0, sizeof(bool) * n);
        qus1.clear();

        for ( int i = 0; i <= cnt; i ++ )
            qus2[i].clear();

        part.Clear();

        for ( const auto &v : qus )
        {
            if ( v.opt == 1 )
            {
                qus1.push_back(Question1(v.x - 1, -v.id));
                qus1.push_back(Question1(v.y, v.id));

                qus2[v.x - 1].push_back(Question2(v.id, v.x, v.y));

                ans[v.id] = 0;
            }
            else
                vis[v.x] = true;
        }

        sort(qus1.begin(), qus1.end());

        for ( int i = 1; i <= n; i ++ )
        {
            if ( vis[i] )
            {
                for ( const auto &v : qus )
                    color[v.id] = 0;

                int siz = qus1.size() - 1, now = 0, len = pos[i].size() - 1;

                for ( int j = 0; j <= siz; j ++ )
                {
                    while ( now <= len && pos[i][now] <= qus1[j].pos )
                        ++now;

                    if ( qus1[j].id < 0 )
                        color[-qus1[j].id] -= now;
                    else
                        color[qus1[j].id] += now;
                }

                for ( auto v : qus )
                {
                    if ( v.opt == 1 )
                    {
                        if ( color[v.id] )
                            ans[v.id] += val[i];
                    }
                    else
                    {
                        if ( v.x == i )
                            val[i] += v.y;
                    }
                }
            }
        }

        for ( int i = 1; i <= n; i ++ )
            if ( !vis[i] )
                part.Insert(bin[i], val[i]);

        for ( int i = 0; i <= cnt; i ++ )
        {
            if ( !vis[id[i].first] && suffix[i] != cnt + 1 )
                part.Insert(suffix[i], val[id[i].first]);

            for ( const auto &v : qus2[i] )
                ans[v.id] += part.Query(v.L, v.R);
        }
    }

    qus.clear();

    return;
}

int main ()
{
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);

    power[0] = Hash_Value(1, 1);
    for ( int i = 1; i <= max1; i ++ )
        power[i] = power[i - 1] * Hash_Value(base, base);

    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= n; i ++ )
    {
        scanf("%lld%s", &val[i], s + 1);

        int len = strlen(s + 1);
        H[i].Build(s, len);

        for ( int j = 1; j <= len; j ++ )
            id[++cnt] = make_pair(i, j);
    }

    sort(id + 1, id + 1 + cnt, [&]( const pair <int, int> &x, const pair <int, int> &y ){ return Cmp(H[x.first], H[y.first], x.second, y.second); });

    for ( int i = 1; i <= cnt; i ++ )
        pos[id[i].first].push_back(i);
    
    for ( int i = 1; i <= n; i ++ )
        bin[i] = cnt + 1;
    
    for ( int i = cnt; i >= 1; i -- )
    {
        suffix[i] = bin[id[i].first];
        bin[id[i].first] = i;
    }

    ST.Build();
    part.Build();

    memset(ans + 1, -1, sizeof(long long) * m);
    qus.clear();

    int opt, x, y;

    for ( int i = 1; i <= m; i ++ )
    {
        scanf("%d", &opt);

        if ( opt == 1 )
        {
            scanf("%s", s + 1);

            int len = strlen(s + 1);
            tmp.Build(s, len);

            int L = 1, R = cnt, pos = 0;

            while ( L <= R )
            {
                int mid = (L + R) >> 1;

                if ( Cmp(H[id[mid].first], tmp, id[mid].second, 1) )
                    pos = mid, L = mid + 1;
                else
                    R = mid - 1;
            }

            int Prev, Next;

            if ( pos == 0 || Match(H[id[pos].first], tmp, id[pos].second, 1) < len )
                Prev = pos + 1;
            else
                Prev = ST.Query_Prev(pos, len);
            
            if ( pos == cnt || Match(H[id[pos + 1].first], tmp, id[pos + 1].second, 1) < len )
                Next = pos;
            else
                Next = ST.Query_Next(pos + 2, len) - 1;
            
            qus.push_back(Question(1, i, Prev, Next));
        }
        else
        {
            scanf("%d%d", &x, &y);
            qus.push_back(Question(2, i, x, y));
        }

        if ( !(i % B) )
            Solve();
    }
    Solve();

    for ( int i = 1; i <= m; i ++ )
        if ( ans[i] != -1 )
            printf("%lld\n", ans[i]);

    return 0;
}

标签：__,const,int,h1,国赛,38.1,2023,Hash,id
From： https://www.cnblogs.com/KafuuChinocpp/p/17563716.html

T1 智力游戏

T2 区域划分

T3 基因识别

相关文章

赞助商

阅读排行