12月15日DP作业

[APIO2014]连珠线

考虑一组以 \(x\) 为中点的蓝边，有两种可能：

\[son[x]->x->fa[x]
\]

\[son[x]->x->son[x]
\]

其中若有两个儿子间连边的点不存在祖先关系，那么它们就无法被连接到一起

因此所有的儿子间连边的点一定在一条链上

因此，若以链的最低点为根，那么所有儿子间连边的点的情况可以归纳为 \(son[x]->x->fa[x]\) 的情况

换根 \(dp\) 即可

点击查看代码

#include<bits/stdc++.h>

using namespace std;

int n;

int ver[400005],ne[400005],head[200005],cnt,val[400005];

inline void link(int x,int y,int v){

	ver[++cnt]=y;

	ne[cnt]=head[x];

	head[x]=cnt;val[cnt]=v;

}

long long dp[2][200005],f[200005];

void dfs1(int x,int fi){

	dp[1][x]=f[x]=-1e18;

	for(int i=head[x];i;i=ne[i]){

		int u=ver[i];

		if(u==fi)continue;

		dfs1(u,x);

		long long tmp=max(dp[0][u],dp[0][u]+dp[1][u]+val[i]),tmp2=dp[0][u]+val[i]-tmp;

		if(tmp2>dp[1][x])f[x]=max(f[x],dp[1][x]);

		else f[x]=max(f[x],tmp2);

		dp[0][x]+=tmp;dp[1][x]=max(dp[1][x],tmp2);

	}

}

long long ans;

void dfs2(int x,int fi){

	ans=max(ans,dp[0][x]);

	for(int i=head[x];i;i=ne[i]){

		int u=ver[i];

		if(u==fi)continue;

		long long tmp=max(dp[0][u],dp[0][u]+dp[1][u]+val[i]),tmp2=dp[0][u]+val[i]-tmp;

		if(dp[1][x]==tmp2)dp[1][x]=f[x];

		dp[0][x]-=tmp;

		{

			long long tmp3=max(dp[0][x],dp[0][x]+dp[1][x]+val[i]),tmp4=dp[0][x]+val[i]-tmp3;

			dp[0][u]+=tmp3;

			if(tmp4>dp[1][u])f[u]=max(f[u],dp[1][u]);

			else f[u]=max(f[u],tmp4);

			dp[1][u]=max(dp[1][u],tmp4);

			dfs2(u,x);

		}

		dp[0][x]+=tmp;dp[1][x]=max(dp[1][x],tmp2);

	}

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<n;i++){

		int x,y,z;scanf("%d%d%d",&x,&y,&z);

		link(x,y,z);link(y,x,z);

	}

	dfs1(1,1);dfs2(1,1);

	printf("%lld",ans);

	return 0;

}

[ZJOI2017]仙人掌

对树加边，使每条边最多一个环上，等价于将若干条不相交的链覆盖到树上

对于每个点，枚举与它相连的边的所有匹配情况即可

点击查看代码

#include<bits/stdc++.h>

using namespace std;

int t;

int n,m;

int ver[5000005],ne[5000005],head[5000005],ct;

bool is;

inline void link(int x,int y){

	ver[++ct]=y;

	ne[ct]=head[x];

	head[x]=ct;

}

int dfn[5000005],low[5000005],cnt;

int stk[5000005],top,col[5000005],tot;

void tarjan(int x,int fi){

	dfn[x]=low[x]=++cnt;

	bool flag=0;stk[++top]=x;

	for(int i=head[x];i;i=ne[i]){

		int u=ver[i];

		if(u==fi)continue;

		if(!dfn[u]){

			tarjan(u,x);

			low[x]=min(low[x],low[u]);

			if(low[u]<dfn[x]){

				if(flag){is=0;return ;}

				flag=1;

			}

		}

		else {

			low[x]=min(low[x],dfn[u]);

			if(dfn[u]<dfn[x]){

				if(flag){is=0;return ;}

				flag=1;

			}

		}

	}

	if(dfn[x]==low[x]){

		col[x]=++tot;

		while(stk[top]!=x)col[stk[top--]]=tot;

		top--;

	}

}

long long dp[5000005],g[5000005];

const long long md=998244353;

bool vis[5000005];

void dfs(int x,int fi){

	dp[x]=1;vis[x]=1;

	int siz=0;

	for(int i=head[x];i;i=ne[i]){

		int u=ver[i];

		if(u==fi||col[u]==col[x])continue;

		dfs(u,x);siz++;

		dp[x]=dp[x]*dp[u]%md;

	}

	dp[x]=dp[x]*g[siz+(fi!=x)]%md;

//	cout<<x<<" "<<dp[x]<<" "<<siz+(fi!=x)<<endl;

}

int main(){

	g[0]=g[1]=1;

	for(int i=2;i<=5e6;i++)g[i]=(g[i-1]+g[i-2]*(i-1)%md)%md;

	scanf("%d",&t);

	while(t--){

		scanf("%d%d",&n,&m);

		for(int i=1;i<=n;i++)head[i]=0;ct=0;is=1;

		for(int i=1;i<=n;i++)vis[i]=0;cnt=0;tot=0;

		for(int i=1;i<=n;i++)dfn[i]=0;

		for(int i=1;i<=m;i++){

			int x,y;

			scanf("%d%d",&x,&y);

			link(x,y);link(y,x);

		}

		tarjan(1,1);

//		for(int i=1;i<=n;i++)cout<<col[i]<<" ";cout<<endl;

		if(!is){

			puts("0");

			continue;

		}

		long long ans=1;

		for(int i=1;i<=n;i++)if(!vis[i]){

			dfs(i,i);//cout<<i<<":\n";

			ans=ans*dp[i]%md;

		}

//		for(int i=1;i<=n;i++)cout<<dp[i]<<" ";

		printf("%lld\n",ans);

	}

	return 0;

}

[ZJOI2016]线段树加强版（小小猫咪）

期望乘以总方案数就是对所有方案求和

考虑暴力 \(dp\) ：令 \(f[v][i][l][r]\) 表示区间 \([l,r]\) 内的值小于 \(val[v]\) ，且 \(a[l-1],a[r+1]>val[v]\) 的方案数，再令：

\[pre(v,i,j)=\sum_{t=1}^{j}f[v][i][t][r]*(t-1)
\\
suf(v,i,j)=\sum_{t=j}^{n}f[v][i][l][t]*(n-t)
\]

有：

\[f[v][i][l][r]=f[v][i-1][l][r]*g(l,r)+pre(v,i-1,l-1)+suf(v,i-1,r+1)
\]

其中 \(g(l,r)=\frac{l*(l-1)}{2}+\frac{(n-r)*(n-r+1)}{2}+\frac{(r-l+1)*(r-l+2)}{2}\) 表示无用操作数

则有：

\[ans[i]=\sum_{i\in[l,r]}\sum_{v}(f[v][p][l][r]-f[v-1][p][l][r])*val[v]
\]

拆开，有：

\[ans[i]=\sum_{i\in[l,r]}\sum_{v}f[v][p][l][r]*val[v]-\sum_{i\in[l,r]}\sum_{v}f[v-1][p][l][r]*val[v]
\\

=\sum_{i\in[l,r]}\sum_{v}f[v][p][l][r]*(val[v]-val[v+1])
\]

因此，可以直接设 \(dp[i][l][r]=\sum_{v}f[v][i][l][r]\)

转移方程：

\[pre(i,j)=\sum_{t=1}^{j}dp[i][t][r]*(t-1)
\\
suf(i,j)=\sum_{t=j}^{n}dp[i][l][t]*(n-t)
\\
dp[i][l][r]=dp[i-1][l][r]*g(l,r)+pre(i-1,l-1)+suf(i-1,r+1)

进而时间复杂度 \(O(n^4)->O(n^3)\)

点击查看代码

#include<bits/stdc++.h>

using namespace std;

int n,q;

int a[405];

long long dp[2][405][405],pre[405][405],suf[405][405];

long long g[405][405],ans[405];

const long long md=1e9+7;

int main(){

	scanf("%d%d",&n,&q);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	a[0]=a[n+1]=1e9;

	for(int l=1;l<=n;l++){

		int mx=a[l];

		for(int r=l;r<=n;r++){

			mx=max(mx,a[r]);

			if(mx<=a[l-1]&&mx<=a[r+1])dp[0][l][r]=(mx-(l==1&&r==n?0:min(a[l-1],a[r+1])))%md;

			g[l][r]=(l*(l-1)/2+(n-r)*(n-r+1)/2+(r-l+1)*(r-l+2)/2)%md;

		}

	}

	for(int t=1;t<=q;t++){

		int lst=((t-1)&1),nxt=(t&1);

		for(int r=1;r<=n;r++){

			for(int i=1;i<=r;i++)pre[i][r]=(pre[i-1][r]+dp[lst][i][r]*(i-1))%md;

		}

		for(int l=1;l<=n;l++){

			for(int i=n;i>=l;i--)suf[l][i]=(suf[l][i+1]+dp[lst][l][i]*(n-i))%md;

		}

		for(int l=1;l<=n;l++){

			for(int r=l;r<=n;r++){

				dp[nxt][l][r]=(dp[lst][l][r]*g[l][r]+pre[l-1][r]+suf[l][r+1])%md;

			}

		}

	}

	for(int i=1;i<=n;i++){

		for(int l=1;l<=i;l++){

			for(int r=i;r<=n;r++)ans[i]=(ans[i]+dp[q&1][l][r])%md;

		}

	}

	for(int i=1;i<=n;i++)printf("%lld ",(ans[i]+md)%md);

	return 0;

}

星际旅行

点击查看代码

创造题目

点击查看代码

后宫

点击查看代码

分组

点击查看代码

攻城机变

点击查看代码

基因改造问题

拼接 \(SAM\) 即可

点击查看代码

#include<bits/stdc++.h>

using namespace std;

int T;

int rt,cnt,lst,son[26][2000005],l[2000005],fa[2000005];

inline void insert(int c){

	int i=lst,x=++cnt;l[x]=l[lst]+1;lst=x;

	while(i&&!son[c][i])son[c][i]=x,i=fa[i];

	if(!i)fa[x]=rt;

	else{

		int j=son[c][i];

		if(l[i]+1==l[j])fa[x]=j;

		else {

			int e=++cnt;l[e]=l[i]+1;

			for(int t=0;t<26;t++)son[t][e]=son[t][j];

			fa[e]=fa[j];fa[x]=fa[j]=e;

			while(i&&son[c][i]==j)son[c][i]=e,i=fa[i];

		}

	}

}

char s[2000005];

int pre,ed,ans,op;

bool vis[2000005];

void dfs1(int x){

	if(op)printf("%s\n",s+1);ans++;

	bool is=0;

	for(int i=0;i<26;i++){

		if(!son[i][x])continue;

		s[++ed]=i+'A';

		dfs1(son[i][x]);

		s[ed--]=0;

	}

}

long long dp[2000005];

const long long md=1e9+7;

void dfs2(int x){

	if(dp[x])return ;dp[x]=1;

	for(int i=0;i<26;i++){

		if(!son[i][x])continue;

		dfs2(son[i][x]);

		dp[x]=(dp[x]+dp[son[i][x]])%md;

	}ans=dp[x];

}

int main(){

	scanf("%d",&T);

	for(int t=1;t<=T;t++){

		scanf("%s",s+1);

		int n=strlen(s+1);rt=++cnt;lst=cnt;vis[cnt]=1;

		for(int i=1;i<=n;i++)insert(s[i]-'A');

	}

	for(int i=cnt;i;i--){

		for(int j=0;j<26;j++)if(!son[j][i])son[j][i]=son[j][pre];

		if(vis[i])pre=i;

	}

	memset(s,0,sizeof(s));

	scanf("%d",&op);

	if(op)dfs1(1);else dfs2(1);

	printf("%d",ans);

	return 0;

}

UR #1 外星人

点击查看代码

庆典

点击查看代码

小猫咪

直接从 \(1\sim n\) 顺次填写 { \(a\) } 的第 \(i\) 位

设 \(dp[i][j][k]\) 表示，已经填完了 \(1\sim i\) 这些位置，并且目前已经确定在 \(1\sim i\) 中位置上的，值在 \(1\sim i\) 的数字有 \(j\) 个，这 \(j\) 个已经被确定的位置上的 \(\max\) 和为 \(k\) 的方案数

转移时枚举 \(i+1\) 这个数值被填到了哪里，以及在最终的排列里 \(i+1\) 这个位置上的值是什么即可

点击查看代码

#include<bits/stdc++.h>

using namespace std;

int n,m;

long long dp[2][55][2505],ans;

const long long md=998244353;

int main(){

	scanf("%d%d",&n,&m);

	dp[0][0][0]=1;

	for(int i=0,u=1;i<n;i++,u^=1){

		for(int j=0;j<=i;j++){

			for(int k=0;k<=i*i;k++){

				long long &t=dp[u^1][j][k];

				if(!t)continue;

				dp[u][j+2][k+2*(i+1)]=(dp[u][j+2][k+2*(i+1)]+1ll*t*(i-j)%md*(i-j)%md)%md;

				dp[u][j+1][k+i+1]=(dp[u][j+1][k+i+1]+1ll*t*(i-j)%md*2%md+t)%md;

				dp[u][j][k]=(dp[u][j][k]+t)%md;t=0;

			}

		}

	}

	for(int i=m;i<=n*n;i++)ans=(ans+dp[n&1][n][i])%md;

	for(int i=1;i<=n;i++)ans=1ll*ans*i%md;

	printf("%lld",ans);

	return 0;

}

基因改造计划

点击查看代码

```cpp

</details>

### [求余数]()

<details>

<summary>点击查看代码</summary>

```cpp

摩天大楼

点击查看代码

巴特西

12月15日DP作业

[APIO2014]连珠线

[ZJOI2017]仙人掌

[ZJOI2016]线段树加强版（小小猫咪）

星际旅行

创造题目

后宫

分组

攻城机变

基因改造问题

UR #1 外星人

庆典

小猫咪

基因改造计划

摩天大楼

最新文章

热门文章