3.30省选模拟

本文主要是介绍3.30省选模拟，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

开局\(MTT\)优化\(dp,\)跳,\(dp\)计数,跳,虚树\(dp,QAQ,\)昨天是数学场,今天搁这\(dp\)场呢

看题解都能看自闭...

\(T1\)

考场上很容易转化到取石子,转化成阶梯博弈就好了,然后至于优化\(dp,\)使用\(MTT\)就好了

于是乎,我前几天看的一个博客,讲了除了阶梯博弈的所有博弈,看了一个多项式论文,\(MTT\)在后面一页,我当时只看了看循环卷积...然后出题人好巧的出了这两个融合题

挂一下博客

https://www.cnblogs.com/Eternal-Battle/p/16060888.html

https://www.cnblogs.com/Eternal-Battle/p/16064390.html

那么问题简化为,我们现在有\(n-m\)个棋子,放到\(m+1\)个盒子(可空),并且奇数位置异或和不为\(0\)的方案数

对于二进制的\(dp,\)可以比较套路的拆位计算

\(dp[t][i][j][0/1]\)表示我们目前考虑第\(t\)位,目前考虑完前\(i\)个石子堆,用了\(j\)个石子,目前异或起来等于\(1/0\)的方案数

我们最后的答案只是\(N=n-m\)

那么我们考虑\(N\)是怎么放的

我们从高往低考虑,我们考虑这一位是怎么加上来的,可能原来某一次直接加上来,或者是进位得到

\(f[t][i][s][0/1]\)表示我们已经从高到低考虑了第\(t\)位,目前保证了高位异或和为\(0,\)正在安排第\(i\)堆石子第\(t\)位,异或为\(1/0,\)欠下进位和为\(s\)的方案数

那么每次转移只需要保证和\(N\)这一位相等就好了

然后由于每一堆等价,直接预处理即可,然后\(MTT\)优化

#define Eternal_Battle ZXK
#include<bits/stdc++.h>
#define mod 1000000009
#define int long long
#define MAXX 32005
#define MAXM 16005
#define MAXN 8005
using namespace std;
const double PI=acos(-1);
int fac[MAXN],inv[MAXN],pp[MAXN];
int my_pow(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
int C(int x,int y)
{
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void init(int N)
{
	fac[0]=1;
  	for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod;
  	inv[N]=my_pow(fac[N],mod-2);
  	for(int i=N;i;i--) inv[i-1]=inv[i]*i%mod;
  	int a=N/2,b=(N+1)/2;
  	for(int k=0;k<=N;k++)
  	{
    	for(int i=0;i<=a;i+=2)
    	{
      		if(0<=k-i&&k-i<=b) pp[k]=(pp[k]+C(a,i)*C(b,k-i))%mod;
    	}
  	}
}
int g[70][MAXM];
long long n,m;
typedef complex<double> com;
const com I(0, 1);
com Wn[MAXX];
int R[MAXX];
void FFT(com *A,int n,int t)
{
	if(t==-1)
		for(int i=1;i<n;i++)
			if(i<(n-i))swap(A[i],A[n-i]);
	for(int i=0;i<n;i++)
		if(i<R[i]) swap(A[i],A[R[i]]);
	for(int m=1,l=0;m<n;m<<=1,l++)
	{
		for(int i=0;i<n;i+=m<<1)
		{
			for(int k=i;k<i+m;k++)
			{
				com W=Wn[1ll*(k-i)*n/m];
				com a0=A[k],a1=A[k+m]*W;
				A[k]=a0+a1;
				A[k+m]=a0-a1;
			}
		}
	}
	if(t==-1)
		for(int i=0;i<n;i++) A[i]/=n;
}
long long num(com x)
{
	double d=x.real();
	return d<0?(long long)(d-0.5)%mod:(long long)(d+0.5)%mod;
}
void FFTFFT(com *a,com *b,int len,int t)
{
	for(int i=0;i<len;i++) a[i]=a[i]+I*b[i];
	FFT(a,len,t);
	for(int i=0;i<len;i++)
		b[i]=conj(a[i?len-i:0]);
	for(int i=0;i<len;i++)
	{
		com p=a[i],q=b[i];
		a[i]=(p+q)*0.5;
		b[i]=(q-p)*0.5*I;
	}
}
com a0[MAXM],b0[MAXM],a1[MAXM],b1[MAXM];
com q[MAXM],p[MAXM];
int ans[MAXX];
void MTT(int x)
{
	int fl=(((n-m)>>x)&1);
	memset(a0,0,sizeof(a0));
	memset(b0,0,sizeof(b0));
	memset(a1,0,sizeof(a1));
	memset(b1,0,sizeof(b1));
	int nn=2*(m+1)+fl,mm=m+1;
	int M=(int)(sqrt(mod)+1);
	for(int i=0;i<=m+1;i++)
	{
		a0[i*2+fl]=g[x+1][i]/M;
		a1[i*2+fl]=g[x+1][i]%M;
	}
	for(int i=0;i<=m+1;i++)
	{
		b0[m+1-i]=pp[i]/M;
		b1[m+1-i]=pp[i]%M;
	}
	int len=1;
	while(len<nn+mm+1) len<<=1;
	for(int i=1;i<len;i++)
	{
		R[i]=R[i>>1]>>1|((i&1)*(len>>1));
	}
	for(int i=0;i<len;i++)
	{
		Wn[i]=com(cos(PI/len*i),sin(PI/len*i));
	}
	FFTFFT(a0,a1,len,1);
	FFTFFT(b0,b1,len,1);
	for(int i=0;i<len;i++)
	{
		p[i]=a0[i]*b0[i]+I*a1[i]*b0[i];
		q[i]=a0[i]*b1[i]+I*a1[i]*b1[i];
	}
	FFT(p,len,-1);
	FFT(q,len,-1);
	for(int i=0;i<=nn+mm;i++)
	{
		ans[i]=(M*M*num(p[i].real())%mod+M*(num(p[i].imag())+num(q[i].real()))%mod+num(q[i].imag()))%mod;
	}
	for(int i=m+1;i<=2*(m+1);i++)
	{
		g[x][i-(m+1)]=ans[i];
	}
}
signed main()
{
	freopen("fall.in","r",stdin);
	freopen("fall.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	init(m+1);
	g[61][0]=1;
	int Ti=log2(n),fi=60-Ti+1;
	for(int t=60;t>=0;t--)
	{
		MTT(t);
	}
	long long buf=inv[m];
	for(int i=1;i<=m;i++)buf=buf*((n-i+1)%mod)%mod;
	printf("%lld",(buf+mod-g[0][0])%mod);
	return 0;
}

\(T2\)

求出有多少张无向图,满足\(1\)到所有点的最短路唯一,而且最短路长度不降

计数题,基本上是\(dp,\)生成函数之类的

由于需要满足最短路唯一,最后的图,必然是\(bfs\)完之后分完层,不存在跨两层的路,或者说每个点连向上一层只有一条边,其余的边必然是同层的

那么有了结论之后,就可以愉快的\(dp\)了,而且比较显然的,我们最短路长度递增,我们就可以顺着\(dp\)

\(dp[i][j]\)表示我们已经考虑前\(i\)个点,最后\(j\)个深度相同的方案数,和线性\(dp\)划分区域很像吧

而且设计\(g[i][j][k]\)表示这一层有\(i\)个点,上一层度数为二有\(j\)个点,度数为三有\(k\)个点边集的方案数,然后使用这个来辅助转移,枚举这一层和上一层的所有状态,考虑我们为什么不记录这一层的度数,这次转移不需要考虑这一层之间怎么连的,由于已知肯定需要花费一度数,那么在下一层时候才考虑这一层的同层状态

\(dp[i][j]=\sum_{k=1}^{i-j-1}dp[i-j][k]\times g[j][c_0][c_1]\)

还是说,这个转移是在下一次转移才考虑这一层的转移状态,那么统计答案那个式子也可以看懂了

那么考虑\(g\)是怎么转移的

\(g[0][0][0]=1\)显然

\(i=j=0,k\neq 0\)

那么上一层节点都是度数为\(3\),并且其余两条边都是连向同一层,现在的图是一些联通块,那么枚举一下联通块大小转移一下就好了,我们为了保证不重复计算,枚举包含最后一个点环的大小,乘上其余的方案数即可、

\(g[i][j][k]=\sum_{l=2}^{k-1}(g[0][0][k-l-1]\times C(k-1,l)\times \frac{l!}{2})\)

\(i=0,j>0,k>0\)

艹,什么\(lj\)题解,让我看了半天,直接看新增的是哪个不就好了\(?\)由于有标号,所以情况不一样

\(g[0][j][k]=g[0][j-2][k]\times(j-1)+g[0][j][k-1]\times k\)

\(i>0,j>0,k>0\)

\(g[i][j][k]=g[i-1][j-1][k]\times j+g[i-1][j+1][k-1]\times k\)

分析一致

#define Eternal_Battle ZXK
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
#define MAXN 305
#define Maxn 300
using namespace std;
int n,d[MAXN],a[MAXN],g[MAXN][MAXN][MAXN],f[MAXN][MAXN],c[MAXN][MAXN];
void Init()
{
	a[0]=a[1]=0;
	a[2]=a[3]=1;
	for(int i=4;i<=Maxn;i++)
	{
		a[i]=a[i-1]*(i-1)%mod;
	}
	for(int i=0;i<=Maxn;i++)
	{
		c[i][i]=c[i][0]=1;
	}
	for(int i=1;i<=Maxn;i++)
	{
		for(int j=1;j<i;j++)
		{
			c[i][j]=c[i-1][j-1]+c[i-1][j];
			c[i][j]%=mod;
		}
	}
	g[0][0][0]=1;
	for(int j=0;j<=Maxn;j++)
	{
		for(int k=0;k<=Maxn-j;k++)
		{
			if(j==0&&k>0)
			{
				for(int l=2;l<k;l++)
				{
					g[0][j][k]+=(g[0][j][k-l-1]*c[k-1][l])%mod*a[l+1]%mod;
					g[0][j][k]%=mod;
				}
			}
			else
			{
				if(j>=2) g[0][j][k]+=(g[0][j-2][k]*(j-1))%mod,g[0][j][k]%=mod;
		    	if(k>=1) g[0][j][k]+=(g[0][j][k-1]*k)%mod,g[0][j][k]%=mod;
			}
			
		}
	}
	for(int i=1;i<=Maxn;i++)
	{
		for(int j=0;j<=Maxn-i;j++)
		{
			for(int k=0;k<=Maxn-i-j;k++)
			{
				if(j>=1) g[i][j][k]+=(g[i-1][j-1][k]*j)%mod,g[i][j][k]%=mod;
				if(k>=1) g[i][j][k]+=(g[i-1][j+1][k-1]*k)%mod,g[i][j][k]%=mod;
			}
		}
	}
}
int c1,c2;
void Input()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
}
void Eternal_Battle()
{
	f[d[1]+1][d[1]]=1;
	for(int i=d[1]+2;i<=n;i++)
	{
		for(int j=1;j<=i-d[1]-1;j++)
		{
			c1=c2=0;
			for(int k=1;k<=i-j;k++)
			{
				if(d[i-j-k+1]==2) c1++;
				else c2++;
				f[i][j]+=f[i-j][k]*g[j][c1][c2]%mod;
				f[i][j]%=mod;
			}
		}
	}
	c1=c2=0;
	int ans=0;
	for(int j=1;j<n;j++)
	{
		if(d[n-j+1]==2)c1++;
		else c2++;
		ans+=f[n][j]*g[0][c1][c2]%mod;
		ans%=mod;
	}
	printf("%lld\n",ans);
}
signed main()
{
	freopen("search.in","r",stdin);
	freopen("search.out","w",stdout);
	Init();
	Input();
	Eternal_Battle();
}

\(T3\)

观察数据范围,比较显然的就是\(\sum q,\)关于询问点不超过一个范围,显然是一个虚树\(dp\)

那么对于我们询问节点造出一棵虚树,发现这道题和\([HNOI2014]\)世界树神似...

这个也是询问所有最近的点里面的最大值,世界树也是把这个点归到最近的点了

这道题麻烦的多...

看出来是虚树只是开始,如何在虚树上转移是最大问题

我们首先求出虚树上每个点距离最近的关键点距离是多少,然后考虑答案必然在链上取到

套路的考虑,虚树上的点贡献最大值,不在虚树上的点贡献最大值

那么不在虚树上的点

分情况讨论\(:\)

\(Sit_1:\)整个子树没有在虚树内,那么就直接找一个深度最大点就好了

\(Sit_2:\)在虚树节点之间的边上

考虑一下我们世界树的套路,就是把这个点分到对应的区间,这个的话也同样处理一下

处理一下倍增数组,然后找距离就好了

#include<bits/stdc++.h>
#define MAXM 300005
#define MAXN 150005
using namespace std;
int head[MAXM],last[MAXM],to[MAXM],cnt,d1[MAXM],n;
int head1[MAXN],last1[MAXM],to1[MAXM],cnt1;
int head2[MAXM],last2[MAXM],to2[MAXM],cnt2;
int in[MAXM],out[MAXM],tim;
int dp[MAXM],ans;
bool vis[MAXM];
void add1(int u,int v)
{
	cnt1++;
	last1[cnt1]=head1[u];
	head1[u]=cnt1;
	to1[cnt1]=v;
}
void add(int u,int v)
{
	cnt++;
	last[cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
}
void build1(int u,int f)
{
	d1[u]=d1[f]+1;
	int pre=u;
	for(int i=head1[u];i;i=last1[i])
	{
		int v=to1[i];
		if(v==f)
		{
			continue;
		}
		build1(v,u);
		n++;
		d1[n]=d1[u];
		add(pre,n);
		add(n,v);
		pre=n;
	}
}
int d[MAXM],mxd[MAXM];
int anc[MAXM][20],val1[MAXM][20],val2[MAXM][20];
void dfs(int u)
{
	mxd[u]=d1[u];
	for(int i=head[u];i;i=last[i])
	{
		int v=to[i];
		d[v]=d[u]+1;
		dfs(v);
		if(mxd[v]>mxd[u])
		{
			mxd[u]=mxd[v];
		}
	}
}
void dfs2(int u)
{
	tim++;
	in[u]=tim;
	for(int i=1;i<20;i++)
	{
		anc[u][i]=anc[anc[u][i-1]][i-1];
		val1[u][i]=val1[u][i-1];
		if(val1[anc[u][i-1]][i-1]>val1[u][i])
		{
			val1[u][i]=val1[anc[u][i-1]][i-1];
		}
		val2[u][i]=val2[u][i-1];
		if(val2[anc[u][i-1]][i-1]>val2[u][i])
		{
			val2[u][i]=val2[anc[u][i-1]][i-1];
		}
	}
	for(int i=head[u];i;i=last[i])
	{
		int v=to[i];
		anc[v][0]=u;
		val1[v][0]=d1[u];
		for(int j=head[u];j;j=last[j])
		{
			int w=to[j];
			if(w==v)
			{
				continue;
			}
			if(mxd[w]>val1[v][0])
			{
				val1[v][0]=mxd[w];
			}
		}
		val2[v][0]=val1[v][0]-d1[u]-d1[u];
		dfs2(v);
	}
	out[u]=tim;
}
int lca(int u,int v)
{
	if(d[u]<d[v])
	{
		int t=u;
		u=v;
		v=t;
	}
	int dd=d[u]-d[v];
	for(int i=0;i<20;i++)
	{
		if(dd&(1<<i))
		{
			u=anc[u][i];
		}
	}
	if(u==v)
	{
		return v;
	}
	for(int i=19;i>=0;i--)
	{
		if(anc[u][i]!=anc[v][i])
		{
			u=anc[u][i];
			v=anc[v][i];
		}
	}
	return anc[v][0];
}
void add2(int u,int v)
{
	cnt2++;
	last2[cnt2]=head2[u];
	head2[u]=cnt2;
	to2[cnt2]=v;
}
void sol1(int u)
{
	if(vis[u])
	{
		dp[u]=0;
	}
	else
	{
		dp[u]=1000000;
	}
	for(int i=head2[u];i;i=last2[i])
	{
		int v=to2[i];
		sol1(v);
		if(dp[v]+d1[v]-d1[u]<dp[u])
		{
			dp[u]=dp[v]+d1[v]-d1[u];
		}
	}
}
void sol2(int u)
{
	for(int i=head2[u];i;i=last2[i])
	{
		int v=to2[i];
		if(dp[u]+d1[v]-d1[u]<dp[v])
		{
			dp[v]=dp[u]+d1[v]-d1[u];
		}
		sol2(v);
	}
}
void sol(int u)
{
	int numc=-1;
	for(int i=head2[u];i;i=last2[i])
	{
		numc++;
	}
	if(numc<0)
	{
		if(dp[u]+mxd[u]-d1[u]>ans)
		{
			ans=dp[u]+mxd[u]-d1[u];
		}
	}
	for(int i=head2[u];i;i=last2[i])
	{
		int v=to2[i];
		sol(v);
		int w=v;
		for(int j=19;j>=0;j--)
		{
			if(d1[v]-d1[anc[w][j]]+dp[v]<d1[anc[w][j]]-d1[u]+dp[u])
			{
				if(val2[w][j]+d1[v]+dp[v]>ans)
				{
					ans=val2[w][j]+d1[v]+dp[v];
				}
				w=anc[w][j];
			}
		}
		for(int j=19;j>=0;j--)
		{
			if(d[anc[w][j]]>=d[u]+numc)
			{
				if(val1[w][j]-d1[u]+dp[u]>ans)
				{
					ans=val1[w][j]-d1[u]+dp[u];
				}
				w=anc[w][j];
			}
		}
	}
	head2[u]=0;
	vis[u]=false;
}
struct node
{
	int u;
	int val;
	bool operator<(node b) const
	{
		return val<b.val;
	}
}nn[MAXM];
int s[MAXM];
int main()
{
//	freopen("inception.in","r",stdin);
//	freopen("inception.out","w",stdout);
	int q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add1(u,v);
		add1(v,u);
	}
	d[1]=1;
	build1(1,0);
	dfs(1);
	dfs2(1);
	while(q--)
	{
		cnt2=0;
		ans=0;
		int k;
		scanf("%d",&k);
		for(int i=0;i<k;i++)
		{
			scanf("%d",&nn[i].u);
			nn[i].val=in[nn[i].u];
			vis[nn[i].u]=true;
		}
		sort(nn,nn+k);
		int kk=k;
		for(int i=1;i<k;i++)
		{
			nn[kk].u=lca(nn[i].u,nn[i-1].u);
			nn[kk].val=in[nn[kk].u];
			kk++;
		}
		k=kk;
		sort(nn,nn+k);
		int r=0;
		s[0]=1;
		for(int i=0;i<k;i++)
		{
			while(1)
			{
				if(nn[i].val<=out[s[r]])
				{
					break;
				}
				r--;
			}
			if(s[r]==nn[i].u)
			{
				continue;
			}
			add2(s[r],nn[i].u);
			r++;
			s[r]=nn[i].u;
		}
		sol1(1);
		sol2(1);
		sol(1);
		printf("%d\n",ans);
	}
	return 0;
}

这篇关于3.30省选模拟的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！