USACO FEB09 Gold Summary

February 18, 2009 — gnarlycow

shuttle
贪心
本题看似动态规划题，但实际上存在如下贪心策略：将所有区间按照终点排序，优先让终点靠前的牛上车。直观上看，我们只需要让尽可能多的牛乘车，而不关心具体哪些牛乘车，让路途远的牛乘车和路途近的牛乘车对于我们来说是一样的。这样，终点靠前意味着早下车，可以让出座位留给后面的牛。本题数据量较大，可能需要借助一些高级数据结构来实现空座维护过程。

?View Code CPP
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

/*
ID: lipeiqi1
LANG: C++
PROB: shuttle
*/
#include <iostream>
#include <algorithm>
#include <map>
 
using namespace std;
 
struct segment
{
	int s,e,m;
	bool operator<(const segment &other) const
	{
		return s<other.s;
	}
} d[50005];
 
int main()
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	int k,n,c,ans=0,cur=0;
	map <int,int> h;
	scanf("%d %d %d",&k,&n,&c);
	for(int i=0;i<k;++i) scanf("%d %d %d",&d[i].s,&d[i].e,&d[i].m);
	sort(d,d+k);
	for(int i=0;i<k;++i)
	{
		for(map <int,int>::iterator t=h.begin();t!=h.end()&&t->first<=d[i].s;h.erase(t++))
		{
			ans+=t->second;
			cur-=t->second;
		}
		h[d[i].e]+=d[i].m;
		cur+=d[i].m;
		map <int,int>::iterator t=h.end();
		for(--t;cur>c;)
			if(cur-t->second>c)
			{
				cur-=t->second;
				h.erase(t--);
			}
			else
			{
				t->second-=cur-c;
				cur=c;
			}
	}
	printf("%d\n",ans+cur);
	return 0;
}

stock
贪心+动态规划
在第3天购买某种股票然后在第5天卖，可以看成第3天购买，第4天卖出，第4天再购买，第5天再卖出。我们只关心低价购买，高价卖出，而股票的获利于你持股的时间没有关系，每天的买卖也没有限制，因此我们可以依次考虑每相邻的两天我们如何购买前一天的股票然后在后一天全部卖出。这样我们得到一个贪心算法，依次考虑每相邻两天，前一天买入后一天全部卖出所能得到的最大收益，而这正是个简单的背包问题：股票就是物品，花费就是前一天的价格，收益就是后一天的价格，背包就是资金。

?View Code CPP
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

/*
ID: lipeiqi1
LANG: C++
PROG: stock
*/
#include <iostream>
 
using namespace std;
 
int p[55][11],f[500005];
 
int main()
{
    freopen("stock.in","r",stdin);
    freopen("stock.out","w",stdout);
    int s,d,m;
    scanf("%d %d %d",&s,&d,&m);
    for(int i=0;i<s;++i)
        for(int j=0;j<d;++j)
            scanf("%d",&p[i][j]);
    for(int i=1;i<d;++i)
    {
        for(int j=0;j<=m;++j) f[j]=j;
		for(int j=0;j<s;++j)
			if(p[j][i]>p[j][i-1])
			{
				int prev=p[j][i-1],curr=p[j][i];
				for(int k=prev;k<=m;++k)
				{
					int t=f[k-prev]+curr;
					if(t>f[k]) f[k]=t;
				}
			}
		m=f[m];
    }
    printf("%d\n",m);
    return 0;
}

revamp
图论
按照如下方法构造新图：新图中结点用有序数对(i,j)表示，其中1<=i<=n且0<=j<=k。对于原图中的无向边(a,b)，在新图中加入(a,u)与(b,u)之间的无向边(0<=u<=k)，加入(a,u)与(b,u+1)之间的权为０的无向边(0<=u<k)。除此之外，对于所有的u(0<=u<k)加入(a,u)与(a,u+1)之间权为0的无向边。显然新图中点(1,0)到(n,k)的最短路径就是所求答案。我们可以使用Dijkstra和堆来快速求最短路径。

?View Code CPP
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

/*
ID: lipeiqi1
LANG: C++
PROG: revamp
*/
#include <cstdio>
#include <cstring>
 
const int MAX_NODE_NUM=210012;
struct edge
{
	int v,w;
	edge *next;
	edge(int v,int w,edge *next):v(v),w(w),next(next) {}
} *e[10001];
struct THeap
{
	int v,d;
} heap[MAX_NODE_NUM];
int heapsize,k,n,pos[MAX_NODE_NUM];
 
void heapInit()
{
	heapsize=0;
	memset(pos,0,sizeof(pos));
}
 
void downMaintain(int k)
{
	int i=k;
	THeap x=heap[k];
	for(int j=k<<1;j<=heapsize;)
	{
		if(j<heapsize&&heap[j].d>heap[j+1].d) j++;
		if(x.d<=heap[j].d) break;
		heap[i]=heap[j];
		pos[heap[j].v]=i;
		i=j;
		j=i<<1;
	}
	heap[i]=x;
	pos[heap[i].v]=i;
}
 
void heapUpdate(int v,int dis)
{
	int i=pos[v];
	if(i&&heap[i].d<=dis) return;
	if(!i) i=++heapsize;
	for(;i!=1&&dis<heap[i>>1].d;i>>=1) heap[i]=heap[i>>1],pos[heap[i>>1].v]=i;
	heap[i].v=v;
	heap[i].d=dis;
	pos[v]=i;
}
 
void deleteMin()
{
	pos[heap[1].v]=0;
	heap[1]=heap[heapsize--];
	downMaintain(1);
}
 
int dijkstra(int vstart)
{
	bool visited[MAX_NODE_NUM]={false};
	int pv,pdis,vend=n*(k+1);
	heapInit();
	heapUpdate(vstart,0);
	for(int i=0;i<vend;i++)
	{
		do
		{
			pv=heap[1].v,pdis=heap[1].d;
			deleteMin();
		} while(visited[pv]);
		if(pv==vend) return pdis;
		visited[pv]=true;
		int comp=(pv-1)/n;
		for(edge *t=e[pv-n*comp];t;t=t->next)
		{
			if(!visited[t->v+n*comp]) heapUpdate(t->v+n*comp,pdis+t->w);
			if(comp<k&&!visited[t->v+n*(comp+1)]) heapUpdate(t->v+n*(comp+1),pdis);
		}
		if(comp<k&&!visited[pv+n]) heapUpdate(pv+n,pdis);
	}
}
 
int main()
{
	freopen("revamp.in","r",stdin);
	freopen("revamp.out","w",stdout);
	int m,a,b,w;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i<m;++i)
	{
		scanf("%d %d %d",&a,&b,&w);
		e[a]=new edge(b,w,e[a]);
		e[b]=new edge(a,w,e[b]);
	}
	printf("%d\n",dijkstra(1));
	return 0;
}
Posted in Gold Division, USACO. Tags: , , . RSS feed for comments on this post.. TrackBack URL.

3 Comments

  1. zqzas says:
    April 7, 2009 at 20:12

    国内的比赛不是不让用……么?

    [Reply]

  2. zqzas says:
    April 7, 2009 at 20:15

    “algorithm”

    [Reply]

  3. admin says:
    April 8, 2009 at 00:55

    是我偷懒了，确实不让用,不过我怀疑NOI自动评测是并不判断是否使用这些头文件。

    [Reply]

Leave a comment

«
»