bef-> NO.30

Veröffentlicht am

P1182 数列分段Section II

题目描述

对于给定的一个长度为N的正整数数列A-iA−i，现要将其分成M(M≤N)M(M≤N)段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列4 2 4 5 142451要分成33段

将其如下分段：

[4 2][4 5][1][42][45][1]

第一段和为66，第22段和为99，第33段和为11，和最大值为99。

将其如下分段：

[4][2 4][5 1][4][24][51]

第一段和为44，第22段和为66，第33段和为66，和最大值为66。

并且无论如何分段，最大值不会小于66。

所以可以得到要将数列4 2 4 5 142451要分成33段，每段和的最大值最小为66。

输入输出格式

输入格式：

第11行包含两个正整数N，M。

第22行包含NN个空格隔开的非负整数A_iAi，含义如题目所述。

输出格式：

一个正整数，即每段和最大值最小为多少。

输入输出样例

输入样例#1：

1
2
5 3
4 2 4 5 1

输出样例#1：

1
6

说明

对于20\%20%的数据，有N≤10N≤10；

对于40\%40%的数据，有N≤1000N≤1000；

对于100\%100%的数据，有N≤100000,M≤N, A_iN≤100000,M≤N,Ai之和不超过10^9。

题解

二分答案+贪心

这道题由于满足答案可行性单调，可以进行二分答案。

对于二分的答案判断可以用贪心策略：每个数尽量加到一段里，不够了在用一段新的。

正确性：每一个数总要被分进一组，没组权重相等，与其多开一个，还不如尽量放入以前的对吧。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define maxRange 2000000000
int A[maxn] , n , ans , m;
bool check(int cur){
	int now = 0 , cnt = 1 , ans = 0;
	for(int i = 1 ; i <= n; ++i){
		if(now + A[i] <= cur)	now += A[i];
		else if(A[i] > cur)		return false;
		else ++cnt , now = 0 , now += A[i];
		if(cnt > m)	return false;
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&A[i]);
	int l = 0 , r = maxRange;
	while(l <= r){
		int mid = l + r >> 1;
		if(check(mid))	ans = mid , r = mid - 1;
		else l = mid + 1;
	}
	printf("%d",ans);
	
}

[ZJOI2008]生日聚会

题目描述

今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：

对于任意连续的一段，男孩与女孩的数目之差不超过k。

很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考这个问题……

假设参加party的人中共有n个男孩与m个女孩，你是否能解答Susie和hidadz的疑问呢？由于这个数目可能很多，他们只想知道这个数目除以12345678的余数。

输入输出格式

输入格式：

输入文件party.in仅包含一行共3个整数，分别为男孩数目n, 女孩数目m, 常数k。

输出格式：

输出文件party.out应包含一行，为题中要求的答案。

输入输出样例

输入样例#1：

1
1 2 1

输出样例#1：

1
1

说明

对于30%的数据，n , m ≤ 20；

对于100%的数据, n , m ≤ 150，k ≤ 20。

题解

似乎没想到状态。。。其实状态还是听套路的。

由于我们要时刻知道当前状态代表的方案数中最大的差是多少，假如我们只设一维表示男生女生的差最大是多少，不一定女生和男生的差也最大。所以我们就再加一维变成四维状态。

表示前i个男生，j个女生，男女最大差为k，女男最大差为p

就很好转移了。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map>
#define maxn 155
#define maxk 25
#define mod 12345678
#define max(a,b) (a) > (b) ? (a) : (b)
int f[maxn][maxn][maxk][maxk] , n , m , k;
std::map<int,int> dp[maxn][maxn];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	f[0][0][0][0] = 1;
	for(int i = 0 ; i <= n ; ++i)
		for(int j = 0 ; j <= m ; ++j)
			for(int t = 0 ; t <= k ; ++t)
				for(int p = 0 ; p <= k ; ++p){
					(f[i+1][j][t+1][max(p-1,0)] += f[i][j][t][p]) %= mod;
					(f[i][j+1][max(t-1,0)][p+1] += f[i][j][t][p]) %= mod;
				}
	int ans = 0;
	for(int i = 0 ; i <= k ; ++i)
		for(int j = 0 ; j <= k ; ++j)
			(ans += f[n][m][i][j]) %= mod;
	printf("%d",ans);

}

[POI2012]HUR-Warehouse Store

题目描述

n天。第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。

如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。

输入输出格式

输入格式：

第一行包含一个整数n，表示有n天。

第二行有n个整数ai，表示第i天上午进货a件商品。

第三行包含n个整数bi，表示在第i天中午有顾客来买b件商品。

输出格式：

第一行一个整数，表示最多能满足几天中顾客的需求。

第二行输出满足这么哪些天顾客的需求。

输入输出样例

输入样例#1：

1
2
3
6
2 2 1 2 1 0
1 2 2 3 4 4

输出样例#1：

1
2
3
1 2 4

说明

对于100%的数据，

题解

又一次想出贪心题233.

这个题是一个堆贪心。

最本质的是每个人权值均相同，所以后面的人需求小于前面的人且货不够的时候，我们优先满足他，这样使得存货最大化对后面一定不会更劣，满足了贪心的无后效性。而当前能满足则尽量满足，假设满足他不是一个最优全局决策而只是当前最优，这种策略也能保证后面出现可以更优情况时调整到最优。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#define maxn 250005
#define mp(x,y) std::make_pair((x),(y))
#define pii std::pair<int,int>
std::priority_queue<pii> q;
int n , p[maxn] , r[maxn] , ans;
int main(){
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&r[i]);
	long long sum = 0;
	for(int i = 1 ; i <= n ; ++i){
		sum += p[i];
		if(q.empty()){
			if(sum < r[i])	continue;
			else if(sum >= r[i]){
				sum -= r[i];
				++ ans;
				q.push(mp(r[i],i));
				continue;
			}
		}
		else{
			int k = q.top().first;
			if(k > r[i] && r[i] > sum){
				q.pop();
				sum += k;
				sum -= r[i];
				q.push(mp(r[i],i));
			}
			else if(r[i] <= sum){
				++ans;
				sum -= r[i];
				q.push(mp(r[i],i));
			}
		}

	}
	printf("%d",ans);
	putchar(10);
	while(!q.empty())
	{
		printf("%d ",q.top().second);
		q.pop();
	}

}

BFS剩余类

解决这样一个问题：

给定k的范围，请问有多少组非负整数解？

大概是一种建图思想，就是把余数分类建点，然后用最短路求解，重点是这种做法的原理。

假设我们取A中一个（一般取最小，原因后面说）记为

假设我们找到一个k，k在模

意义下和余数r同余，使得

同样成立。

我们要做的就是求出那个t，即可根据余数快速统计。

我们可以试着枚举那个k，每次试着加上

这么做恭喜你前面白分析了。

我们考虑最短路模型，将

建长度为

的有向边，即可将代价最小转换成最短路。

想了半天，确实是道好题。

[国家集训队]墨墨的等式

题目描述

墨墨突然对等式很感兴趣，他正在研究

存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

输入输出格式

输入格式：

输入的第一行包含3个正整数，分别表示N、

、

分别表示数列的长度、B的下界、B的上界。

输入的第二行包含N个整数，即数列

的值。

输出格式：

输出一个整数，表示有多少b可以使等式存在非负整数解。

输入输出样例

输入样例：

1
2
2 5 10
3 5

输出样例#1：

1
5

说明

对于100%的数据，

题解

分析如上，用上述方法的时间复杂度不是很好计算（有向边数量并不确定），但是对于题目要求没有问题。

L，R变量的意义相当于在枚举的余数下

其给定的t为多少。

Code：

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
#include <cstdio>
#include <cstdlib>
#include<algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 500005
#define mp(x,y) std::make_pair((x),(y))
#define pii std::pair<LL,int> 
#define LL long long
const LL INF = 9187201950435737471;
int n , p[maxn];
LL bmin , bmax , d[maxn] , ans;
bool vis[maxn];
inline void SPDIJ(int s)
{
	std::priority_queue<pii , std::vector<pii> , std::greater<pii> > q;
	std::memset(d,0x7f,sizeof(d));
	std::memset(vis,false,sizeof(vis));
	d[s] = 0; // s = 0
	q.push(mp(d[s],s));
	while(!q.empty())
	{
		int k = q.top().second;
		q.pop();
		if(vis[k])	continue;
		vis[k] = true;
		for(int i = 2 ; i <= n ; ++i){
			int v = (k + p[i]) % p[1];
			if(d[k] + p[i] < d[v]){
				d[v] = d[k] + p[i];
				q.push(mp(d[v],v));
			}
		}
	}
}
int main(){
	scanf("%d%lld%lld",&n,&bmin,&bmax);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]);
	std::sort(p+1,p+n+1);
	SPDIJ(0);
	for(int i = 0 ; i < p[1] ; ++i){
		if(d[i] != INF){
			d[i] -= i , d[i] /= p[1];
			LL L = (bmin - i - 1) / p[1] , R = (bmax - i) / p[1] ; // caution : [L,R]
			LL totL = L - d[i] + 1 , totR = R - d[i] + 1; //do not remember itself
			totL = std::max(1LL*0,totL) , totR = std::max(1LL*0 , totR);
			ans += totR - totL;
		}
	}
	printf("%lld",ans);
}

[USACO12MAR]园林绿化Landscaping

题目描述

Farmer John is building a nicely-landscaped garden, and needs to move a large amount of dirt in the process.

The garden consists of a sequence of N flowerbeds (1 <= N <= 100), where flowerbed i initially contains A_i units of dirt. Farmer John would like to re-landscape the garden so that each flowerbed i instead contains B_i units of dirt. The A_i’s and B_i’s are all integers in the range 0..10.

To landscape the garden, Farmer John has several options: he can purchase one unit of dirt and place it in a flowerbed of his choice for XX. He can remove one unit of dirt from a flowerbed of his choice and have it shipped away for YY. He can also transport one unit of dirt from flowerbed i to flowerbed j at a cost of ZZtimes |i-j|. Please compute the minimum total cost for Farmer John to complete his landscaping project. 有n块土地，每块有A[i]泥土，现把其改造成B[i]泥土，有3种操作：(1)花费X向任意土地增加1泥土；(2)花费Y向任意土地减少1泥土；(3)花费Z*|i-j|把土地i的1泥土运到土地j。问最小花费是多少。

输入输出格式

输入格式：

* Line 1: Space-separated integers N, X, Y, and Z (0 <= X, Y, Z <= 1000).

* Lines 2..1+N: Line i+1 contains the space-separated integers A_i and B_i.

输出格式：

* Line 1: A single integer giving the minimum cost for Farmer John’s landscaping project.

输入输出样例

输入样例#1：

1
2
3
4
5
4 100 200 1 
1 4 
2 3 
3 2 
4 0

输出样例#1：

1
210

说明

There are 4 flowerbeds in a row, initially with 1, 2, 3, and 4 units of dirt. Farmer John wishes to transform them so they have 4, 3, 2, and 0 units of dirt, respectively. The costs for adding, removing, and transporting dirt are 100, 200, and 1.

One unit of dirt must be removed (from flowerbed #4), at a cost of 200. The remaining dirt can be moved at a cost of 10 (3 units from flowerbed #4 to flowerbed #1, 1 unit from flowerbed #3 to flowerbed #2).

题解

这是一道好神的贪心啊。（dp好像也能做），D1T2难度偏上，有概率D1T3。

看到那个10其实应该想到拆成一件一件的，然而还是没有想到。

之后的堆贪心倒不是非常的难，只不过想出前缀和的形式压进堆然后取出来和当前元素做差还是有些难度。

我们来分析一波。

假设当前是土少了，要加上或从别的地方运。

从别的地方运上一份土，我们应该运一份最优的（显然由于运输费用给定都相同，且前后路长差与代价线性）。

假设没有，我们只能买一份。

这就是这道题的大致思路。它为什么正确呢？

考虑到当前我们没有选择最优的决策，后面选择的决策并不会因此更优，没了，不会严格证明

显然的无后效性和最优子结构

由于每份土地不能重复用（当然你可以动态调整不断地运，注意费用即可），因此用堆维护。

用堆维护什么值呢？

为什么是这个奇奇怪怪的东西呢？主要是考虑一种标准，使得取出的元素能快速和当前元素合并价值。

显然从前面取土是

这样上面维护的那个元素形式就不是很难理解了吧（虽然有点难想？）

还有一点就是，假设我们拿了一块土地，并不意味着这块土地一定最优了，因此要把它的代价压进另一个堆使得后面可能会调用。

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#define maxn 100005
int n , x , y , z , ans;
std::priority_queue<int> q1 , q2;
int main()
{
	scanf("%d%d%d%d",&n,&x,&y,&z);
	int fr , to;
	for(int k = 1 ; k <= n ; ++k){
		scanf("%d%d",&fr,&to);
		if(fr < to){
			for(int i = 1 ; i <= to - fr ; ++i){
				if(q1.empty() || k * z - q1.top() > x){
					ans += x;
					q2.push(k * z + x);
				}
				else{
					int g = q1.top();
					ans += k * z - g;
					q1.pop();
					q2.push(k * z + k * z - g);
				}
			}
		}
		else {
			for(int i = 1 ; i <= fr - to ; ++i){
				if(q2.empty() || k * z - q2.top() > y){
					ans += y;
					q1.push(k * z + y);
				}
				else {
					int g = q2.top();
					ans += k * z - g;
					q2.pop();
					q1.push(k * z + k * z - g);
				}
			}
		}
	}
	printf("%d",ans);
}