[SNMOJ280]Atom-wwt by dsl

发布于 2018-02-10  154 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[SNMOJ280]Atom-wwt by dsl

Description

题面

Solution

考虑到一个串是一个子串的情况只可能是他在 \(fail\) 树上的祖先或者是回文树上的祖先。

所以把回文树和\(fail\)树拼在一起,每次二分最大权值,跑最长反链覆盖,判断覆盖数是否大于等于 \(k\) 即可。

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

typedef long long ll;
const int maxn = 100005, Maxn = 1000005, Inf = 1 << 30;

struct edge {
    int nt, to, flow, cap; 
} g[3000005];
struct Edge{
    int u,v; 
} e[1000005];

int head[maxn], q[maxn], d[maxn], a[maxn], S, T, n, k, cnt, num, ans;
char s[maxn];

inline int gi()
{
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    int sum = 0;
    while('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

int len[maxn], fail[maxn], ch[maxn][26], mxl[maxn], tot, last;

inline void add(int n, int c)
{
    int x = last; 
    while (s[n - len[x] - 1] != s[n]) x = fail[x];
    if (!ch[x][c]) {
        int v = ++tot, k = fail[x]; 
        while (s[n - len[k] - 1] != s[n]) k = fail[k];
        fail[v] = ch[k][c]; len[v] = len[x] + 2; ch[x][c] = v;
    }
    last = ch[x][c]; return;
}

inline void insert(int from, int to, int cap)
{
    g[++num] = (edge) {head[from], to, 0, cap}; head[from] = num;
    g[++num] = (edge) {head[to], from, 0, 0}; head[to] = num;
}

int bfs(int S, int T)
{
    memset(d, 0, sizeof(int) * (T + 1));
    int h = 0, t = 1; q[t] = S; d[S] = 1;
    while (h < t) {
        int x = q[++h], v;
        for (int i = head[x]; i; i = g[i].nt) {
            v = g[i].to;
            if (!d[v] && g[i].cap > g[i].flow) {
                d[v] = d[x] + 1; q[++t] = v;
                if (v==T) return 1;
            }
        }
    }
    return d[T];
}

inline int dfs(int x, int T, int a)
{
    if (!a || x == T) return a; 
    int f, flow = 0;
    for(int i =head[x], v; i; i = g[i].nt) 
        if (d[v = g[i].to] == d[x] + 1 && g[i].cap > g[i].flow) {
            f = dfs(v, T, min(a, g[i].cap - g[i].flow));
            if (!f) {d[v] = -1; continue;}
            g[i].flow += f; g[i ^ 1].flow -= f;
            flow += f; a -= f; if (!a) return flow;
        }
    return flow;
}

inline bool check(int key)
{
    memset(head, 0, sizeof(head));
    num = 1; S = 2 * tot + 1; T = S + 1; 
    int sum = 0;
    for (int i = 2; i <= tot; ++i) {
        if (mxl[i] >= key) ++sum, insert(S, i, 1), insert(i + tot, T, 1);
        insert(i + tot, i, Inf);
    }
    for (int i = 1; i <= cnt; ++i) insert(e[i].u, e[i].v + tot, 1);
    int flow = 0; 
    while (bfs(S, T)) flow += dfs(S, T, Inf);
    return sum - flow >= k;
}

#define mid ((l + r) >> 1)
int main()
{
    freopen("atom.in", "r", stdin);
    freopen("atom.out", "w", stdout);
    n=gi(); k=gi(); scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i) a[i] = gi();
    len[fail[0] = tot = 1] = -1;
    for (int i = 1; i <= n; ++i)
        add(i, s[i] - 'a'), mxl[last] = max(mxl[last], a[i]);

    for (int i=tot;i;--i)
        mxl[fail[i]]=max(mxl[fail[i]],mxl[i]);

    for(int i = tot; i; --i)
        mxl[fail[i]] = max(mxl[fail[i]], mxl[i]);

    for (int i = 2; i <= tot; ++i)
        for (int j = 0; j < 26; ++j)
            if (ch[i][j]) e[++cnt] = (Edge) {i, ch[i][j]};

    for (int i = tot; i; --i) if (fail[i]) e[++cnt] = (Edge) {fail[i], i};
    sort(a + 1, a + n + 1), n = unique(a + 1, a + n + 1) -  a - 1; 
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        if (check(a[mid])) ans = a[mid], l = mid + 1; 
        else r = mid - 1;
    }

    if (ans) printf("%d\n", ans);
    else puts("NEGATIVE"); 

    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[SNMOJ280]Atom-wwt by dsl


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!