15.10.07【字符串、动归/大根堆、最小生成树+lca】

OI&ACM, OI训练
  1. 1.文件列表（file）
  2. 2.编译优化(compile)
  3. 3.过路费（cost）

40+65+30

1.文件列表（file）

【问题描述】 BSOI在线评测机被不明身份的人入侵了！！系统中大量的数据遭到恶意破坏，数据文件残缺不全。现在，老师正在尽力抢救数据文件。为了检查数据文件是否完整，老师打印出了所有文件的列表，但数据文件太多，老师眼睛都要看花了。所以，为了方便老师检查，需要你写个程序处理一下文件列表，转换成下面这样统一的格式：(//后面为注释) data //data文件夹,根目录 |----prob //data下面的文件夹 | |----a.in //prob下面的文件 | |----a.out |----qq //data下面的文件夹 | |----new //qq下面的文件夹 | | |----ok.txt //new下面的文件 | |----old //空文件夹 |----xxx.rmvb 生成的列表格式有如下要求: 1.属于同一层的文件或文件夹位于相同的缩进处，相邻两层文件间差距5个字符； 2.每个文件夹或文件前有4个'-'(根目录除外)，文件夹下方属于文件夹的部分有'|'； 3.属于统一文件夹下的文件或子文件夹按字典序排列； 【文件输入】 第一行一个整数n（n<=50），表示总共的文件数目； 接下来n行，每行描述一个文件的路径，路径以'/'作为文件分隔符； 所有文件（及文件夹）名均由小写字母和英文点组成； 所有输入的根目录都是一样的，文件名长度不超过10个字符，每个文件夹下不超过15个文件，不超过5层。 【文件输出】 输出符合要求的文件列表

显然我又傻了。。。 同一个名字可以在不同文件夹里出现好多次，它们是不一样的。。。 然而我Hash的时候直接拿字符串Hash了，40 QAQ。。。 后来把上一层的Hash值乘上去，立刻好了（悔过中。。。）

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
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
map <int,int> m;
const int d=29;
int n,tot,pre,prej,fa[300],son[300][100];
unsigned x;
char s[100],f[300][15];
struct node{
	char s[15];int num;
};
int mycomp(const node &a,const node &b)
{
	int i=1;
	while(i<=strlen(a.s+1)&&i<=strlen(b.s+1))
	{
		if(a.s[i]<b.s[i]) return 1;
		if(a.s[i]>b.s[i]) return 0;
		i++;
	}
	return strlen(a.s+1)<=strlen(b.s+1);
}
void dfs(int root,int deep)
{
	node a[20]={0};
	int size=son[root][0];
	if(!size) return;
	for(int i=1;i<=size;i++)
	{
		int y=son[root][i];
		a[i].num=y;
		for(int j=1;j<=strlen(f[y]+1);j++) a[i].s[j]=f[y][j];
	}
	sort(a+1,a+size+1,mycomp);
	for(int i=1;i<=size;i++)
	{
		for(int j=1;j<deep;j++) printf("|    ");
		printf("|----");
		for(int j=1;j<=strlen(a[i].s+1);j++) 
		  printf("%c",a[i].s[j]);
		printf("\n");
		dfs(a[i].num,deep+1);
	}
}
int main()
{
	freopen("file.in","r",stdin);
	freopen("file.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		memset(s,0,sizeof(s));
		scanf("%s",s+1);
		pre=0;prej=0;
		int j=1;
		while(j<=strlen(s+1))
		{
			x=0;
			while(s[j]!='/'&&j<=strlen(s+1))
			{
				if(s[j]=='.') x=x*d+27;
				else x=x*d+(s[j]-'a'+1);
				j++;
			}
			x*=pre;
			if(!m[x]) 
			  {
			  	m[x]=++tot;
			    if(pre)
			      son[pre][++son[pre][0]]=tot;
			    for(int k=prej+1;k<j;k++)
			      f[tot][k-prej]=s[k];
			  }
			pre=m[x];prej=j++;
		}
	}
	for(int i=1;i<=strlen(f[1]+1);i++)
	  printf("%c",f[1][i]);
	printf("\n");
	dfs(1,1);
}

2.编译优化(compile)

【问题描述】 众所周知，衡量一个编译器是否优秀的标准，除了它的编译速度和正确性以外，编译出的代码的质量也很重要。最近，作为XCC系列编译器作者的Dr.X发明了一种跨时代的优化算法：“NanGe不等式优化”。一个程序可以看成是由若干个连续的函数构成的，NanGe不等式算法能针对某一个函数进行优化，得到一个优化效果值, 不同的函数的效果值可能是不同的。但这个算法还有一个很大的Bug： 该算法不能同时优化相邻的两个函数，否则就会直接Compile Error，值得注意的是，一个程序的第一个函数和最后一个函数也算是相邻的。 现在给你一个程序从头到尾每个函数的优化效果值，Dr.X想用NanGe不等式对该程序的M个函数进行优化，他该怎么选择才能使总的优化效果值最大（前提是不能出现错误）？如果错误不能避免，请输出“Error!” 【输入文件】 输入文件的第一行包含两个正整数n、m。第二行为n个整数Ai。 【输出文件】 输出文件仅一个整数，表示最后对该程序进行优化后的最大效果值。如果无解输出“Error!”，不包含引号。

法一：（65分） 动态规划，设f[i][j][0/1]表示前i个位置，选了j个，最后一个选没选： f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]); f[i][j][1]=f[i][j-1][0];

法二：（100分） 这个题标准解法是借鉴网络流中的残余流思想，用堆来维护解决。映射建大根堆，记录每一个数值在堆中的位置好方便删除操作。每回出堆顶元素后，a[k]=a[l[k]]+a[r[k]]-a[k],l[k]和r[k]是k的左边节点和右边节点，即双链表思想，再将a[l[k]]和a[r[k]]删除，将新的a[k]加入堆中。

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<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y,L,R,ans;
int pos[200001],a[200001],d[200001],l[200001],r[200001];
void up(int x)
{
	while(x>1&&a[d[x]]>a[d[x/2]])
	{
		swap(d[x],d[x/2]);
		swap(pos[d[x]],pos[d[x/2]]);
		x/=2;
	}
}
void down(int x)
{
	int i=x,j;
	while(i*2<=n)
	{
		if(i*2==n||a[d[i*2]]>a[d[i*2+1]])
		  j=i*2;
		else j=i*2+1;
		if(a[d[i]]>a[d[j]]) return;
		swap(d[i],d[j]);
		swap(pos[d[i]],pos[d[j]]);
		i=j;
	}
}
int main()
{
	freopen("compile.in","r",stdin);
	freopen("compile.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(m*2>n) {printf("Error!");return 0;}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		d[i]=pos[i]=i;
		up(i);
		l[i]=i-1;r[i]=i+1;
	}
	l[1]=n;r[n]=1;
	for(int i=1;i<=m;i++)
	{
		x=d[1];
		ans+=a[x];
		a[x]=a[l[x]]+a[r[x]]-a[x];
		a[l[x]]=-1001;down(pos[l[x]]);
		a[r[x]]=-1001;down(pos[r[x]]);
		down(1);
		l[x]=l[l[x]];r[x]=r[r[x]];
		r[l[x]]=x;l[r[x]]=x;
	}
	printf("%d",ans);
}

3.过路费（cost）

【问题描述】 在某个遥远的国家里，有n个城市。编号为1,2,3,…,n。这个国家的政府修建了m条双向道路，每条道路连接着两个城市。政府规定从城市S到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为2，B到C长度为3，那么开车从A经过B到C需要上交的过路费为3。 佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而，当他交的过路费越多他的心情就变得越糟糕。作为秘书的你，需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上交多少过路费。 【输入文件】 第一行是两个整数n 和m，分别表示城市的个数以及道路的条数。 接下来m行，每行包含三个整数 a，b，w（1≤a，b≤n，0≤w≤10^9），表示a与b之间有一条长度为w的道路。 接着有一行为一个整数q，表示佳佳发出的询问个数。 再接下来q行，每一行包含两个整数S，T（1≤S,T≤n，S≠T）, 表示开始城市S和目的城市T。 【输出文件】 输出文件共q行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。

本来写的SPFA，结果30，后面全都超时。。。 二分也是30

正解： 仔细分析一下题目，会发现如果要任意两点之间的路径中最大边最小，整个图便符合了最小生成树性质。 证明如下：若存在从a到b的一条比最小生成树上连接a与b的所经过路径上边更小的边c，则将c加入最小生成树中可得到一个更小的生成树，这显然不符合最小生成树的定义，故不存在这样的边c。 其实最小生成树克鲁斯卡尔算法的思想就是按照选择两点之间权值最小的边来构建的。 大概算法就出来了，读入数据，克鲁斯卡尔算法求最小生成树，但这时会发现一个严重问题：怎样处理询问？n的范围过大，dist[n][n]无法存储，枚举根节点来dfs求到任意节点的答案，则算法时间上升到O(n^2)，只能得30分。 再分析一下，对于一棵以任一结点为根的已经建好的最小生成树，此时询问无非是两种情况 1：两个节点为直系祖先关系，可直接求得解。2：两个节点为不同分枝上的节点。求这两个节点的答案难以相出好办法。但可以知道两个节点之间只存在唯一一条简单路径，这条唯一简单路径上的变的最大值即为答案，且这两个结点的最近公共最先必然在这一点上。想到可以转化为LCA算法，dfs一边，当处理完当前节点所有的子节点后开始回答关于这个节点的问题。

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
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
vector<int> to[10001],cost[10001];
queue<int> q;
int n,m,Q,x,y,z,c,k,f1,f2,ans;
int fat[10001],dep[10001],e[10001],fa[10001][20];
struct point{
	int xx,yy,vv;
}g[100001];
int cmp(const point &a,const point &b)
{
	return a.vv<b.vv;
}
int father(int x)
{
	if(fat[x]!=x) fat[x]=father(fat[x]);
	return fat[x];
}
void dfs(int x)
{
	for(int i=0;i<to[x].size();i++)
	{
		int y=to[x][i];
		if(fa[x][0]==y) continue;
		fa[y][0]=x; dep[y]=dep[x]+1; e[y]=cost[x][i];
		dfs(y);
	}
}
int Lca(int x,int y)
{
	for(int i=log(n)/log(2)-1;i>=0;i--)
	  if(dep[fa[x][i]]>=dep[y]) 
	    x=fa[x][i];
	if(x==y) return x;
	for(int i=log(n)/log(2)-1;i>=0;i--)
	  if(fa[x][i]!=fa[y][i])
	    x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		g[i].xx=x;g[i].yy=y;g[i].vv=z;
	}
	for(int i=1;i<=n;i++) fat[i]=i;
	sort(g+1,g+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		x=g[i].xx;y=g[i].yy;c=g[i].vv;
		f1=father(x);f2=father(y);
		if(f1!=f2)
		{
			k++;
			fat[f1]=f2;
			to[x].push_back(y);cost[x].push_back(c); 
			to[y].push_back(x);cost[y].push_back(c);
		}
		if(k==n-1) break;
	}
	dfs(1);
	for(int i=1;i<=log(n)/log(2);i++)
	  for(int j=1;j<=n;j++)
	    fa[j][i]=fa[fa[j][i-1]][i-1];
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		ans=0;
		scanf("%d%d",&x,&y);
		if(dep[x]<dep[y]) z=x,x=y,y=z;
		z=Lca(x,y);
		while(x!=z)
		{
			if(e[x]>ans) ans=e[x];
			x=fa[x][0];
		}
		while(y!=z)
		{
			if(e[y]>ans) ans=e[y];
			y=fa[y][0];
		}
		printf("%d\n",ans);
	}
}