2017 ACM/ICPC 乌鲁木齐赛区 网络赛

OI&ACM, ACM训练
  1. 1 Banana
  2. 2 Out-out-control cars
  3. 3 Coconut
  4. 4 Hack Portals
  5. 5 Half-consecutive Numbers

萌帝的题解

1 Banana

有一些猴子和一些地点，每只猴子有喜欢吃的香蕉种类，每个地方种有一些种类的香蕉。输出所有数对(x,y)，表示第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
#include <algorithm>
#include <cstdio>
int T,n,m,tot,a[55][55],b[55][55],ans[2505];
int main() {
	for(scanf("%d", &T); T; T--) {
		scanf("%d%d", &n, &m);
		for(int i=1; i<=50; i++) a[i][0]=b[i][0]=0;
		for(int i=1,x,y; i<=n; i++) {
			scanf("%d%d", &x, &y);
			a[x][++a[x][0]]=y;
		}
		for(int i=1,x,y; i<=m; i++) {
			scanf("%d%d", &x, &y);
			b[x][++b[x][0]]=y;
		}
		for(int x=1; x<=50; x++) {
			tot=0;
			for(int i=1; i<=a[x][0]; i++) {
				int y=a[x][i];
				for(int j=1; j<=b[y][0]; j++) {
					int z=b[y][j];
					ans[++tot]=z;
				}
			}
			std::sort(ans+1,ans+tot+1);
			tot=std::unique(ans+1,ans+tot+1)-ans-1;
			for(int i=1; i<=tot; i++)
				printf("%d %d\n", x, ans[i]);
		}
		printf("\n");
	}
}

2 Out-out-control cars

一辆车被描述成一个运动的三角形，(x1,y1)(x2,y2)(x3,y3)表示车的跨度，向量(dx,dy)表示车运动的方向，即一秒钟之后，车的坐标为(xi+dx,yi+dy)。求两辆车是否会相撞。

把一个三角形固定，另一个相对运动。判断运动路径所在射线与固定的三角形的三条边是否相交。

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
#include <cstdio>
int T;
struct node {
	long long x,y;
}a[2][5];
node operator - (node a, node b) {
	a.x -= b.x; a.y -= b.y; return a;
}
node operator + (node a, node b) {
	a.x += b.x; a.y += b.y; return a;
}
long long operator * (node a, node b) {
	return a.x*b.y - a.y*b.x;
}
inline bool Judge(bool f) {
	long long x0 = a[f][4].x-a[!f][4].x, y0 = a[f][4].y-a[!f][4].y;
	for(int i = 1; i <= 3; i++) {
		for(int j = 1; j <= 3; j++) {
			node A = a[!f][i], B = a[!f][i%3+1], C = a[f][j], D = a[f][j]+a[f][4]-a[!f][4];
			long long k1 = (D-A) * (B-A), k2 = (B-A) * (C-A);
			double x = D.x + (double)(C.x-D.x)*k1/(k1+k2), y = D.y + (double)(C.y-D.y)*k1/(k1+k2);
			if(x0 && k1+k2 && (double)(C.x-D.x)*k2/(k1+k2)/x0<=0 && (x-A.x)*(x-B.x)<=0 && (y-A.y)*(y-B.y)<=0)
				return 1;
			if(y0 && k1+k2 && (double)(C.y-D.y)*k2/(k1+k2)/y0<=0 && (x-A.x)*(x-B.x)<=0 && (y-A.y)*(y-B.y)<=0)
				return 1;
		}
	}
	return 0;
}
int main() {
	scanf("%d", &T);
	for(int tt = 1; tt <= T; tt++) {
		for(int i = 0; i <= 1; i++) 
			for(int j = 1; j  <= 4; j++)
				scanf("%lld%lld", &a[i][j].x, &a[i][j].y);
		printf("Case #%d: ",tt);
		printf(Judge(0)||Judge(1)?"YES\n":"NO\n");
	}
	
}

3 Coconut

n个点排成一行，点权C[i]；n-1条边相连，边权D[i]。从1走到n，走过一个点+C[i]，走过一条边-D[i]*B，问有没有和小于零的时候。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
int T,n,B,C[1005],D[1005];
inline bool Calc()
{
	int a=0;
	for(int i=1;i<n;i++)
	{
		a+=C[i]-D[i]*B;
		if(a<0) return 0;
	}
	return 1;
}
int main()
{
	for(scanf("%d",&T);T;T--)
	{
		scanf("%d%d",&n,&B);
		for(int i=1;i<=n;i++) scanf("%d",&C[i]);
		for(int i=1;i<n;i++) scanf("%d",&D[i]);
		if(Calc()) printf("Yes\n");
		else printf("No\n");
	}
}

4 Hack Portals

5 Half-consecutive Numbers

\(t_i = \frac{1}{2}i(i+1)\) 。给定 \(N\) ，求最小的 \(t_r(\ge N)\) ，使 \(t_r\) 为完全平方数，若不存在输出\(-1\)。 \(1 \le N \le 10^{16}\)

方法一：\(\frac{1}{2}i(i+1)\) 位完全平方数，则其中 偶数÷2 和 奇数 分别为完全平方数。则\(i=a^2,i+1=2b^2\)，或\(i=2b^2,i+1=a^2\)，枚举a，暴力打表。

方法二：OEIS A001108

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <cstdio>
const int maxn = 22;
int T;
long long n, A[maxn+1], B[maxn+1], C[maxn+1];
int main() {
	B[0] = 0;
	C[0] = 1;
	for(int i = 1; i <= maxn; i ++) {
		B[i] = B[i-1] + C[i-1];
		C[i] = B[i-1] + B[i];
		A[i] = i&1 ? C[i] * C[i] : (B[i] * B[i]) << 1;
	}
	scanf("%d",&T);
	for(int tt = 1; tt <= T; tt++) {
		scanf("%lld", &n);
		printf("Case #%d: %lld\n", tt, *std::lower_bound(A+1, A+maxn+1, n));
	}
}