CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » wangzai_milk » codeforces_dp_tag_随便做
2020-2021:teams:wangzai_milk:codeforces_dp_tag_随便做

目录

codeforces DP tag 随便做

1380F

题意

定义一种加法，没有进位，进行的方式就是按位做加法，然后把结果落下来。给定一个结果，有m个操作，每个操作会把这个结果的某一位换成另一个数字，每次操作都询问有多少组加数可以得出这个结果。

题解

我们设$dp_i$为到第$i$位结果有多少种加数组合，显然有转移方程$dp_i = dp_{i-1}\times (t_i+1) + [10\leq t_{i-1}\times 10 + t_i\leq 18]dp_{i-2}\times (19 - t_{i-1}\times 10 - t_i)$

这个东西显然可以用矩阵乘法转移，所以对于修改的操作上矩阵乘法线段树就可以。

代码

点击以显示 ⇲

点击以隐藏 ⇱ 

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
const int mod = 998244353;
typedef long long ll;
 
struct Matrix {
	int a[2][2];
	Matrix() {a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}
};
Matrix operator *(Matrix x,Matrix y) {
	Matrix ans;
	for (int i = 0;i<= 1;i++)
		for (int j = 0;j<= 1;j++)
			for (int k = 0;k<= 1;k++)
				(ans.a[i][j]+=(ll)x.a[i][k]*y.a[k][j]%mod)%=mod;
	return ans;
}
Matrix st[N],tr[N<<2],E;
char s[N];
int c[N];
int lth,n,m;
void Build(int p,int l,int r) {
	if (l==r) {tr[p] = st[l];return;}
	int mid = (l+r)>>1;
	Build(p<<1,l,mid);
	Build(p<<1|1,mid+1,r);
	tr[p] = tr[p<<1]*tr[p<<1|1];
}
void Update(int p,int l,int r,int a,Matrix b) {
	if (l==r) {
		tr[p] = b;
		return;
	}
	int mid = (l+r)>>1;
	if (a <= mid) Update(p<<1,l,mid,a,b);
	else Update(p<<1|1,mid+1,r,a,b);
	tr[p] = tr[p<<1]*tr[p<<1|1];
}
Matrix Getans(int p,int l,int r,int a,int b) {
	if (l>=a && r<=b)return tr[p];
	Matrix ans = E;
	int mid = (l+r)>>1;
	if (a <= mid)ans = ans*Getans(p<<1,l,mid,a,b);
	if (b > mid)ans = ans*Getans(p<<1|1,mid+1,r,a,b);
	return ans;
}
int main()
{
	scanf("%d%d%s",&n,&m,s+1);
	//lth = 1;
	//while (lth <= n)lth <<= 1;
	for (int i = 1;s[i];i++)
		c[i] = s[i]-'0';
	E.a[0][0] = E.a[1][1] = 1;
	st[0] = E;
	for (int i = 1;i<= n;i++)
	{
		int tmp = c[i]+c[i-1]*10;
		Matrix tmpm;
		tmpm.a[0][0] = 0;tmpm.a[1][0] = 1;
		tmpm.a[0][1] = (i > 1 && tmp >= 10 && tmp <= 18 ? 19-tmp : 0);
		tmpm.a[1][1] = c[i] + 1;
		st[i] = tmpm;
	}
	Build(1,0,n);
	while (m--) {
		int x,y;
		scanf("%d%d",&x,&y);
		c[x] = y;
		int tmp1 = c[x]+c[x-1]*10;
		int tmp2 = c[x+1]+c[x]*10;
		st[x].a[0][1] = (x > 1 && 10 <= tmp1 && tmp1 <= 18 ? 19-tmp1 : 0);
		st[x].a[1][1] = c[x]+1;
		Update(1,0,n,x,st[x]);
		if (x < n) {
			st[x+1].a[0][1] = (10 <= tmp2 && tmp2 <= 18 ? 19-tmp2 : 0);
			Update(1,0,n,x+1,st[x+1]);
		}
		Matrix ans = Getans(1,0,n,1,n);
		printf("%d\n",ans.a[1][1]);
	}
	return 0;
}


1383E

题意

给定一个01串，对01串进行操作，操作定义为选择两个相邻的字符，保留较大的那个，删去另一个，问经过若干次操作可以得到多少种本质不同的01串。

题解

我们假设我们经过若干次操作获得了一个结果t，我们应该怎样确定是否能得到这个t呢。我们假设现在已经用了s的前i位，匹配到了t的前j位，如果t的第j+1位时1，那么我们找出s后面第一个1匹配上即可。如果是0，我们需要考虑t里有一段多长的连续的0，假设是k为，那么就需要匹配一段长度为k的0。所以我们现在知道可以贪心构造01串。

所以我们按照这个贪心的思想进行dp，$dp_i$表示有多少个串t能够贪心匹配到s的第i位，按照原方法考虑01两种情况进行转移即可。

代码

点击以显示 ⇲

点击以隐藏 ⇱ 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
typedef long long ll;
 
int f[N],dst[N],pos[N],nxt1[N],nxtd[N];
char str[N];
int main()
{
	scanf("%s",str+1);
	int n = strlen(str+1);
	int st = 0;
	for (int i = 1;i<= n;i++)
		if (str[i]=='1')
			{st = i;break;}
	if (!st)printf("%d\n",n);
	else {
		for (int i = 1;i<= n;i++)
			if (str[i]=='0')
				dst[i] = dst[i-1]+1;
		for (int i = 0;i<= n+1;i++)pos[i] = n+1;
		for (int i = n;i>=1;i--) {
			nxt1[i] = pos[0];
			nxtd[i] = pos[dst[i]+1];
			pos[dst[i]] = i;
		}
		f[st] = st;
		for (int i = st;i < n;i++) {
			if (nxt1[i]!=n+1)(f[nxt1[i]]+=f[i])%=mod;
			if (nxtd[i]!=n+1)(f[nxtd[i]]+=f[i])%=mod;
		}
		int ans = 0;
		for (int i = st;i<=n;i++)
			if (dst[i] <= dst[n])
				(ans+=f[i])%=mod;
		printf("%d\n",ans);
	} 
	return 0;
}


1389F

题意

给定n个线段，每个线段都有一个颜色，总共有两种颜色。

我们定义一种坏的线段对为两个线段颜色不相同同时有相交的部分。

问最多可以选择多少个线段同时两两不为坏的线段对。

题解

这个题目的dp解法应该是先把线段按照右端点排序，设状态$dp_{i,j}$，代表结束位置为i，颜色为j的情况最多能选多少个线段，然后靠线段树转移即可。但是除了dp解法之外还有一种更简单的做法，我们可以考虑把线段看做点，然后在坏的线段对之间连一条边，这样我们去求最大独立集就是这道题的答案。

而关于这道题的匹配，只需要按照右端点排序，选取预期相交的r最小的不同颜色线段匹配即可得到最大匹配，n-最大匹配就是最大独立集了。

代码

点击以显示 ⇲

点击以隐藏 ⇱ 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
typedef long long ll;
 
int f[N],dst[N],pos[N],nxt1[N],nxtd[N];
char str[N];
int main()
{
	scanf("%s",str+1);
	int n = strlen(str+1);
	int st = 0;
	for (int i = 1;i<= n;i++)
		if (str[i]=='1')
			{st = i;break;}
	if (!st)printf("%d\n",n);
	else {
		for (int i = 1;i<= n;i++)
			if (str[i]=='0')
				dst[i] = dst[i-1]+1;
		for (int i = 0;i<= n+1;i++)pos[i] = n+1;
		for (int i = n;i>=1;i--) {
			nxt1[i] = pos[0];
			nxtd[i] = pos[dst[i]+1];
			pos[dst[i]] = i;
		}
		f[st] = st;
		for (int i = st;i < n;i++) {
			if (nxt1[i]!=n+1)(f[nxt1[i]]+=f[i])%=mod;
			if (nxtd[i]!=n+1)(f[nxtd[i]]+=f[i])%=mod;
		}
		int ans = 0;
		for (int i = st;i<=n;i++)
			if (dst[i] <= dst[n])
				(ans+=f[i])%=mod;
		printf("%d\n",ans);
	} 
	return 0;
}


1394D

题意

给定一颗树，树上每个点都有一个高度值$h_i$和一个价值$t_i$，现在要求选若干条链，链上的点高度值单调，使得每一条边都仅被选择一次，问怎样选择能使选择的链的价值和最小（链的价值为链上所有点价值之和）。

题解

考虑对于树上的一条边，如果边两侧的高度不同，那么这条边就已经有了方向，从高度低的一侧指向高度高的一侧，如果所有的边都已知方向，那么这个问题的答案就是$\sum min(ind_i,outd_i)\times t_i$。那么要解决的就是不知道方向的边。我们考虑dp，设$f_u$为$fa_u\rightarrow u$时删去点的最大值，$g_u$为$u\rightarrow fa_u$时删去点的最大值，最后答案就是$\sum t_i\times 2$减去每一颗高度相同边组成的树的根节点的f

代码

点击以显示 ⇲

点击以隐藏 ⇱ 

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
typedef long long ll;
struct E {
	int nxt,to;
}e[N<<1];
int head[N],tot;
void add(int x,int y) {
	e[++tot].nxt = head[x];head[x] = tot;e[tot].to = y;
	e[++tot].nxt = head[y];head[y] = tot;e[tot].to = x;
}
int ind[N],outd[N],h[N],t[N];
ll f[N],g[N],stk[N];
bool vis[N];
bool cmp(const ll &a,const ll &b) {return a > b;}
void dfs(int x,int fa) {
	vis[x] = true;
	for (int i = head[x];i;i=e[i].nxt)
		if (e[i].to!=fa)
			dfs(e[i].to,x);
	int top = 0;
	ll nowans = 0;
	for (int i = head[x];i;i=e[i].nxt)
		if(e[i].to!=fa) {
			int y = e[i].to;
			nowans+=g[y];
			stk[++top] = f[y]-g[y];
		}
	sort(stk+1,stk+top+1,cmp);
	for (int i = 0;i<= top;i++) {
		nowans+=stk[i];
		if (fa != 0) {
			f[x] = max(f[x],1ll*min(ind[x]+1+top-i,outd[x]+i)*t[x]+nowans);
			g[x] = max(g[x],1ll*min(ind[x]+top-i,outd[x]+1+i)*t[x]+nowans);
		} else {
			f[x] = max(f[x],1ll*min(ind[x]+top-i,outd[x]+i)*t[x]+nowans);
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for (int i = 1;i<= n;i++)scanf("%d",&t[i]);
	for (int i = 1;i<= n;i++)scanf("%d",&h[i]);
	int x,y;
	ll ans = 0;
	for (int i = 1;i < n;i++) {
		scanf("%d%d",&x,&y);
		if (h[x]==h[y])add(x,y);
		else {
			if (h[x] > h[y])outd[x]++,ind[y]++;
			else outd[y]++,ind[x]++;
		}
		ans+=t[x]+t[y];
	}
	for (int i = 1;i<= n;i++)
		if (!vis[i])
		{
			dfs(i,0);
			ans-=f[i];
		}
	printf("%lld\n",ans);
	return 0;
}


1398F

题意

给定一个长度为n的字符串，里面有01和?三种字符，0代表a赢了一局游戏，1代表b赢了一局游戏，?代表不知道这局游戏的结果，现在我们定义x度游戏为两个人对决，有一个人赢了x轮游戏就结束，现在问对于$x=1,2…n$，他们最多能举行多少轮游戏。

题解

我们设$dp_i$为到第i局最多能进行$dp_i$次x轮游戏，我们知道转移只需要枚举上一次结束的位置，然后判断上一次位置到当前位置之间0和1个数较多的那一个加上问号的个数是否大于等于x就行，如果是就在上一次结束的基础上加一。这个东西可以转换为一个贪心，然后用预处理加速，最后算一下复杂度是$O(nlogn)$的。

代码

点击以显示 ⇲

点击以隐藏 ⇱ 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int pre[N][2];
char str[N];
int a[N],n;
int main()
{
	scanf("%d",&n);
	scanf("%s",str+1);
	for (int i = 1;i<= n;i++) 
		a[i] = str[i]=='?'?2:str[i]-'0';
	for (int i = 1;i<= n;i++) {
		pre[i][0] = pre[i-1][0];
		pre[i][1] = pre[i-1][1];
		if (a[i]!=2)pre[i][a[i]] = i;
	}
	for (int x = 1;x <= n;x++) {
		int l = 1,ans = 0;
		while (l+x-1<=n) {
			int r = l+x-1;
			if (pre[r][0] == pre[l-1][0] || pre[r][1] == pre[l-1][1]) {
				ans++;
				l = r+1;
			} else {
				l = min(pre[r][1],pre[r][0])+1;
			}
		}
		printf("%d ",ans);
	}
	return 0;
}
2020-2021/teams/wangzai_milk/codeforces_dp_tag_随便做.txt · 最后更改: 2020/08/21 11:23 由 infinity37

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3