是男人就過 8 題--Pony.AI 題 - A String Game -开发者知识库

是男人就過 8 題--Pony.AI 題 - A String Game -开发者知识库,第1张

是男人就過 8 題--Pony.AI 題 - A String Game


題目來源

題意:給一個串t以及n個t的子串s,兩個人每輪可以選擇一個s在他的后邊添加一個字符滿足得到的新串仍是t的子串,第一個不能操作的人輸。

做法:對s串建SAM,在一個子串后邊添加字符,等價於在SAM上向后移動一步,預處理每個狀態的sg函數,將n個子串的答案異或起來。SAM空間要開兩倍(女裝警告~~

#include <bits/stdc  .h>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;  i)
const int N = 2e5   7;
typedef long long ll;
using namespace std;

struct SAM {
    int n, step[N], fa[N], num[N], last, root, cnt;
    char s[N];
    map<char , int> ch[N];
    void init() {
        for(int i = 0; i <= cnt;   i) ch[i].clear();
        cnt = 0; last = root =   cnt;
    }
    void add(int x) {
        int tmp = s[x], p = last, np =   cnt;
        step[last = np] = x;
        while(p && !ch[p][tmp]) ch[p][tmp] = np, p =fa[p];
        if(!p) fa[np] = root;
        else {
            int q = ch[p][tmp];
            if(step[q] == step[p]   1) fa[np] = q;
            else {
                int nq =    cnt; step[nq] = step[p]   1;
                ch[nq] = ch[q];
                fa[nq] = fa[q], fa[q] = fa[np] = nq;
                while(ch[p][tmp] == q) ch[p][tmp] = nq, p = fa[p];
            }
        }
    }
    int A[N], sg[N], vis[N];
    void init_sg() {
        memset(A, 0 , sizeof(A));
        memset(sg, 0 , sizeof(sg));
        memset(vis, 0 , sizeof(vis));
        for(int i = 1; i <= cnt;   i)    A[step[i]];
        for(int i = 1; i <= n;   i) A[i]  = A[i-1];
        for(int i = cnt; i; --i) num[A[step[i]]--] = i;

        for(int i = cnt; i; --i) {
            for(auto x: ch[num[i]]) {
                int t = x.second;
                vis[sg[t]] = num[i];
            }
            for(int j = 0; ;   j) if(vis[j] != num[i]) {
                sg[num[i]] = j; break;
            }
        }
    }
    int cal_sg(char str[]) {
        int len = strlen(str 1), now = root;
        for(int i = 1; i <= len;   i) now = ch[now][str[i]];
        return sg[now];
    }
    void run() {
        init();
        for(int i = 1; i <= n;   i) add(i);
        init_sg();
    }
} Fe;
char str[N];
int main() {
    while(scanf(" %s",Fe.s 1) != EOF) {
        Fe.n = strlen(Fe.s 1);
        Fe.run(); int n;
        scanf("%d",&n);
        int ans = 0;
        rep(i, 1, n) {
            scanf(" %s",str 1);
            ans ^= Fe.cal_sg(str);
        }
        puts(ans ? "Alice" : "Bob");
    }
    return 0;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复