首页 > 其他分享 >CF590E Birthday

CF590E Birthday

时间:2023-03-15 21:36:33浏览次数:59  
标签:ch 覆盖 int CF590E tr Birthday fail now

\(\text{Solution}\)

建出 ACAM 后利用 fail 树就可以确定子串关系了,如果建成有向图
然后看问题,考虑最长反链等于最小链覆盖,那么就是求一个可重路径覆盖问题
Floyd 传递闭包后变成不可重路径覆盖,拆点二分图就有最小路径覆盖等于总点数减最大匹配
考虑构造方案,本质上是个传递闭包后的最大独立集
找到残量网络上由 \(S\) 出发能走到的点,那么左部不能到的点和右部能到的点构成了最小点覆盖
取补集就是最大独立集了

\(\text{Code}\)

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

template <typename Tp>
void read(Tp &x) {
	x = 0; char ch = getchar(); int f = 0;
	for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());
	for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
	if (f) x = ~x + 1;
}

const int N = 755, M = 1e7 + 5;
int n;
char str[M];

struct Network {
    int tot, h[N << 2], cur[N << 2], T, dep[N << 2], vis[N << 2];
    struct edge{int to, nxt, w;}e[N * N << 2];
    void init() {
        tot = 1, T = n + n + 1;
        for(int i = 0; i <= T; i++) h[i] = 0;
    }
    void add(int x, int y, int z) {
        e[++tot] = edge{y, h[x], z}, h[x] = tot;
        e[++tot] = edge{x, h[y], 0}, h[y] = tot;
    }
    queue<int> Q;
    int bfs() {
        for(int i = 0; i <= T; i++) dep[i] = 0, cur[i] = h[i];
        Q.push(0), dep[0] = 1;
        while (!Q.empty()) {
            int now = Q.front(); Q.pop();
            for(int i = h[now]; i; i = e[i].nxt) {
                int v = e[i].to;
                if (dep[v] || !e[i].w) continue;
                dep[v] = dep[now] + 1, Q.push(v);
            }
        }
        return dep[T];
    }
    int dfs(int x, int lim) {
        if (lim <= 0 || x == T) return lim;
        int flow = 0;
        for(int i = cur[x], v, f; i; i = e[i].nxt) {
            cur[x] = i, v = e[i].to;
            if (dep[v] != dep[x] + 1 || !e[i].w) continue;
            f = dfs(v, min(lim, e[i].w));
            if (f <= 0) continue;
            e[i].w -= f, e[i ^ 1].w += f, flow += f, lim -= f;
            if (lim <= 0) break;
        }
        return flow;
    }
    int dinic(){int flow = 0; while (bfs()) flow += dfs(0, N); return flow;}
    void dfs(int x) {
        vis[x] = 1;
        for(int i = h[x]; i; i = e[i].nxt) if (e[i].w && !vis[e[i].to]) dfs(e[i].to);
    }
    void work() {
        dfs(0);
        for(int i = 1; i <= n; i++)
            if (!(!vis[i] || vis[i + n])) printf("%d ", i);
    }
}nt;

struct Graph {
    int g[N][N];
    void Floyd() {
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++) if (i ^ k)
                for(int j = 1; j <= n; j++) if ((j ^ i) && (j ^ k))
                    g[i][j] |= g[i][k] & g[k][j];
    }
    void build() {
        nt.init();
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) if (g[i][j]) nt.add(i, j + n, 1);
        for(int i = 1; i <= n; i++) nt.add(0, i, 1);
        for(int i = 1; i <= n; i++) nt.add(i + n, nt.T, 1);
    }
}G;

struct ACAM {
    int id[M], size, tr[M][2], fail[M], ed[N], fa[M];
    void insert(int x, int len)  {
        int u = 0, ch;
        for(int i = 1; i <= len; i++) {
            ch = str[i] - 'a';
            if (!tr[u][ch]) tr[u][ch] = ++size;
            fa[tr[u][ch]] = u, u = tr[u][ch];
        }
        id[u] = x, ed[x] = u;
    }
    void getfail() {
        queue<int> Q;
        for(int i = 0; i < 2; i++) if (tr[0][i]) Q.push(tr[0][i]);
        while (!Q.empty()) {
            int now = Q.front(); Q.pop();
            for(int i = 0; i < 2; i++) {
                if (tr[now][i]) fail[tr[now][i]] = tr[fail[now]][i], Q.push(tr[now][i]);
                else tr[now][i] = tr[fail[now]][i];
            }
        }
    }
    void build() {
        vector<int> Q;
        for(int i = 1; i <= n; i++) {
            for(int j = ed[i]; j; j = fa[j]) {
                int x = fail[j];
                while (x && !id[x]) Q.eb(x), x = fail[x];
                while (!Q.empty()) fail[Q.back()] = x, Q.pop_back();
                fail[j] = x;
                if (j != ed[i] && id[j]) x = j;
                if (x) G.g[i][id[x]] = 1;
            }
        }
    }
}ac;

int main() {
    read(n);
    for(int i = 1; i <= n; i++) scanf("%s", str + 1), ac.insert(i, strlen(str + 1));
    ac.getfail(), ac.build(), G.Floyd(), G.build();
    printf("%d\n", n - nt.dinic()), nt.work();
}

标签:ch,覆盖,int,CF590E,tr,Birthday,fail,now
From: https://www.cnblogs.com/leiyuanze/p/17220138.html

相关文章

  • Birthday Attack
    BirthdayAttackQ&A1Q:Howmanypeoplemustbethereinaroomtomaketheprobability100%thatat-leasttwopeopleintheroomhavesamebirthday?A:367(s......
  • Codeforces Round #619 (Motarack's Birthday)
    题面DarkisgoingtoattendMotarack’sbirthday.DarkdecidedthatthegiftheisgoingtogivetoMotarackisanarrayaofnnon-negativeintegers.Darkcr......
  • NEUOJ 1207(Birthday present-前缀和)
    给你一个数组a,给你一个k,你可以讲每个数减去不超过k,要求最后的GCD最大,求这个gcd1 ≤ n ≤ 3·1e5; 1 ≤ k ≤ 1e61 ≤ ai ≤ 1e6显然min(ai)<=k时,答案为min......
  • Happy Second Birthday Jenkins X!
    始于2019年初的JenkinsX项目在去年的1月14号庆祝了它的第一个生日,这对任何开源项目来说都是一件大事,我们刚刚又庆祝了它的第二个生日。JenkinsX的两周年!JenkinsX已......
  • 双哈希_Birthday_Cake
    BirthdayCake思路:找到每个串的公共前后缀,统计公共前后缀之间的字符串的hash值,并判断所给n个串中是否存在符合条件的串eg:abbddab对于该串,我们不难发现,公共前后缀是ab,公......
  • H - Mr. Panda and Birthday Song Gym - 101775H
    题意:给你一个长度不大于1e6的字符串,由'a'-'z'或‘?’组成,且‘?’可转化为任意小写字母。和两个数x,y。现在有两个条件:字符串中存在任意一个长度为x的子串均为元音,或存在......
  • MathProblem 37 Common birthday problem
    Whatistheminimumnumberofpeopledoyouneed,chosenatrandom,sothatthereisatleasta50%chancethatatleasttwohavethesamebirthday.Assumetha......