[作业题] #1 CF512D & CF516D & CF521D

CF512D Fox And Travelling

题目描述

点此看题

给出一张无向图，每次你可以选择一个度数 \(\leq 1\) 的点并将其删除。

问对于 \(k=0,1,2...n\) 有多少个删除 \(k\) 个点的序列，答案模 \(10^9+9\)

\(n\leq 100,m\leq \frac{n(n-1)}{2}\)

解法

因为只能删除度数 \(\leq 1\) 的点，所以环是和删除序列没关系的，那么我们把环去掉之后就得到了一个森林，这个过程可以用拓扑排序实现，没有拓扑掉的点就不需要考虑了。

但是这个森林的树是不相同的，因为如果有一棵树连接着环，那么必须要把链接的点当成根，最后选取它。但是如果树没有连接着环，就没有根这一说。所以这个森林混合了有根树和无根树。

首先考虑有根树怎么做，树形 \(dp\) 是显然的，\(dp[u][i]\) 表示点 \(u\) 内选取了 \(i\) 个点，然后树背包板。

无根树怎么做才是重点，根据我以前总结的套路我们可以枚举根，按照有根树的方法做树形 \(dp\)，再把得到的结果求和。这样做显然会算重，本题的点睛之笔就是考虑一种方案被算重了多少次（直接但实用方法），对于选取了 \(i\) 个点的方案，由于这 \(i\) 个点一定处在树的边缘，所以选取其他的 \(size-i\) 个点为根都会算到这个方案，那么我们除以 \(size-i\) 即可。

时间复杂度 \(O(n^3)\)，由于我不学多项式所以更优的做法将不再讲解。

细节：无向图的拓扑排序还是增设一个访问标记吧，然后在 \(deg\leq 1\) 的时候塞到队列里面。

#include 
#include 
#include 
using namespace std;
const int M = 105;
const int MOD = 1e9+9;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,tot,f[M],d[M],b[M],inv[M],fac[M],vis[M];
int dp[M][M],g[M],h[M],s[M],zinv[M],siz[M];
struct edge {int v,next;}e[M*M];
void add(int &x,int y) {x=(x+y)%MOD;}
void init(int n)
{
	fac[0]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=0;i<=n;i++) zinv[i]=inv[i];
	for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
int C(int n,int m)
{
	if(n q;
	for(int i=1;i<=n;i++)
		if(d[i]<=1) vis[i]=1,q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=f[u];i;i=e[i].next)
		{
			int v=e[i].v;d[v]--;
			if(d[v]<=1 && !vis[v]) vis[v]=1,q.push(v);
		}
	}
}
void dfs(int u,int rt)
{
	b[u]=rt;s[rt]++;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(!b[v] && !d[v]) dfs(v,rt);
	}
}
void get(int u,int fa)
{
	for(int i=0;i<=n;i++) dp[u][i]=0;
	dp[u][0]=1;siz[u]=1;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa || b[u]!=b[v]) continue;
		get(v,u);
		for(int j=siz[u];j>=0;j--)
			for(int k=1;k<=siz[v];k++)
				add(dp[u][j+k],dp[u][j]*dp[v][k]%MOD*C(j+k,j));
		siz[u]+=siz[v];
	}
	dp[u][siz[u]]=dp[u][siz[u]-1];
}
signed main()
{
	n=read();m=read();init(n);
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();d[u]++;d[v]++;
		e[++tot]=edge{u,f[v]},f[v]=tot;
		e[++tot]=edge{v,f[u]},f[u]=tot;
	}
	tpsort();
	for(int i=1;i<=n;i++)
		if(d[i]==1) dfs(i,i);
	for(int i=1;i<=n;i++)
		if(!d[i] && !b[i]) dfs(i,i);
	g[0]=1;
	for(int i=1;i<=n;i++) if(i==b[i])
	{
		for(int j=0;j<=n;j++) h[j]=0;
		if(d[i]==1)
		{
			get(i,0);
			for(int j=0;j<=s[i];j++) h[j]=dp[i][j];
		}
		else
		{
			for(int o=1;o<=n;o++) if(b[o]==i)
			{
				get(o,0);
				for(int j=0;j<=s[i];j++)
					add(h[j],dp[o][j]);
			}
			for(int j=0;j<=s[i];j++)
				h[j]=h[j]*zinv[s[i]-j]%MOD;
		}
		for(int j=n;j>=0;j--)
			for(int k=1;k<=s[i] && j+k<=n;k++)
				add(g[j+k],g[j]*h[k]%MOD*C(j+k,j));
	}
	for(int i=0;i<=n;i++)
		printf("%lld\n",g[i]);
}

CF516D Drazil and Morning Exercise

题目描述

点此看题

解法

首先考虑本题最基本的量 \(f(x)\) 怎么计算，连我都知道的套路是转化成树的直径问题，可以用反证法说明 \(f(x)=dis(x,y)\) 的 \(y\) 一定是直径的某一个端点。

然后好像没有什么好的思路，但是考虑如果不要求 \(S\) 的点联通，可以直接求出 \(f(x)\) 之后排序，然后枚举最小值，贴着限制能选就选即可。

现在要求 \(S\) 联通，我们可以去考察 \(f(x)\) 在树上的分布情况：他的最大值在直径端点取得，最小值在直径中心取得，并且变化较为均匀。可以以直径为根建树，那么树的从上到下 \(f(x)\) 一定是递增的。

实际上没有必要以直径为根建树，以最小的 \(f(x)\) 建树即可，这样还是能保证从上到下 \(f(x)\) 递增。然后我们类似地枚举最小值，剩下的点只能在子树中选取了，好的实现方式是每个点往上打树上差分标记（其实就是切换了主体）

时间复杂度 \(O(nq)\)，我个人的想法稍复杂一点，但很接近正解了。

#include 
#include 
#include 
#include 
#include 
using namespace std; 
const int M = 100005;
#define int long long
const int inf = 1e18;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,x,ans,rt,tot,f[M],da[M],db[M],d[M],c[M];
vector v,p;
struct edge{int v,c,next;}e[M<<1];
void dfs1(int u,int fa,int *d)
{
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		d[v]=d[u]+e[i].c;
		dfs1(v,u,d);
	}
}
void dfs2(int u,int fa)
{
	v.push_back(d[u]);p.push_back(u);
	c[p[lower_bound(v.begin(),v.end(),d[u]-x)-
	v.begin()-1]]--;c[u]=1;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs2(v,u);
		c[u]+=c[v];
	}
	ans=max(ans,c[u]);
	v.pop_back();p.pop_back();
}
signed main()
{
	n=read();
	for(int i=1;id[i]) rt=i;
	}
	m=read();
	v.push_back(-inf);p.push_back(0);
	while(m--)
	{
		x=read();ans=0;
		for(int i=0;i<=n;i++) c[i]=0;
		dfs2(rt,0);
		printf("%lld\n",ans);
	}
}

CF521D Shop

题目描述

点此看题

解法

我直接手切所以简记一下，最后发现做法和 \(\tt jiangly\) 聚聚一模一样。

操作很多样，首先我们可以做出一些简单的观察：

• 如果知道了要选哪些操作，那么操作的顺序一定是 赋值->加法->乘法
• 赋值操作只需要保留每个位置最大的即可。
• 因为赋值操作最先进行，所以可以看成加法。
• 因为加法一定是从大到小进行，所以可以看成乘法，也就是在原来的基础上增加了几倍。
• 因为答案的特殊形式，所以一定是乘上的值越大越好。

根据上面的观察，就不难设计出先把赋值转化成加法，然后把加法按照权值排序，计算转化成乘法之后的数乘。然后直接按权值从小到大选取乘法，但是注意这不是最终的顺序，还要按照种类排序，时间复杂度 \(O(n\log n)\)

总结

化归的思想，把不同操作统一成同种形式更有利于分析。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 100005;
#define db double
#define pb push_back
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,a[M];pair mx[M];
struct node{db v;int id,ty;};vector v,ad[M];
bool cmp1(node a,node b) {return a.v>b.v;}
bool cmp2(node a,node b) {return a.tya[i])//trans cover to add
			ad[i].pb
			(node{mx[i].first-a[i],mx[i].second,1});
		sort(ad[i].begin(),ad[i].end(),cmp1);
		db sum=a[i];
		for(auto x:ad[i])//trans add to mul
		{
			v.pb(node{(sum+x.v)/sum,x.id,x.ty});
			sum+=x.v;
		}
	}
	sort(v.begin(),v.end(),cmp1);
	while(v.size()>k) v.pop_back();
	sort(v.begin(),v.end(),cmp2);
	printf("%d\n",(int)v.size());
	for(auto x:v) printf("%d ",x.id);
	puts("");
}