NC20289. [SCOI2012]喵星球上的点名
描述
输入描述
现在定义喵星球上的字符串给定方法：先给出一个正整数L，表示字符串的长度，接下来L个整数表示字符串的每个字符。
输入的第一行是两个整数N和M。
接下来有N行，每行包含第i个喵星人的姓和名两个串。姓和名都是标准的喵星球上的字符串。
接下来有M行，每行包含一个喵星球上的字符串，表示老师点名的串。
输出描述
对于每个老师点名的串输出有多少个喵星人应该答到。
然后在最后一行输出每个喵星人被点到多少次。
示例1
输入:
2 3 6 8 25 0 24 14 8 6 18 0 10 20 24 0 7 14 17 8 7 0 17 0 5 8 25 0 24 0 4 8 25 0 24 4 7 0 17 0 4 17 0 8 25
输出:
2 1 0 1 2
说明:
【提示】C++(g++ 7.5.0) 解法, 执行用时: 231ms, 内存消耗: 77612K, 提交时间: 2023-01-09 20:51:09
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<deque>
#define pii pair<pair<int,int>,int>
#define pir pair<long long,long long>
#define endl '\n'
#define ll long long
#define ld long double
//#define int long long
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define bug cout<<"又卡了吧，sb"<<'\n'
const double pi = acos(-1);
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N=3e6+100,mod=1e9+7,inf=1e18,base=13331,MAXN=1e5+7;
/*
//线性基板子
ll d[70];
void add(ll x)
{
for(int i=62;i>=0;i--)
{
if(x&(1ll<<i))
{
if(d[i])x^=d[i];
else
{
d[i]=x;
break;
}
}
}
}
//欧拉筛
ll vis[N],pos,pri[N];
void init()
{
vis[1]=0;
ll n=N;
for(int i=2;i<=n;i++)
{
if(!vis[i])
pri[++pos]=i;
for(int j=1;pri[j]*i<=n;j++)
{
vis[pri[j]*i]=1;
if(i%pri[j]==0)
break;
}
}
}
-----------------------------------
求[1,N]组合式和逆元
ll fac[N],inv[N];
void init()
{
fac[0]=1;
for(int i=1;i<N;i++)
fac[i]=fac[i-1]*i%mod;
inv[N-1]=ksm(fac[N-1],mod-2);
for(int i=N-2;i>=0;i--)
inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(int m,int n){//组合式C(m,n);
if(!n){
return 1;
}
return fac[m]*inv[n]%mod*inv[m-n]%mod;
}
---------------------------------
unordered_map<int,int>mp;
//优先队列默认小顶堆 ， greater<int> --小顶堆 less<int> --大顶堆
priority_queue<elemt,vector<elemt>,comp>q;
set<int>::iterator it=st.begin();
*/
// vector<vector<int>>edge; 二维虚拟储存坐标
//-----------------------------------------------------------------------------------------------------------------*/
//unordered_map<ll,int>mp;
/*cout<<setiosflags(ios::fixed)<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（不含整数部分）*/
/*cout<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（含整数部分）*/
long long read() {
long long x = 0, f = 1;
char s = getchar();
for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;
for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
return x * f;
}
void write(long long x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
ll ksm(ll x,ll y) {
ll s = 1;
while(y) {
if(y & 1) s = s * x%mod;
x = x * x%mod;
y >>= 1;
}
return s%mod;
}
ll lcm(ll a,ll b) {
return a/__gcd(a,b)*b;
};
struct node {
int l,r,id;
}p[N];
ll a[N],b[N],c[N];
//ll pre[N],nex[N];
ll num[N];
//ll sum[N];
//ll vis[N],vis1[N];
//ll f[N];
int rk[N],sa[N],tp[N],tax[N],n,m,height[N],sum;
int s[N];
int ans[N];
int lg[N],las[N],le[N];
int st[N][30];
int pos[N];
bool cmp(node a,node b)
{
return (a.l>>9)==(b.l>>9) ? a.r<b.r : a.l<b.l;
}
void add(int x,int y)
{
if(!tax[c[x]])
sum++,las[c[x]]=y;
tax[c[x]]++;
}
void del(int x,int y)
{
tax[c[x]]--;
if(!tax[c[x]])
sum--,num[c[x]]+=y-las[c[x]];
}
void rsort()
{
for(int i=0;i<=m;i++)
tax[i]=0;
for(int i=1;i<=n;i++)
tax[rk[tp[i]]]++;
for(int i=1;i<=m;i++)
tax[i]+=tax[i-1];
for(int i=n;i>=1;i--)
sa[tax[rk[tp[i]]]--]=tp[i];
}
void suffix()
{
for(int i=1;i<=n;i++)
rk[i]=s[i],tp[i]=i;
rsort();
for(int k=1;k<=n;k<<=1)
{
int num=0;
for(int i=n-k+1;i<=n;i++)
tp[++num]=i;
for(int i=1;i<=n;i++)
if(sa[i]>k)tp[++num]=sa[i]-k;
rsort();
swap(rk,tp);
rk[sa[1]]=1;
num=1;
for(int i=2;i<=n;i++)
rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?num:++num;
if(num==n)break;
m=num;
}
}
void get_height()
{
int k=0;
for(int i=1;i<=n;i++)
rk[sa[i]]=i;
for(int i=1;i<=n;i++)
{
if(rk[i]==1)
continue;
if(k)--k;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k])++k;
height[rk[i]]=k;
}
}
void get_st()
{
lg[0]=-1;
for(int i=1;i<=n;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++)
st[i][0]=height[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
ll lcp(int l,int r)
{
l++;int i=lg[r-l+1];
return min(st[l][i],st[r-(1<<i)+1][i]);
}
signed main()
{
ll T=1;
//T=read();
while(T--)
{
m=1e4+10;
ll nn=read(),q=read();
for(int i=1;i<=nn;i++)
{
ll len=read();
while(len--)
s[++n]=read();
s[++n]=1e4+1,len=read();
while(len--)
s[++n]=read();
s[++n]=1e4+2;
}
ll temp=n,cnt=1;
for(int i=1;i<=q;i++)
{
ll len=read();
pos[i]=n+1;le[i]=len;
while(len--)s[++n]=read();
if(i!=q)s[++n]=1e4+2;
}
suffix();get_height();get_st();
for(int i=1;i<=temp;i++)
{
if(s[i]==1e4+2)
cnt++;
else
c[rk[i]]=cnt;
}
for(int i=1;i<=q;i++)
{
int x=rk[pos[i]],len=le[i];
ll l=1,r=x-1,t=x;
while(l<=r)
{
ll mid=l+r>>1;
if(lcp(mid,x)>=len)
t=mid,r=mid-1;
else
l=mid+1;
}
l=x+1,r=n;int tt=x;
while(l<=r)
{
ll mid=l+r>>1;
if(lcp(x,mid)>=len)
tt=mid,l=mid+1;
else
r=mid-1;
}
p[i]=(node){t,tt,i};
}
sort(p+1,p+q+1,cmp);
memset(tax,0,sizeof(tax)),sum=0;
for(int i=1,l=1,r=0;i<=q;i++)
{
while(r<p[i].r)add(++r,i);
while(r>p[i].r)del(r--,i);
while(l<p[i].l)del(l++,i);
while(l>p[i].l)add(--l,i);
ans[p[i].id]=sum-(tax[0]>0);
}
for(int i=1;i<=q;i++)
cout<<ans[i]<<endl;
for(int i=1;i<=nn;i++)
{
if(tax[i])
num[i]+=q-las[i]+1;
}
for(int i=1;i<=nn;i++)
cout<<num[i]<<" ";
cout<<endl;
}
}
C++14(g++5.4) 解法, 执行用时: 186ms, 内存消耗: 19720K, 提交时间: 2020-09-15 17:06:04
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
using namespace std;
int n,m,cnt=1,ans1[maxn],ans2[maxn],fail[maxn];
bool vst[maxn],mark[maxn];
vector<int> a[maxn],tag[maxn],V,M;
map<int,int> t[maxn];
queue<int> q;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void insert(int id)
{
int len=read(),x,now=1;
F(i,1,len)
{
x=read();
if (!t[now][x]) t[now][x]=++cnt;
now=t[now][x];
}
tag[now].push_back(id);
}
void getfail()
{
q.push(1);
while (!q.empty())
{
int x=q.front();q.pop();
for(map<int,int>::iterator i=t[x].begin();i!=t[x].end();i++)
{
int tmp=i->first,y=i->second,j=fail[x];
while (j&&!t[j][tmp]) j=fail[j];
fail[y]=j?t[j][tmp]:1;
q.push(y);
}
}
}
void getans(int id,int x)
{
for(int i=x;i;i=fail[i]) if (!vst[i])
{
vst[i]=true;V.push_back(i);
for(int j=0;j<tag[i].size();j++) if (!mark[tag[i][j]])
{
mark[tag[i][j]]=true;M.push_back(tag[i][j]);
ans1[tag[i][j]]++;ans2[id]++;
}
}
}
void solve(int id)
{
int now=1;
for(int i=0;i<a[id].size();i++)
{
int x=a[id][i];
while (now&&!t[now][x]) now=fail[now];
now=now?t[now][x]:1;
getans(id,now);
}
for(int i=0;i<V.size();i++) vst[V[i]]=false;
for(int i=0;i<M.size();i++) mark[M[i]]=false;
V.clear();M.clear();
}
int main()
{
n=read();m=read();
int len,x;
F(i,1,n)
{
len=read();F(j,1,len) x=read(),a[i].push_back(x);
a[i].push_back(100001);
len=read();F(j,1,len) x=read(),a[i].push_back(x);
}
F(i,1,m) insert(i);
getfail();
F(i,1,n) solve(i);
F(i,1,m) printf("%d\n",ans1[i]);
F(i,1,n-1) printf("%d ",ans2[i]);
printf("%d\n",ans2[n]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 262ms, 内存消耗: 20708K, 提交时间: 2019-03-09 12:09:12
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define N 100010
using namespace std;
int L,n,m,x,y,ans1[N],ans2[N],f[N],vis[N];
vector<int>a[N],pos[N],A,B;
map<int,int>ch[N];
struct use{
int cnt,fail[N],q[N];
use(){
cnt=1;
for (int i=-1;i<=10000;i++) ch[0][i]=1;
}
void insert(int x){
scanf("%d",&L);int now=1;int t;
for (int i=1;i<=L;i++){
scanf("%d",&t);
if (!ch[now][t]) ch[now][t]=++cnt;
now=ch[now][t];
}
pos[now].push_back(x);
}
void build(){
int h(0),t(1);
fail[1]=0;q[0]=1;
while (h!=t){
int x=q[h++];
for (map<int,int>::iterator i=ch[x].begin();i!=ch[x].end();i++){
int tt=i->first,k=fail[x];
while (!ch[k][tt]) k=fail[k];
fail[i->second]=ch[k][tt];
q[t++]=i->second;
}
}
}
void update(int x,int k){
for (int i=k;i;i=fail[i]){
if (!vis[i]){
vis[i]=1;A.push_back(i);
for (int j=0;j<pos[i].size();j++)
if(!f[pos[i][j]]){
f[pos[i][j]]=1;B.push_back(pos[i][j]);
ans1[pos[i][j]]++;
ans2[x]++;
}
}
}
}
void calc(int x){
int k(1);
for (int i=0;i<a[x].size();i++){
int t=a[x][i];
while (!ch[k][t]) k=fail[k];
k=ch[k][t];update(x,k);
}
for(int i=0;i<A.size();i++)vis[A[i]]=0;
for(int i=0;i<B.size();i++)f[B[i]]=0;
A.clear();B.clear();
}
}acm;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&L);
for (int j=1;j<=L;j++) scanf("%d",&x),a[i].push_back(x);
a[i].push_back(-1);
scanf("%d",&L);
for (int j=1;j<=L;j++) scanf("%d",&x),a[i].push_back(x);
}
for (int i=1;i<=m;i++) acm.insert(i);
acm.build();
for (int i=1;i<=n;i++) acm.calc(i);
for (int i=1;i<=m;i++) printf("%d\n",ans1[i]);
for (int i=1;i<=n;i++){
printf("%d",ans2[i]);
if (i!=n) printf(" ");
}
}