分类 数据结构 下的文章

BZOJ 1012 zkw

嗯嗯向我这种没智商的沙茶一定是会打残代码的。
同一个名称就不要乱用了啊（die。
或许说太久没打zkw忘了怎么打还是得翻以前的代码……
一言以蔽之，曰智商低。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5;
namespace FastIO
{
    template<class T>
    void read(T& x)
    {
        char ch = getchar(); T n = 1, a = 0;
        while(ch < '0' || ch > '9'){if(ch == '-') n = -1; ch = getchar();}
        while(ch >= '0' && ch <= '9'){a = a * 10 + ch - '0'; ch = getchar();}
        x = n * a;
    }
    template<class T, class U>
    void read(T& x, U& y)
    {
        read(x), read(y);
    }
}
using namespace FastIO;

struct info
{
    int ma;
    info(int x = 0) : ma(x){}
} A[maxn * 3];

int main()
{
    int m, d;
    read(m, d);
    int t = 0, cur = 0;
    int zkwt = 1;
    while(zkwt <= maxn + 3) zkwt <<= 1;
    while(m--)
    {
        char a[2];int n;
        scanf("%s", a);
        read(n);
        if(a[0] == 'A')
        {
            int i;
            for(A[i = cur + zkwt + 1] = info((n + t) % d), i >>= 1; i > 0; i >>= 1)
                A[i].ma = max(A[i * 2].ma, A[i * 2 + 1].ma); 
            cur++;
        }
        else
        {
            int ans = 0;
            for(int l = cur - n + zkwt, r = cur + zkwt + 1; l ^ r ^ 1; l >>= 1, r >>= 1)
            {
                if(~l & 1)
                    ans = max(ans, A[l ^ 1].ma);
                if(r & 1)
                    ans = max(ans, A[r ^ 1].ma);
            }
            printf("%d\n", t = ans);
        }
    }
    return 0;
}

回文树

好像是去年毛子发明的对付回文串的数据结构。
下午再次研究了一遍，发现总算看懂了。
贴一份模板。

template<int maxn = int(1e5), int sigma = 26>
class PalindromeTree
{
private:
    int n, p, tail;
    int S[maxn];
    int next[maxn][sigma], fail[maxn], len[maxn], cnt[maxn];
    inline int idx(char c){return c - 'a';}

public:
    int newnode(int l)
    {
        cnt[p] = 0;
        len[p] = l;
        return p++;
    }
    void init()
    {
        newnode(0), newnode(-1);
        S[n = 0] = -1;
        fail[0] = 1;
    }

    int get_fail(int x)
    {
        while(S[n - len[x] - 1] != S[n])
            x = fail[x];
        return x;
    }

    void add(char c)
    {
        int id = idx(c);
        S[++n] = id;
        int cur = get_fail(tail);
        if(!next[cur][id])
        {
            int node = newnode(len[cur] + 2);
            fail[node] = next[get_fail(fail[cur])][id];
            next[cur][id] = node;
        }
        tail = next[cur][id];
        cnt[tail]++;
    }

    void count()
    {
        for(int i = p - 1; i >= 0; i--)
            cnt[fail[i]] += cnt[i];
    }
};

hiho1014 Trie树

本来想顺便写个trie的教程，无奈手头没有专业的画图工具，还是等暑假再补上吧。

链

hiho

解

要求相同前缀个数的话，只需要在每一个节点维护一个变量用来记录子串数量。维护很简单，只需要每增加一个字符串时从根走下对每一个经过的节点的该变量加一即可。【啊啊啊我废话好多
多说一句现在数据结构在下真是写得越来越专业了……对比一下以前模仿lrj写的简直就是【】

码

#include <iostream>
using namespace std;
template<int maxn, int sigma = 26>
class Trie
{
private:
    struct Node
    {
        Node *ch[sigma];
        int cnt;
    }*root, pool[maxn * 2];
    int cnt;
    inline int idx(char c){return c - 'a';}
public:
    Trie()
    {
        root = &pool[0];
        cnt = 1;
    }
    void add(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                p -> ch[idx(s[i])] = &pool[cnt++];
            p -> ch[idx(s[i])] -> cnt++;
            p = p -> ch[idx(s[i])];
        }
    }
    int go(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                return 0;
            p = p -> ch[idx(s[i])];
        }
        return p -> cnt;
    }
};
Trie<1000000> trie;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        trie.add(s);
    }
    int m;
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        cout<<trie.go(s)<<endl;
    }
    return 0;
}

再附一个节点池的炫酷指针版

#include <iostream>
using namespace std;
template<int maxn, int sigma = 26>
class Trie
{
private:
    struct Node
    {
        Node *ch[sigma];
        int cnt;
    }*root, *nodecur, pool[maxn * 2];
    inline int idx(char c){return c - 'a';}
public:
    Trie()
    {
        root = &pool[0];
        nodecur = &pool[1];
    }
    void add(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                p -> ch[idx(s[i])] = nodecur++;
            p -> ch[idx(s[i])] -> cnt++;
            p = p -> ch[idx(s[i])];
        }
    }
    int go(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                return 0;
            p = p -> ch[idx(s[i])];
        }
        return p -> cnt;
    }
};
Trie<1000000> trie;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        trie.add(s);
    }
    int m;
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        cout<<trie.go(s)<<endl;
    }
    return 0;
}

话说指针这东西千万不要乱用啊【捂脸熊】，用得不好会出人命的啊……

vijos1437 简单的口令

链

vijos1437

解

打算去清远前清理桌面，于是发现了这个GDOI遗留下的未完成品。
最小表示法什么的，虽说有专门的算法，不过SAM用起来似乎更顺手。直接两倍原串后按字典序跑一遍就行了。
但那个神奇的算法还是找个时间研究一下吧。
RE了六次，WA了两次。
原因：变量名打错；字符串被分割称多行却无告知。
呃，几乎每次都是变量名打错而出错的呢。

码

#include <iostream>
#include <cstring>
using namespace std;
namespace DEL
{
    template<int maxn, int sigma = 26>
    class Suffix_Automaton
    {
    private:
        struct Node
        {
            Node *fail;
            Node *ch[sigma];
            int len;
            Node(){memset(ch, 0, sizeof ch);}
        } *head, *tail, pool[maxn * 2];
        int cnt, len;
        inline int idx(char c)
        {
            return c - 'a';
        }
    public:
        void init(int l)
        {
            //memset(&pool, 0, sizeof pool);
            head = tail = &pool[0];
            cnt = 1;
            len = l;
        }
        void add(char c)
        {
            int id = idx(c);
            Node *p = tail, *newnode = &pool[cnt++];
            newnode -> len = p -> len + 1;
            tail = newnode;
            for(; p && !p -> ch[id]; p = p -> fail)
                p -> ch[id] = newnode;
            if(!p)
                newnode -> fail = head;
            else if(p -> len + 1 == p -> ch[id] -> len)
                newnode -> fail = p -> ch[id];
            else
            {
                Node *q = p -> ch[id], *r = &pool[cnt++];
                *r = *q;
                r -> len = p -> len + 1;
                q -> fail = newnode -> fail = r;
                for(; p && p -> ch[id] == q; p = p -> fail)
                    p -> ch[id] = r;
            }
        }
        int go()
        {
            Node *p = head;
            for(int i = 0; i < len; i++)
                for(int j = 0; j < sigma; j++)
                {
                    if(p -> ch[j])
                    {
                        p = p -> ch[j];
                        break;
                    }
                }
            return p -> len - len;
        }
    };
}
DEL::Suffix_Automaton<1000000> SAM;
int main()
{
    int l;
    cin>>l;
    string s;
    cin>>s;
    string s1;
    while(cin>>s1)
        s += s1;
    SAM.init(l);
    s += s;
    for(unsigned int i = 0; i < s.length(); i++)
        SAM.add(s[i]);
    cout<<SAM.go()<<endl;
    return 0;
}
  1. 1
  2. 2
  3. 3