【题解】Comet OJ Round 70 简要题解

【题解】Comet OJ Round 70 简要题解

A

将放在地上的书按照从小到大排序后，问题的本质就变成了合并两个序列使得字典序最小。可以直接模拟归并排序。直接用循环和std::merge实现这个过程。复杂度\(O(n)\)

//@winlere
#include<cstdio>
#include<algorithm>
using namespace std;
int data[100003],in[100003],data2[100003],ans[100003],cnt,n,m;
int main(){
      scanf("%d%d",&n,&m);
      for(int t=1;t<=m;++t) scanf("%d",data+t),in[data[t]]=1;
      for(int t=1;t<=n;++t) if(!in[t]) data2[++cnt]=t;
      merge(data+1,data+m+1,data2+1,data2+cnt+1,ans+1);
      for(int t=1;t<=n;++t) printf("%d\n",ans[t]);
      return 0;
}

B

由于题目保证了字符串之间互不为前缀，所以由给定字符串的排名连接而成形成排列的字典序就是这个字符串的字典序。

现在问题就是求出\(\sum|S|\le 1e6\)的这么多字符串的字典序，你若肝的话可以直接上SA，但是更简单的办法是建出一颗Trie树随后在上面DFS。匹配最后那个串的时候也可以直接在Tri树上查询。

现在我们得到了一个排列，问字典序排名第几，直接魔改一下康拓展开即可。复杂度\(O(n\log n)\)

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;  
const int maxn=1e6+5;
const int mod=1e9+7;
char c[maxn];
struct NODE{
      int son[26],id;
      NODE(){}
      inline int&operator[](int x){return son[x];}
      inline int&operator[](char x){return son[x-'a'];}
}ac[maxn];
int data[maxn],cnt,seg[maxn],jc[maxn],inv[maxn],rk[maxn],n,k,ans=1;

inline void insert(const char*c,const int&len,const int&i){
      int now=0;
      for(int t=1;t<=len;++t)
        ac[now][c[t]]?now=ac[now][c[t]]:now=ac[now][c[t]]=++cnt;
      ac[now].id=i;
}

void dfs(const int&now){
      if(ac[now].id) rk[ac[now].id]=++*rk;
      for(int t=0;t<26;++t) if(ac[now][t]) dfs(ac[now][t]);
}

inline void add(const int&pos,const int&tag){for(int t=pos;t<=n;t+=t&-t) seg[t]+=tag;}
inline int que(const int&pos,int ret=0){
      for(int t=pos;t>0;t-=t&-t) ret+=seg[t];
      return ret;
}
inline int ksm(const int&base,const int&p,int ret=1){
      for(int t=p,b=base;t;t>>=1,b=1ll*b*b%mod) if(t&1) ret=1ll*ret*b%mod;
      return ret;
}
inline void pre(const int&n){
      jc[0]=inv[0]=1;
      for(int t=1;t<=n;++t) jc[t]=1ll*jc[t-1]*t%mod;
      inv[n]=ksm(jc[n],mod-2);
      for(int t=n-1;t;--t) inv[t]=1ll*inv[t+1]*(t+1)%mod;
}

int main(){
      pre(1e6); scanf("%d%d",&n,&k);
      for(int t=1;t<=n;++t) scanf("%s",c+1),insert(c,strlen(c+1),t);
      dfs(0);
      scanf("%s",c+1);
      for(int t=1,cur=1,ed=strlen(c+1);t<=ed;t=cur){
        int now=0,f=0;
        while(!f)  now=ac[now][c[cur++]],f=ac[now].id;
        data[++*data]=rk[f];
      }
      for(int t=1;t<=n;++t) add(t,1);
      for(int t=1,ed=*data,g;t<=ed;++t)
        g=que(data[t]),add(data[t],-1),ans=(ans+1ll*(g-1)*jc[n-t]%mod*inv[n-k])%mod;
      printf("%d",ans);
      return 0;
}

主办方看起来会让\(O(n^2)\)开O2过是什么鬼...

C

在路上