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

  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

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

方法一:12i(i+1)\frac{1}{2}i(i+1) 位完全平方数,则其中 偶数÷2 和 奇数 分别为完全平方数。则i=a2,i+1=2b2i=a^2,i+1=2b^2,或i=2b2,i+1=a2i=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));
}
}