bef-> NO.33

Veröffentlicht am

[USACO4.1]麦香牛块Beef McNuggets

题目描述

农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”奶牛们说，“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块，你就不可能满足一次只想买1、2、4、5、7、8、11、14或者17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”

你的任务是帮助这些奶牛。给出包装盒的种类数N(1<=N<=10)和N个代表不同种类包装盒容纳麦香牛块个数的正整数(1<=i<=256)，输出顾客不能用上述包装盒(每种盒子数量无限)买到麦香牛块的最大块数。如果所有购买方案都能得到满足或者不存在不能买到块数的上限，则输出0。 不能买到的最大块数（倘它存在）不超过2,000,000,000。

输入输出格式

输入格式：

第1行: 包装盒的种类数N

第2行到N+1行: 每个种类包装盒容纳麦香牛块的个数

输出格式：

输出文件只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或0(如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限)。

输入输出样例

输入样例#1：

1
2
3
4
3
3
6
10

输出样例#1：

1
17

说明

题目翻译来自NOCOW。

USACO Training Section 4.1

题解

同余最短路瞎跑，也不知怎么就对了

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define maxn 1005
struct Node{
	int v , k;
	bool operator < (const Node& x)const{
		return v < x.v;
	}
};
int p[maxn] , n , d[maxn];
inline void SPDIJ(int s){
	std::priority_queue<Node> q;
	std::memset(d,-1,sizeof(d));
	d[s] = 0;
	q.push((Node){d[s],s});
	while(!q.empty())
	{
		int k = q.top().k;
		q.pop();
		for(int i = 2 ; i <= n ; ++i){
			int v = (k + p[i]) % p[1];
			if(d[v] > d[k] + p[i] || d[v] == -1){
				d[v] = d[k] + p[i];
				q.push((Node){d[v],v});
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	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] == -1){
			puts("0");
			return 0;
		}
	int ans = 0;
	for(int i = 0 ; i < p[1] ; ++i)
		ans = std::max(ans , d[i] - p[1]);
	if(!ans){
		puts("0");
		return 0;
	}
	printf("%d\n",ans);
}

今天可能以结论题，数学/数论题为主

上午对着LNOI那道黑题想了一上午，血亏的感觉。。下午做做NOIp剩下的原题和USACO的题吧（天天爱跑步这种也属于神题，考场出了暴力都不一定对）

[USACO15DEC]最大流Max Flow

题目描述

Farmer John has installed a new system of N-1N−1 pipes to transport milk between the NN stalls in his barn (2 \leq N \leq 50,0002≤N≤50,000), conveniently numbered 1 \ldots N1…N. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between KK pairs of stalls (1 \leq K \leq 100,0001≤K≤100,000). For the iith such pair, you are told two stalls s_isi and t_iti, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the KK paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from s_isi to t_iti, then it counts as being pumped through the endpoint stalls s_isi and

t_iti, as well as through every stall along the path between them.

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

输入输出格式

输入格式：

The first line of the input contains NN and KK.

The next N-1N−1 lines each contain two integers xx and yy (x \ne yx≠y) describing a pipe

between stalls xx and yy.

The next KK lines each contain two integers ss and tt describing the endpoint

stalls of a path through which milk is being pumped.

输出格式：

An integer specifying the maximum amount of milk pumped through any stall in the

barn.

输入输出样例

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

题解

随手花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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int head[maxn] , cnt , n , c[maxn] , x , y , k , f[maxn] , top[maxn] , sz[maxn] , hs[maxn] , dep[maxn];
struct edge{
	int next , to;
}e[maxn*2];
void dfs1(int x , int fx)
{
	f[x] = fx;
	dep[x] = dep[fx] + 1;
	sz[x] = 1;
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == fx)	continue;
		dfs1(v , x);
		sz[x] += sz[v];
		if(sz[v] > sz[hs[x]])	hs[x] = v;
	}
}
void dfs2(int x , int topv){
	top[x] = topv;
	if(!hs[x])	return ;
	dfs2(hs[x] , topv);
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == f[x] || v == hs[x])	continue;
		dfs2(v , v);
	}
}
int LCA(int x , int y)
{
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])	std::swap(x,y);
		x = f[top[x]];
	}
	if(dep[x] > dep[y])	std::swap(x,y);
	return x;
}
void getDif(int x , int fx)
{
	for(int i = head[x] ; i ; i = e[i].next){
		if(e[i].to != fx)
			getDif(e[i].to , x)	, c[x] += c[e[i].to];
	}
}
inline void add(int x , int y)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1 ; i <= n -1 ; ++i)	
		scanf("%d%d",&x,&y) , add(x,y) , add(y,x);
	dfs1(1,1);
	dfs2(1,1);
	int x , y;
	for(int i = 1 ; i <= k ; ++i){
		scanf("%d%d",&x,&y);
		++c[x] , ++c[y] , --c[LCA(x,y)] , --c[f[LCA(x,y)]];
	}
	getDif(1,1);
	int ans = -0x7ffffff;
	for(int i = 1 ; i <= n ; ++i)
		ans = std::max(ans , c[i]);
	printf("%d",ans);
}

[AHOI2005]航线规划

题目描述

对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。

星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编号1、2、3……。

一些先遣飞船已经出发，在星球之间开辟探险航线。

探险航线是双向的，例如从1号星球到3号星球开辟探险航线，那么从3号星球到1号星球也可以使用这条航线。

例如下图所示：

img

在5个星球之间，有5条探险航线。

A、B两星球之间，如果某条航线不存在，就无法从A星球抵达B星球，我们则称这条航线为关键航线。

显然上图中，1号与5号星球之间的关键航线有1条：即为4-5航线。

然而，在宇宙中一些未知的磁暴和行星的冲撞，使得已有的某些航线被破坏，随着越来越多的航线被破坏，探险飞船又不能及时回复这些航线，可见两个星球之间的关键航线会越来越多。

假设在上图中，航线4-2（从4号星球到2号星球）被破坏。此时，1号与5号星球之间的关键航线就有3条：1-3，3-4，4-5。

小联的任务是，不断关注航线被破坏的情况，并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

输入输出格式

输入格式：

第一行有两个整数N，M。表示有N个星球（1< N < 30000），初始时已经有M条航线（1 < M < 100000）。随后有M行，每行有两个不相同的整数A、B表示在星球A与B之间存在一条航线。接下来每行有三个整数C、A、B。C为1表示询问当前星球A和星球B之间有多少条关键航线；C为0表示在星球A和星球B之间的航线被破坏，当后面再遇到C为1的情况时，表示询问航线被破坏后，关键路径的情况，且航线破坏后不可恢复； C为-1表示输入文件结束，这时该行没有A,B的值。被破坏的航线数目与询问的次数总和不超过40000。

输出格式：

对每个C为1的询问，输出一行一个整数表示关键航线数目。

输入输出样例

输入样例#1：

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

输出样例#1：

1
2
1
3

说明

我们保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。

题解

思维难度较高，实现复杂度很大，适合作为NOIp D2T3，这里说下思路。

由于太菜不会LCT，显然动态删边不会，因此就倒着来做。

  • 将需要被删除的边先标记下

  • Tarjan求出所有边双连通分量，然后将图缩点成树

  • 树链剖分。边对应点。初始点权均为1表示都是割边
  • 开始倒着查询，到了修改只需要将边两边的点在树上的链全变成0，表示不再是割边，查询只需要查询两点间的值

这道题就做完了，由于时间关系，考虑我现在的水平做这题考场出了也做不出来。

[USACO13DEC]最优挤奶Optimal Milking

题目描述

Farmer John has recently purchased a new barn containing N milking machines (1 <= N <= 40,000), conveniently numbered 1..N and arranged in a row.

Milking machine i is capable of extracting M(i) units of milk per day (1 <= M(i) <= 100,000). Unfortunately, the machines were installed so close together that if a machine i is in use on a particular day, its two neighboring machines cannot be used that day (endpoint machines have only one neighbor, of course). Farmer John is free to select different subsets of machines to operate on different days.

Farmer John is interested in computing the maximum amount of milk he can extract over a series of D days (1 <= D <= 50,000). At the beginning of each day, he has enough time to perform maintenance on one selected milking machine i, thereby changing its daily milk output M(i) from that day forward. Given a list of these daily modifications, please tell Farmer John how much milk he can produce over D days (note that this number might not fit into a 32-bit integer).

FJ最近买了1个新仓库, 内含N 个挤奶机,1 到N 编号并排成一行。

挤奶机i 每天能产出M(i) 单位的奶。不幸的是, 机器装得太近以至于如果一台机器i 在某天被使用, 那与它相邻的两台机器那一天不能被使用

(当然, 两端点处的机器分别只有一个与之相邻的机器)。

FJ 可自由选择不同的机器在不同的日子工作。

FJ感兴趣于计算在D 天内他能产出奶的最大值。在每天开始时, 他有足够的时间维护一个选中的挤奶机i, 从而改变它从那天起的每日产奶量M(i)。

给出这些每日的修改,请告诉FJ他D 天中能产多少奶。

输入输出格式

输入格式：

* Line 1: The values of N and D.

* Lines 2..1+N: Line i+1 contains the initial value of M(i).

* Lines 2+N..1+N+D: Line 1+N+d contains two integers i and m,

indicating that Farmer John updates the value of M(i) to m at the beginning of day d.

输出格式：

* Line 1: The maximum total amount of milk FJ can produce over D days.

输入输出样例

输入样例#1：

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

输出样例#1：

1
32

说明

There are 5 machines, with initial milk outputs 1,2,3,4,5. On day 1, machine 5 is updated to output 2 unit of milk, and so on.

On day one, the optimal amount of milk is 2+4 = 6 (also achievable as 1+3+2). On day two, the optimal amount is 7+4 = 11. On day three, the optimal amount is 10+3+2=15.

题意简述：给定n个点排成一排，每个点有一个点权，多次改变某个点的点权并将最大点独立集计入答案，输出最终的答案

题解

想到了线段树但是一开始没想出来怎么维护。。。一开始只维护左边选右边不选和右边选左边不选，结果pushup发现有些情况不对，然后又加上两边都不选和两边都选就行了。

这个题最重要的有这么几点

  • 所有数非负，本题最重要的条件之一，这意味着我们可以贪心地选取尽量长的，能带上端点就带上。
  • 假如有时候我们发现子问题无法很好的转移或合并，牺牲一定的时间复杂度附加维护更多的信息也许是很正确的选择，本题中仅仅增加了一点常数。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ll long long
#define max(a,b) (a) > (b) ? (a) : (b)
int n , p[maxn] , d;
ll ans;
struct SegmentTree
{
	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)
	ll f[maxn<<2] , g[maxn<<2] , h[maxn<<2] , t[maxn<<2];//both , left , right , none
	inline void pushup(int Node){
		t[Node] = max(h[ls(Node)] + t[rs(Node)] , g[rs(Node)] + t[ls(Node)]);
		h[Node] = max(f[rs(Node)] + t[ls(Node)] , h[rs(Node)] + h[ls(Node)]);
		g[Node] = max(f[ls(Node)] + t[rs(Node)] , g[ls(Node)] + g[rs(Node)]);
		f[Node] = max(f[ls(Node)] + h[rs(Node)] , f[rs(Node)] + g[ls(Node)]);
	}
	void build(int l , int r , int Node)
	{
		if(l == r){
			f[Node] = p[l];
			return;
		}
		int mid = l + r >> 1;
		build(l , mid , ls(Node)); 
		build(mid + 1 , r , rs(Node));
		pushup(Node);
	}
	void update(int pos , int l , int r , int Node , int v)
	{
		if(l == r){
			f[Node] = v;
			p[l] = v;
			return;
		}
		int mid = l + r >> 1;
		if(pos <= mid)	update(pos , l , mid , ls(Node) , v);
		if(pos > mid)		update(pos , mid + 1 , r , rs(Node) , v);
		pushup(Node);
	}
	ll query(){
		ll ans = 0;
//		printf("%lld %lld %lld %lld\n",f[1],g[1],h[1],t[1]);
		ans = max(ans , max(f[1],g[1]));
		ans = max(ans , max(h[1],t[1]));
		return ans;
	}
}tr;
int main()
{
	scanf("%d%d",&n,&d);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]);
	tr.build(1,n,1);
	for(int i = 1 ; i <= d ; ++i){
		int x , y;
		scanf("%d%d",&x,&y);
		tr.update(x,1,n,1,y);
		ans += tr.query();
	}
	printf("%lld",ans);
}

[TJOI2007]线段

题目描述

在一个 n*n 的平面上，在每一行中有一条线段，第 i 行的线段的左端点是(i, L(i))，右端点是(i, R(i))，其中 1 ≤ L(i) ≤ R(i) ≤ n。

你从(1, 1)点出发，要求沿途走过所有的线段，最终到达(n, n)点，且所走的路程长度要尽量短。

更具体一些说，你在任何时候只能选择向下走一步（行数增加 1）、向左走一步（列数减少 1）或是向右走一步（列数增加 1）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。

输入输出格式

输入格式：

输入文件的第一行有一个整数 n，以下 n 行，在第 i 行（总第(i+1)行）的两个整数表示

L(i)和 R(i)。

输出格式：

输出文件仅包含一个整数，你选择的最短路程的长度。

输入输出样例

输入样例#1：

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

输出样例#1：

1
24

说明

我们选择的路线是

1
2
3
4
5
6
(1,1) (1,6)
 (2,6) (2, 3)
 (3, 3) (3, 1)
 (4, 1) (4, 2)
 (5, 2) (5, 6)
 (6, 6) (6, 4) (6, 6)

不难计算得到，路程的总长度是 24。 100%的数据中，n ≤ 20 000。

题解

这种是最套路的dp了。。然后我一开始还WA了。。。

一开始我设的

表示前i行到左/右端点最小值，然后转移加上上一条线段的长度什么的，结果挂了。

然后换成包括当前行就好转移了一点，就过了。。

难度低于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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 500005
int l[maxn] , r[maxn] , n , f[maxn][2];
int abs(int x){
	return x >= 0 ? x : (-x);
}
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&l[i],&r[i]);
	std::memset(f,0x7f,sizeof(f));
	f[1][0] = r[1] - 1 + r[1] - l[1] , f[1][1] = r[1] - 1;
	for(int i = 2 ; i <= n ; ++i){
		f[i][0] = std::min(f[i-1][0] + abs(l[i-1] - r[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - r[i]) + r[i] - l[i] + 1),
    	f[i][1] = std::min(f[i-1][0] + abs(l[i-1] - l[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - l[i]) + r[i] - l[i] + 1);
	}
	
	printf("%d",std::min(f[n][0] + abs(n - l[n]), f[n][1] + abs(n - r[n])));
	
}

[USACO08DEC]在农场万圣节Trick or Treat on the Farm

题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

输入格式

第1行 整数n。

第2行到n+1行 每行包含一个整数 next_i 。

输出格式

n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。

样例解释

有4个隔间

隔间1要求牛到隔间1

隔间2要求牛到隔间3

隔间3要求牛到隔间2

隔间4要求牛到隔间3

牛1，从1号隔间出发，总共访问1个隔间；

牛2，从2号隔间出发，然后到三号隔间，然后到2号隔间，终止，总共访问2个隔间；

牛3，从3号隔间出发，然后到2号隔间，然后到3号隔间，终止，总共访问2个隔间；

牛4，从4号隔间出发，然后到3号隔间，然后到2号隔间，然后到3号隔间，终止，总共访问3个隔间。

翻译提供者：吃葡萄吐糖

题目描述

Every year in Wisconsin the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N (1 <= N <= 100,000) stalls conveniently numbered 1..N.

Because the barn is not so large, FJ makes sure the cows extend their fun by specifying a traversal route the cows must follow. To implement this scheme for traveling back and forth through the barn, FJ has posted a ‘next stall number’ next_i (1 <= next_i <= N) on stall i that tells the cows which stall to visit next; the cows thus might travel the length of the barn many times in order to collect their candy.

FJ mandates that cow i should start collecting candy at stall i. A cow stops her candy collection if she arrives back at any stall she has already visited.

Calculate the number of unique stalls each cow visits before being forced to stop her candy collection.

POINTS: 100

每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N个牛棚里转 悠，来采集糖果.她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果.

农场不大，所以约翰要想尽法子让奶牛们得到快乐.他给每一个牛棚设置了一个“后继牛 棚”.牛棚i的后继牛棚是next_i 他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去， 就可以搜集到很多糖果.事实上这是一种有点欺骗意味的手段，来节约他的糖果.

第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．

输入输出格式

输入格式：

* Line 1: A single integer: N

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

输出格式：

* Lines 1..N: Line i contains a single integer that is the total number of unique stalls visited by cow i before she returns to a stall she has previously visited.

输入输出样例

输入样例#1：

1
2
3
4
5
4 
1 
3 
2 
3

输出样例#1：

1
2
3
4
1 
2 
2 
3

说明

Four stalls.

* Stall 1 directs the cow back to stall 1.

* Stall 2 directs the cow to stall 3

* Stall 3 directs the cow to stall 2

* Stall 4 directs the cow to stall 3

Cow 1: Start at 1, next is 1. Total stalls visited: 1.

Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.

题解

D1T2难度。

由于这个有向图非常简单，每个点均初度为一，一开始感觉记忆化搜索就能解决，后来发现环和链返回值不一样，又不好分类讨论。

于是这题我写的标算是

Tarjan+记忆化搜索

显然记录每个点最多能获得多少糖果，初始每个点的值由Tarjan缩点后的强联通分量大小得到。

显然一个点连的出边的点的SCC糖果可以被它得到。记忆化搜索当前的点所在强联通分量的值是否已经最大，否则递归获得更多糖果。

时间复杂度

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
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
#define maxn 100005
int f[maxn] , n , next[maxn] , dfn[maxn] , low[maxn] , tot , scc[maxn] , idx;
bool vis[maxn] , ins[maxn];
std::stack<int> st;
int dfs(int x)
{
	if(vis[scc[x]])	return f[scc[x]];
	if(scc[x] == scc[next[x]]){
		vis[scc[x]] = true;
		return f[scc[x]];
	}
	else{
		vis[scc[x]] = true;
		return f[scc[x]] = f[scc[x]] + dfs(next[x]);
	}
}
void Tarjan(int x)
{
	dfn[x] = low[x] = ++idx ;
	st.push(x);
	ins[x] = true;
	if(!dfn[next[x]]){
		Tarjan(next[x]);
		low[x] = std::min(low[x] , low[next[x]]);
	}
	else if(ins[next[x]]){
		low[x] = std::min(low[x] , dfn[next[x]]);
	}
	if(dfn[x] == low[x])
	{
		++tot;
		while(st.top() != x){
			scc[st.top()] = tot;
			++f[tot];
			ins[st.top()] = false;
			st.pop();
		}
		++f[tot];
		scc[st.top()] = tot;
		ins[st.top()] = false;
		st.pop();
	}
} 
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d",&next[i]);
	}
	for(int i = 1 ; i <= n ; ++i){
		if(!dfn[i])	Tarjan(i);
	}
	for(int i = 1 ; i <= n ; ++i)
		if(!vis[scc[i]])
			dfs(i);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d\n",f[scc[i]]);
}

比较基础的一道题还写错多次，实在是不应该。

P2661 信息传递

题目描述

有 nn 个同学（编号为 11 到 nn ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 ii 的同学的信息传递对象是编号为 T_iTi 的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自 己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入输出格式

输入格式：

共22行。

第11行包含1个正整数 nn ，表示 nn 个人。

第22行包含 nn 个用空格隔开的正整数 T_1,T_2,\cdots\cdots,T_nT1,T2,⋯⋯,Tn ，其中第 ii 个整数 T_iTi 表示编号为 ii 的同学的信息传递对象是编号为 T_iTi 的同学， T_i \leq nTi≤n 且 T_i \neq iTi≠i 。

输出格式：

11个整数，表示游戏一共可以进行多少轮。

输入输出样例

输入样例#1：

1
2
5
2 4 2 3 1

输出样例#1：

1
3

说明

样例1解释

img

游戏的流程如图所示。当进行完第33 轮游戏后， 44号玩家会听到 22 号玩家告诉他自己的生日，所以答案为 33。当然，第 33 轮游戏后，22号玩家、 33 号玩家都能从自己的消息来源得知自己的生日，同样符合游戏结束的条件。

对于 30\%的数据， n ≤ 200；

对于 60\%的数据， n ≤ 2500；

对于100\%的数据， n ≤ 200000。

题解

可以Tarjan后求最小环（不包括自环）

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <stack>
#define maxn 200005
int n , p[maxn] , dfn[maxn] , low[maxn] , idx , sz[maxn] , tot , scc[maxn];
std::stack<int> st;
bool ins[maxn];
void Tarjan(int x)
{
    dfn[x] = low[x] = ++idx;
    st.push(x);
    ins[x] = true;
    if(!dfn[p[x]]){
        Tarjan(p[x]);
        low[x] = std::min(low[x] , low[p[x]]);
    }
    else if(ins[p[x]]){
        low[x] = std::min(low[x] , dfn[p[x]]);
    }
    if(dfn[x] == low[x]){
        ++tot;
        while(st.top() != x)
        {
            scc[st.top()] = tot;
            ins[st.top()] = false;
            ++sz[tot];
            st.pop();
        }
        ++sz[tot];
        ins[x] = false;
        scc[x] = tot;
        st.pop();
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&p[i]);
    for(int i = 1 ; i <= n ; ++i)
        if(!dfn[i])	Tarjan(i);
    int ans = 0x7fffff;
    for(int i = 1 ; i <= tot ; ++i)
        if(sz[i] > 1)
            ans = std::min(ans , sz[i]);
    printf("%d",ans);
}

P1627 [CQOI2009]中位数