Anjuta1.2.4a的ppa

May 18, 2009 — gnarlycow

OIers都用Anjuta1.2.4a，可是在源中它早已被新版本所取代。事实上，绝大多数人都用新版的anjuta，只有像OIer这样需要对单文件代码编译和调试的人才会使用旧版。

我的同学Aron把anjuta1.2.4a搞进他的ppa里面了，从此我们可以用源安装并更新这个旧版本的anjuta。

添加PPA的方法：
1.先导入密钥以验证签名，在终端里输入这条命令：
sudo apt-key adv –recv-keys –keyserver keyserver.ubuntu.com DDA4DB69
2.然后是在软件包管理器的“设置”->“软件库”里面，找到“第三方软件”->“添加”相应apt行：
Ubuntu 9.10：
deb http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu karmic main
deb-src http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu karmic main
Ubuntu 9.04：
deb http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu jaunty main
deb-src http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu jaunty main
确定后点“刷新”或sudo apt-get update更新软件包列表，这样就可以进行安装或者更新了。软件包名称为anjuta-old和anjuta-old-common。

Posted in Software. Tags: , , , . 3 Comments »

POI 1999 Water

May 18, 2009 — gnarlycow

优先队列

注意到边界上的格子一定不能存水，否则会流到外面去。现在考虑与边界相邻的格子。注满水后，对于某个与边界相邻的格子来水，它的积水状态只与它自己的恶高度和相邻边界格子的最低高度有关。这样，我们可以取边界格子中高度最低的格子，然后来得到与之相邻的内部格子的水位。假设边界格子中高度最低的为格子(x,y)，那么对于(x,y)的任意一个相邻非边界格子(x’,y’)来说，只要h(x,y)>h(x’,y’)” />，格子(x’,y’)就会有高度为<img src=的积水，这时我们可以把h(x,y)-h(x',y')累加到答案中去，然后把h(x',y')赋为h(x,y)并把(x’,y’)看作边界格子。如果h(x,y)<=h(x',y')，我们可以直接把(x’,y’)看作边界格子。当处理完所有(x,y)的相邻非边界格子后，把(x,y)从边界格子中删去。重复这个过程，直至边界格子集合为空为止。显然，用一个小根堆来维护边界格子集合是在适合不过了。

?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

#include <iostream>
 
using namespace std;
 
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
bool u[111][111];
int ans,heapsize,h[111][111];
struct node
{
	int x,y,v;
} heap[11111];
 
void insert(int x,int y,int v)
{
	node key={x,y,v};
	int p=++heapsize;
	while(p>1&&heap[p>>1].v>v)
	{
		heap[p]=heap[p>>1];
		p>>=1;
	}
	heap[p]=key;
}
 
void deleteMin()
{
	int p=1;
	while((p<<1)<heapsize)
	{
		int i=p<<1;
		if(i+1<heapsize&&heap[i+1].v<heap[i].v) ++i;
		if(heap[i].v<heap[heapsize].v)
		{
			heap[p]=heap[i];
			p=i;
		}
		else break;
	}
	heap[p]=heap[heapsize--];
}
 
int main()
{
	freopen("wod.in","r",stdin);
	freopen("wod.out","w",stdout);
	int r,c;
	scanf("%d%d",&r,&c);
	for(int i=0;i<r;++i)
		for(int j=0;j<c;++j)
			scanf("%d",&h[i][j]);
	for(int i=0;i<c;++i)
	{
		u[0][i]=u[r-1][i]=true;
		insert(0,i,h[0][i]);
		insert(r-1,i,h[r-1][i]);
	}
	for(int i=1;i+1<r;++i)
	{
		u[i][0]=u[i][c-1]=true;
		insert(i,0,h[i][0]);
		insert(i,c-1,h[i][c-1]);
	}
	while(heapsize)
	{
		int x=heap[1].x,y=heap[1].y;
		deleteMin();
		for(int i=0;i<4;++i)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>-1&&tx<r&&ty>-1&&ty<c&&!u[tx][ty])
			{
				u[tx][ty]=true;
				if(h[tx][ty]<h[x][y])
				{
					ans+=h[x][y]-h[tx][ty];
					h[tx][ty]=h[x][y];
				}
				insert(tx,ty,h[tx][ty]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}
Posted in POI. Tags: , . No Comments »

POI 2003 Monkeys

May 18, 2009 — gnarlycow

并查集

这是一道很棒的并查集类问题，具有较高的思维难度。注意到题目中所描述的猴子的连接方式，有可能猴子a抓住猴子b的尾巴，也有可能b抓住a的尾巴，也有可能a和b互相抓住对方的尾巴。其实我们只关心两个猴子是否相连，以上三种情况都是猴子a和b相连。现在题目要求的就是每只猴子第一次直接或间接脱离猴子1的时间。看起来好像和并查集的操作是相反的，那我们就反过来求解。首先求出时刻m所有放手行为都执行后猴子们的连接情况，然后从时刻m往前反过来执行“抓尾巴”行为，这样问题转化为求每个猴子第一次直接或间接与猴子1相连的时刻。这正是并查集所支持的操作，只是每次将猴子1所在集合与其它集合合并时，需要把那个集合的所有猴子的答案都设置为这个时刻。我们可以另外对每个集合维护一个链表，包含这个集合的所有猴子，合并时将链表合并。这样总的时间复杂度不变，问题成功解决。

?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

#include <iostream>
 
using namespace std;
 
struct node
{
	int v;
	node *next;
	node(int v,node *next):v(v),next(next) {}
} *first[200002],*last[200002];
int d[400004][2],holdOrig[200002][2],holdCur[200002][2],ans[200002],f[200002];
 
int getRoot(int v)
{
	if(f[v]==v) return v;
	else return f[v]=getRoot(f[v]);
}
 
void unite(int a,int b)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
void uniteAndUpdateAns(int a,int b,int moment)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		if(x==getRoot(1))
			for(node *t=first[y];t;t=t->next)
				ans[t->v]=moment;
		else if(y==getRoot(1))
			for(node *t=first[x];t;t=t->next)
				ans[t->v]=moment;
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
int main()
{
	int n,m;
	memset(ans,-1,sizeof(ans));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&holdOrig[i][0],&holdOrig[i][1]);
		holdCur[i][0]=holdOrig[i][0];
		holdCur[i][1]=holdOrig[i][1];
	}
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&d[i][0],&d[i][1]);
		--d[i][1];
		holdCur[d[i][0]][d[i][1]]=-1;
	}
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		first[i]=last[i]=new node(i,NULL);
	}
	for(int i=1;i<=n;++i)
	{
		if(holdCur[i][0]>-1) unite(i,holdCur[i][0]);
		if(holdCur[i][1]>-1) unite(i,holdCur[i][1]);
	}
	for(int i=m-1;i>-1;--i)
		if(holdOrig[d[i][0]][d[i][1]]>-1)
			uniteAndUpdateAns(d[i][0],holdOrig[d[i][0]][d[i][1]],i);
	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}
Posted in POI. Tags: , . No Comments »
«
»