语言漩涡

thirtiseven 的博客

0%

2017 ACM Hong Kong onsite

Posted on Edited on

题目链接 https://www.jisuanke.com/contest/967

自己打的...没有java队友...高精度题看到就扔...结果有三个高精度题 喵喵喵？ 吃吃喝喝水水群，最后E题还没做完...只出了三题 还是要提高自己的姿势水平，不要再依赖队友了（现在并没有队友了哭哭），提高切水题的速度，以及继续学习那些大家都会但是我好菜啊并不会的算法。 应该要继续补题...但是今天做B感觉人生毫无希望啊？

###A

//TODO

###B //TODO

###C //TODO

###D 最短路模板题 Dijkstra解决 

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
#include <iostream>
#include <vector> 
#include <queue>
#include <cstring>
#define INF 0x7FFFFFFF 
#define maxn 1000 

class Dijkstra{ 
private:
	struct HeapNode{ 
		int u;
		int d;
		HeapNode(int u, int d) :u(u), d(d){}
		bool operator < (const HeapNode &b) const{
			return d > b.d; 
		}
	};
	struct Edge{ 
		int v;
		int w; 
		Edge(int v, int w) :v(v), w(w){}
	}; 
	std::vector<Edge>G[maxn];
	bool vis[maxn];
public:
	int d[maxn];
	void clear(int n){
		int i;
		for(i=0;i<n;++i) 
			G[i].clear(); 
		for(i=0;i<n;++i) 
			d[i] = INF;
		memset(vis, 0, sizeof(vis)); 
	}
	void AddEdge(int u, int v, int w){ 
		G[u].push_back(Edge(v, w));
	}
	void Run(int s){ 
		int u;
		std::priority_queue<HeapNode> q;
		d[s] = 0; 
		q.push(HeapNode(s, 0)); 
		while (!q.empty()){
			u = q.top().u;
			q.pop();
			if (!vis[u]){
				vis[u] = 1;
				for (std::vector<Edge>::iterator e = G[u].begin(); e != G[u].end(); ++e) {
					if (d[e->v] > d[u] + e->w){ 
						d[e->v] = d[u] + e->w;
						q.push(HeapNode(e->v, d[e->v])); 
					}
				}
			}
		}
	}
};

int main(int argc, char *argv[]) {  
	int m;
	while (std::cin >> m) {
		Dijkstra dij;
		dij.clear(m+1);
		int from, to;
		int tu, tv, tw;
		std::cin >> from >> to;
		while(std::cin >> tu) {
			if(!tu) {
				break;
			}
			std::cin >> tv >> tw;
			dij.AddEdge(tu, tv, tw);
			dij.AddEdge(tv, tu, tw);
		}
		dij.Run(from);
		std::cout << dij.d[to] << '\n';
	}
	return 0;
}

###E 给出在同一条直线上的L个备选的基站，从中选出S个位置放置基站，使相邻两个基站之间的最短距离最长。 二分答案，对于每一个答案a，从第一个位置开始，记录该位置+a之后的下一个基站，计数。重复执行，如果cnt >= S，则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
#include <iostream>
#include <algorithm>
int p[100009];
int l, s;

bool check(int a) {
	int now = p[0];
	int ans = 1;
	for (int i = 0; i < l;) {
		do {
			i++;
			if(i >= l) {
				goto next;
			}
		} while(p[i]<now+a);
		now = p[i];
		ans++;
	}
	next:
	if (ans >= s) {
		return true;
	}
	return false;
}

int main(int argc, char *argv[]) {  
	while (std::cin >> l >> s) {
		if (l == 0 && s == 0) break;
		for (int i = 0; i < l; i++) {
			std::cin >> p[i];
		}
		std::sort(p, p+l);
		int left = 1, right = p[l-1]-p[0], middle;
		while (left <= right) {
			middle = (left + right)/2;
			if (check(middle)) {
				left = middle+1;
			} else {
				right = middle-1;
			}
		}
		std::cout << right << '\n';
	}
	return 0;
}

###F 计(zhi)算(jie)几(bao)何(li) 有一堆自行车和一堆顾客，每个顾客会在分别不同的范围里面找自行车，求每个顾客的范围里面能找到的自行车。考虑到小的一塌糊涂的数据范围，直接数组存点暴力求答案就好了。这题我猜大数据的时候会有什么非常毒瘤的算法可以做，不懂不懂。 这题的读入...真是服了... 我大概...C语言没学好... scanf("(%d,%d)",x,y) 这种奇怪的操作...我好像...写不对？然后浪费了一堆时间...非常难过啊 

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
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <cstring>

struct point {
	long long x, y;
	point() { };
};

int main(int argc, char *argv[]) {  
	int m, n;
	while (scanf("%d %d", &m, &n)) {
		point cost[1009], bike[1009];
		if (m==0 && n==0) {
			break;
		}
		std::string temp;
		getchar();
		for (int i = 0; i < m; i++) {
			std::cin >> temp;
			int pos;
			for (int b = 0; b < temp.length(); b++) {
				if(temp[b] == ',') pos = b;
			}
			bike[i].x = stoll(temp.substr(1,pos-1));
			bike[i].y = stoll(temp.substr(pos+1,temp.length()-pos));
		}
		for (int i = 0; i < n; i++) {
			std::cin >> temp;
			int pos;
			for (int b = 0; b < temp.length(); b++) {
				if(temp[b] == ',') pos = b;
			}
			cost[i].x = stoll(temp.substr(1,pos-1));
			cost[i].y = stoll(temp.substr(pos+1,temp.length()-pos));
		}
		long long s[1009];
		memset(s, 0, sizeof(s));
		for (int i = 0; i < n; i++) {
			scanf("%lld", &s[i]);
		}
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < m; j++) {
				if ( (cost[i].x - bike[j].x)*(cost[i].x - bike[j].x) + (cost[i].y - bike[j].y)*(cost[i].y - bike[j].y) <= s[i] * s[i] ) {
					cnt++;
				}
			}
		std::cout << cnt << (i!=n-1?" ":"\n");
		}
	}	
	return 0;
}

###G 完全背包的找零钱问题，具体不说了。 

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
#include <iostream>
#include <map>
#include <cstring>

const int maxm = 100000;
std::map<int, int> miao;
int coin[12];
int ans[12];

void FindMin(int money, int n) {
	int coinNum[maxm];
	int coinValue[maxm];
	coinNum[0]=0;
	for(int i=1;i<=money;i++) {
		int minNum=i;
		int usedMoney=0;
		for(int j=0;j<n;j++) {
			if(i>=coin[j]) {
				if(coinNum[i-coin[j]]+1<=minNum && (i==coin[j] || coinValue[i-coin[j]]!=0)) {
					minNum = coinNum[i-coin[j]]+1;
					usedMoney = coin[j];
				}
			}
		}
		coinNum[i] = minNum;
		coinValue[i] = usedMoney;
	}
	if(coinValue[money]==0) {
		std::cout<<"-1"<<std::endl;
	} else {
		while(money>0) {
			ans[miao[coinValue[money]]]++;
			money-=coinValue[money];
		}
		for (int i = 0; i < n; i++) {
			std::cout << ans[i] << (i!=n-1?" ":"\n");
		}
	}
}

int main(int argc, char *argv[]) {
	int u, n;	
	while(std::cin >> u >> n) {
		memset(ans, 0, sizeof(ans));
		for (int i = 0; i < n; i++) {
			std::cin >> coin[i];
			miao[coin[i]] = i;
		}
		FindMin(u, n);
	}
	return 0;
}

###H //TODO ###I //TODO ###J //TODO

我感觉...我顶到天也就能再补几个高精度吧... 菜鸡太菜了，之前都没有补过题...什么比赛都是打完就扔...