15.10.03【前缀和、Dijkstra、BFS+Kruskal+Lca】

OI&ACM, OI训练
  1. 1.NOIONI
  2. 2.蜜袋鼯
  3. 3.水壶

30+25+0

1.NOIONI

【题目描述】 NOIONI是NOI的叔叔。NOIONI先生很受欢迎，因为他的名字中N,O,I 各重复了两遍。最近NOIONI先生生了一个孩子（吓）。现在NOIONI先生打算给他的孩子取名字，他希望他的孩子的名字也由N,O,I 组成，而且每个字母重复的次数相同。NOIONI 先生找来了一个世代相传的手卷，手卷里写着一首由N,O,I组成的N个字符的诗，NOIONI先生打算从这个手卷里找出一个最长的子串，使得这个子串符合每个字母出现次数相同，并且尽可能的长，以此作为儿子的名字。

我开始想的就是把N、O、I各赋一个值，然后前缀和相差三数和的倍数的话就表示可以了，然而我还是用了n^2的算法 后来查了查，每个前缀和都mod（N、O、I的和）这样数一样就行，用map存下来前缀和第一次出现的位置，以后再出现就减去第一次就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n,ans,sum[200001];
map<int,int> m;
char c;
int main()
{
	freopen("noioni.in","r",stdin);
	freopen("noioni.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>c;
		if(c=='N') sum[i]=(sum[i-1]+1)%40000200001;
		else if(c=='O') sum[i]=(sum[i-1]+200000)%40000200001;
		else sum[i]=(sum[i-1]+40000000000)%40000200001;
		if(m[sum[i]]==0) m[sum[i]]=i;
		else if(i-m[sum[i]]>ans) ans=i-m[sum[i]];
	}
	printf("%d",ans);
}

正解： 考虑任意一个串都是两个前缀之差. 如果这个串要满足num(N)=num(O)=num(I),那么两个前缀num(N),num(O),num(I)的相对大小关系必须是相同的. 我们对于每个前缀记下num(N)-num(O),num(N)-num(I),然后利用map随便搞搞就行了.（什么叫随便搞搞。。。）

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
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> pii;
#define mp make_pair
#define N 200010
char s[N]; 
map<pii,int>M;
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    M[mp(0,0)]=0;
    int J=0,O=0,I=0,ans=0;
    for(int i=1;i<=n;++i){
        if(s[i]=='J')
            ++J;
        if(s[i]=='O')
            ++O;
        if(s[i]=='I')
            ++I;
        if(M.count(mp(J-O,J-I)))
            ans=max(ans,i-M[mp(J-O,J-I)]);
        else
            M[mp(J-O,J-I)]=i;
    }
    cout<<ans<<endl;
    return 0;
}

2.蜜袋鼯

【题目描述】 蜜袋鼯居住的森林里有N棵树。树从1标号到N,其中第i棵树的高度是Hi米。蜜袋鼯可以在其中M对树之间跳来跳去，在这些树之间跳跃需要花费Tj的时间。 而当蜜袋鼯在两棵树之间跳跃的时候，蜜袋鼯会以每秒1 米的速度下降，也就是说如果这次跳跃花了t的时间，跳之前的高度是h,跳之后的高度就是h-t. 显然，这个数值应该在0到目标树的高度之间。 蜜袋鼯可以在树上爬来爬去，也就是说如果这棵树的高度是Hi，这时候蜜袋鼯离地面的高度就可以在0到Hi之间变化。蜜袋鼯每秒可以爬1米。 最开始的时候，蜜袋鼯在第1棵树的X米处，他想知道，爬到第N棵树顶需要的最少时间是多少？ 【输入格式】 第一行输入三个整数N，M，X, 分别表示树的数量，有M组树之间可以跳跃，最开始的高度是X. 接下来N行，其中第i行一个整数Hi表示第i棵树的高度。 接下来M行，其中第j行有三个整数Aj，Bj，Tj表示可以在树Aj和树Bj之间跳跃，需要花费Tj的时间。输入保证没有Aj=Bj , 也不会有重边。 【输出格式】 输出一个整数，表示从第i 棵树跳到第N 棵树的最短时间，无解输出-1.

暴力：每一棵树上的每一个高度建了一个点，过了25。。。

正解： 分3种情况： 1. 当到达目标后高度比树高的时候，先向下移动到移动后的高度是目标树的高度再过去 2. 当到达目标的高度在目标树的高度范围内，直接移动 3. 当到达目标的高度小于0的时候，调整当前高度使得移动后的高度大于等于0，再过去（如果不管怎么调整都移动不了就放弃）

用Dijkstra，SPFA有20分过不了。。。 好像是因为如果两种转移方式转移到同一棵树上的最小值相等时，两种情况都要考虑，但SPFA做不到。

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
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=100001;
vector<int> to[N],cost[N];
int n,m,X,a,b,tt,h[N],now;
long long ans,ds[N],inf;
struct node{
	int x,g;long long d;
	inline node(int a,int b,long long c):x(a),g(b),d(c){}
	inline bool operator<(const node&t) const{return d>t.d;}
};
priority_queue<node> q;
int main()
{
	freopen("sugar.in","r",stdin);
	freopen("sugar.out","w",stdout);
	scanf("%d%d%d",&n,&m,&X);
	for(int i=1;i<=n;i++)	scanf("%d",&h[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&tt);
		to[a].push_back(b);cost[a].push_back(tt);
		to[b].push_back(a);cost[b].push_back(tt);
	}
	memset(ds,0x7f,sizeof(ds));inf=ds[0];ans=inf;
	q.push(node(1,X,0));
	while(!q.empty()){
		node x=q.top(); q.pop();
		if(ds[x.x]<inf) continue;
		ds[x.x]=x.d;now=x.g;
		if(x.x==n)
		  {long long a=h[n]-now+ds[n];if(a<ans) ans=a;}
		for(int j=0;j<to[x.x].size();j++)
	    {
	    	int y=to[x.x][j],t=cost[x.x][j],next=0,c=0;
			if(now-t>=0&&now-t<=h[y])  c=t,next=now-t;
			else if(now-t>h[y])  c=now-h[y],next=h[y];
			else if(h[x.x]>=t) c=2*t-now,next=0;
			else continue;
			q.push(node(y,next,ds[x.x]+c));
	    }
	}
	/*while(!q.empty())  SPFA
	{
		int x=q.front(); q.pop(); vis[x]=0;
		int now=q2.front(); q2.pop();
		int maxx=0x7fffffff;
		for(int i=0;i<to[x].size();i++)
		{
			int y=to[x][i],t=cost[x][i],next=0,c=0;
			if(now-t>=0&&now-t<=h[y])  c=t,next=now-t;
			else if(now-t>h[y])  c=now-h[y],next=h[y];
			else if(h[x]>=t) c=2*t-now,next=0;
			else continue;
			if(ds[y]>ds[x]+c)
			{
				ds[y]=ds[x]+c;
				if(y==n)
				  {long long a=h[n]-next+ds[n];if(a<ans) ans=a;}
				if(!vis[y])
				{
					vis[y]=1;
					q.push(y);q2.push(next);
				}
			}
		}
	}*/
	if(ds[n]==inf) printf("-1");
	else  printf("%lld",ans);
}

3.水壶

【题目描述】 NOI所居住的IOI城全年都很热。IOI城是一个高H宽W的长方形城区，城区中有建筑物或者原野或者墙壁。有P个从1开始编号的建筑物。NOI只能在建筑和原野之间移动，如果两个建筑或者原野之间有共享的边，NOI就可以直接移动过去，NOI不能走出地图。 NOI需要在地图上跑来跑去。建筑物内是有空调的，但是，由于太阳太热了，所以在原野到原野之间行走时，每一步都需要喝1的水。此外，IOI 城的建筑物里有很多的饮水机或者自动售货机。而如果你拿着一个最大容积是x的水壶，你就可以在建筑物内把它装满。 带着水壶跑来跑去是很累的一件事情。所以，NOI希望能带着尽可能小的水壶。关于在一些建筑物之间移动的问题，我希望你写一个程序来寻找NOI 所需要的最小的水壶的容积大小。 【输入格式】 第一行四个整数H; W; P; Q, 用空格间隔。表示IOI 市的大小，建筑物的个数和询问个数。 接下来H行，第r行有W个字符，'.'表示建筑或者原野，'#'表示墙，其中第c个字符表示第r行第c列的地图。 接下来P行，第j行有两个整数Aj和Bj表示第Aj行，第Bj列这块空地是一个建筑物，保证这个位置在上面给出的地图是个'.'。 接下来Q行，第i行两个整数Si和Ti表示询问从第Si个建筑物到第Ti个建筑物需要的最小的水壶的容积。 【输出格式】 输出Q行，第i行一个整数表示从Si到Ti需要的最小的水壶的容积是多少，如果不能从Si到Ti则输出1, 类似，如果不需要在原野之间移动，那就输出0.

恕我暂且不会写。。。 题解：

标程： 

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXH = 2010;
const int MAXW = 2010;
const int MAXP = 200010;
const int HEIGHT = 20;
const int INF = 1000000000;
int H, W, P, Q;
int field[MAXH][MAXW];
char in[MAXW + 10];
int ax[] = {-1, 0, 0, 1}, ay[] = {0, -1, 1, 0};
pair<int, int> reg[MAXH][MAXW];
int uf[MAXP];
vector<int> tree[MAXP], dist[MAXP];
int depth[MAXP], up[MAXP][HEIGHT], upd[MAXP][HEIGHT];
int root(int p)
{
	return uf[p] < 0 ? p : (uf[p] = root(uf[p]));
}
bool join(int p, int q)
{
	p = root(p); q = root(q);
	if(p == q) return false;
	uf[p] += uf[q];
	uf[q] = p;
	return true;
}
void bfs()
{
	queue<pair<int, int> > qu;
	for(int i=0;i<H;i++) for(int j=0;j<W;j++){
		if(field[i][j] < 0) reg[i][j] = make_pair(-1, -1);
		else{
			reg[i][j] = make_pair(0, field[i][j]);
			qu.push(make_pair(i, j));
		}
	}
	while(!qu.empty()){
		pair<int, int> tmp = qu.front(); qu.pop();
		int y = tmp.first, x = tmp.second;
		for(int i=0;i<4;i++){
			int y2 = y + ay[i], x2 = x + ax[i];
			if(y2 < 0 || x2 < 0 || y2 >= H || x2 >= W) continue;
			if(reg[y2][x2].first != -1 || field[y2][x2] == -2) continue;
			reg[y2][x2] = make_pair(reg[y][x].first + 1, reg[y][x].second);
			qu.push(make_pair(y2, x2));
		}
	}
}
void add_edge(int x, int y, int d)
{
	tree[x].push_back(y);
	tree[y].push_back(x);
	dist[x].push_back(d);
	dist[y].push_back(d);
}
void visit(int p, int r, int d)
{
	if(r == -1){
		for(int i=0;i<HEIGHT;i++){
			up[p][i] = -1;
		}
		depth[p] = 0;
	}else{
		up[p][0] = r; upd[p][0] = d;
		depth[p] = depth[r] + 1;
		for(int i=1;i<HEIGHT;i++){
			if(up[p][i-1] == -1) up[p][i] = -1;
			else{
				up[p][i] = up[up[p][i-1]][i-1];
				upd[p][i] = max(upd[p][i-1], upd[up[p][i-1]][i-1]);
			}
		}
	}
	for(int i=0;i<tree[p].size();i++) if(tree[p][i] != r) visit(tree[p][i], p, dist[p][i]);
}
void make_MST()
{
	vector<pair<int, pair<int, int> > > cand;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(field[i][j] == -2) continue;
			if(i < H-1 && field[i+1][j] != -2 && reg[i][j].second != reg[i+1][j].second)
				cand.push_back(make_pair(reg[i][j].first + reg[i+1][j].first, make_pair(reg[i][j].second, reg[i+1][j].second)));
			if(j < W-1 && field[i][j+1] != -2 && reg[i][j].second != reg[i][j+1].second)
				cand.push_back(make_pair(reg[i][j].first + reg[i][j+1].first, make_pair(reg[i][j].second, reg[i][j+1].second)));
		}
	}
	sort(cand.begin(), cand.end());
	for(int i=0;i<P;i++) uf[i] = -1;
	for(int i=0;i<cand.size();i++){
		int x=cand[i].second.first, y=cand[i].second.second, d=cand[i].first;
		if(join(x, y)){
			add_edge(x, y, d);
		}
	}
	for(int i=1;i<P;i++){
		if(join(i-1, i)) add_edge(i-1, i, INF);
	}
	visit(0, -1, 0);
}
int solve(int p, int q)
{
	if(depth[p] > depth[q]) swap(p, q);
	int ret = 0;
	for(int i=HEIGHT-1;i>=0;i--) if(depth[q] - (1<<i) >= depth[p]){
		ret = max(ret, upd[q][i]);
		q = up[q][i];
	}
	if(p == q) return ret;
	for(int i=HEIGHT-1;i>=0;i--){
		if(up[p][i] != up[q][i]){
			ret = max(ret, max(upd[p][i], upd[q][i]));
			p = up[p][i];
			q = up[q][i];
		}
	}
	ret = max(ret, max(upd[p][0], upd[q][0]));
	return ret;
}
int main()
{
	freopen("bottle.in", "r", stdin);
	freopen("bottle.out", "w", stdout);
	scanf("%d%d%d%d", &H, &W, &P, &Q);
	for(int i=0;i<H;i++){
		scanf("%s", in);
		for(int j=0;j<W;j++){
			if(in[j] == '.') field[i][j] = -1;
			else field[i][j] = -2;
		}
	}
	for(int i=0;i<P;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		--a; --b;
		field[a][b] = i;
	}
	bfs();
	make_MST();
	for(int i=0;i<Q;i++){
		int s, t;
		scanf("%d%d", &s, &t);
		--s; --t;
		int ret = solve(s, t);
		if(ret == INF) ret = -1;
		printf("%d\n", ret);
	}
	return 0;
}