2020-12-09

2018 ACM-ICPC, Asia Jiaozuo Regional

字数统计: 1.8k字 | 阅读时长: 9分

solved	A	B	C	D	E	F	G	H	I	J	K	L
5 / 12	O	·	·	O	Ø	O	·	·	O	·	·	·

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

比赛链接

A - Xu Xiake in Henan Province

solved by Tryna. 0:05(+)

AC代码

#include<bits/stdc++.h>
using namespace std;
 
int t, a[5];
 
void solve() {
	for(int i = 0; i < 4; i++) scanf("%d", &a[i]);
	int f = 0;
	for(int i = 0; i < 4; i++){
		if(a[i]) f++;
	}
	if(f == 0) puts("Typically Otaku");
	else if(f == 1) puts("Eye-opener");
	else if(f == 2) puts("Young Traveller");
	else if(f == 3) puts("Excellent Traveller");
	else puts("Contemporary Xu Xiake");
}
 
int main() {
	scanf("%d", &t);
	while(t--)
		solve();
}

D - Keiichi Tsuchiya the Drift King

solved by Tryna & lllllan. 2:40(+)

题意： 给出车子的长和宽以及圆的半径和弯的角度，求这辆车能过弯的最小道路宽度

题解： 先来看一张图

由上图容易看出分两种情况

$\theta <= d$ 时，此时答案为红色三角形的斜边$$\sqrt{b^2 + (a + r)^2} - r$$
$\theta > d$ 时，此时答案为绿色的边$${\sqrt{b^2 + (a + r)^2}} *{\cos{(\theta - d)}}- r$$

AC代码

#include<bits/stdc++.h>
using namespace std;
const double pi = acos((double)(-1));
#define eps 1e-8

int sgn(double x) {
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}

int t;
double a, b, r, d;

void solve() {
	scanf("%lf %lf %lf %lf", &a, &b, &r, &d);
	double x = sqrt((r + a) * (r + a) + b * b);
	if(sgn((atan(b / (a + r))) * (180 / pi) - d) <= 0) printf("%.12f\n", x - r);
	else{
		d = (atan(b / (a + r))) * (180 / pi) - d;
		double result = x * cos(d * pi / 180) - r;
		printf("%.12f\n", result);
	}
}

int main(){
	scanf("%d", &t);
	while(t--)
	 solve();
	return 0;
}

E - Resistors in Parallel

Solved by Sstee1XD & Tyrna. (-)

题解： 没啥想法打表找规律，发现和质数很很大关系。然后就写java大数。

AC代码

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
	static BigInteger one = new BigInteger("1");
	static BigInteger six = new BigInteger("6");
	static BigInteger two = new BigInteger("2");
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		while (t != 0) {
			t--;
			BigInteger a = in.nextBigInteger();
			if (a.compareTo(one) == 0) {
				System.out.println("1/1");
				continue;
			}
			if (a.compareTo(six) < 0) {
				System.out.println("2/3");
				continue;
			}
			BigInteger tt = new BigInteger("1");
			BigInteger dd = new BigInteger("2");
			BigInteger now = new BigInteger("6");
			Integer tgo = 5;
			while (a.compareTo(now) > 0) {
				while (!isPrime(tgo)) {
					tgo += 2;
				}
				BigInteger go = new BigInteger(tgo.toString());
				now = now.multiply(go);
				if (a.compareTo(now) < 0) {
					break;
				}
				tt = tt.multiply(go);
				dd = dd.multiply(go.add(one));
				BigInteger tmp = tt.gcd(dd);
				tt = tt.divide(tmp);
				dd = dd.divide(tmp);
				tgo += 2;
			}
			System.out.println(tt + "/" + dd);
		}
	}
	static public boolean isPrime(int x) {
		for (int i = 2; i <= Math.sqrt(x); ++i) {
			if (x % i == 0) return false;
		}
		return true;
	}
}

F. Honeycomb

solved by lllllan. 04:40(+5)

题意： 【巨恶心的输入】按图形给出一个蜂巢，要求计算从 $S$ 点到 $T$ 点最少需要访问多少个点。

题解： 【不脑抽写个优先队列就轻松过了Orz】。输入虽然有点恐怖，但是根据规律我们可以自行给每个点进行编号【我的编号规则为：第一列从上到下编号 $[1,r]$ ，第二列从上到下编号 $[r+1,2r]$ 】。
然后就是去计算每个蜂窝的中心点【 $S、T$ 在蜂窝中心】、三条边【一个蜂窝有六条边，但是为了较少重复计数，选择其中三边即可】的位置。如果某条边为空，则对两边的蜂窝 “建边” 【BFS嘛，直接存边然后去遍历】。

【一些数据】

设从左上第一个蜂窝 $[1,1]$ 【i, j】到右下最后一个蜂窝 $[r,c]$ 的编号为 $(j - 1) * r + i$ 。

$[i,j]$ 蜂窝的编号为 $id = (j - 1) * r + i$

$[i,j]$ 蜂窝的中心点在图中的坐标为 $[x][y] = [(j \& 1) ~? ~(4 * i - 1) : (4 * i + 1)][6 * j - 1]$ 。

$[i,j]$ 蜂窝的下边中心的在图中的坐标为 $[x + 2][y]$ ，连接的蜂窝编号为 $id + 1$

$[i,j]$ 蜂窝的右上边在图中的坐标为 $[x - 1][y + 3]$ ，连接的蜂窝编号为 $id + r - (j \% 2 == 1)$

$[i,j]$ 蜂窝的右下边在图中的坐标为 $[x + 1][y + 3]$ ，连接的蜂窝编号为 $id + r + (j \% 2 == 0)$

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
const int maxm = 6 * maxn;
#define pII pair<int, int>
#define fi first
#define se second

int _T, r, c;
int bg, ed;
int vis[maxn* maxn];
char mp[maxm][maxm];
vector<int> G[maxn * maxn];

void BFS () {
	queue<pII> Q;
	memset(vis, 0, sizeof vis);
	Q.push({bg, 1}); vis[bg] = 1;
	while (!Q.empty()) {
		pII e = Q.front(); Q.pop();
		int u = e.fi, w = e.se;
		if (u == ed) return (void)(printf("%d\n", w));
		for (auto v : G[u]) {
			if (vis[v]) continue;
			Q.push({v, w + 1});	vis[v] = 1;
		}
	}
	printf("-1\n");
}

void run () {
	scanf("%d%d", &r, &c); getchar();
	int num = r * c + 10;
	for (int i = 0; i <= num; ++i) G[i].clear();
	for (int i = 1; i <= 4 * r + 3; ++i) gets(mp[i] + 1);
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			int id = (j - 1) * r + i;
			int x = (j & 1) ? (4 * i - 1) : (4 * i + 1);
			int y = 6 * j - 1;
			if (mp[x][y] == 'S') bg = id;
			if (mp[x][y] == 'T') ed = id;
			if (mp[x + 2][y] == ' ') {
				G[id].push_back(id + 1);
				G[id + 1].push_back(id);
			}
			if (mp[x - 1][y + 3] == ' ') {
				G[id].push_back(id + r - (j & 1));
				G[id + r - (j & 1)].push_back(id);
			}
			if (mp[x + 1][y + 3] == ' ') {
				G[id].push_back(id + r + (j % 2 == 0));
				G[id + r + (j % 2 == 0)].push_back(id);
			}
		}
	}
	BFS();
}

int main () {
	scanf("%d", &_T);
	while (_T--) run();
	return 0;
}

I. Distance

solved by lllllan. & Sstee1XD. 00:30(+)

题意： $n$ 个点，每组数据有 $n-1$ 个数，表示第 $i$ 个点与前一个点的距离。要求选 $1$ ~ $n$ 个点，每次输出选中点的两两距离和，并要求和最大。

题解： 【前缀和】。列好每个点的坐标之后，只要一前一后取点即可【即第一次取最左边的点，第二次取最右边的点（可以达到两个点的最大距离），第三次又取最左边第二个点，，，以此类推】。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
ll a[N];
int _T, n;
ll x;
void run () {
	scanf("%d", &n);
	for (int i = 2; i <= n; ++i) {
		scanf("%lld", &x);
		a[i] = a[i - 1] + x;
	}
	ll sum = 0;
	ll pre_sum = 0;
	for (int i = 1; i <= n; ++i) {
		if ((i & 1) == 0) {
			pre_sum += abs(a[(n + 1) - i / 2] - a[i / 2]);
		} 
		sum += pre_sum;
		printf("%lld%c", sum, " \n"[i == n]);
	}
}

int main () {
	scanf("%d", &_T);
	while (_T--) run();
	return 0;
}