图论

【Luogu P8428】 Pastiri

题目描述

给定一棵 \(N\) 点的树，点编号为 \(1\) 到 \(N\)，现在在 \(K\) 个点上有羊，你的任务是在树上分配一些牧羊人。

这些牧羊人很懒，只会看管离他最近的羊。当然如果有多个离他最近的羊，那么他会都看管。

当然，牧羊人可以和羊在同一个点上，但这样牧羊人只会看管这一个点上的那个羊。

求一种牧羊人的分配方案使得牧羊人总数最小，\(1 \le n \le 5 \times 10^5\)。

解题思路

首先这题用树形 \(dp\) 是极其不现实的 ，数据大且信息不好表示。

我们可以考虑贪心：将所有羊按深度从大到小排序，每次选取一个深度最大的羊，在它的祖先中选取一个能够管到它的节点，在该节点上放牧羊人。

这个贪心的正确性是显然的，因为放的越高能照顾到的也越多，且由于深度最大，无需放到别的子树去管别的节点。

我们得到了一个 \(O(n^2)\) 的做法，考虑优化。

我们每次都需要花 \(O(n)\) 的时间复杂度来找深度最小且能照顾到自己的节点，并且将该节点能照顾到的所有节点都打上标记。

考虑优化查找，我们可以使用边定向，先求出每个节点 \(i\) 距离它最近的羊距离设为 \(dis_i\) ，然后对于所有 \(dis_u=dis_v+1\) 的边，我们在新图上建一条有向边 \((u,v)\) 表示点 \(u\) 能照顾点 \(v\) ，那我们就可以与处理出所有羊深度最小的且能处理它的节点了。

时间复杂度 \(O(n)\) 。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,t[500005],dis[500005],deep[500005],f[500005],t1[500005],k,s;
bool v1[500005],v[500005];
vector<int> a[500005],a1[500005];
bool cmp1(int q,int w){return deep[q]>deep[w];}
void dfs1(int x,int y)
{
	if(!v1[x])dis[x]=n+1;
	deep[x]=deep[y]+1;
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==y)continue;
		dfs1(a[x][i],x);
		dis[x]=min(dis[x],dis[a[x][i]]+1);
	}
	return;
}
void dfs2(int x,int y,int z)
{
	dis[x]=min(dis[x],z);
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==y)continue;
		dfs2(a[x][i],x,dis[x]+1);
	}
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==y)continue;
		if(dis[a[x][i]]==dis[x]+1)a1[a[x][i]].push_back(x);
		if(dis[x]==dis[a[x][i]]+1)a1[x].push_back(a[x][i]);
	}
	return;
}
void dfs4(int x,int y,int z)
{
	f[x]=z;
	for(int i=0;i<a1[x].size();i++)
	{
		if(a1[x][i]==y)continue;
		dfs4(a1[x][i],x,z);
	}
	return;
}
void dfs3(int x,int y)
{
	if(f[x]==n+1)dfs4(x,y,x);
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==y)continue;
		dfs3(a[x][i],x);
	}
	return;
}
void dfs5(int x,int y)
{
	v[x]=1;
	for(int i=0;i<a1[x].size();i++)
	{
		if(a1[x][i]==y||v[a1[x][i]])continue;
		dfs5(a1[x][i],x);
	}
	return;
}
int main()
{
	int x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		a[x].push_back(y),a[y].push_back(x);
	}
	for(int i=1;i<=m;i++)scanf("%d",&t[i]),v1[t[i]]=1;
	for(int i=1;i<=n;i++)f[i]=n+1;
	dfs1(1,0),dfs2(1,0,n+1),dfs3(1,0);
	sort(t+1,t+m+1,cmp1);
	for(int i=1;i<=m;i++)
	{
		if(v[t[i]])continue;
		s++,t1[++k]=f[t[i]];
		dfs5(f[t[i]],0);
	}
	sort(t1+1,t1+k+1);
	printf("%d\n",s);
	for(int i=1;i<=k;i++)printf("%d ",t1[i]);


  return 0;
}

动态规划

【Luogu P10681】 奇偶矩阵 Tablica

题目描述

考虑只包含 \(0\) 和 \(1\) 的 \(N\times M\) 矩阵 \(A\)。

我们称满足以下条件的矩阵是好的：

• \(\forall 1\le i\le N\)，\(\displaystyle \sum_{j=1}^M A_{i,j}\in \{1,2\}\)；
• \(\forall 1\le j\le M\)，\(\displaystyle \sum_{i=1}^N A_{i,j}\in \{1,2\}\)。

求出 \(N\) 行 \(M\) 列的好的矩阵的数量，对 \((10^9+7)\) 取模，\(1 \le n ,m \le 3000\)。

解题思路

法一

由于矩阵只包含 \(0\) 和 \(1\) ，我们把每个 \(1\) 的节点 \((i,j)\) 看成第 \(i\) 行所代表的点向第 \(j\) 行所代表的点连了一条边。

很明显，我们构造出了一个二分图，若这个图满足题目要求有两个条件，每个点不是独立的且每个连通块必须是一条链或一个环。

注意每个连通块在左右两边所占的个数最多只差 \(1\) ，参考 ABC180F ，做一个 \(n^2\) 的 \(dp\) 即可。

法二

我们可以枚举有多少行、列和分别为 \(1\) 或 \(2\) ，设有 \(a\) 行的和为 \(1\) ，\(b\) 行的和为 \(2\) ，\(c\) 列的和为 \(1\) ，\(d\) 列的和为 \(2\) ，满足 \(a+b=n,c+d=m,a+2b=c+2d\)。

我们可以 \(O(n)\) 枚举 \(a,b,c,d\) ，考虑如何贡献答案。

首先给每行每列安排为 \(1\) 还是 \(2\) ，即乘上 \(C_{n}^{a} C_{m}^{b}\) ，然后考虑如何将每列的 \(1\) 分配到每行。

我们看成这样一个问题：有 \(c+2d\) 个小球，共有 \(m\) 种颜色，\(c\) 种颜色的小球每种各 \(1\) 个，\(d\) 种颜色的小球每种个 \(2\) 个，分成 \(n\) 个块，要求每块里面的球的颜色不能相同。

我们考虑将其排成一个序列，共有 \(\frac{(c+2d)!}{2^d}\) 种方案，然后按顺序分成块。

可能会有两种重复，第一种为出现 \({1,2}\) 与 \({2,1}\) 的情况，这种直接除 \(2^b\) 即可。

第二种为出现 \({1,1}\) 的情况，这种情况我们需要容斥，考虑 \(t(0 \le t \le min(b,d))\) 个 \(1,1\) 的集合，每次的答案即为 \((-1)^t A_{b}^{t}C_{d}^{t} \frac{(c+2d-2t)!}{2^{b+d-t}}\)。

总答案 $ans=\sum C_{n}^a C_m^b \sum_{t=0}^{min(b,d)} (-1)^t A_{b}^t C_{d}^t \frac{(c+2d-2t)!}{2^{b+d-t}} $ 。

Code

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,C[3005][3005],p[10005],p1[10005],a,b,c,d,s,f[10005];
long long poww(long long x,long long y)
{
	long long h=1;
	while(y)
	{
		if(y&1)h=(h*x)%mod;
		x=(x*x)%mod,y>>=1; 
	}
	return h;
}
int main()
{
	long long x,s1=0;
	scanf("%lld%lld",&n,&m),p[0]=p1[0]=f[0]=1;
	for(int i=1;i<=10000;i++)p[i]=p[i-1]*2%mod,p1[i]=poww(p[i],mod-2),f[i]=(f[i-1]*i)%mod;
	for(int i=0;i<=3000;i++)C[i][i]=C[i][0]=1;
	for(int i=1;i<=3000;i++)
		for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(int i=0;i<=n;i++)
	{
		a=i,b=n-i,d=a+2*b-m,c=m-d,x=min(b,d),s1=0;
		if(c<0||d<0)continue;
		for(int j=0;j<=x;j++)
			s1=(s1+((j&1)?(-1):1)*(((C[b][j]*C[d][j]%mod)*f[j]%mod)*(f[c+2*d-2*j]*p1[b+d-j]%mod)%mod)%mod)%mod;
		s=(s+s1*(C[n][a]*C[m][c]%mod)%mod)%mod;
	}
	printf("%lld",(s+mod)%mod);


  return 0;
}