bef-> NO.38

Veröffentlicht am

P3959 宝藏

题目描述

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 nn 个深埋在地下的宝藏屋， 也给出了这 nn 个宝藏屋之间可供开发的mm 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。

新开发一条道路的代价是：

L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。

输入输出格式

输入格式：

第一行两个用空格分离的正整数 n,mn,m，代表宝藏屋的个数和道路数。

接下来 mm 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 1-n1−n），和这条道路的长度 vv。

输出格式：

一个正整数，表示最小的总代价。

输入输出样例

输入样例#1：

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

输出样例#1：

1
4

输入样例#2：

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

输出样例#2：

1
5

说明

img

【样例解释1】

小明选定让赞助商打通了11 号宝藏屋。小明开发了道路 1 \to 21→2，挖掘了 22 号宝 藏。开发了道路 1 \to 41→4，挖掘了 44 号宝藏。还开发了道路 4 \to 34→3，挖掘了33号宝 藏。工程总代价为：1 \times 1 + 1 \times 1 + 1 \times 2 = 41×1+1×1+1×2=4

【样例解释2】

小明选定让赞助商打通了11 号宝藏屋。小明开发了道路 1 \to 21→2，挖掘了 22 号宝 藏。开发了道路 1 \to 31→3，挖掘了 33 号宝藏。还开发了道路 1 \to 41→4，挖掘了44号宝 藏。工程总代价为：1 \times 1 + 3 \times 1 + 1 \times 1 = 51×1+3×1+1×1=5

题解

这道题其实不难，而且很有启发意义。

之所以最小生成树是错误的，主要原因在于深度对费用的干扰导致贪心的错误。

既然这样我们就把深度作为状态压缩的一维进行dp

而转移我们发现枚举量很大，在枚举深度的前提下枚举当前打通的点集枚举补集的子集，然后再判断当前点集和补集子集能否一步联通。

我们预处理任意两不相交点集联通代价

注意两点集不能一次联通应设为无穷量。

dp转移

注意枚举补集。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 12
#define INF 0x2fffffff
//must from zero
int pre[1<<maxn][1<<maxn] , dis[maxn][maxn] , n , m , f[maxn+1][1<<maxn];
inline int Cost(int S1 , int S2)
{
	int ans = 0;
	for(int i = 0 ; i < n ; ++i){
		int v = 1 << i;
		if(S2 & v){
			int cur = INF;
			for(int j = 0 ; j < n ; ++j)
				if(S1 & (1 << j))
					cur = std::min(cur , dis[i][j]);
			if(cur == INF)	return INF;
			ans += cur;
		}
	}
	return ans;
}
void write(int x)
{
	if(!x)	return;
	write(x >> 1);
	putchar((x&1)+48);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 0 ; i < n ; ++i)
		for(int j = 0 ; j < n ; ++j)
			dis[i][j] = INF;
	for(int i = 1 ; i <= m ; ++i){
		int x , y , d;
		scanf("%d%d%d",&x,&y,&d);
		--x , --y;
		dis[x][y] = dis[y][x] = std::min(dis[x][y] , d);
	}
	int S = 1 << n;
	for(int i = 0 ; i < S ; ++i){//prepare the one step minimum value
		int G = S - 1 ^ i;
		for(int j = G ; j ; j = j - 1 & G){
			pre[i][j] = Cost(i,j);
		}
	}
	for(int i = 0 ; i <= n ; ++i)
		for(int j = 0 ; j < S ; ++j)
			f[i][j] = INF;
	for(int i = 0 ; i < n ; ++i)	f[0][1<<i] = 0;
	for(int h = 0 ; h < n ; ++h){
		for(int i = 0 ; i < S ; ++i){
			int G = S - 1 ^ i;
			for(int j = G ; j ; j = j - 1 & G)
				if(f[h][i] < INF && pre[i][j] < INF){
					f[h+1][i | j] = std::min(f[h+1][i | j] , f[h][i] + (h + 1) * pre[i][j]);
				}
		}
	}
	int ans = 0x7ffffff;
	for(int i = 0 ; i <= n ; ++i)
		ans = std::min(ans , f[i][S-1]);
	printf("%d",ans);
}

注意只有一个点的情况，考试丢5分也很亏啊。。

P1080 国王游戏

题目描述

恰逢 HH国国庆，国王邀请nn 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 nn 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入输出格式

输入格式：

第一行包含一个整数nn，表示大臣的人数。

第二行包含两个整数 aa和 bb，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 nn行，每行包含两个整数aa 和 bb，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式：

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

输入输出样例

输入样例#1：

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

输出样例#1：

1
2

说明

【输入输出样例说明】

按11、22、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按 11、33、22 这样排列队伍，获得奖赏最多的大臣所获得金币数为22；

按 22、11、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按22、33、11这样排列队伍，获得奖赏最多的大臣所获得金币数为99；

按 33、11、22这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按33、22、11 这样排列队伍，获得奖赏最多的大臣所获得金币数为 99。

因此，奖赏最多的大臣最少获得 22个金币，答案输出 22。

【数据范围】

对于 20%的数据，有 1≤ n≤ 10,0 < a,b < 81≤n≤10,0<a,b<8；

对于 40%的数据，有1≤ n≤20,0 < a,b < 81≤n≤20,0<a,b<8；

对于 60%的数据，有 1≤ n≤1001≤n≤100；

对于 60%的数据，保证答案不超过 10^9109；

对于 100%的数据，有 1 ≤ n ≤1,000,0 < a,b < 100001≤n≤1,000,0<a,b<10000。

NOIP 2012 提高组 第一天 第二题

题解

一道很不错的贪心题。

应用微扰法证明贪心正确性。（前后代价做商应该不难看出）

顺便练了练恶心的高精度，学了下高精除低精。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1005
#define ll long long
ll n;
struct Node{
	ll x , y;
	bool operator < (const Node& g)const {
		return x * y < g.x * g.y;
	}
}p[maxn]; 
struct BIGNUM{
	ll num[maxn*10] , len;
	BIGNUM(){
		num[1] = 1;
		len = 1;
	}
	void mul(const ll& x)
	{
		for(int i = 1 ; i <= len ; ++i){
			num[i] *= x;
		}
		for(int i = 1 ; i <= len ; ++i){
			if(num[i] > 9){
				if(i + 1 > len){
					++len;
				}
				num[i+1] += num[i] / 10;
				num[i] %= 10;
			}
		}
	}
	void max(BIGNUM& x , BIGNUM& y)
	{
		if(x.len < y.len){
			x = y;
			return;
		}
		else if(x.len > y.len)	return;
		else{
			for(int i = x.len ; i ; --i){
				if(x.num[i] > y.num[i])	return;
				else if(x.num[i] < y.num[i]){
					x = y;
					return;
				}
			}
		}
	}
	void div(const BIGNUM& g , ll x)
	{
		ll cur = 0;
		for(int i = len ; i ; --i){
			num[i] = (cur * 10 + g.num[i]) / x;
			cur = (cur * 10 + g.num[i]) % x;
		}
		while(!num[len]) --len;
	}
	void print()
	{
		for(int i = len ; i >= 1 ; --i)
			printf("%d",num[i]);
	}
}cur , ans , g; 
int main()
{
//	freopen("King.in","r",stdin);
	scanf("%lld",&n);
	for(int i = 0 ; i <= n ; ++i)
		scanf("%lld%lld",&p[i].x,&p[i].y);
	std::sort(p + 1 , p + n + 1);
	cur.mul(p[0].x);
	for(int i = 1 ; i <= n ; ++i){
		g = cur;
		g.div(cur , p[i].y);
		ans.max(ans , g);
		cur.mul(p[i].x);
	}
	ans.print();

}

一共就做了这两题。上午考了次试，感觉题都还行。

Pictionary

题意：给你n个独立的点，一共有m天，第i天会将gcd(a,b)=m-i+1的点连接起来，q个询问，求x,y在哪一天被连接起来。

n <= 100000

题解

为什么就我想不到正解啊啊啊啊啊。

我就会30分。。

30分做法：
考虑两点之间的传递，用类似Floyd的方法更新，成功成为全场最低分（第二题折半搜索其实是正解，只不过我当时没想到按高度统计这一非常简单的方法。。加个n又不是过不了）

满分做法：

其实还是有建图的思想。以后看到这种连续的gcd，lcm之类的就可以想到倍数关系啦！！

考虑从m开始，向它的倍数连边权为它的边，假设这个点和它连向的点已经联通了，那就不要连了，因为这两点之间的最小边一定不小于当前你连的这条边。

所以这道题在明白倍数关系后就是一个最大生成树+HPD维护两点间最小边，这个最小边由于最大生成树的性质一定最大，本题做完了。

代码有问题，先上下以供参考

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
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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define INF 100000005
#define maxn 100005
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int n , q , x , y , m , head[maxn] , cnt , tot , uf[maxn] , val[maxn] , ref[maxn*20];
struct edge{
	int next , to , dis;
}e[maxn*10];
struct HPD
{
	#define pushup(x) maxx[x] = std::max(maxx[ls(x)] , maxx[rs(x)])
	int id[maxn] , sz[maxn] , top[maxn] , dep[maxn] , hs[maxn] , maxx[maxn<<2] , f[maxn] , v[maxn] , idx;
	void dfs1(int x , int fx)
	{
		f[x] = fx;
		sz[x] = 1;
		dep[x] = dep[fx] + 1;
		for(int i = head[x] ; i ; i = e[i].next){
			if(e[i].to != fx){
				dfs1(e[i].to , x);
				sz[x] += sz[e[i].to];
				if(sz[hs[x]] < sz[e[i].to])	hs[x] = e[i].to;
			}
		}
	}
	void dfs2(int x , int topv)
	{
		top[x] = topv;
		id[x] = ++idx;
		v[id[x]] = val[x];
		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);
		}
	}
	void build(int l , int r , int node)
	{
		if(l == r){
			maxx[node] = v[l];
			return ;
		}
		int mid = l + r >> 1;
		build(l , mid , ls(node));
		build(mid + 1 , r , rs(node));
		pushup(node);
	}
	int query(int L , int R , int l , int r , int node)
	{
		if(L <= l && r <= R){
			return maxx[node];
		}
		int mid = l + r >> 1 , ans = -INF;
		if(L <= mid)	ans = std::max(ans , query(L , R , l , mid , ls(node)));
		if(R > mid)		ans = std::max(ans , query(L , R , mid + 1, r , rs(node)));
		return ans;
	}
	int	queryMax(int x , int y)
	{
		int ans = -INF;
		while(top[x] != top[y]){
			if(dep[top[x]] < dep[top[y]])	std::swap(x,y);
			ans = std::max(ans , query(id[top[x]] , id[x] , 1 , n , 1));
			x = f[top[x]];
		}
		if(dep[x] < dep[y])	std::swap(x,y);
		ans = std::max(ans , query(id[y] , id[x] , 1 , n , 1));
		return ans;
	}
}tr;
inline void add(int x , int y , int d)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].dis = d;
	head[x] = cnt;
}
int find(int x){
	if(uf[x] != x)	return uf[x] = find(uf[x]);
	return uf[x];
}
void dfs(int x , int fx , int d)
{
	val[x] = d;
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == fx)	continue;
		dfs(v , x , e[i].dis);
	}
}
int main()
{
//	freopen("Pictionary.in","r",stdin);
//	freopen("Pictionary.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i = 1 ; i <= n ; ++i)
		uf[i] = i;
	for(int i = m ; i ; --i)
		for(int j = 2 * i ; j <= n ; j += i)
			if(find(i) != find(j)){
				uf[find(i)] = find(j) , add(i , j , i) , add(j , i , i);
			}
	dfs(1,1,0);
	tr.dfs1(1,1);
	tr.dfs2(1,1);
	tr.build(1,n,1);
	for(int i = 1 ; i <= q ; ++i){
		int x , y;
		scanf("%d%d",&x,&y);
		printf("%d\n", m - tr.queryMax(x,y) + 1);
	}
}