Chenfan Blog

Do cool things that matter.

0%

The 2015 ACM-ICPC Asia Regional Changchun Online

Posted on Edited on In

【A】Alisha’s Party 堆模拟
【B】Ponds
【C】Aggregated Counting
【D】Clock Adjusting
【E】Travel 并查集
【F】Favorite Donut
【G】The Water Problem
【H】Elven Postman
【I】Food Problem
【J】Unknown Treasure
【K】Good Numbers
【L】Marisa’s Cake
【M】Robot Dog

题解在此：

acminfo 结题报告整理页

然后是这个 长春2015的那一场网络赛

可能是最后一次写题解了，后面的题目也不会再补了。

下半年还是希望能够打出现场赛名额，但是我已经不会再参加了。

【A】HDU 5437 Alisha’s Party

Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Problem Description

Princess Alisha invites her friends to come to her birthday party. Each of her friends will bring a gift of some value v, and all of them will come at a different time. Because the lobby is not large enough, Alisha can only let a few people in at a time. She decides to let the person whose gift has the highest value enter first.

Each time when Alisha opens the door, she can decide to let p people enter her castle. If there are less than p people in the lobby, then all of them would enter. And after all of her friends has arrived, Alisha will open the door again and this time every friend who has not entered yet would enter.

If there are two friends who bring gifts of the same value, then the one who comes first should enter first. Given a query n Please tell Alisha who the n−th person to enter her castle is.

Input

The first line of the input gives the number of test cases, T , where 1≤T≤15.

In each test case, the first line contains three numbers k,m and q separated by blanks. k is the number of her friends invited where 1≤k≤150,000. The door would open m times before all Alisha’s friends arrive where 0≤m≤k. Alisha will have q queries where 1≤q≤100.

The i−th of the following k lines gives a string Bi, which consists of no more than 200 English characters, and an integer vi, 1≤vi≤10^8, separated by a blank. Bi is the name of the i−th person coming to Alisha’s party and Bi brings a gift of value vi.

Each of the following m lines contains two integers t(1≤t≤k) and p(0≤p≤k) separated by a blank. The door will open right after the t−th person arrives, and Alisha will let p friends enter her castle.

The last line of each test case will contain q numbers n1,…,nq separated by a space, which means Alisha wants to know who are the n1−th,…,nq−th friends to enter her castle.

Note: there will be at most two test cases containing n>10000.

Output

For each test case, output the corresponding name of Alisha’s query, separated by a space.

Sample Input

1
5 2 3
Sorey 3
Rose 3
Maltran 3
Lailah 5
Mikleo 6
1 1
4 2
1 2 3

Sample Output

Sorey Lailah Rose

题意

所有的人按照一个队列的顺序到达，但是门只有在特定的时间才打开，且每次打开只能有前p个值最大的才能进入。要求输出第n个进门者的名字。

分析

刚拿到题就觉得这个按照题意要求直接模拟即可。

然而priority_queue打上去TLE了…

刚分析觉着是不是一个一个从队列里面删掉太慢了，改用splay这样旋转到位一次性全删掉应该会更快点…然后就听旁边另一队手打堆过了。

那么事实证明STL的优先队列效率并没有这么高咯。

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
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: 1001
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef struct fri
{
	char name[250];
	int time,value;
	friend bool operator < (fri a,fri b)
	{
		if (a.value==b.value) return a.time>b.time;
		else return a.value<b.value;
	}
} friends;

friends a[150010];

typedef struct ti
{
	int t,p;
} tim;

bool op_ti(tim a,tim b)
{
	return a.t<b.t;
}

tim b[150010];

int c,outlist[150010];

typedef struct heaptyp
{
	int num,key;
} heaptype;
heaptype heap[150010];
int heaptail;

void heapadd(int s,int t)
{
	int i,j;
	heaptail++;
	heap[heaptail].num=s;
	heap[heaptail].key=t;
	i=heaptail;
	j=i>>1;
	while (i>1&&(heap[i].num>heap[j].num||(heap[i].num==heap[j].num&&heap[i].key<heap[j].key)))
	{
		swap(heap[i],heap[j]);
		i=j;
		j=i>>1;
	}
}

heaptype heappop()
{
	int i,j;
	heaptype x,y;
	y=heap[1];
	x=heap[heaptail];
	heaptail--;
	i=1;
	j=i<<1;
	while (j<=heaptail)
	{
		if (j<heaptail&&(heap[j].num<heap[j+1].num||(heap[j].num==heap[j+1].num&&heap[j].key>heap[j+1].key))) j++;
		if (x.num<heap[j].num||(x.num==heap[j].num&&(x.key>heap[j].key)))
		{
			heap[i]=heap[j];
			i=j;
			j=i<<1;
		} else j=heaptail+1;
	}
	heap[i]=x;
	return y;
}

int main()
{
	//freopen("1001.txt","r",stdin);

	int t;
	scanf("%d",&t);

	for (int tt=1;tt<=t;tt++)
	{
		int k,m,q;
		scanf("%d%d%d",&k,&m,&q);

		for (int i=1;i<=k;i++)
		{
			scanf("%s%d",&a[i].name,&a[i].value);
			a[i].time=i;
		}

		for (int i=1;i<=m;i++)scanf("%d%d",&b[i].t,&b[i].p);
		b[m+1].t=k;
		b[m+1].p=k;

		sort(&b[1],&b[m+2],op_ti);

		int tail=0;
		heaptail=0;
		for (int i=0;i<=m;i++)
		{
			for (int j=b[i].t+1;j<=b[i+1].t;j++) 
			{
				heapadd(a[j].value,a[j].time);
			}
			int temp=0;
			while (heaptail&&temp<b[i+1].p)
			{
				heaptype now=heappop();
				tail++;
				temp++;
				outlist[tail]=now.key;
			}
		}

		scanf("%d",&c);
		printf("%s",a[outlist[c]].name);
		
		for (int i=1;i<q;i++)
		{
			scanf("%d",&c);
			printf(" %s",a[outlist[c]].name);
		}
		
		printf("\n");
	}

	return 0;
}

【E】HDU 5441 Travel

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Problem Description

Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are n cities and m bidirectional roads connecting the cities. Jack hates waiting too long on the bus, but he can rest at every city. Jack can only stand staying on the bus for a limited time and will go berserk after that. Assuming you know the time it takes to go from one city to another and that the time Jack can stand staying on a bus is x minutes, how many pairs of city (a,b) are there that Jack can travel from city a to b without going berserk?

Input

The first line contains one integer T,T≤5, which represents the number of test case.

For each test case, the first line consists of three integers n,m and q where n≤20000,m≤100000,q≤5000. The Undirected Kingdom has n cities and m bidirectional roads, and there are q queries.

Each of the following m lines consists of three integers a,b and d where a,b∈{1,…,n} and d≤100000. It takes Jack d minutes to travel from city a to city b and vice versa.

Then q lines follow. Each of them is a query consisting of an integer x where x is the time limit before Jack goes berserk.

Output

You should print q lines for each test case. Each of them contains one integer as the number of pair of cities (a,b) which Jack may travel from a to b within the time limit x.

Note that (a,b) and (b,a) are counted as different pairs and a and b must be different cities.

Sample Input

1
5 5 3
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6000
10000
13000

Sample Output

2
6
12

题意

给了一个无向图。给出一个x作为两点间每一段路径的上限。求从a到b上所有的路径长度都不超过x的（a，b）的点对总数。

分析

这样的并查集其实做过很多次了已经。

对所有边按照长度排序，询问也是按照长度先排序，然后从小到大进行。边长满足条件的两端并进一同一个集中，每合并两个集合，总点对数都增加 $左集合的点数/*右集合的点数/*2$ （a,b和b,a算两个不同点对）

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
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: 1005
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int father[20010],ran[20010]; 

void clean_father(int n)
{
	for (int i=1;i<=n;i++)
	{
		father[i]=i;
		ran[i]=1;
	}
}

int getfather(int x)
{
	if (father[x]!=x) father[x]=getfather(father[x]);
	return father[x];
}

void link_ran(int x,int y)
{
	int xx=getfather(x),yy=getfather(y);
	if (ran[xx]>ran[yy]) 
	{
		father[yy]=xx;
		ran[xx]+=ran[yy];
	}
	else 
	{
		father[xx]=yy;
		ran[yy]+=ran[xx];
	}
}

typedef struct nod
{
	int a,b,c;
} node ;

bool op(node a,node b)
{
	return a.c<b.c;
}

node a[100010];

typedef struct nod1
{
	int limit,no;
	long long ans;
} node1 ;

bool op1(node1 a,node1 b)
{
	return a.limit<b.limit;
}

bool op2(node1 a,node1 b)
{
	return a.no<b.no;
}

node1 b[5010];

bool flag[20010];

int main()
{
	//freopen("1005.txt","r",stdin);

	int t;
	scanf("%d",&t);

	for (int tt=1;tt<=t;tt++)
	{
		int n,m,q;
		scanf("%d%d%d",&n,&m,&q);

		clean_father(n);

		for (int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);

		sort(&a[1],&a[m+1],op);

		for (int i=1;i<=q;i++)
		{
			scanf("%d",&b[i].limit);
			b[i].no=i;
		}

		sort(&b[1],&b[q+1],op1);

		int j=1;
		long long ans=0;
		for (int i=1;i<=q;i++)
		{
			for (;j<=m;j++)
			{
				if (a[j].c>b[i].limit) break;
				if (getfather(a[j].a)!=getfather(a[j].b))
				{
					ans+=ran[getfather(a[j].a)]*ran[getfather(a[j].b)]*2;
					link_ran(a[j].a,a[j].b);
				}
			}

			b[i].ans=ans;
		}

		sort(&b[1],&b[q+1],op2);

		for (int i=1;i<=q;i++) printf("%lld\n",b[i].ans);
	}

	return 0;
}
Related Posts