牛客暑期多校訓練營2020第2場

這套題很棒！題目很有趣，很考驗思維能力和代碼強度，看得出命題人很認真，就連題目名稱首字母都是和題号對應的hhhh!

A All with Pairs

題意：n個串（s1,s2,……,sn），求 ∑ i = 1 n \sum_{i=1}^n ∑i=1n ∑ j = 1 n \sum_{j=1}^n ∑j=1nf2(si,sj)。其中f(s,t)為s的字首和t的字尾的最長比對長度。

思路：hash / 廣義字尾自動機+KMP

1.hash+KMP

記錄所有字尾的hash值，對每一個字首（長度為i）查詢有多少字尾與之比對。但要除去同一對串(s, t)的多次比對的情況。假設s[1……i] = t[l-i+1……l] 且s[1……j] = t[l-j+1, l]，(i < j)，那麼nxt[j] = i，是以隻需在其kmp中的前驅節點除去後繼的值就可以了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define LL long long
using namespace std;
const int N=1e5+10;
const int M=1e6+10;
const LL base=37;
const LL md=998244353;
map<LL,int>mp[M];
string s[N];
int nxt[M];
LL f[M],cnt[M];
void get_next(int id)
{
	int l=s[id].length();
	nxt[0]=-1;
	int j=-1;
	for(int i=1;i<l;i++)
	{
		while(j!=-1&&s[id][j+1]!=s[id][i])
			j=nxt[j];
		if(s[id][j+1]==s[id][i])
			j++;
		nxt[i]=j;
	}
}
int main()
{
	LL ans=0;
	int n;
	f[0]=1;
	for(int i=1;i<=1e6;i++)
		f[i]=f[i-1]*base;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		int l=s[i].length();
		LL now=0;
		for(int j=l-1;j>=0;j--)
		{
			now=now*base+s[i][j]-'a';
			mp[l-j][now]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		get_next(i);
		int l=s[i].length();
		LL now=0;
		for(int j=0;j<l;j++)
		{
			now=now+(s[i][j]-'a')*f[j];
			if(mp[j+1].find(now)!=mp[j+1].end())
			{
				cnt[j]=mp[j+1][now];
				if(nxt[j]>=0)
					cnt[nxt[j]]-=cnt[j];
			}
			else
				cnt[j]=0;
		}
		for(int j=0;j<l;j++)
			ans=(ans+(LL)(j+1)*(j+1)%md*cnt[j]%md)%md;
	}
	cout<<ans;
	return 0;
}

2.廣義字尾自動機+KMP

建出廣義字尾自動機，枚舉串在字尾自動機上跑比對。KMP判重同上。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const LL md=998244353;
const int N=2e6+10;
struct EDGE{
	int to,nxt;
	EDGE(){}
	EDGE(int x,int y){to=x; nxt=y;}
}edge[N];
int ch[N][26],fa[N],len[N],t[N],nxt[N];
LL g[N];
string s[N];
int tot=1,last,K;
void addedge(int x,int y)
{
	edge[++K]=EDGE(y,t[x]);
	t[x]=K;
}
int insert(int c,int last)
{
	int p=last;
	if(ch[p][c])
	{
		int np=ch[p][c];
		if(len[p]+1==len[np])
			return np;
		else
		{
			int nq=++tot;
			len[nq]=len[p]+1;
			for(int i=0;i<26;i++)
				ch[nq][i]=ch[np][i];
			while(p&&ch[p][c]==np)
				ch[p][c]=nq,p=fa[p];
			fa[nq]=fa[np],fa[np]=nq;
			return nq;	
		}
	}
	int q=++tot;
	len[q]=len[p]+1;
	while(p&&!ch[p][c]) ch[p][c]=q,p=fa[p];
	if(!p)	fa[q]=1;
	else
	{
		int np=ch[p][c];
		if(len[p]+1==len[np])	fa[q]=np;
		else
		{
			int nq=++tot;
			len[nq]=len[p]+1;
			for(int i=0;i<26;i++)
				ch[nq][i]=ch[np][i];
			while(p&&ch[p][c]==np)
				ch[p][c]=nq,p=fa[p];
			fa[nq]=fa[np],fa[np]=fa[q]=nq; 
		}
	}
	return q;
}
void dfs(int x)
{
	for(int p=t[x];p;p=edge[p].nxt)
	{
		int y=edge[p].to;
		dfs(y);
		g[x]+=g[y];
	}
}
void get_next(int id)
{
	int l=s[id].length();
	nxt[0]=-1;
	int j=-1;
	for(int i=1;i<l;i++)
	{
		while(j!=-1&&s[id][j+1]!=s[id][i])
			j=nxt[j];
		if(s[id][j+1]==s[id][i])
			j++;
		nxt[i]=j;
	}
}
int main()
{
	int n;
	LL ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>s[i]; 
		last=1;
		for(int j=0;s[i][j];j++)
			last=insert(s[i][j]-'a',last);
		g[last]++;
		
	}
	for(int i=2;i<=tot;i++)
		addedge(fa[i],i);
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		int now=1;
		get_next(i);
		for(int j=0;s[i][j];j++)
		{
			now=ch[now][s[i][j]-'a'];
			ans=(ans+(LL)(j+1)*(j+1)%md*g[now]%md)%md;
			if(nxt[j]>=0)
				ans=(ans-(LL)(nxt[j]+1)*(nxt[j]+1)%md*g[now]%md+md)%md;
		}
	}
	printf("%lld",ans);
	return 0;
}

H Happy Triangle

題意：維護一個集合，支援如下操作：

插入一個元素x
删除一個元素x
詢問集合中是否存在一對(a, b)使得x, a, b可以構成三角形

思路：

求三角形即使求一組(a, b)使得a-b<x<a+b，是以問題就可以轉化成區間覆寫問題。但是，如果兩兩求區間，區間數量達到O(n2)的級别，會TLE，是以要考慮如何減少區間。我們發現對于确定的a，當a>b>c的時候，（a-c, a+c）的區間被包含在（a-b, a+b）的區間内。是以對于确定的a，第一個比它小的元素與它構成的區間能夠包含所有比a小的元素與a構成的區間，也就是說，我們隻需要處理相鄰元素的區間就可以了。

是以，我們用set維護集合，插入或删除元素時，隻需處理相鄰元素與之構成的區間即可。線段樹做區間覆寫。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<stack>
using namespace std;
const int N=2e5+10;
const int inf=1e9+10; 
struct EDGE{
	int x,id;
	EDGE(){}
	EDGE(int a,int b)
	{	x=a;	id=b;}
	bool operator < (const EDGE &other)
	const{	return x<other.x||(x==other.x&&id<other.id);}
};
set<EDGE>s;
set<EDGE>ss;
set<EDGE>::iterator it;
set<EDGE>::iterator itt;
stack<int>stk[N];
int v[N*4],tag[N*4],h[N],a[N],opt[N];
int cnt;
void pushdown(int x)
{
	tag[x*2]+=tag[x];
	tag[x*2+1]+=tag[x];
	v[x*2]+=tag[x];
	v[x*2+1]+=tag[x];
	tag[x]=0;
}
void insert(int x,int l,int r,int ll,int rr,int vv)
{
	if(r<ll||rr<l)
		return;
	if(ll<=l&&r<=rr)
	{
		v[x]+=vv;		tag[x]+=vv;		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	insert(x*2,l,mid,ll,rr,vv);
	insert(x*2+1,mid+1,r,ll,rr,vv);
}
int query(int x,int l,int r,int ll)
{
	if(l==r)
		return v[x];
	pushdown(x);
	int mid=(l+r)>>1;
	if(ll<=mid)
		return query(x*2,l,mid,ll);
	else
		return query(x*2+1,mid+1,r,ll);
}
void ins(int i)
{
	int l,r;
	int x=lower_bound(h+1,h+cnt+1,a[i])-h;
	stk[x].push(i);
	it=ss.upper_bound(EDGE(-a[i],-i));//負集 
	if(it!=ss.end())
	{
		l=lower_bound(h+1,h+cnt+1,a[i]+(*it).x)-h;	r=lower_bound(h+1,h+cnt+1,a[i]-(*it).x)-h;
		if(h[l]==a[i]+(*it).x)	l++;
		r--;
		insert(1,1,cnt,l,r,1);
	}
	itt=s.upper_bound(EDGE(a[i],i));
	if(itt!=s.end()&&it!=ss.end())
	{
		l=lower_bound(h+1,h+cnt+1,(*itt).x+(*it).x)-h;	r=lower_bound(h+1,h+cnt+1,(*itt).x-(*it).x)-h;
		if(h[l]==(*itt).x+(*it).x)	l++;
		r--;
		insert(1,1,cnt,l,r,-1);
	}
	if(itt!=s.end())
	{
		l=lower_bound(h+1,h+cnt+1,(*itt).x-a[i])-h;	r=lower_bound(h+1,h+cnt+1,(*itt).x+a[i])-h;
		if(h[l]==(*itt).x-a[i])	l++;
		r--;
		insert(1,1,cnt,l,r,1);
	}
	s.insert(EDGE(a[i],i));
	ss.insert(EDGE(-a[i],-i));
}
void del(int i)
{
	int l,r;
	int x=lower_bound(h+1,h+cnt+1,a[i])-h;
	int ti=stk[x].top();
	stk[x].pop();
	it=ss.upper_bound(EDGE(-a[i],-ti));//負集 
	if(it!=ss.end())
	{
		l=lower_bound(h+1,h+cnt+1,a[i]+(*it).x)-h;	r=lower_bound(h+1,h+cnt+1,a[i]-(*it).x)-h;
		if(h[l]==a[i]+(*it).x)	l++;
		r--;
		insert(1,1,cnt,l,r,-1);
	}
	itt=s.upper_bound(EDGE(a[i],ti));
	if(itt!=s.end()&&it!=ss.end())
	{
		l=lower_bound(h+1,h+cnt+1,(*itt).x+(*it).x)-h;	r=lower_bound(h+1,h+cnt+1,(*itt).x-(*it).x)-h;
		if(h[l]==(*itt).x+(*it).x)	l++;
		r--;
		insert(1,1,cnt,l,r,1);
	}
	if(itt!=s.end())
	{
		l=lower_bound(h+1,h+cnt+1,(*itt).x-a[i])-h;	r=lower_bound(h+1,h+cnt+1,(*itt).x+a[i])-h;
		if(h[l]==(*itt).x-a[i])	l++;
		r--;
		insert(1,1,cnt,l,r,-1);
	}
	s.erase(EDGE(a[i],ti));
	ss.erase(EDGE(-a[i],-ti));
}
void que(int i)
{
	int x=lower_bound(h+1,h+cnt+1,a[i])-h;
	if(query(1,1,cnt,x))	printf("Yes\n");
	else	printf("No\n");
} 
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&opt[i],&a[i]);
		h[i]=a[i];
	}
	sort(h+1,h+n+1);
	cnt=unique(h+1,h+n+1)-h-1;
	h[cnt+1]=inf;
	for(int i=1;i<=n;i++)
	{
		if(opt[i]==1)	ins(i);
		if(opt[i]==2)	del(i);
		if(opt[i]==3)	que(i);
	}
	return 0;
}
/*
10 
1 1
1 2
1 3
3 1
3 2 
3 3
1 1 
1 2 
2 3
3 1 
*/

牛客暑期多校訓練營2020第2場

A All with Pairs

H Happy Triangle

繼續閱讀

D. Dr. Evil Underscores

Codeforces Round #685 (Div. 2) D,ECodeforces Round #685 (Div. 2)D. Circle GameE2 - Bitwise Queries (Hard Version)

2017-2018 ACM-ICPC, Asia Daejeon Regional Contest

2020牛客寒假算法基礎訓練營2

牛客暑期多校訓練營2020第3場

2021（CCPC）- 網絡選拔賽Problem K. Shooting Bricks

The 2019 ICPC Asia Shanghai Regional Contest

[kuangbin]各種各樣的題單

2019牛客多校賽第六場 D.Move (枚舉+multiset)

Half-consecutive Numbers

Bomb

[ 牛客 ] “補題|總結|題解“ 牛客小白月賽35B.我(不)是酸菜魚C:逆元處理 (闆子題哭唧唧)H-登入!(字元串我投降了)

2021牛客國慶集訓派對day5 題解-A,B,F,G,J

Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))

codeforces443B