bef-> NO.27

Veröffentlicht am

[USACO14MAR]浇地Watering the Fields

题目描述

Due to a lack of rain, Farmer John wants to build an irrigation system to

send water between his N fields (1 <= N <= 2000).

Each field i is described by a distinct point (xi, yi) in the 2D plane,

with 0 <= xi, yi <= 1000. The cost of building a water pipe between two

fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his

fields are linked together — so that water in any field can follow a

sequence of pipes to reach any other field.

Unfortunately, the contractor who is helping FJ install his irrigation

system refuses to install any pipe unless its cost (squared Euclidean

length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all

his fields with a network of pipes.

农民约翰想建立一个灌溉系统，给他的NN (1 <= N <= 2000)块田送水。农田在一个二维平面上，第i块农田坐标为

，在农田ii 和农田jj 自己铺设水管的费用是这两块农田的欧几里得距离的平方

农民约翰希望所有的农田之间都能通水，而且希望花费最少的钱。但是安装工人拒绝安装费用小于C的水管(1 <= CC <= 1,000,000)。

请帮助农民约翰建立一个花费最小的灌溉网络，如果无法建立请输出-1。

输入输出格式

输入格式：

* Line 1: The integers N and C.

* Lines 2..1+N: Line i+1 contains the integers xi and yi.

输出格式：

* Line 1: The minimum cost of a network of pipes connecting the

fields, or -1 if no such network can be built.

输入输出样例

输入样例#1：

1
2
3
4
3 11
0 2
5 0
4 3

输出样例#1：

1
46

说明

INPUT DETAILS:

There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor

will only install pipes of cost at least 11.

OUTPUT DETAILS:

FJ cannot build a pipe between the fields at (4,3) and (5,0), since its

cost would be only 10. He therefore builds a pipe between (0,2) and (5,0)

at cost 29, and a pipe between (0,2) and (4,3) at cost 17.

Source: USACO 2014 March Contest, Silver

题解

可以Kruskal。

然而最开始忘了判-1还错了个点，不应该啊。D1T1难度。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 2005
struct Node{
	int x , y , dis;
	bool operator<(const Node& p)const{
		return dis < p.dis;
	}
}p[maxn*maxn];
int n , px[maxn] , c , py[maxn] , tot , f[maxn] , mst , cnt;
inline int dist(int x , int y , int xx , int yy){
	return (x-xx)*(x-xx) + (y-yy)*(y-yy);
}
int find(int x){
	if(f[x] != x)	return f[x] = find(f[x]);
	return f[x];
}
int main()
{
	scanf("%d%d",&n,&c);
	for(int i = 1 ; i <= n ; ++i)
	{
		scanf("%d%d",&px[i],&py[i]);
		for(int j = 1 ; j < i ; ++j)
			p[++cnt].x = i , p[cnt].y = j , p[cnt].dis = dist(px[i] , py[i] , px[j] , py[j]);
	}
	std::sort(p+1,p+cnt+1);
	for(int i = 1; i <= n ; ++i)
		f[i] = i;
	for(int i = 1 ; i <= cnt ; ++i){
		int x = p[i].x , y = p[i].y , d = p[i].dis;
		int fx = find(x) , fy = find(y);
		if(d < c)	continue;
		if(tot == n-1)	break;
		if(fx != fy){
			f[fx] = fy;
			mst += d;
			++tot;
		}
	}
	if(tot < n-1){
		puts("-1");
		return 0;
	}
	printf("%d",mst);
	
}

[USACO16FEB]负载平衡Load Balancing_Silver

题目描述

Farmer John’s NN cows are each standing at distinct locations (x_1, y_1) \ldots (x_n, y_n)(x1,y1)…(xn,yn) on his two-dimensional farm (1 \leq N \leq 10001≤N≤1000, and the x_ixi’s and y_iyi’s are positive odd integers of size at most 1,000,0001,000,000). FJ wants to partition his field by building a long (effectively infinite-length) north-south fence with equation x=ax=a (aawill be an even integer, thus ensuring that he does not build the fence through the position of any cow). He also wants to build a long (effectively infinite-length) east-west fence with equation y=by=b, where bb is an even integer. These two fences cross at the point (a,b)(a,b), and together they partition his field into four regions.

FJ wants to choose aa and bb so that the cows appearing in the four resulting regions are reasonably “balanced”, with no region containing too many cows. Letting MM be the maximum number of cows appearing in one of the four regions, FJ wants to make MM as small as possible. Please help him determine this

smallest possible value for MM.

给你一个矩阵，里面有些点，让你横向切一刀，纵向切一刀，使得得到的四个区域内的最大的点数最少。

输入输出格式

输入格式：

The first line of the input contains a single integer, NN. The next NN lines

each contain the location of a single cow, specifying its xx and yy

coordinates.

输出格式：

You should output the smallest possible value of MM that FJ can achieve by

positioning his fences optimally.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

输出样例#1：

1
2

题解

本题的主要思路是离散化+前缀和优化。

考虑点数较小而坐标较大，我们对点坐标离散化。离散化的标准是值的相对关系不变。可以用如下方法：

1
2
3
4
5
6
7
8
9
10
11
std::sort(g+1,g+cnt+1);
for(int i = 1 ; i <= cnt ; ++i)
{
	if(g[i].type){
		if(g[i].v == g[i-1].v)	X[g[i].k] = tot;
		else X[g[i].k] = ++tot;
	}else{
		if(g[i].v == g[i-1].v)	Y[g[i].k] = tot;
		else Y[g[i].k] = ++tot;
	}
}

这是我自己琢磨出来的办法，还是很好用的。

然后我们把这n个坐标不超过tot的点放到二维数组中做前缀和。

然后枚举每一条横线与纵线，

的更新答案。

最后的时间复杂度为

可以通过本题。

一遍切D1T2难度的题呢。。

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
54
55
56
57
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 2005
int p[maxn][maxn] , s[maxn][maxn] , n , tot , ans = 0x7fffffff, X[maxn] , Y[maxn] , ss[maxn];
struct Node{
	int v , k , type;
	bool operator < (const Node& p)const {
		return v < p.v;
	}
}g[maxn];
int main()
{
	scanf("%d",&n);
	int x , y;
	int cnt = 0;
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d%d",&x,&y);
		g[++cnt].v = x , g[cnt].k = i , g[cnt].type = 0;
		g[++cnt].v = y , g[cnt].k = i , g[cnt].type = 1;
	}
	std::sort(g+1,g+cnt+1);
	for(int i = 1 ; i <= cnt ; ++i)
	{
		if(g[i].type){
			if(g[i].v == g[i-1].v)	X[g[i].k] = tot;
			else X[g[i].k] = ++tot;
		}else{
			if(g[i].v == g[i-1].v)	Y[g[i].k] = tot;
			else Y[g[i].k] = ++tot;
		}
	}
	for(int i = 1 ; i <= n ; ++i)
		p[X[i]][Y[i]] = 1;
	n = tot;
	for(int i = 1 ; i <= n ; ++i)
	{
		std::memset(ss,0,sizeof(ss));
		for(int j = 1 ; j <= n ; ++j)
			ss[j] = ss[j-1] + p[i][j];
		for(int j = 1 ; j <= n ; ++j)
			s[i][j] = s[i-1][j] + ss[j];
	}
	for(int i = 1 ; i <= tot ; ++i)
		for(int j = 1 ; j <= tot ; ++j)
		{
			int cur = -0x7fffff;
			cur = std::max(cur , s[i][j]);
			cur = std::max(cur , s[tot][j] - s[i][j]);
			cur = std::max(cur , s[i][tot] - s[i][j]);
			cur = std::max(cur , s[tot][tot] - s[tot][j] - s[i][tot] + s[i][j]);
			ans = std::min(ans , cur);
		}
	printf("%d",ans);
}

[USACO07NOV]挤奶的时间Milking Time

题目描述

Bessie is such a hard-working cow. In fact, she is so focused on maximizing her productivity that she decides to schedule her next N (1 ≤ N ≤ 1,000,000) hours (conveniently labeled 0..N-1) so that she produces as much milk as possible.

Farmer John has a list of M (1 ≤ M ≤ 1,000) possibly overlapping intervals in which he is available for milking. Each interval i has a starting hour (0 ≤ starting_houri ≤ N), an ending hour (starting_houri < ending_houri ≤ N), and a corresponding efficiency (1 ≤ efficiencyi ≤ 1,000,000) which indicates how many gallons of milk that he can get out of Bessie in that interval. Farmer John starts and stops milking at the beginning of the starting hour and ending hour, respectively. When being milked, Bessie must be milked through an entire interval.

Even Bessie has her limitations, though. After being milked during any interval, she must rest R (1 ≤ R ≤ N) hours before she can start milking again. Given Farmer Johns list of intervals, determine the maximum amount of milk that Bessie can produce in the N hours.

奶牛Bessie在0~N时间段产奶。农夫约翰有M个时间段可以挤奶，时间段f,t内Bessie能挤到的牛奶量e。奶牛产奶后需要休息R小时才能继续下一次产奶，求Bessie最大的挤奶量。

输入输出格式

输入格式：

* Line 1: Three space-separated integers: N, M, and R

* Lines 2..M+1: Line i+1 describes FJ’s ith milking interval withthree space-separated integers: starting_houri , ending_houri , and efficiencyi

输出格式：

* Line 1: The maximum number of gallons of milk that Bessie can product in the N hours

输入输出样例

输入样例#1：

1
2
3
4
5
12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

输出样例#1：

1
43

题解

这个题是个很简单的dp，然而我并没有想出状态是什么。。。非常失败qwq

我们考虑最大的那种方案肯定是以某个区间结尾，然后我们需要一个子问题满足后面可以方便的转移。

就设

表示以第i个区间作为结尾的最大值，然后从前面不相交的状态中找一个最大的加上它自己就可以了。

当然这种dp必须将区间按照左端点排序，否则就没有无后效性的性质了。

比较套路，然后我没做出来，GG

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>
#include <queue>
#define maxn 1005
#define maxm 1000005
int  n , m , r , ans , f[maxn];
struct Node{
	int l  , r , v;
	bool operator < (const Node& x)const{
		return l < x.l;
	}
	bool operator > (const Node& x)const{
		return v < x.v;
	}
}p[maxn];
int main(){
	scanf("%d%d%d",&m,&n,&r);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d%d",&p[i].l , &p[i].r , &p[i].v);
	std::sort(p+1,p+n+1);
	for(int i = 1 ; i <= n ; ++i){
		for(int j = 1 ; j < i ; ++j)
			if(p[i].l - p[j].r >=r)
				f[i] = std::max(f[i],f[j]);
		f[i] += p[i].v;
		ans = std::max(ans , f[i]);
	}
	printf("%d",ans);
}

CF670C Cinema

题意翻译

莫斯科在举办一场重要的有nn 个不同国家的珂学家参与的国际会议，每个珂学家都只会一种语言。为了方便起见，我们规定一种语言用11 到10^9109 的数来描述。 在会议之后的晚上，珂学家们决定去看电影。他们去的电影院有mm 场电影，每场有两个不同的数字，分别代表配音的语言和字幕的语言。如果一个珂学家能听懂配音，他会非常愉悦；如果能看懂字幕，他会比较满意。如果既看不懂也听不懂，他会很生气。 珂学家们决定去看同一场电影，你必须帮助他们选择一场电影，让愉悦的人最多的前提下，比较满意的人最多。 输入格式： 第一行一个整数n(1 \leq n \leq 200000)n(1≤n≤200000) 表示珂学家个数。 第二行nn 个整数a_1, a_2, …, a_n(1 \leq a_i \leq 10^9)a1,a2,…,an(1≤ai≤109) 表示珂学家们会的语言。 第三行一个整数1 \leq m \leq 2000001≤m≤200000 表示电影的场数。 第四行mm 个整数b_1, b_2, …, b_n(1 \leq b_j \leq 10^9)b1,b2,…,bn(1≤bj≤109) 表示电影的配音用的语言。 第五行mm 个整数c_1, c_2, …, c_n(1 \leq c_j \leq 10^9)c1,c2,…,cn(1≤cj≤109) 表示电影的字幕用的语言。 输出格式： 一个整数表示安排哪一场电影。 如果有多种情况，选择比较满意的方案输出。

题目描述

Moscow is hosting a major international conference, which is attended by nn scientists from different countries. Each of the scientists knows exactly one language. For convenience, we enumerate all languages of the world with integers from 11 to 10^{9}109 .

In the evening after the conference, all nn scientists decided to go to the cinema. There are mm movies in the cinema they came to. Each of the movies is characterized by two distinct numbers — the index of audio language and the index of subtitles language. The scientist, who came to the movie, will be very pleased if he knows the audio language of the movie, will be almost satisfied if he knows the language of subtitles and will be not satisfied if he does not know neither one nor the other (note that the audio language and the subtitles language for each movie are always different).

Scientists decided to go together to the same movie. You have to help them choose the movie, such that the number of very pleased scientists is maximum possible. If there are several such movies, select among them one that will maximize the number of almost satisfied scientists.

输入输出格式

输入格式：

The first line of the input contains a positive integer n

— the number of scientists.

The second line contains nn positive integers

where a_{i}ai is the index of a language, which the ii -th scientist knows.

The third line contains a positive integer m

— the number of movies in the cinema.

The fourth line contains mm positive integers

, where b_{j}bj is the index of the audio language of the jj -th movie.

The fifth line contains mm positive integers

, where

is the index of subtitles language of the j -th movie.

It is guaranteed that audio languages and subtitles language are different for each movie, that is

输出格式：

Print the single integer — the index of a movie to which scientists should go. After viewing this movie the number of very pleased scientists should be maximum possible. If in the cinema there are several such movies, you need to choose among them one, after viewing which there will be the maximum possible number of almost satisfied scientists.

If there are several possible answers print any of them.

输入输出样例

输入样例#1：

1
2
3
4
5
3
2 3 2
2
3 2
2 3

输出样例#1：

1
2

输入样例#2：

1
2
3
4
5
6
6 3 1 1 3 7
5
1 2 3 4 5
2 3 4 5 1

输出样例#2：

1
1

说明

In the first sample, scientists must go to the movie with the index 22 , as in such case the 11 -th and the 33 -rd scientists will be very pleased and the 22 -nd scientist will be almost satisfied.

In the second test case scientists can go either to the movie with the index 11 or the index 33 . After viewing any of these movies exactly two scientists will be very pleased and all the others will be not satisfied.

题解

一道比较水的模拟题了，只要会用map就可以了。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#define maxn 200005
std::map<int,int> s;
std::queue<int> q;
int n , p[maxn] , au[maxn] , st[maxn] , ans , m;
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]) , ++s[p[i]];
	scanf("%d",&m);
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d",&au[i]);
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d",&st[i]);
	int now = -0x7f7ffff;
	for(int i = 1 ; i <= m ; ++i)
	{
//		printf("i movie : %d\n",s[au[i]]);
		if(s[au[i]] > now) {
			now = s[au[i]];
			while(!q.empty()) q.pop();
			q.push(i);
		}
		else if(s[au[i]] == now){
			q.push(i);
		}
	}
//	printf("%d\n",q.front());
	int semax = -0x7fffff;
	while(!q.empty()){
		int now = q.front();
		q.pop();
		int cur = s[st[now]];
		if(cur > semax) semax = cur , ans = now;
	}
	printf("%d",ans);
}

P1119 灾后重建

题目背景

BB地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出BB地区的村庄数NN，村庄编号从00到N-1N−1，和所有MM条公路的长度，公路是双向的。并给出第ii个村庄重建完成的时间t_iti，你可以认为是同时开始重建并在第t_iti天重建完成，并且在当天即可通车。若t_iti为00则说明地震未对此地区造成损坏，一开始就可以通车。之后有QQ个询问(x, y, t)(x,y,t)，对于每个询问你要回答在第tt天，从村庄xx到村庄y的最短路径长度为多少。如果无法找到从xx村庄到yy村庄的路径，经过若干个已重建完成的村庄，或者村庄xx或村庄yy在第t天仍未重建完成 ，则需要返回-1−1。

输入输出格式

输入格式：

第一行包含两个正整数N,MN,M，表示了村庄的数目与公路的数量。

第二行包含NN个非负整数t_0, t_1,…, t_{N-1}t0,t1,…,tN−1，表示了每个村庄重建完成的时间，数据保证了t_0 ≤ t_1 ≤ … ≤ t_{N-1}t0≤t1≤…≤tN−1。

接下来MM行，每行33个非负整数i, j, wi,j,w，ww为不超过1000010000的正整数，表示了有一条连接村庄ii与村庄jj的道路，长度为ww，保证i≠ji≠j，且对于任意一对村庄只会存在一条道路。

接下来一行也就是M+3M+3行包含一个正整数QQ，表示QQ个询问。

接下来QQ行，每行33个非负整数x, y, tx,y,t，询问在第tt天，从村庄xx到村庄yy的最短路径长度为多少，数据保证了tt是不下降的。

输出格式：

共QQ行，对每一个询问(x, y, t)(x,y,t)输出对应的答案，即在第tt天，从村庄xx到村庄yy的最短路径长度为多少。如果在第t天无法找到从xx村庄到yy村庄的路径，经过若干个已重建完成的村庄，或者村庄x或村庄yy在第tt天仍未修复完成，则输出-1−1。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4

输出样例#1：

1
2
3
4
-1
-1
5
4

说明

对于30\%30%的数据，有N≤50N≤50；

对于30\%30%的数据，有t_i= 0ti=0，其中有20\%20%的数据有t_i = 0ti=0且N>50N>50；

对于50\%50%的数据，有Q≤100Q≤100；

对于100\%100%的数据，有N≤200，

，所有输入数据涉及整数均不超过100000。

题解

第一反应是Floyd。

显然一个点没被修好那就不以它为中转点更新其他点最短路就好。但是要注意查询的两点必须也在查询时间之后才行。D1T2难度（可能偏低一点）

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 205
#define maxq 50005
#define INF 0x3fffffff
int n , m , dis[maxn][maxn] , tim[maxn] , q;
struct Node{
	int x , y , t;
	bool operator < (const Node& q)const{
		return t < q.t;
	}
}p[maxq];
inline void Floyd(){
	int cur = 1;
	for(int i = 1 ; i <= q ; ++i){
		int x = p[i].x + 1, y = p[i].y + 1, t = p[i].t;
		while(tim[cur] <= t && cur <= n){
			for(int j = 1 ; j <= n ; ++j)
				for(int k = 1 ; k <= n ; ++k)
					if(dis[j][cur] + dis[cur][k] < dis[j][k])
						dis[j][k] = dis[j][cur] + dis[cur][k];
			++cur;
		}
		if(dis[x][y] != INF && tim[x] <= t  && tim[y] <= t){
			printf("%d\n",dis[x][y]);
		}
		else puts("-1");
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= n ; ++j)
			dis[i][j] = INF;
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&tim[i]);
	int x , y , d;
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d%d%d",&x,&y,&d) , dis[x+1][y+1] = dis[y+1][x+1] = d;
	scanf("%d",&q);
	for(int i = 1 ; i <= q ; ++i)
		scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].t);
	Floyd();
}

[USACO14MAR]哞哞哞Mooo Moo

题目描述

Farmer John has completely forgotten how many cows he owns! He is too embarrassed to go to his fields to count the cows, since he doesn’t want the cows to realize his mental lapse. Instead, he decides to count his cows secretly by planting microphones in the fields in which his cows tend to gather, figuring that he can determine the number of cows from the total volume of all the mooing he hears.

FJ’s N fields (1 <= N <= 100) are all arranged in a line along a long straight road. Each field might contain several types of cows; FJ owns cows that come from B different breeds (1 <= B <= 20), and a cow of breed i moos at a volume of V(i) (1 <= V(i) <= 100). Moreover, there is a strong wind blowing down the road, which carries the sound of mooing in one direction from left to right: if the volume of mooing in some field is X, then in the next field this will contribute X-1 to the total mooing volume (and X-2 in the field after that, etc.). Otherwise stated, the mooing volume in a field is the sum of the contribution due to cows in that field, plus X-1, where X is the total mooing volume in the preceding field.

Given the volume of mooing that FJ records in each field, please compute the minimum possible number of cows FJ might own.

The volume FJ records in any field is at most 100,000.

民约翰忘记了他到底有多少头牛，他希望通过收集牛叫声的音量来计算牛的数量。

他的N (1 <= N <= 100)个农场分布在一条直线上，每个农场可能包含B (1 <= B <= 20)个品种的牛，一头品种i的牛的音量是V(i) ，(1 <= V(i) <= 100)。一阵大风将牛的叫声从左往右传递，如果某个农场的总音量是X，那么将传递X-1的音量到右边的下一个农场。另外，一个农场的总音量等于该农场的牛产生的音量加上从上一个农场传递过来的音量（即X-1）。任意一个农场的总音量不超过100000。

请计算出最少可能的牛的数量。

输入输出格式

输入格式：

* Line 1: The integers N and B.

* Lines 2..1+B: Line i+1 contains the integer V(i).

* Lines 2+B..1+B+N: Line 1+B+i contains the total volume of all mooing

in field i.

输出格式：

* Line 1: The minimum number of cows owned by FJ, or -1 if there is no

configuration of cows consistent with the input.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
5 2
5
7
0
17
16
20
19

输出样例#1：

1
4

说明

INPUT DETAILS:

FJ owns 5 fields, with mooing volumes 0,17,16,20,19. There are two breeds

of cows; the first moos at a volume of 5, and the other at a volume of 7.

OUTPUT DETAILS:

There are 2 cows of breed #1 and 1 cow of breed #2 in field 2, and there is

another cow of breed #1 in field 4.

Source: USACO 2014 March Contest, Silver

题解

一道很水的题，只要你愿意读题。。

显然根据题意我们能算出每块农场的音量到底是多少。

然后就是一个完全背包了。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define INF 0x7ffffff
#define maxn 100005
int f[maxn] , w[maxn] , n , b , v[maxn] , ans , ba[maxn];
int main()
{
	scanf("%d%d",&n,&b);
	for(int i = 1 ; i <= b ; ++i)
		scanf("%d",&w[i]);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d",&ba[i]);
		v[i] = ba[i] - std::max(ba[i-1]-1,0);
	}
	for(int i = 1 ; i <= 100000 ; ++i)
		f[i] = INF;
	f[0] = 0;
	for(int i = 1 ; i <= b ; ++i)
		for(int j = w[i] ; j <= 100000 ; ++j)
			f[j] = std::min(f[j] , f[j - w[i]] + 1);
	for(int i = 1 ; i <= n ; ++i){
		if(f[v[i]] != INF) ans += f[v[i]];
		else{
			puts("-1");
			return 0;
		}
	}
	printf("%d",ans);
}

P2342 叠积木

题目背景

Cube Stacking, 2004 Open

题目描述

约翰和贝西在叠积木。共有30000块积木，编号为1到30000。一开始，这些积木放在地上，自然地分成N堆。贝西接受约翰的指示，把一些积木叠在另一些积木的上面。一旦两块积木相叠， 彼此就再也不会分开了，所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作，操作分为两种：

 第一种是移动操作，格式为“移动X到Y的上面”。X和Y代表两块积木的编号，意思是将X所的那堆积木，整体叠放到Y所在的那堆积木之上；

 第二种是统计操作，格式为“统计Z下方的积木数量”。Z代表一块积木的编号，意思是贝西需要报告在编号为Z的积木之下还有多少块积木

请编写一个程序，帮助贝西回答每条统计问题。

输入输出格式

输入格式：

 第一行：单个整数：P，1 ≤ P ≤ 10^5

 第二行到第P + 1行：每行描述一条命令，如果这行开头的字母是 M，代表一条移动命令，后面的两个整数代表上文中的X和Y；如果开头字母是 C，代表一条统计命令。后面的整数代表上文中的Z，保证所有的移动命令都有意义，X和Y不会已经出现在同一堆积木里

输出格式：

 对每一个统计命令，输出正确回答，用换行符分开每个查询的结果

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

输出样例#1：

1
2
3
1
0
2

说明

第一次查询时， 1 下面只有一个 6；第二次查询时， 3 下面没有任何积木；第三次查询时，4 下面有两块积木：1 和 6

题解

一道带权并查集的维护，不过还要加个数组维护每个元素底下有多少个。

我们让每一堆积木最底下那块做根，然后模拟下就行了。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 30005
int f[maxn] , sz[maxn] , n , m ,x , y , h[maxn];
char ch;
int find(int x){
	if(f[x] == x)	return x;
	int fa = find(f[x]);
	h[x] += h[f[x]];
	return f[x] = fa;  
}
int main(){
	scanf("%d",&m);
	n = 30000;
	for(int i = 1 ; i <= n ; ++i)
		f[i] = i , sz[i] = 1;
	for(int i = 1 ; i <= m ; ++i){
		std::cin>>ch;
		if(ch == 'M') {
			scanf("%d%d",&x,&y);
			int fx = find(x) , fy = find(y);
			f[fx] = fy;
			h[fx] = sz[fy];
			sz[fy] += sz[fx];
		}
		else{
			scanf("%d",&x);
			int fx = find(x);
			printf("%d\n",h[x]);
		}
	}
}

[USACO13NOV]挤奶牛Crowded Cows

题目描述

Farmer John’s N cows (1 <= N <= 50,000) are grazing along a one-dimensional fence. Cow i is standing at location x(i) and has height h(i) (1 <= x(i),h(i) <= 1,000,000,000).

A cow feels “crowded” if there is another cow at least twice her height within distance D on her left, and also another cow at least twice her height within distance D on her right (1 <= D <= 1,000,000,000). Since crowded cows produce less milk, Farmer John would like to count the number of such cows. Please help him.

FJ有N(1 <= N <= 50,000)头奶牛沿着一维的栅栏吃草，第i头奶牛在目标点x(i) ，它的身高是 h(i) (1 <=x(i),h(i) <= 1,000,000,000)。

当一头奶牛左边D距离内而且右边D距离内有身高至少是它的两倍的奶牛，t (1 <= D <= 1,000,000,000)，它就会觉得拥挤。

请计算觉得拥挤的奶牛的数量。

输入输出格式

输入格式：

* Line 1: Two integers, N and D.

* Lines 2..1+N: Line i+1 contains the integers x(i) and h(i). The locations of all N cows are distinct.

输出格式：

* Line 1: The number of crowded cows.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
6 4 
10 3 
6 2 
5 3 
9 7 
3 6 
11 2

输出样例#1：

1
2

说明

There are 6 cows, with a distance threshold of 4 for feeling crowded. Cow #1 lives at position x=10 and has height h=3, and so on.

The cows at positions x=5 and x=6 are both crowded.

题解

一道很简单的单调队列题，一遍切。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#define maxn 50005
int n , d , ans;
bool f[maxn] , g[maxn];
struct Node{
	int x , h , k;
	bool operator < (const Node& p)const{
		return x < p.x;
	}
}p[maxn];
std::deque<int>	q;
int main(){
	scanf("%d%d",&n,&d);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].x , &p[i].h) , p[i].k = i;
	std::sort(p+1,p+n+1);
	for(int i = 1 ; i <= n ; ++i)
	{
		while(!q.empty() && p[q.front()].x < p[i].x - d) q.pop_front();
		while(!q.empty() && p[q.back()].h < p[i].h)	q.pop_back();
		if(!q.empty() && p[q.front()].h >= 2 * p[i].h)	f[p[i].k] = true;
		q.push_back(i);
	}
	while(!q.empty())	q.pop_back();
	for(int i = n ; i >= 1 ; --i)
	{
		while(!q.empty() && p[q.front()].x > p[i].x + d)	q.pop_front();
		while(!q.empty() && p[q.back()].h < p[i].h)		q.pop_back();
		if(!q.empty() && p[q.front()].h >= 2 * p[i].h)	g[p[i].k] = true; 
		q.push_back(i);
	}
	for(int i = 1 ; i <= n ; ++i)
		if(f[i] && g[i])	++ans;
	printf("%d",ans);
}

[USACO12FEB]附近的牛Nearby Cows

题目描述

Farmer John has noticed that his cows often move between nearby fields. Taking this into account, he wants to plant enough grass in each of his fields not only for the cows situated initially in that field, but also for cows visiting from nearby fields.

Specifically, FJ’s farm consists of N fields (1 <= N <= 100,000), where some pairs of fields are connected with bi-directional trails (N-1 of them in total). FJ has designed the farm so that between any two fields i and j, there is a unique path made up of trails connecting between i and j. Field i is home to C(i) cows, although cows sometimes move to a different field by crossing up to K trails (1 <= K <= 20).

FJ wants to plant enough grass in each field i to feed the maximum number of cows, M(i), that could possibly end up in that field — that is, the number of cows that can potentially reach field i by following at most K trails. Given the structure of FJ’s farm and the value of C(i) for each field i, please help FJ compute M(i) for every field i.

农民约翰已经注意到他的奶牛经常在附近的田野之间移动。考虑到这一点，他想在每一块土地上种上足够的草，不仅是为了最初在这片土地上的奶牛，而且是为了从附近的田地里去吃草的奶牛。

具体来说，FJ的农场由N块田野构成（1 <= n <= 100，000),每两块田野之间有一条无向边连接（总共n-1条边）。FJ设计了农场，任何两个田野i和j之间，有且只有一条路径连接i和j。第 i块田野是C(i)头牛的住所，尽管奶牛们有时会通过k条路到达其他不同的田野（1<=k<=20）。

FJ想在每块田野上种上够M(i)头奶牛吃的草。M(i)指能从其他点经过最多k步就能到达这个点的奶牛的个数。

现给出FJ的每一个田野的奶牛的数目，请帮助FJ计算每一块田野的M(i)。

输入输出格式

输入格式：

* Line 1: Two space-separated integers, N and K.

* Lines 2..N: Each line contains two space-separated integers, i and j (1 <= i,j <= N) indicating that fields i and j are directly connected by a trail.

* Lines N+1..2N: Line N+i contains the integer C(i). (0 <= C(i) <= 1000)

第一行：n和k;

后面n-1行：i和j（两块田野）;

之后n行：1..n每一块的C(i);

输出格式：

* Lines 1..N: Line i should contain the value of M(i).

n行：每行M(i);//i：1..2

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
6 2 
5 1 
3 6 
2 4 
2 1 
3 2 
1 
2 
3 
4 
5 
6

输出样例#1：

1
2
3
4
5
6
15 
21 
16 
10 
8 
11

说明

There are 6 fields, with trails connecting (5,1), (3,6), (2,4), (2,1), and (3,2). Field i has C(i) = i cows.

Field 1 has M(1) = 15 cows within a distance of 2 trails, etc.

题目简述：给出一棵n个点的树，每个点上有C_i头牛，问每个点k步范围内各有多少头牛。

题解

一道非常非常经典的树形dp ， 并且由于每个点除了子树内还有子树外，可以考虑up and down。(一遍过真高兴)

首先考虑up的过程，我们如何从儿子转移呢？

就是这么简单。由于是求和，所以down非常好容斥（这也是up and down能应用的一个重要原则）

最终的状态值为：

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
54
55
56
57
58
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define maxk 21
int head[maxn] , cnt , n , f[maxn][maxk], k;
struct edge{
	int next , to;
}e[maxn*2];
inline void add(int x , int y){
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void up(int x , int fx)
{
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == fx)	continue;
		up(v , x);
		for(int j = 1 ; j <= k ; ++j)
			f[x][j] += f[v][j-1];
	}

}
void down(int x , int fx)
{
	for(int i = head[x] ; i ; i = e[i].next)
	{
		int v = e[i].to;
		if(v == fx)	continue;
		for(int j = k ; j >= 2 ; --j)
			f[v][j] -= f[v][j-2];
		for(int j = k ; j >= 1 ; --j)
			f[v][j] += f[x][j-1];
		down(v , x);
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1 ; i <= n-1 ; ++i){
		int x , y;
		scanf("%d%d",&x,&y);
		add(x,y) , add(y,x);
	}
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&f[i][0]);
	up(1,1);
	down(1,1);
	for(int i = 1 ; i <= n ; ++i){
		int ans = 0 ;
		for(int j = 0 ; j <= k ; ++j)
			ans += f[i][j];
		printf("%d\n",ans);
	}
}

[USACO14MAR]懒惰的牛The Lazy Cow_Sliver

题目描述

It’s a hot summer day, and Bessie the cow is feeling quite lazy. She wants

to locate herself at a position in her field so that she can reach as much

delicious grass as possible within only a short distance.

The field Bessie inhabits is described by an N by N grid of square cells

(1 <= N <= 400). The cell in row r and column c (1 <= r,c <= N) contains

G(r,c) units of grass (0 <= G(r,c) <= 1000). From her initial square in

the grid, Bessie is only willing to take up to K steps (0 <= K <= 2*N).

Each step she takes moves her to a cell that is directly north, south,

east, or west of her current location.

For example, suppose the grid is as follows, where (B) describes Bessie’s

1
2
3
4
5
50    5     25*   6     17    
14    3*    2*    7*    21    
99*   10*   1*(B) 2*    80*    
8     7*    5*    23*   11   
10    0     78*   1     9

initial position (here, in row 3, column 3):

If K=2, then Bessie can only reach the locations marked with *s.

Please help Bessie determine the maximum amount of grass she can reach, if

she chooses the best possible initial location in the grid.

奶牛贝西非常懒惰，她希望在她的地盘内找到一点最佳位置居住，以便在有限的步数内可以吃到尽量多的青草。

她的地盘是一个N行N列(1 <= N <= 400)的矩阵，第r行c列包含G(r,c)单位的青草(0 <= G(r,c) <= 1000)。从她的居住点，她最多愿意走K步(0 <= K <= 2*N)，每一步她可以找到上、下、左、右直接相邻的某个格子。

输入输出格式

输入格式：

* Line 1: The integers N and K.

* Lines 2..1+N: Line r+1 contains N integers describing row r of the

grid.

输出格式：

* Line 1: The maximum amount of grass Bessie can reach, if she chooses

the best possible initial location (the location from which

she can reach the most grass).

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9

输出样例#1：

1
342

说明

OUTPUT DETAILS:

In the example above, Bessie can reach 342 total units of grass if she

locates herself in the middle of the grid.

Source: USACO 2014 March Contest, Silver

题解

一开始以为得

的菱形前缀和，后来发现只需要简单的

然后前缀和优化掉一维就行了。

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
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define maxn 405
int s[maxn][maxn] , p[maxn][maxn] , n , k , g[maxn][maxn] , ans;
inline int abs(int x){
	return x >= 0 ? x : (-x);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= n ; ++j)
			scanf("%d",&p[i][j]);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= n ; ++j)	
			s[i][j] = s[i][j-1] + p[i][j];
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= n ; ++j){
			int cur = i - k;
			while(cur <= i + k){
				if(cur <= 0){
					++cur;
					continue;
				} 	
				if(cur > n)break;
				int lr = k - abs(i - cur);
				lr = k - abs(cur - i);
				g[i][j] += s[cur][(j + lr) <= n ? (j + lr) : n] - s[cur][(j - lr - 1) > 0 ? (j - lr - 1) : 0];
				++cur;
			}
		ans = std::max(ans , g[i][j]);
		}
	printf("%d",ans);
}

P1730 最小密度路径

题目描述

给出一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个节点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。

输入输出格式

输入格式：

第一行包括2个整数N和M。

以下M行，每行三个数字A、B、W，表示从A到B有一条权值为W的有向边。

再下一行有一个整数Q。

以下Q行，每行一个询问X和Y，如题意所诉。

输出格式：

对于每个询问输出一行，表示该询问的最小密度路径的密度（保留3位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3

输出样例#1：

1
2
5.000
5.500

说明

1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000

题解

由于精度原因怕被卡，口胡一个做法：分数规划

二分一个密度，看看能不能找到一条路有这样的密度。

P4948 数列求和

题目描述

求数列

的前 {n}n 项和 {T_n \ mod \ \left( 10^9+7 \right) }Tn mod (109+7)

输入输出格式

输入格式：

输入共 1 行，包含 3 个非负整数： n，a，k

输出格式：

输出共 1 行，包含 1 个非负整数：

输入输出样例

输入样例#1：

1
3 4 0

输出样例#1：

1
84

输入样例#2：

1
3 10 1

输出样例#2：

1
3210

输入样例#3：

1
3 9 2

输出样例#3：

1
6894

说明

Luogu

题解

这道题难在要有基于k递推的意识。

设

为所求答案，只针对变量k

第一步等比错位相减变换

注意的是前万不要把后面的写反了！！

接下来二项式展开，减掉一项

然后回带

然而计算还是会超时，这时候我们用一点小技巧：更改枚举顺序

可知右侧的式子是

项，假如我们把里面的j循环提出来答案还是一样的。

这下就大功告成了，最后的答案是：

特别的

时间复杂度

可以轻松通过本题。

upd：发现应该是

….当时不知怎么就写错了。白白浪费一个小时！以后这种题出错还是要检查一下结论！！！

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
54
55
56
57
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
#define maxk 2005
#define mod 1000000007
ll n , a , k , f[maxk] , C[maxk][maxk];
inline ll pow(ll x , ll y){
    ll ans = 1 , base = x % mod;
    while(y){
        if(y&1)	ans = ans * base % mod;
        base = base * base % mod;
        y >>= 1;
    }
    return ans;
}
ll exgcd(ll a , ll b , ll& x, ll& y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b , a % b , y , x);
    y -= a/b * x;
    return g;
}
ll inv(ll a){
    ll x , y;
    ll g = exgcd(a,mod,x,y);
    x = (x % mod + mod) % mod;
    return x;
}

int main()
{
    for(int i = 0 ; i <= 2000 ; ++i)
    	C[i][0] = 1;
    for(int i = 1 ;i <= 2000 ; ++i)
    	for(int j = 1 ; j <= i ; ++j)
    		C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
    scanf("%lld%lld%lld",&n,&a,&k);
    f[0] = a * (pow(a,n) - 1) % mod * inv(a-1) % mod;
    for(int i = 1 ; i <= k ; ++i){
        ll gx = 0;
        for(int j = 0 ; j <= i-1 ; ++j){
        	ll tmp = f[j] - a;
        	tmp = (tmp % mod + mod) % mod;
            gx = (gx + C[i][j] * pow(-1,i-j) % mod * tmp % mod) % mod;
        }
        f[i] = pow(a,n+1) * pow(n,i) % mod - a + gx;
        f[i] = (f[i] % mod + mod) % mod;
        f[i] = f[i] * inv(a-1) % mod;
    }
    printf("%lld",f[k]);
}