Post 30

Veröffentlicht am | Edited on

[USACO07MAR]牛交通Cow Traffic

题目描述

The bovine population boom down on the farm has caused serious congestion on the cow trails leading to the barn. Farmer John has decided to conduct a study to find the bottlenecks in order to relieve the ‘traffic jams’ at milking time.

The pasture contains a network of M (1 ≤ M ≤ 50,000) one-way trails, each of which connects exactly two different intersections from the set of N (1 ≤ N ≤ 5,000) intersections conveniently numbered 1..N; the barn is at intersection number N. Each trail connects one intersection point to another intersection point with a higher number. As a result, there are no cycles and, as they say on the farm, all trails lead to the barn. A pair of intersection points might be connected by more than one trail.

During milking time rush hour, the cows start from their respective grazing locations and head to the barn. The grazing locations are exactly those intersection points with no trails connecting into them. Each cow traverses a ‘path’, which is defined as a sequence of trails from a grazing location to the barn.

Help FJ finding the busiest trail(s) by computing the largest number of possible paths that contain any one trail. The answer is guaranteed to fit in a signed 32-bit integer.

输入输出格式

输入格式：

Line 1: Two space-separated integers: N and M.

Lines 2..M+1: Two space-separated intersection points.

输出格式：

Line 1: The maximum number of paths passing through any one trail.

输入输出样例

输入样例#1：

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

输出样例#1：

1
4

说明

Here are the four possible paths that lead to the barn:

1 3 4 6 7

1 3 5 6 7

2 3 4 6 7

2 3 5 6 7

题解

做出这道题的关键在于不要被luogu的沙雕翻译影响，自己读一遍英文题面。

这道题的意思是问你对于一条边的价值定义为被包含在从入度为0的点到n的路径中的数量，求这个最大价值。

这种边的问题显然尽可能转化成关于点的问题比较好求，比如说这道题：[HAOI2012]道路

他们都通过巧妙的组合原理把对边统计转化成了对点统计。

显然这题简单的多，对于一条边就是到边起点的数量乘上到终点的数量。

（又去看了看道路那道题感觉还是挺难）

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 <vector>
#include <queue>
#define maxn 100005
int n , m , d1[maxn] , d2[maxn] , fr[maxn] , to[maxn] , f[maxn] , w[maxn];
std::vector<int> g[maxn] , r[maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= m ; ++i)
	{
		scanf("%d%d",&fr[i],&to[i]);
		g[fr[i]].push_back(to[i]);
		++d1[to[i]];
		r[to[i]].push_back(fr[i]);
		++d2[fr[i]];
	}
	std::queue<int> q;
	for(int i = 1 ; i <= n ; ++i)
		if(!d1[i]) q.push(i) , f[i] = 1;
	for( ; q.size() ; q.pop())
	{
		int k = q.front();
		for(int i = 0 ; i < (int)g[k].size() ; ++i)
		{
			int v = g[k][i];
			f[v] += f[k];
			if(!(--d1[v])) q.push(v);
		}
	}

	while(!q.empty()) q.pop();
	for(int i = 1 ; i <= n ; ++i)
		if(!d2[i]) q.push(i) , w[i] = 1;
	for( ; q.size() ; q.pop())
	{
		int k = q.front();
		for(int i = 0 ; i < (int) r[k].size() ; ++i)
		{
			int v = r[k][i];
			w[v] += w[k];
			if(!(--d2[v])) q.push(v);
		}
	}

	long long ans = -0x7fffffff;
	for(int i = 1 ; i <= m ; ++i)
		ans = std::max(ans , 1ll * f[fr[i]] * w[to[i]]);
	printf("%lld\n",ans);
}

[POI2005]AUT-The Bus

题目描述

The streets of Byte City form a regular, chessboardlike network - they are either north-south or west-east directed. We shall call them NS- and WE-streets. Furthermore, each street crosses the whole city. Every NS-street intersects every WE- one and vice versa. The NS-streets are numbered from 11 to nn, starting from the westernmost. The WE-streets are numbered from 11 to mm, beginning with the southernmost. Each intersection of the ii’th NS-street with the jj’th WE-street is denoted by a pair of numbers (i,j)(i,j) (for 1\le i\le n1≤i≤n, 1\le j\le m1≤j≤m).

There is a bus line in Byte City, with intersections serving as bus stops. The bus begins its itinerary by the (1,1)(1,1)intersection, and finishes by the (n,m)(n,m) intersection. Moreover, the bus may only travel in the eastern and/or northern direction.

There are passengers awaiting the bus by some of the intersections. The bus driver wants to choose his route in a way that allows him to take as many of them as possible. (We shall make an assumption that the interior of the bus is spacious enough to take all of the awaiting passengers, regardless of the route chosen.)TaskWrite a programme which:

reads from the standard input a description of the road network and the number of passengers waiting at each intersection,finds, how many passengers the bus can take at the most,writes the outcome to the standard output.

Byte City 的街道形成了一个标准的棋盘网络 – 他们要么是北南走向要么就是西东走向. 北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m). Byte City里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)结束.公交车只能往北或往东走. 现在有一些乘客在某些站点等车. 公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.

输入输出格式

输入格式：

The first line of the standard input contains three positive integers nn, mm and kk - denoting the number of NS-streets, the number of WE-streets and the number of intersections by which the passengers await the bus, respectively (1\le n\le 10^91≤n≤109, 1\le m\le 10^91≤m≤109, 1\le k\le 10^51≤k≤105).

The following kk lines describe the deployment of passengers awaiting the bus, a single line per intersection. In the (i+1)(i+1)’st line there are three positive integers x_ixi, y_iyi and p_ipi, separated by single spaces, 1\le x_i\le n1≤xi≤n,1\le y_i\le m1≤yi≤m,1\le p_i\le 10^61≤pi≤106 . A triplet of this form signifies that by the intersection(x_i,y_i)p_i(xi,yi)pi passengers await the bus. Each intersection is described in the input data once at the most. The total number of passengers waiting for the bus does not exceed 1\ 000\ 000\ 0001 000 000 000.

输出格式：

Your programme should write to the standard output one line containing a single integer - the greatest number of passengers the bus can take.

输入输出样例

输入样例#1：

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

输出样例#1：

1
11

题解

很水的二维偏序。

这告诉我们闲着没事画图。

想到二维偏序是因为扫描线的思想。

恩，所以问题就变成了一个带权的LIS（我一开始没看到带权，打了个贪心美滋滋）

然后我们可以用长时间的经验套路出一个dp状态：设$f_i$为以$i$为结尾的前$i$个的最大值（我一直觉得这个状态相当套路，不过非常正确233）

$f_i = max\{f_j\}+v_j $

$x_j \leq x_i , y_j \leq y_i $

然后我们用线段树优化转移就可以以$O(klogk)$的复杂度通过本题。

话说sb洛谷数据都写错，明明比1e5要大，害我浪费了几分钟。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
struct Node{
	int x , y , v;
	bool operator<(const Node& t)const{
		if(x == t.x) return y < t.y;
		return x < t.x;
	}	
}p[maxn];
int n , pos , a ,r , seg[maxn] , tot , h[maxn] , v[maxn] , f[maxn];

inline void update(int p , int v)
{
	p += pos;
	seg[p] = std::max(seg[p] , v);
	for(p >>= 1 ; p ; p >>= 1) seg[p] = std::max(seg[p<<1] , seg[p<<1|1]);
}

inline int query(int l , int r)
{
	int ans = 0;
	for(l = l + pos - 1 , r = r + pos + 1 ; l ^ r ^ 1 ; l >>= 1 , r >>= 1)
	{
		if(~l&1) ans = std::max(ans , seg[l^1]);
		if(r&1) ans = std::max(ans , seg[r^1]);
	}
	return ans;
}
struct Data{
	int v , k;
	bool operator<(const Data& x)const{
		return v < x.v;
	}
}t[maxn];
int main()
{
	scanf("%d%d%d",&a,&r,&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v);
	std::sort(p+1,p+n+1);
	for(int i = 1 ; i <= n ; ++i)
		t[i].v = p[i].y , t[i].k = i;
	std::sort(t+1,t+n+1);
//	t[0].v = 3154651;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(t[i].v == t[i-1].v) h[t[i].k] = tot;
		else h[t[i].k] = ++tot;
	}
	for(int i = 1 ; i <= n ; ++i)
		v[i] = p[i].v;

	for(pos = 1 ; pos < tot ; pos <<= 1);
	
	int ans = -0x7ffffff;
	for(int i = 1 ; i <= n ; ++i)
	{	
		f[i] = query(1,h[i]) + v[i];
		ans = std::max(ans , f[i]);
		update(h[i] , f[i]);
	}
	printf("%d\n",ans);
}

CF86D Powerful array

题意翻译

题意：给出一个n个数组成的数列a，有t次询问，每次询问为一个[l,r]的区间，求区间内每种数字出现次数的平方×数字的值 的和。

输入：第一行2个正整数n,t。

接下来一行n个正整数，表示数列a_1a1~a_nan的值。

接下来t行，每行两个正整数l,r，为一次询问。

输出：t行，分别为每次询问的答案。

数据范围：1 \leq n,t \leq 2*10^5,1 \leq a_i \leq 10^6,1 \leq l,r \leq n1≤n,t≤2∗105,1≤ai≤106,1≤l,r≤n

题目描述

An array of positive integers a_{1},a_{2},…,a_{n}a1,a2,…,an is given. Let us consider its arbitrary subarray a_{l},a_{l+1}…,a_{r}al,al+1…,ar , where 1<=l<=r<=n1<=l<=r<=n . For every positive integer ss denote by K_{s}Ks the number of occurrences of ss into the subarray. We call the power of the subarray the sum of products K_{s}·K_{s}·sKs⋅Ks⋅s for every positive integer ss . The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.

You should calculate the power of tt given subarrays.

输入输出格式

输入格式：

First line contains two integers nn and tt ( 1<=n,t<=2000001<=n,t<=200000 ) — the array length and the number of queries correspondingly.

Second line contains nn positive integers a_{i}ai ( 1<=a_{i}<=10^{6}1<=ai<=106 ) — the elements of the array.

Next tt lines contain two positive integers ll , rr ( 1<=l<=r<=n1<=l<=r<=n ) each — the indices of the left and the right ends of the corresponding subarray.

输出格式：

Output tt lines, the ii -th line of the output should contain single positive integer — the power of the ii -th query subarray.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).

输入输出样例

输入样例#1：

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

输出样例#1：

复制

1
2
3
6

输入样例#2：

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

输出样例#2：

1
2
3
20
20
20

说明

Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):

img Then K_{1}=3K1=3 , K_{2}=2K2=2 , K_{3}=1K3=1 , so the power is equal to 3^{2}·1+2^{2}·2+1^{2}·3=2032⋅1+22⋅2+12⋅3=20 .

题解

很水但这是我的第一道莫队题。

好像除了边界调了会，其他直接根据原理写不难的。

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 <cmath>
#define maxn 200005
#define maxv 1000005
#define int long long
int v[maxn] , n , f[maxv] , curans , bl , m , ans[maxn];
inline void upd(int x , int ty){
    curans += v[x] + 2 * f[v[x]] * v[x] * ty;
    f[v[x]] += ty;
}

struct Node
{
    int l , r , id;
    bool operator<(const Node& x)const{
        if(l/bl == x.l/bl) return r < x.r;
        return l/bl < x.l/bl;
    }
}q[maxn];
inline void solve()
{
    bl = (int)pow(n,0.5);
    std::sort(q+1,q+m+1);
    int l = 1 , r = 1;
    for(int i = 1 ; i <= m ; ++i)
    {
        while(l > q[i].l) upd(--l , 1);
        while(r < q[i].r) upd(r++ , 1) ;
        while(l < q[i].l) upd(l++ , -1);
        while(r > q[i].r) upd(--r , -1);
        ans[q[i].id] = curans;
    }
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld",&v[i]);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%lld%lld",&q[i].l,&q[i].r) , ++q[i].r ,q[i].id = i;
    solve();
    for(int i = 1 ; i <= m ; ++i)
        printf("%lld\n",ans[i]);
}