P3823 [NOI2017]蚯蚓排队

NOI2017D1T2

其实就是个复杂(~~简单的~~)暴力啊,不需要任何高级技巧

可能手写hash表算一个?

1.把两个字符串合并

2.把两个字符串分裂

3.询问一个模式串S长度为k的所有子串在所有文本串出现次数之积

$\sum{|S|}<=1e7,k<=50$

这个题主要的思想其实就是围绕着这个询问来考虑修改

因为这个k你不觉得很突兀吗?只有50?

那我们是不是可以把文本串中所有小于等于k的子串压成一个hash值存在hash表中呢?

这样查询总复杂度就是 $\sum{|S|}$ 的了!

我们只需要考虑小于等于k的子串压在一起,所以合并就相当于枚举新产生k^2个子串暴力加入hash表,删除就相当于暴力删了...这好像就完了

具体hash表写法看代码

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
//using namespace std;
#define ULL unsigned long long
using namespace std;
namespace fastIO {

	inline int read() {
		int x=0,f=1;
		register char s=getchar();
		for(; !isdigit(s); s=getchar())if(s=='-')f=-1;
		for(; isdigit(s); s=getchar())x=(x<<1)+(x<<3)+s-'0';
		return x*f;
	}
}
using namespace fastIO;
const int MAXN=6e5+7;
const int MAX_K=52;
const int P1=1145145;
const int P=998244353;
int n,m,q,a[MAXN],pre[MAXN],nxt[MAXN],cnt[MAXN],f[MAX_K*2+10];
ULL g[MAX_K*2+16],bin[MAX_K*2];
const int MOD=(1<<24)-1;

struct OPO {
	struct edge {
		ULL x;
		int cnt,nxt;
	} e[21000000];

	int home[MOD+1],cnt_e;

	void add(ULL x,int d) {
		int u=(x&MOD);
		for(int i=home[u]; i; i=e[i].nxt) {
			if(e[i].x==x) {//把具体hash值比一下,如果这都相同你命没了
				e[i].cnt+=d;
				return ;
			}
		}
		e[++cnt_e]=(edge) {
			x,d,home[u]
		};
		home[u]=cnt_e;
	}

	int query(ULL x) {
		int u=(x&MOD);
		for(int i=home[u]; i; i=e[i].nxt) {
			if(e[i].x==x)return e[i].cnt;
		}
		return 0;
	}
} _;

void merge() {
	int x=read(),y=read();
	memset(f,0,sizeof(f));
	int L=MAX_K,R=L-1;
	for(int i=x; i&&L>1; i=pre[i]) {
		f[--L]=a[i];
	}
//左端点
	for(int i=y; i&&R+1<MAX_K*2; i=nxt[i]) {
		f[++R]=a[i];
	}
//右端点
	for(int i=1; i<=R; ++i)g[i]=g[i-1]*P1+f[i];
//这个是处理新长为2*k的序列hash
	for(int i=L; i<MAX_K; ++i)
		for(int j=MAX_K; j<=min(R,i+49); ++j) {
			_.add((g[j]-g[i-1]*bin[j-i+1]),1);
			//k^2暴力
		}
	nxt[x]=y;
	pre[y]=x;
}

inline void split() {
	int x=read(),y=nxt[x];
	memset(f,0,sizeof(f));
	int L=MAX_K,R=L-1;
	for(int i=x; i&&L>1; i=pre[i])
		f[--L]=a[i];
	for(int i=y; i&&R+1<MAX_K*2; i=nxt[i])
		f[++R]=a[i];
	for(int i=1; i<=R; ++i)g[i]=g[i-1]*P1+f[i];
	for(int i=L; i<MAX_K; ++i)
		for(int j=MAX_K; j<=min(R,i+49); ++j) {
			_.add(g[j]-g[i-1]*bin[j-i+1],-1);//move
		}
	nxt[x]=pre[y]=0;//重新成为队尾或队头
}
char s[11000000];
int query() {
	scanf("%s",s+1);
	int k=read(),n=strlen(s+1);
	ll ans=1;
	ULL val=0;
	if(k==1)for(int i=1; i<=n; ++i)ans=(1ll*ans*cnt[s[i]])%P;
	else for(int i=1; i<=n; ++i) {
			val=val*P1+s[i];
			if(i>k)val-=bin[k]*s[i-k];
			if(i>=k)ans=1ll*ans*_.query(val)%P;
		}
	return ans;
}

int main() {
	int n=read(),q=read();
	bin[0]=1;
	for(int i=1; i<MAX_K; ++i)bin[i]=bin[i-1]*P1;
	for(int i=1; i<=n; ++i)cnt[a[i]=read()+'0']++;
	while(q--) {
		//	printf("%d?\n",q);
		int opt=read();
		if(opt==1)merge();
		else if(opt==2)split();
		else printf("%d\n",query());
	}
	return 0;
}

夏晓光(loveJY)的博客

P3826 [NOI2017]蔬菜