bef-> NO.31

Veröffentlicht am

[HAOI2015]树上染色

题目描述

有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他 的N-K个点染成白色 。 将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。

输入输出格式

输入格式：

第一行包含两个整数 N, K 。接下来 N-1 行每行三个正整数 fr, to, dis ， 表示该树中存在一条长度为 dis 的边 (fr, to) 。输入保证所有点之间是联通的。

输出格式：

输出一个正整数，表示收益的最大值。

输入输出样例

输入样例#1：

1
2
3
3 1
1 2 1
1 3 2

输出样例#1：

1
3

说明

对于 100% 的数据， 0<=K<=N <=2000

题解

被wzx大佬毁了的一道好题。D2T2难度。

这里如果我们设

表示子树u内选k个点最优的价值是不可能转移的，因为它完全不存在无后效性。

因此这个题难就难在能看出每条边能被分别统计答案。

倒也不是很难想，因为可以考虑到子树内每个黑点和子树外经过的边以及白边，这个是可以树上背包解决的。

我们让

表示子树u内选k个点对答案的贡献。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 2005
#define LL long long
LL f[maxn][maxn] , n , k , head[maxn] , cnt , sz[maxn];
struct edge{
    LL next , to , dis;
}e[maxn*2];
inline void add(LL x , LL y , LL dis)
{
    e[++cnt].next = head[x] ;
    e[cnt].to = y;
    e[cnt].dis = dis;
    head[x] = cnt;
}
void dfs(LL x , LL fx , LL dis)
{
    f[x][0] = f[x][1] = 0;
    sz[x] = 1;
    for(int i = head[x] ; i ; i = e[i].next){
        if(e[i].to == fx)	continue;
        dfs(e[i].to , x , e[i].dis);
        sz[x] += sz[e[i].to];
        for(int j = std::min(sz[x] , k) ; j >= 0 ; --j)
            for(int t = 0 ; t <= j && t <= sz[e[i].to] ; ++t){
                LL val = t * (k - t) * e[i].dis + (sz[e[i].to] - t) * (n - k - sz[e[i].to] + t) * e[i].dis;
                f[x][j] = std::max(f[x][j] , f[x][j-t] + f[e[i].to][t] + val); 
            }
    }
}
int main()
{
    std::memset(f,-0x3f,sizeof(f));
    scanf("%lld%lld",&n,&k);
    LL x ,y , z;
    for(int i = 1 ; i <= n-1 ; ++i)
        scanf("%lld%lld%lld",&x,&y,&z) , add(x,y,z) , add(y,x,z);
    dfs(1,1,0);		
    printf("%lld\n",f[1][k]);
}

[ZJOI2012]灾难

题目描述

阿米巴是小强的好朋友。

阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。

学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。

我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：

一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。

这个图没有环。

图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。

如果某个消费者的所有食物都灭绝了，它会跟着灭绝。

我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。

举个例子：在一个草场上，生物之间的关系是：

如 img

如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以，草的灾难值是4。

给定一个食物网，你要求出每个生物的灾难值。

输入输出格式

输入格式：

输入文件 catas.in 的第一行是一个正整数 N，表示生物的种数。生物从 1 标

号到 N。

接下来 N 行，每行描述了一个生物可以吃的其他生物的列表，格式为用空

格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是 0 表示列

表的结束。

输出格式：

输出文件catas.out包含N行，每行一个整数，表示每个生物的灾难值。

输入输出样例

输入样例#1：

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

输出样例#1：

1
2
3
4
5
4
1
0
0
0

说明

【样例说明】

样例输入描述了题目描述中举的例子。

【数据规模】

对50%的数据，N ≤ 10000。

对100%的数据，1 ≤ N ≤ 65534。

输入文件的大小不超过1M。保证输入的食物网没有环。

题解

又是wzx大佬推荐的题，还是挺不错的一道题。放在D1T3挺不错。

这题主要是构造+贪心

考虑一个动物什么时候会被灭绝，可以反图拓扑。时间复杂度不够优秀。

因此我们（打开标签看到倍增）构造一棵树，树的性质是子节点有唯一的父节点，让直接导致灭绝关系的连在一起。在纸上使劲画图 发现是所有食物的LCA。

思路很明确了：
拓扑 + 构造树 + 倍增优化LCA

然而我！必！须！得！说！，我倍增某处写错了导致交了10多遍，不然就一次AC了！！

以后当程序出错了，还是要关注每一个细节，而不是只关注主要部分。

倍增好久不写居然真的出错了。。

讲真我要是NOIp想出这种难度题的正解然后写疵了我大概会气死

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
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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define maxn 100005
int f[maxn][19] , n , x , y , head[maxn] , lg[maxn] , dep[maxn] , sz[maxn] , cnt ,  d[maxn];
struct edge{
    int next , to;
}e[maxn*20];
int LCA(int x , int y)
{
    if(dep[x] < dep[y]) std::swap(x,y);
    while(dep[x] > dep[y] && f[x][lg[dep[x]-dep[y]]-1] != -1)	
        x = f[x][lg[dep[x]-dep[y]]-1];
    if(x == y)	return x;
    for(int i = lg[dep[x]] ; i >= 0 ; --i)	
        if(f[x][i] != f[y][i])
            x = f[x][i] , y = f[y][i];
    return f[x][0];

}
void dfs(int x , int fx){
    sz[x] = 1;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs(e[i].to , x) , sz[x] += sz[e[i].to];
}
void add(int x , int y)
{
    e[++cnt].next = head[x] ;
    e[cnt].to = y;
    head[x] = cnt;
    ++d[y];
}
inline void Toposort()
{
    std::queue<int> q;
    for(int i = 0 ; i <= n ; ++i)
        if(!d[i])	q.push(i);
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(int i = head[k] ; i ; i = e[i].next){
            int v = e[i].to;
            if(f[v][0] == -1){
                f[v][0] = k;
            }
            else{
                f[v][0] = LCA(f[v][0] , k);
            }
            --d[v];
            if(!d[v]){
            	dep[v] = dep[f[v][0]] + 1;
            	for(int j = 1 ; j <= 18 ; ++j)
                	if(f[v][j-1] != -1)
                		f[v][j] = f[f[v][j-1]][j-1];
                q.push(v);
        }
    }
	}
}
int main()
{
    scanf("%d",&n);
    std::memset(f,-1,sizeof(f));
    for(int i = 1 ; i <= n ; ++i)
        lg[i] = lg[i-1] + (1<<lg[i-1]==i);
    for(int i = 1 ; i <= n ; ++i){
        int x;
        while(scanf("%d",&x)){
            if(!x)	break;
            add(x,i);
        }
    }
    for(int i = 1 ; i <= n ; ++i)
        if(!d[i])	add(0,i);
    Toposort();
    
    std::memset(head,0,sizeof(head));
    std::memset(e,0,sizeof(e));
    cnt = 0;
    
    for(int i = 1 ; i <= n ; ++i)
        add(f[i][0],i) , add(i,f[i][0]);
    dfs(0,0);
    for(int i = 1 ; i <= n ; ++i)
        printf("%d\n",sz[i]-1);
}

[USACO12MAR]花盆Flowerpot

题目描述

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:

img

Each drop falls downward (towards the x axis) at a rate of 1 unit per second. You would like to place Farmer John’s flowerpot of width W somewhere along the x axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount D (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.

Given the value of D and the locations of the N raindrops, please compute the minimum possible value of W.

老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。

每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着的最后1滴水结束，之间的时间差至少为D。

我们认为，只要水滴落到x轴上，与花盆的边沿对齐，就认为被接住。给出N滴水的坐标和D的大小，请算出最小的花盆的宽度W。

输入输出格式

输入格式：

第一行2个整数 N 和 D。

第2.. N+1行每行2个整数，表示水滴的坐标(x,y)。

输出格式：

仅一行1个整数，表示最小的花盆的宽度。如果无法构造出足够宽的花盆，使得在D单位的时间接住满足要求的水滴，则输出-1。

输入输出样例

输入样例#1：

1
2
3
4
5
4 5
6 3
2 4
4 10
12 15

输出样例#1：

1
2

说明

【样例解释】

有4滴水， (6,3), (2,4), (4,10), (12,15).水滴必须用至少5秒时间落入花盆。花盆的宽度为2是必须且足够的。把花盆放在x=4..6的位置，它可以接到1和3水滴, 之间的时间差为10-3 = 7满足条件。

【数据范围】

40%的数据：1 ≤ N ≤ 1000，1 ≤ D ≤ 2000；

100%的数据：1 ≤ N ≤ 100000，1 ≤ D ≤ 1000000，0≤x,y≤10^6。

题解

很简单的单调队列嘛。

放在D1T2送分比较合适。（然而去年是个很毒瘤的模拟）

但是不要sb的交好几遍这种题才AC

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#define maxn 100005
int n , d;
struct Node{
	int v , t , k;
	bool operator < (const Node& x)const{
		return v < x.v;
	}
}p[maxn];
inline int abs(int x){
	return x >= 0 ? x : (-x);
}
bool check(int x)
{
	std::deque<int> q1 , q2;
	for(int i = 1 ; i <= n ; ++i){
		while(!q1.empty() && p[q1.back()].t < p[i].t)	q1.pop_back();//max
		while(!q2.empty() && p[q2.back()].t > p[i].t)	q2.pop_back();//min
		while(!q1.empty() && p[i].v - p[q1.front()].v > x)	q1.pop_front();
		while(!q2.empty() && p[i].v - p[q2.front()].v > x)  q2.pop_front();
		q1.push_back(i);
		q2.push_back(i);
		if(p[q1.front()].t - p[q2.front()].t >= d)	return true;
	}
	return false;
}
int main() 
{
	scanf("%d%d",&n,&d);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].v,&p[i].t);
	std::sort(p+1,p+n+1);
	int l = 1 , r = 1000000 , ans = 0;
	while(l <= r){
		int mid = l + r >> 1;
		if(check(mid))	ans = mid , r = mid - 1;
		else l = mid + 1;
	}
	if(ans == 0){
		puts("-1");
		return 0;
	}
	printf("%d",ans);
}

[USACO10MAR]伟大的奶牛聚集Great Cow Gather

题目描述

Bessie is planning the annual Great Cow Gathering for cows all across the country and, of course, she would like to choose the most convenient location for the gathering to take place.

Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

Each cow lives in one of N (1 <= N <= 100,000) different barns (conveniently numbered 1..N) which are connected by N-1 roads in such a way that it is possible to get from any barn to any other barn via the roads. Road i connects barns A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). The Great Cow Gathering can be held at any one of these N barns. Moreover, barn i has C_i (0 <= C_i <= 1,000) cows living in it.

每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住者C_i(0 <= C_i <= 1,000)只奶牛。

When choosing the barn in which to hold the Cow Gathering, Bessie wishes to maximize the convenience (which is to say minimize the inconvenience) of the chosen location. The inconvenience of choosing barn X for the gathering is the sum of the distances all of the cows need to travel to reach barn X (i.e., if the distance from barn i to barn X is 20, then the travel distance is C_i*20). Help Bessie choose the most convenient location for the Great Cow Gathering.

在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。

Consider a country with five barns with [various capacities] connected by various roads of varying lengths. In this set of barns, neither barn 3 nor barn 4 houses any cows.

1 3 4 5

@—1—@—3—@—3—@[2]

[1] |

2 | @[1] 2 Bessie can hold the Gathering in any of five barns; here is the table of inconveniences calculated for each possible location:

Gather ——- Inconvenience ———

Location B1 B2 B3 B4 B5 Total

1 0 3 0 0 14 17

2 3 0 0 0 16 19

3 1 2 0 0 12 15

4 4 5 0 0 6 15

5 7 8 0 0 0 15

If Bessie holds the gathering in barn 1, then the inconveniences from each barn are:

Barn 1 0 — no travel time there!

Barn 2 3 — total travel distance is 2+1=3 x 1 cow = 3 Barn 3 0 — no cows there!

Barn 4 0 — no cows there!

Barn 5 14 — total travel distance is 3+3+1=7 x 2 cows = 14 So the total inconvenience is 17.

The best possible convenience is 15, achievable at by holding the Gathering at barns 3, 4, or 5.

输入输出格式

输入格式：

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: C_i

* Lines N+2..2*N: Line i+N+1 contains three integers: A_i, B_i, and L_i

第一行：一个整数 N 。

第二到 N+1 行：第 i+1 行有一个整数 C_i

第 N+2 行到 2*N 行：第 i+N+1 行为 3 个整数：A_i,B_i 和 L_i。

输出格式：

* Line 1: The minimum inconvenience possible

第一行：一个值，表示最小的不方便值。

输入输出样例

1
2
3
4
5
6
7
8
9
10
5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3
1
15

题解

简单树形dp中up and down的运用。

假设我们知道一个子树大小和距离和，向他的父亲贡献的答案除了已知的距离和只需要再加上到父亲那条边的长度乘上子树大小。

于是我们知道了一个有根树每个点其子树的距离和，这时候要把它转无根树，使每个点都作为根 算一遍会超时，因此考虑容斥O1转移。

因此:

设1为根（可选任意点）

设

表示i子树内距离和，

表示子树内的牛数。

时间复杂度

请注意开Long Long！！

而且注意极大值够大，毒瘤

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ll long long
ll head[maxn] , c[maxn] , cnt , n , f[maxn] , sz[maxn];
struct edge{
	ll next , to , dis;
}e[maxn*2];
inline void add(ll x , ll y , ll dis)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].dis = dis;
	head[x] = cnt;
}
void up(ll x , ll fx)
{
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == fx)	continue;
		up(v , x);
		c[x] += c[v];
		f[x] += f[v] + c[v] * e[i].dis;
	}
}
void down(ll x , ll fx)
{
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == fx)	continue;
		f[v] = (f[x] - 1ll * c[v] * e[i].dis) + 1ll*(c[1] - c[v]) * e[i].dis;
		down(v , x);
	}
}
int main()
{
	scanf("%lld",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%lld",&c[i]);
	int x , y , d;
	for(int i = 1 ; i <= n-1 ; ++i)
		scanf("%lld%lld%lld",&x,&y,&d) , add(x,y,d) , add(y,x,d);
	up(1,1);
	down(1,1);
	ll ans = 0x7fffffffffff;
	for(int i = 1 ; i <= n ; ++i)
		ans = std::min(ans , f[i]);
	printf("%lld",ans);
}

[POI2008]STA-Station

题目描述

The first stage of train system reform (that has been described in the problem Railways of the third stage of 14th Polish OI.

However, one needs not be familiar with that problem in order to solve this task.) has come to an end in Byteotia. The system consists of bidirectional segments of tracks that connect railway stations. No two stations are (directly) connected by more than one segment of tracks.

Furthermore, it is known that every railway station is reachable from every other station by a unique route. This route may consist of several segments of tracks, but it never leads through one station more than once.

The second stage of the reform aims at developing train connections.

Byteasar count on your aid in this task. To make things easier, Byteasar has decided that:

one of the stations is to became a giant hub and receive the glorious name of Bitwise, for every other station a connection to Bitwise and back is to be set up, each train will travel between Bitwise and its other destination back and forth along the only possible route, stopping at each intermediate station.

It remains yet to decide which station should become Bitwise. It has been decided that the average cost of travel between two different stations should be minimal.

In Byteotia there are only one-way-one-use tickets at the modest price of img bythaler, authorising the owner to travel along exactly one segment of tracks, no matter how long it is.

Thus the cost of travel between any two stations is simply the minimum number of tracks segments one has to ride along to get from one stations to the other.

Task Write a programme that:

reads the description of the train system of Byteotia, determines the station that should become Bitwise, writes out the result to the standard output.

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 ，

输入输出格式

输入格式：

一棵树

输出格式：

一个点

输入输出样例

输入样例#1：

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

输出样例#1：

1
7

题解

好水的一道POI的题啊。D1T1难度

显然题目要求一个

的做法。

然后在图上画一棵树，会发现：

如果选中一个点作为根算出深度和，那么设这个点儿子之一为v，

表示在这个根下的子树大小，当前深度和为S

那么对于这个v的深度和我们可以O(1)计算：

于是两边dfs就解决了。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
int head[maxn] , cnt , n , g[maxn] , p ;
long long sum , ans;
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 pre(int x , int fx)
{
	g[x] = 1;
	for(int i = head[x] ; i ; i = e[i].next)
		if(e[i].to != fx)
			pre(e[i].to , x) , g[x] += g[e[i].to];
}
void dfs1(int x , int fx , int dep)
{
	sum += g[x] * dep;
	for(int i = head[x] ; i ; i = e[i].next)
		if(e[i].to != fx)
			dfs1(e[i].to , x , dep + 1);
}
void dfs2(int x , int fx , long long cur)
{
	if(cur > ans){
		ans = cur;
		p = x;
	}
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == fx)	continue;
		dfs2(v , x , cur - g[v] + (n - g[v]));
	}
}
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n - 1 ; ++i){
		int x, y;
		scanf("%d%d",&x,&y);
		add(x,y) , add(y,x);
	}
	pre(1,0);
	dfs1(1,1,0);
	dfs2(1,1,sum);
	printf("%d",p);
}

[USACO17DEC]Barn Painting

题意翻译

题意：给定一颗N个节点组成的树，3种颜色，其中K个节点已染色，要求任意两相邻节点颜色不同，求合法染色方案数。 翻译贡献者：Il_ItzABC_lI

题目描述

Farmer John has a large farm with NN barns (1 \le N \le 10^51≤N≤105), some of which are already painted and some not yet painted. Farmer John wants to paint these remaining barns so that all the barns are painted, but he only has three paint colors available. Moreover, his prize cow Bessie becomes confused if two barns that are directly reachable from one another are the same color, so he wants to make sure this situation does not happen.

It is guaranteed that the connections between the NN barns do not form any ‘cycles’. That is, between any two barns, there is at most one sequence of connections that will lead from one to the other.

How many ways can Farmer John paint the remaining yet-uncolored barns?

输入输出格式

输入格式：

The first line contains two integers NN and KK (0 \le K \le N0≤K≤N), respectively the number of barns on the farm and the number of barns that have already been painted.

The next N-1N−1 lines each contain two integers xx and yy (1 \le x, y \le N, x \neq y1≤x,y≤N,x≠y) describing a path directly connecting barns xx and yy.

The next KK lines each contain two integers bb and cc (1 \le b \le N1≤b≤N, 1 \le c \le 31≤c≤3) indicating that barn bb is painted with color cc.

输出格式：

Compute the number of valid ways to paint the remaining barns, modulo 10^9 + 7109+7, such that no two barns which are directly connected are the same color.

输入输出样例

输入样例#1：

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

输出样例#1：

1
8

题解

一道普通组合树形dp，D1T2难度。

所以我又被卡了n次。。唉。注意dp的数组初始值是否合适。

设：

表示子树u在u染颜色c的时候方案数。

转移原始形式是所有子树每个颜色的卷积，复杂度会爆炸。

然后通过严密的证明灵敏的眼睛我们发现其实是子树的颜色和相乘，可以自己试着把下面的公式展开就明白了。

时间复杂度

实现注意细节问题！！（每次出这种问题我就担心我的联赛）

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100005
#define mod 1000000007
int head[maxn] , cnt , n , m , vis[maxn];
long long f[maxn][4];
struct edge{
	int next , to;
}e[maxn*2];
//void dfs(int x , int fx)
//{
//	if(vis[x]){
//		f[x][vis[x]] = 1;
//		for(int i = head[x] ; i ; i = e[i].next){
//			if(e[i].to != fx){
//				dfs(e[i].to , x);
//				long long sum = 0;
//				for(int j = 1 ; j <= 3 ; ++j){
//					if(j != vis[x] && f[e[i].to][j] != -1)
//						(sum += f[e[i].to][j]) %= mod;
//					(f[x][vis[x]] *= sum) %= mod;
//				}
//			}
//		}
//	}
//	else{
//		for(int i = 1 ; i <= 3 ; ++i)
//			f[x][i] = 1;
//		for(int i = head[x] ; i ; i = e[i].next){
//			if(e[i].to != fx){
//				dfs(e[i].to , x);
//				for(int j = 1 ; j <= 3 ; ++j){
//					long long sum = 0;
//					for(int k = 1 ; k <= 3 ; ++k)
//						if(k != j && f[e[i].to][k] != -1)	(sum += f[e[i].to][k]) %= mod;
//					(f[x][j] *= sum) %= mod;
//				}
//					
//			}
//		}
//	}
//}
long long dp(int x , int c , int fx)
{
	if(f[x][c] != -1)	return f[x][c];
	f[x][c] = 1;
	if(vis[x] && vis[x] != c) return f[x][c] = 0;
	for(int i = head[x] ; i ; i = e[i].next)	
		if(e[i].to != fx){
			long long sum = 0;
			for(int j = 1 ; j <= 3 ; ++j)
				if(j != vis[x] && j != c)
					sum += dp(e[i].to , j , x) , sum %= mod;
			f[x][c] = (f[x][c] * sum) % mod;
		}
	return f[x][c];
}
inline void add(int x , int y)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
int main()
{
//	freopen("colors.in","r",stdin);
	std::memset(f,-1,sizeof(f));
	scanf("%d%d",&n,&m);
	int x , y;
	for(int i = 1 ; i <= n-1 ; ++i)
		scanf("%d%d",&x,&y) , add(x,y) , add(y,x);
	for(int i = 1 ; i <= m ; ++i){
		scanf("%d%d",&x,&y);
		vis[x] = y;
	}
	long long ans = 1ll*(dp(1,1,1)+dp(1,2,1)+dp(1,3,1))%mod;
	printf("%lld",ans);
}

上面那个不返回值的dfs我也不知道怎么就挂了。。

[USACO17DEC]Haybale Feast

题意翻译

题意：给定2个由N个数字组成的数列F,S,需要找到使得

并输出在所有满足条件的i,j中，

的最小值。

题目描述

Farmer John is preparing a delicious meal for his cows! In his barn, he has NN haybales (1 \le N \le 100,0001≤N≤100,000). The iith haybale has a certain flavor F_iFi (1 \le F_i \le 10^91≤Fi≤109) and a certain spiciness S_iSi (1 \le S_i \le 10^91≤Si≤109).

The meal will consist of a single course, being a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all haybales in the interval.

Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least MM (1 \le M \le 10^{18}1≤M≤1018).

输入输出格式

输入格式：

The first line contains the integers NN and MM, the number of haybales and the minimum total flavor the meal must have, respectively. The next NN lines describe the NN haybales with two integers per line, first the flavor FF and then the spiciness SS.

输出格式：

Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 10
4 10
6 15
3 5
4 9
3 6

输出样例#1：

1
9

题解

这道题是一个很有用的算法：Two Pointer，也称为双指针算法。

这题最重要的条件之一是F数组中都是正整数，这意味着前缀和单调不降，我们可以使用双指针算法来处理区间和大于等于M这个问题。

让R移动到区间[L,R]的和大于M，然后再让L向右移动处理出所有以R为结尾区间和大于M的区间。

指针移动的同时维护同样区间的单调队列，确保队首在[L,R]之间，队列元素单调上升。在合法区间中每次

更新答案。

让我们分析一下时间复杂度：
对于双指针：L，R在单调的序列上单调不向左的移动，并且每次总是会改变，因此最多

对于单调队列：每个元素入队一次出队一次，时间复杂度为

尽管是循环嵌套，但是实际上它们的运行次数是独立并行的，因此最终的时间复杂度为

可以轻松通过本题。

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>
#include <queue>
#define maxn 100005
#define LL long long
LL n , f[maxn] , g[maxn] , s[maxn] , M , ans = 0x7ffffffff;
std::deque<int> q;
int main()
{
//	freopen("TwoPointer.in","r",stdin);
	scanf("%lld%lld",&n,&M);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%lld%lld",&f[i],&g[i]);
	for(int i = 1 ; i <= n ; ++i)
		s[i] = s[i-1] + f[i];
	int L = 1 , R = 1;
	q.push_back(1);
	while(true){
		if(R > n && s[R] - s[L-1] < M)	break;
		while(s[R] - s[L-1] < M && R <= n){
			++R;
			while(!q.empty() && g[q.back()] < g[R]) q.pop_back();
			q.push_back(R);
		}
		while(s[R] - s[L-1] >= M){
			while(!q.empty() && q.front() < L)	q.pop_front();
			if(!q.empty())	ans = std::min(ans , g[q.front()]);
			++L;
		}
	}
	printf("%lld",ans);
}

[USACO13MAR]农场的画Farm Painting

题目描述

After several harsh winters, Farmer John has decided it is time to re-paint his farm. The farm consists of N fenced enclosures (1 <= N <= 50,000), each of which can be described by a rectangle in the 2D plane whose sides are parallel to the x and y axes. Enclosures may be contained within other enclosures, but no two fences intersect, so if two enclosures cover the same area of the 2D plane, one must be contained within the other.

FJ figures that an enclosure contained within another enclosure will not be visible to the outside world, so he only wants to re-paint enclosures that are themselves not contained within any other enclosures. Please help FJ determine the total number of enclosures he needs to paint.

经过几个严冬，农场主约翰决定是重新粉刷农场的时候了。该农场由n个围栏围成（1<=n=500001<=n=50000），每一个都可以用二维平面上的矩形来描述，其两侧平行于x和y轴。牛圈可能包含在其他牛圈中，但没有两个栅栏相交（不同牛圈的边不会有接触）。因此如果两个牛圈覆盖了二维平面的同一区域，那么一个必须包含在另一个内。

FJ知道，被其他牛圈包含的牛圈是不会被外面的人看到的。众所周知，FJ非常懒，所以他只想刷露在外面的牛圈，请帮助他求出总共需要刷的牛圈的个数。

输入输出格式

输入格式：

* Line 1: The number of enclosures, N.

* Lines 2..1+N: Each line describes an enclosure by 4 space-separated integers x1, y1, x2, and y2, where (x1,y1) is the lower-left corner of the enclosure and (x2,y2) is the upper-right corner. All coordinates are in the range 0..1,000,000.

第一行 一个数，牛圈的总数nn

第二到n+1n+1行 每行四个数，起点坐标x1,y1x1,y1和终点坐标x2,y2x2,y2

输出格式：

* Line 1: The number of enclosures that are not contained within other enclosures.

FJ总共需要刷的牛圈的个数

输入输出样例

输入样例#1：

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

输出样例#1：

1
2

说明

There are three enclosures. The first has corners (2,0) and (8,9), and so on.

Enclosure 3 is contained within enclosure 1, so there are two enclosures not contained within other enclosures.

题解

一开始想直接离散化+2D BIT，发现空间不行。

然后yy一下CDQ分治什么的（反正也不会）。

然后发现这道题扫描线+BIT差分随便做233

我们来看看一个矩形被包含的充分条件是什么：画图

发现假如我们的扫描线是x正半轴方向，只要一条左边界线段查询树状数组有值没有被右边界取消时效性，那么这个矩形就是被包含的。

扫描线大概NOIp前就做这么多了，除非有比较难的。

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
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 50005
int bit[maxn<<1] , n , x1 , x2 , y1 , y2 , tot , segs , cnt , ans;
struct Seg{
	int l , r , v , type;
	bool operator < (const Seg& x)const {
		return v < x.v;
	}
}p[maxn<<1];
struct Node{
	int v , type ,k;
	bool operator < (const Node& x)const{
		return v < x.v;
	}
}g[maxn<<2];
inline int query(int x){
	if(!x)	return 0;
	int ans = 0;
	for(int i = x ; i ; i -= (i & -i))
		ans += bit[i];
	return ans;
}
inline void update(int x , int v){
	for(int i = x ; i <= tot ; i += (i & -i))
		bit[i] += v;
}
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		p[++segs].l = y1 , p[segs].r = y2 , p[segs].v = x1 , p[segs].type = 0;
		p[++segs].l = y1 , p[segs].r = y2 , p[segs].v = x2 , p[segs].type = 1;
	}
	std::sort(p+1,p+segs+1);
	for(int i = 1 ; i <= segs ; ++i){
		int l = p[i].l , r = p[i].r;
		g[++cnt].v = l , g[cnt].type = 0 , g[cnt].k = i;
		g[++cnt].v = r , g[cnt].type = 1 , g[cnt].k = i;
	}
	std::sort(g+1,g+cnt+1);
	g[0].v = 19260817;
	for(int i = 1 ; i <= cnt ; ++i){
		int v = g[i].v , t = g[i].type;
		if(v == g[i-1].v){
			if(g[i].type)	p[g[i].k].r = tot;
			else p[g[i].k].l = tot;
		}
		else{
			if(g[i].type)	p[g[i].k].r = ++tot;
			else p[g[i].k].l = ++tot;
		}
	}
//	for(int i = 1 ; i <= segs ; ++i)
//		printf("%d %d %d\n",p[i].l,p[i].r,p[i].type);
	for(int i = 1 ; i <= segs ; ++i)
	{
		if(p[i].type){
			update(p[i].l , -1) , update(p[i].r + 1, 1);
			continue;
		}
		bool isCover = (query(p[i].l) && query(p[i].r));
		if(!isCover)	++ans;
		update(p[i].l , 1) , update(p[i].r + 1 , -1);
	}
	printf("%d",ans);
}