杭電第十場 題解

比賽傳送門

作者： fn

目錄

• 進階題
• • 1003題 Pty loves lines / Pty喜歡行
  • 1008題 Pty loves string / Pty喜歡字元串

進階題

1003題 Pty loves lines / Pty喜歡行

題目大意

在一個平面上放 n n n 條直線，任意三條直線不能交于一點，直線不能重合。輸出所有可能的交點數目。

n≤700，時間限制一秒。

考察内容

dp，背包，複雜度優化

分析

解法一：

設 f [ i ] [ j ] f[i][j] f[i][j] 表示用 i 條直線是否能湊出 j 個交點。

可以用bitset來優化轉移，做到 O ( n 4 w ) O(\frac{n^4}{w}) O(wn4​) 的時間複雜度，這是難以通過1秒的時間限制的。

觀察發現答案有相當長一段連續可行字尾，打表後發現最大不可行交點數不超過 31500 ，于是時間可以優化到 31500 × n 2 w 31500 × \frac{n^2}{w} 31500×wn2​ ，可以通過本題。

解法二：

#include <bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define mod 998244353
#define ll long long
using namespace std;

int f[490000],n,m,i,j,k,l;
int ask[1000];
int main() {
	int T = 0;
	for(cin>>T;T;T--){
		scanf("%d",&n);
		ask[n]=1;
	}
	memset(f,127,sizeof(f)),f[0]=0;
	m=700*700/2;
	for(int j=1;j<=n;j++){
		for(int i=0;i<=m-1;i++){
			k=i+j*(j-1)/2;
			if (k<=m)
				f[k]=min(f[k],f[i]+j);
		}

		if(ask[j]) {
			int mm=j*(j-1)/2;
			for(int i=0;i<=mm-1;i++){
				if (f[mm-i]<=j)
					printf("%d ",i);
			}
			printf("%d\n",mm); //
		}
	}
}
           

1008題 Pty loves string / Pty喜歡字元串

題目大意

字元串S由英文小寫字母組成，長度為n。

Q次詢問，對于每次詢問給定x,y。 讓字元串T是字元串S中長度x的字首和長度y的字尾的連接配接，求T在字元串S中的出現次數。

考察内容

KMP，掃描線

分析

考慮一個出現位置 S[l…r] ，會滿足 S[l…l + x − 1] 和 S[1…x] 相等， S[r − y + 1…r] 和 S[n − y + 1…n] 相等，且 l + x = r − y + 1 。

前兩個條件容易想到border，用KMP即可求出對于所有的 l + x − 1 合法的 x 。

考慮KMP做完從 i 向 i 的border連一條邊，這樣我們會得到一棵樹，一個 x 的所有出現位置即為其子樹。

那麼問題可以變為：有兩棵樹，問兩個子樹内有多少個點編号相同？

這個問題可以轉化為二維數點，用資料結構（掃描線+樹狀數組）維護即可。

複雜度 O ( n l o g n ) O(n log n) O(nlogn) 。

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 200005
using namespace std;
char st[N];
int n,m1,m2,q,fs[N],nt[N],dt[N],fi[N],dx[N],nx[N];
int ft[N],f2[N],sz[N],s2[N],dfn[N],df2[N],dfw[N],cnt,cnt2;
void link(int x,int y)
{
	nt[++m1]=fs[x];
	dt[fs[x]=m1]=y;
}
void dfs(int k,int fa)
{
	dfw[dfn[k]=++cnt]=k;
	sz[k]=1;
	for(int i=fs[k];i;i=nt[i])
	{
		int p=dt[i];
		if(p!=fa) dfs(p,k),sz[k]+=sz[p];
	}
}
void lk(int x,int y)
{
	nx[++m2]=fi[x];
	dx[fi[x]=m2]=y;
}
void dfs2(int k,int fa)
{
	df2[k]=++cnt2;
	s2[k]=1;
	for(int i=fi[k];i;i=nx[i])
	{
		int p=dx[i];
		if(p!=fa) dfs2(p,k),s2[k]+=s2[p];
	}
}
int rt[N],t[40*N][2],sm[40*N],n1;
#define nwp(k) (k=(!k)?++n1:k)
void ins(int k,int w,int l,int r,int x)
{
	if(l==r) {sm[k]=sm[w]+1;return;}
	int mid=(l+r)>>1;
	if(x<=mid) nwp(t[k][0]),t[k][1]=t[w][1],ins(t[k][0],t[w][0],l,mid,x);
	else nwp(t[k][1]),t[k][0]=t[w][0],ins(t[k][1],t[w][1],mid+1,r,x);
	sm[k]=sm[t[k][0]]+sm[t[k][1]];
}
int tot=0;
int query(int k,int w,int l,int r,int x,int y)
{
	tot++;
	if(!k||sm[k]-sm[w]==0||x>r||y<l) return 0;
	if(x<=l&&r<=y) return sm[k]-sm[w];
	int mid=(l+r)>>1,tmp=0;
	return query(t[k][0],t[w][0],l,mid,x,y)+query(t[k][1],t[w][1],mid+1,r,x,y);
}

void solve() {
	cin>>n>>q;
	scanf("%s",st+1);
	int j=0;
	fo(i,2,n)
	{
		while(j&&st[j+1]!=st[i]) j=ft[j];
		if(st[j+1]==st[i]) j++;
		ft[i]=j;
	}
	j=n+1;
	f2[n]=n+1;
	fod(i,n-1,1)
	{
		while(j<=n&&st[j-1]!=st[i]) j=f2[j];
		if(st[j-1]==st[i]) j--;
		f2[i]=j;
	}
	fo(i,1,n) link(ft[i],i),lk(f2[i],i);
	dfs(0,0),dfs2(n+1,0);
	fo(i,1,n+1)
	{
		rt[i]=++n1;
		ins(rt[i],rt[i-1],1,n+1,df2[dfw[i]+1]);
	}
	fo(i,1,q)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		y=n-y+1;
		printf("%d\n",query(rt[dfn[x]+sz[x]-1],rt[dfn[x]-1],1,n+1,df2[y],df2[y]+s2[y]-1));
	}
	m1=m2=0;fo(i,0,n+1) fs[i]=fi[i]=0;cnt=cnt2=0;
	fo(i,1,n+1) rt[i]=0;
	fo(i,1,n1) sm[i]=t[i][0]=t[i][1]=0;n1=0;
}

int main()
{
	int T;cin>>T;
	for(;T;T--) solve();
	return 0;
}