发表更新Problem Solutions2 分钟读完 (大约308个字)

题解：CF628D Magic Numbers

题目

思路

首先可以看出这是一道数位dp。它的参数分为两个部分：是否magic和是否是 $m$ 的倍数。这两个部分其实都比较好处理：前者在dfs是判断即可（这里并不复杂，其实直接从高位开始推就行了，不用考虑奇偶位不一样问题…），后者记录一下当前$\mod m$ 的余数，最后再判断。最后，因为字符串不好减一（其实也可以减），所以需要特判一下左端点字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=2005,mod=1e9+7;

ll m,d;
string a,b;
ll dig[N];
ll len;

ll dp[N][N];

ll dfs(ll x,ll r,bool lim)
{
	if(x==len)
	{
		return r==0;
	}
	
	if(~dp[x][r]&&!lim)
	{
		return dp[x][r];
	}
	
	ll ret=0,up=lim?dig[x]:9;
	for(ll i=0;i<=up;i++)
	{
//		if(x==0&&i==0)
//		{
//			continue;
//		}
		if(x%2==0&&i!=d) //odd
		{
			ret=(ret+dfs(x+1,(r*10+i)%m,lim&&(i==up)))%mod;
		}
		if(x%2==1&&i==d) //even
		{
			ret=(ret+dfs(x+1,(r*10+i)%m,lim&&(i==up)))%mod;
		}
	}
	
	if(!lim)
	{
		dp[x][r]=ret;
	}
	return ret;
}

ll solve(string x)
{
	len=x.size();
	for(ll i=0;i<len;i++)
	{
		dig[i]=x[i]-'0';
	}
	return dfs(0,0,1);
}

bool check(string x)
{
	ll r=0; 
	for(ll i=0;i<len;i++)
	{
		if(i%2==0&&x[i]==d+'0')
		{
			return 0;
		}
		if(i%2==1&&x[i]!=d+'0')
		{
			return 0;
		} 
		r=(r*10+x[i]-'0')%m;
	}
	return r==0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	memset(dp,-1,sizeof dp);
	cin>>m>>d;
	cin>>a>>b;
	
	cout<<(solve(b)-solve(a)+check(a)+mod)%mod<<'\n';	
	
	return 0;
}

发表更新Problem Solutions3 分钟读完 (大约502个字)

题解：洛谷P2929 [USACO09HOL] Transmission Delay G

给出 $N (1 \leq N \leq 2000)$ 表示 $01$ 串的长度， $D(O \leq D < N)$ 表示 $0$ 或 $1$ 的最大偏离距离，一个长度为 $N$ 的 $01$ 串和一个整数 $K(1 \leq K \leq10^8)$，请计算传输延迟发生后一共有多少种可能的 $01$ 串，以及其中第 $K$ 大的串是什么。

洛谷

思路

首先这是一个分成两问的 DP 问题。通过原题，$01$ 串中两种位各自的数量不会发生变化，所以对于 DP 的状态，我们可以选用 $0$（或 $1$ ）的数量，即：$f[i][j]$ 表示 $i…n$ 为中使用 $j$ 个 $0$ 的方案数，这里倒着处理是为了求第二问。

另外，已知 $K(1 \leq K \leq10^8)$ ，如果 $f$ 数组的某一位超过 $10^8$ 那么它就会被取模，这会导致错误，因此我们开一个 $g$ 和 $f$ 的操作基本一致，但是如果某一位超过 $10^8$ ，就直接将其改为 $10^8+1$。

具体的转移还是比较直接的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

const int mod=100000000;

int n,d,k;
string s; 

int f[2005][2005],g[2005][2005]; //f:Question 1; g:Question 2
int cn0[2005],cn1[2005]; // 记录0和1的位置

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>d>>k>>s;
	s=" "+s;
	
	int l0=0,l1=0;
	for(int i=n;i>0;i--)
	{
		if(s[i]=='0')
		{
			cn0[++l0]=i;;
		}
		else
		{
			cn1[++l1]=i;;
		}
	}
	
	
	f[n+1][0]=g[n+1][0]=1;
	for(int i=n+1;i>1;i--)
	{
		for(int j=0;j<=l0;j++)
		{
			if(f[i][j])
			{
				if(j!=l0&&abs(i-1-cn0[j+1])<=d) //当前位选择0
				{
					if(!(j+l1!=n-i+1&&cn1[n-i+2-j]-i+2>d))
					{
						f[i-1][j+1]=(f[i-1][j+1]+f[i][j])%mod;
						g[i-1][j+1]=g[i-1][j+1]+g[i][j];
						g[i-1][j+1]=min(g[i-1][j+1],mod+1);
					}
				}
				
				if(j+l1!=n-i+1&&abs(i-1-cn1[n-i+2-j])<=d) //当前位选择1
				{
					if(!(j!=l0&&cn0[j+1]-i+2>d))
					{
						f[i-1][j]=(f[i-1][j]+f[i][j])%mod;
						g[i-1][j]=g[i-1][j]+g[i][j];
						g[i-1][j]=min(g[i-1][j],mod+1);
					}
				}
			}
//			;cout<<f[i-1][j+1]<<" "<<f[i-1][j]<<"\n";
		}
	}
	
	cout<<f[1][l0]<<"\n";
	
	for(int i=1;i<=n;i++)
	{
//		cout<<"\n"<<g[i+1][l0-1]<<" "<<k<<"\n";
		if(g[i+1][l0-1]>=k) // 如果当前位为0的方案多于k，就输出0，否则输出1
		{
			cout<<0;
			l0--;
		}
		else
		{
			cout<<1;
			k-=g[i+1][l0-1];
		}
	}
	
	return 0;
}
发表更新Problem Solutions11 分钟读完 (大约1576个字)

题解：[Apio2014]序列分割

其实下面的这个题是一个简化版本，原题要给dp数组开滚动数组，这个很简单就不写了；还有就是原题要输出方案，注释在代码里。

Luogu: [APIO2014] 序列分割

题面

题目描述

小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：

1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；

2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。

每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。

输入格式

输入第一行包含两个整数n，k（k+1≤n）。

第二行包含n个非负整数a1，a2，…，an（0≤ai≤10^4），表示一开始小H得到的序列。

输出格式

输出第一行包含一个整数，为小H可以得到的最大分数。

样例

样例输入
1
2
7 3 
4 1 3 4 0 2 3
样例输出
1
108

数据范围与提示

数据满足2≤n≤100000,1≤k≤min(n -1，200)。

注意，输入的a[i]里可能有0

解法

转移方程

$f[l][r][k]$: 将[l,r]这个区间，切k刀，所能得到的最大得分

$f[l][r][k]: \max_{i=1…n-1, j=0..k-1}f[l][i][j]+f[i+1][r][k-1-j]+(sum[r]-sum[i])*(sum[i]-sum[l-1])$

p.s. 当我们确定了最后切分出来的是哪些区间，我们的答案就是一样的

时间复杂度 $O(n^4)$

使用前缀和优化：

$f[m][i]$: 前 $a[1]..a[i]$ 分成m段，这前m段所贡献的最大得分和

记 $s[i]=\sum_{k=1..i}a[k]$

$f[m][i]=\max_{j=0..i-1} f[m-1][j]+(s[i]-s[j])*s[j]$

优化

法1：分离变量后使用单调队列

$s[i]$: 前缀和

$f[m][i]=\max_{j=0..i-1} f[m-1][j]+(s[i]-s[j])*s[j]$

从小到大枚举m，固定当前m，考虑到当前在计算f[m][i]:

假如有两个不同决策点j,k，尝试分析它们谁更优:

不妨设 j<k<i

对于当前的i，k比j更优等价于:

将j,k分到不等式一侧，i分到另一侧得：

$s[i]>(f[m-1][j]-f[m-1][k]-s[j]^2+s[k]^2)/(s[k]-s[j])$

记右式为 $g(j,k)$，左式为 $h(i)$

对于固定的m，有jg(j,k)$

三个决策点，易知，有 j1g(j2,h3)$ ，j2不会成为最优决策点，所以可以直接舍去

双端队列维护j[l]…j[r]从小到大，g函数也是从小到大的

对于任意 $l+1<=x<=r-1$ 有：$g(j[x-1],j[x])<g(j[x],j[x+1])$

1
2
3
4
5
6
7
8
9
10
//框架
for m=1..k
	queue q, l=r=1, q[1]=0
	for i=1..n
		while l+1<=r and h(i)>g(j[l],j[l+1])
			l++
		j[l]为决策点，更新dp[m][i]
		while l+1<=r and g(j[r-1],j[r])>g(j[r],i)
			r--
		j[++r]=i

然后我们可以解决本题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

int n,k;
int a[100005];
ll s[100005];

int q[100005];
ll dp[100005][205];
//int pre[100005][205];

double g(int x,int y,int z)
{
	if(s[x]==s[y])
	{
		return -1e18;
	}
    return (double)(s[x]*s[x]-s[y]*s[y]-dp[x][z-1]+dp[y][z-1])/(s[x]-s[y]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	
	for(int j=1;j<=k;j++)
	{
		int l=1,r=1;
		q[1]=0;
		for(int i=1;i<=n;i++)
		{
			while(l<r&&g(q[l],q[l+1],j)<=s[i])
			{
				l++;
			}
            
//			pre[i][j]=q[l];
			dp[i][j]=dp[q[l]][j-1]+s[q[l]]*(s[i]-s[q[l]]);
			
			while(l<r&&g(q[r-1],q[r],j)>=g(q[r],i,j))
			{
				r--;
			}
			q[++r]=i;
		}
		
	}
	
	cout<<dp[n][k]<<"\n";
//	for(int x=n,i=k;i>=1;i--)
//	{
//		x=pre[x][i];
//		cout<<x<<" ";
//	}
    
	return 0;
}
法2：斜率优化（aka 数形结合）

$f[m][i]=\max_{j=0..i-1}f[m-1][j]+(s[i]-s[j])*s[j]$

=$f[m-1][j]-s[j]s[j]+s[j]s[i]$

$A(j)=f[m-1][j]-s[j]*s[j]$

$B(j)=s[j]$

$C(i)=s[i]$

相当于我们有若干个选项 j，每个j提供一个一次函数 y[j]

$y[j]=A(j)+B(j)*x$

对于所有 $y[0]..y[i-1]$，找一个最大的作为 $f[m][i]$ 的答案

此时我们维护若干个一次函数，要支持插入和求最大值

对于本题的特殊的单调性，即每次插入的 $B(j)$, $C(i)$ （斜率和横坐标）都是递增的

于是，我们可以用双端队列来维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//框架
struct line
{
	int a,b;
} q[];

for m=1..k
	q.clear(),l=r=1,q[1]为j=0代表的直线
	for i=1..n
		while l+1<=r and c(i)>q[l],q[r]交点的x坐标
			l++
		line lnew=i //决策点所代表的直线A(i)+B(i)*x
		while l+1<=r and q[r-1],q[r]交点x坐标>q[r]和lnew的交点x坐标
			r--
		q[++r]=lnew

与刚刚的单调队列优化相比，$g(j1,j2)$ => 交点x坐标 $h(i)$ => $C(i)$

此处也可以用维护凸壳来实现

一般地，给定dp方程

$f[i]=\max_{j=1..i-1} W(i,j)$

通过恒等变形，使其变成：

$W(i,j)=\frac{A(i)-B(j)}{C(i)-D(j)}$

这使得我们联想到了斜率公式

$k=\frac{Δy}{Δx}=\frac{y2-y1}{x2-x1}$

这样可以询问到一个点连到现有的点的斜率最大

  • 如何维护下凸线？

    如果每次加入点的x坐标是单调增的：和上面两种方法几乎一样的单调队列写法即可维护下凸线

  • 如何处理查询？

    对于给定的查询点，凸壳上的点到这个查询点的斜率是先严格单调增，（然后可能会恒等不变一段），然后再严格单调减的。

    在凸壳上使用三分法

斜率优化代码会长成这样：（其实长得跟上面的没什么区别qwq）

1
2
3
4
5
6
7
8
9
10
double slope(int a,int b)
{
	ll x1=-s[a],y1=dp1[a]-s[a]*s[a];
	ll x2=-s[b],y2=dp1[b]-s[b]*s[b];
	if(x1==x2)
	{
		return -1e18;
	}
	return (double)(y2-y1)/(x2-x1);
}
法3：二分队列

考虑一个dp方程 $dp[i]=\max_{j=1..i-1} W(i,j)$

对于某两个 $j1<j2$，如果在某个 $i$ 处 $j2$ 比 $j1$ 优，那么在更大的 $i$ 处 $j2$ 也一定比 $j1$ 优。

即满足强决策单调性：一旦一个后来者超过你，他就会一直超过你，所以随着i增大，最优决策点也严格单调增

而本题满足 $h(i) > g(j1, j2)$ ，可以使用二分队列的方法进行优化

考虑：每个决策点j，是哪些i的最优决策点

对于每个 $j$，它成为最优决策点的 $i$ 要么不存在，要么一定是一段连续的区间，记为 $[l_j,r_j ]$

对于 $ j1<j2$，且 $[l{j1},r{j1} ]$ 和 $[l{j2},r{j2} ]$ 都不为空，那么有 $r{j1}<l{j2}$

所有这些 $ [l_j,r_j ] $ 构成了 $[1, n]$ 的一个划分

我们尝试维护当前[0,i-1]间的最优决策区间：

但是那些>=i的决策点，未来可能“抢走”当前某个j的 $[l_j,r_j]$ 的一部分，因此当前某个j的 $[l_j,r_j]$ ，只有可能变小，不可能再变大。计算i的最优决策点后，因为只需要计算i往后的，所以我们只需要保留构成[i,n]的划分的那些$[l_j,r_j]$

也就是我们将维护若干个三元组(j,l,r)

然后在队列里二分就可以找到切分点了

关注我

链接

分类

最新文章

归档

标签

Combinatorics1
Disjoint Set1
Dynamic Programming3
Euler's totient function1
Game Theory1
Graph Theory2
Monotonic queue1
Number theory1
Ordinary Generating Function1
Segment Tree4
Simulated Annealing1
Society1
Spanning Tree2
Teenagers1
Tree1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×