USACO18DEC Platinum

standing out from the field

给你n个串，对于每个串求出只包含在这个串中的本质不同的子串？

后缀自动机，建树，对于每一个点打上包含在哪个串中的标记。

叶子都是前缀，直接在sam_build时预处理；其余的dfs一遍，由于x是son[x]的后缀，故x的状态由son[x]影响，如果son[x]有出现在不同串中的，标记x为-1。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=;

 char s[N+];

 int last,sc,p,np,l[N],son[N][],fa[N],cnt,head[N],f[N];

 ll ans[N];

 struct node{int to,next;}num[N];

 void add(int x,int y)

 {num[++cnt].to=y;num[cnt].next=head[x];head[x]=cnt;}

 void Sam(int c,int id)

 {

     p=last; np=last=++sc; l[np]=l[p]+;

     for (;p&&!son[p][c];p=fa[p]) son[p][c]=np;

     if (!p) fa[np]=;

     else {

         int q=son[p][c];

         if (l[p]+==l[q]) fa[np]=q;

         else {

             int nq=++sc; l[nq]=l[p]+;

             memcpy(son[nq],son[q],sizeof(son[q]));

             fa[nq]=fa[q];fa[q]=fa[np]=nq;

             for (;son[p][c]==q;p=fa[p]) son[p][c]=nq;

         }

     }

     if (f[np]&&f[np]!=id) f[np]=-;else f[np]=id;//处理叶子及一部分为前缀的非叶子

 }

 void dfs(int x)

 {

     for (int i=head[x];i;i=num[i].next)

       if (num[i].to!=fa[x]) dfs(num[i].to);

     if (f[x]&&f[x]!=-) ans[f[x]]+=l[x]-l[fa[x]];

    if (f[fa[x]]&&f[fa[x]]!=f[x]) f[fa[x]]=-;else f[fa[x]]=f[x];

 }

 int main()

 {

     int T;scanf("%d",&T);

     sc=;

     for (int i=;i<=T;i++)

     {

         scanf("%s",s+); int sl=strlen(s+);

         last=;

         for (int j=;j<=sl;j++) Sam(s[j]-'a',i);

     }

     for (int i=;i<=sc;i++) add(fa[i],i);

     dfs();

     for (int i=;i<=T;i++) printf("%lld\n",ans[i]);

    return ;

 }

push a box

f[x][y][dir]表示箱子在(x,y)格子，人是否可在箱子的dir方向。

两种操作：推箱子，走人。“推箱子”可以用bfs处理，我们将箱子推过去的时候，必然有一个dir是可行的，“走人”就相当于是判断dir是否可以转换，具体地，从dir1的位置是否有一条不经过箱子所在点的路径走到dir2。tarjan点双，建成圆方树，存在路径当且仅当两个点的距离为2且经过一个方点。

greedy gift takers

每次在首位的人拿到礼物会排到倒数a[i]个人前。问无限次操作，有多少人获得礼物？n<=1e5。

拿到礼物的人在原序列中一定是连续的一段。从封闭性的角度考虑，令a[i]=n-a[i],如果前缀M个人均有a[i]<=M，那么其他人一定不会拿到礼物。我们在前M个人中丢掉a[i]最大的一个，如果剩下的M-1个人的max_a[i]<=M-1，同理其他人拿不到礼物……具有二分性，每次如上check。

 #include<bits/stdc++.h>

 using namespace std;

 int read()

 {

    int x=,f=;char ch=getchar();

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

    return x*f;

 }

 const int N=1e5+;

 multiset<int,greater<int> > s;

 int l,r,n,a[N],ans;

 bool check(int x)

 {

     s.clear();

     for (int i=;i<=x;i++) s.insert(a[i]);

     for (int i=x;i>=;i--)

       if (*s.begin()<=i) return ;

       else s.erase(s.begin());

     return ;

 }

 int main()

 {

     n=read();

     for (int i=;i<=n;i++) a[i]=n-read();

     l=;r=n;

     while (l<=r)

     {

         int mid=(l+r)/;

         if (check(mid)) ans=mid,r=mid-;else l=mid+;

     }

     printf("%d\n",n-ans);

    return ;

 }

巴特西

USACO18DEC Platinum

最新文章

热门文章