湖南大学第十六届程序设计竞赛（重现赛）

比赛
字数统计: 2.1k   |   阅读时长≈ 10 分钟

A-Triangles

题目大意

给你三个点的坐标，问这三个点能否构成三角形，如果能则输出三角形的形状。

解题思路

标准的中学数学知识，没啥好说的。

当三点共线的时候，三点无法构成三角形，即两条边斜率相同，$\frac{y_1-y2}{x_1-x_2}=\frac{y_1-y_3}{x_1-x_3}$，需要把除法转成乘法，防止分母为0。

完整代码

（做法一）余弦定理

需要注意精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double cal(int x1, int y1, int x2, int y2) {
	double ans = sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int x1, x2, x3, y1, y2, y3;
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
		double a = cal(x1, y1, x2, y2), b = cal(x1, y1, x3, y3), c = cal(x2, y2, x3, y3);
		double cos1 = (a * a + b * b - c * c) / (2 * a * b), cos2 = (a * a + c * c - b * b) / (2 * a * c), cos3 = (b * b + c * c - a * a) / (2 * b * c);
		if ((y1 - y2) * (x1 - x3) == (x1 - x2) * (y1 - y3))
            cout << "invalid" << endl;
		else {
			if ((abs(cos1) < 1e-5) || (abs(cos2) < 1e-5) || (abs(cos3) < 1e-5)) cout << "right" << endl;
			else if (cos1 < 0 || cos2 < 0 || cos3 < 0)	cout << "obtuse" << endl;
			else cout << "acute" << endl;
		}
	}
	return 0;
}

（做法二）勾股定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int cal(int x1, int y1, int x2, int y2) {
    int ans = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        int x1, x2, x3, y1, y2, y3;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        int dis[5];
        dis[1] = cal(x1, y1, x2, y2), dis[2] = cal(x1, y1, x3, y3), dis[3] = cal(x2, y2, x3, y3);
        sort(dis + 1, dis + 4);
        if ((y1 - y2) * (x1 - x3) == (x1 - x2) * (y1 - y3))
            cout << "invalid" << endl;
        else {
            if (dis[3]==dis[1]+dis[2]) cout << "right" << endl;
            else if (dis[3]>dis[1]+dis[2])   cout << "obtuse" << endl;
            else cout << "acute" << endl;
        }
    }
    return 0;
}

B-Yuki with emofunc and playf

题目大意

刚开始你有一个数字$k=1$，给你两个数字n和x，你每次可以进行两种操作，$k=k\times 10$和$k=k+x-1$。问让k能被n整除的最少操作次数。

解题思路

典型的bfs。

起点从1%n开始，初始步数为0，开始搜索即可。

注意从1%n开始，每个点需要用vis数组标记一下，标记过的点就不用走了。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void bfs(ty a) {
	queue<ty> q;
	q.push(a);
	while (!q.empty()) {
		ty t = q.front(); q.pop();
		if (vis[t.k])	continue;
		vis[t.k] = 1;
		if (!t.k) {
			ans = t.step; break;
		}
		q.push({ (t.k * 10) % n,t.step + 1 });
		q.push({ (t.k + x - 1) % n , t.step + 1 });
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> x;
	bfs({ 1%n,0 });
	if (ans == 1e9)	cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}

D-Queuing

题目大意

给你两个数n和m，有n个窗口m个人，每个人都有$\frac{1}{n}$的概率走到任意一个窗口，你是第m个人，求你的排队次序的期望。

解题思路

概率题or规律题。

把排在前面的m-1个人可以看成是二项分布。

那么排在你前面的人的个数的期望就是np，即$(m-1)\times \frac{1}{n}$。

这只是排在你前面的人数，排名还需要加一。

其实多写几种情况也能看出答案。

完整代码

1
2
3
4
5
6
7
8
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	double ans = 1.0 + 1.0 * (m - 1) / n;
	printf("%.6lf\n", ans);
	return 0;
}

F-Team

题目大意

给你两个数a和b，以及一个很小的数c，求三个数的和。

解题思路

签到题。

大数模拟。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void add(string s) {
	rep(i, 0, s.length() - 1) {
		int t = s[i] - '0';
		ch[i] += t;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	string a, b, c; cin >> a >> b >> c;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	add(a), add(b), add(c);
	rep(i, 0, 100) {
		ch[i + 1] += ch[i] / 10;
		ch[i] %= 10;
		if (ch[i] > 0)	len = max(len,i);
	}
	per(i, len, 0)	cout << ch[i];
	cout << endl;
	return 0;
}

G-Binbin’s string

题目大意

给你两个字符串s和t，你可以进行两种操作，删除某一段字符串和在任意位置添加某一段字符串，问把s变成t最少需要多少次操作。

解题思路

当两个字符串完全相同的时候，不需要任何操作。

无论两个字符串啥样，最多进行两次操作，即全部删除，添加t字符串。

那么只需要考虑1次操作的情况。

假设长的那段是s。

只需要先从头开始找相同的一段，再从结尾开始找相同的一段，判断两段的和是否刚好构成t字符串。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	string s, t; cin >> s >> t;
	if (s == t)	cout << 0 << endl;
	else {
		int lens = s.length() - 1, lent = t.length() - 1;
		int ans = 2;
        if (lens <= lent) swap(s,t),swap(lens,lent);
        int fa = 0, fb = lent, fc = lens;
		while (s[fa] == t[fa] && fa <= lent)	fa++;
		while (fb >= fa && s[fc] == t[fb] && fb >= 0)	fb--,fc--;
		if (fa - fb == 1)	ans = 1;
		cout << ans << endl;
	}
	return 0;
}

I-Binbin and Balls

题目大意

你拿着两个球，站在一个n层高的楼上，球存在某一个楼层刚刚好丢下去不会碎，碎了的球就不能再扔了，问你最坏情况下找到这个楼层的最小次数。

解题思路

假设最少次数是k次，那么最好的选择是先从第k层扔，如果碎了，需要从1~k-1开始扔，如果没碎，则下一次从k+k-1层开始丢，这样能够保证，在k次以下一定能够在相应的区间找到，并且所有区间和最大，即搜索范围最大。

对于k来说，能确定的范围为$\sum\limits_{i=1}^{k}i$，在保证这个sum大于n的条件下，二分搜索使k最小即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		ll n; cin >> n;
		ll l = 1, r = 2e9;
		while (l < r) {
			ll mid = l + r >> 1;
			if (mid * (mid + 1) / 2 < n)	l = mid + 1;
			else r = mid;
		}
		cout << l << endl;
	}
	return 0;
}

L-Cracked Pipes

题目大意

有六种类型的水管，给你一个水管的分布图，问你能否从起点连接到终点。

解题思路

这题没啥好说的，就一个dfs。

注意判断一下起点和终点就行。

完整代码

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
const int N = 2e5+5;
vector<short> M[N], vis[N];
int flag = 0;
vector<char> dis[10];
int n, m;

pair<int, int> check(char t) {
	if (t == 'U')	return { 0,-1 };
	if (t == 'D')	return { 0,1 };
	if (t == 'L')	return { -1,0 };
	if (t == 'R')	return { 1,0 };
}

void dfs(int x, int y, char d) {
	if (x<1 || y<1 || x>m || y>n || vis[y][x]|| flag)	return;
	int t = M[y][x];
	if (t == 1 && (d == 'L' || d == 'R'))	return;
	if (t == 2 && (d == 'U' || d == 'D'))	return;
	if (t == 3 && (d == 'R' || d == 'D')) return;
	if (t == 4 && (d == 'L' || d == 'U')) return;
	if (t == 5 && d == 'U')	return;
	if (t == 6 && d == 'D') return;
	if (x == m && y == n) {
		flag = 1; return;
	}
	vis[y][x] = 1;
	for (auto c : dis[t]) {
		pair<int, int> tmp = check(c);
		int dx = tmp.first, dy = tmp.second;
		dfs(x + dx, y + dy, c);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	rep(i, 1, n) {
        M[i].push_back(0);
        vis[i].push_back(0);
		rep(j, 1, m) {
			short t; cin >> t;
			M[i].push_back(t);
			vis[i].push_back(0);
		}
	}
	if ((M[1][1] == 1) || (M[1][1] == 3)|| (M[n][m] == 1) || (M[n][m] == 3)) {
		cout << "NO" << endl;
	}
	else {
		dis[1].push_back('U');dis[1].push_back('D');
		dis[2].push_back('L');dis[2].push_back('R');
		dis[3].push_back('D');dis[3].push_back('R');
		dis[4].push_back('U');dis[4].push_back('L');
		dis[5].push_back('U');dis[5].push_back('L');
        dis[5].push_back('R');dis[6].push_back('L');
		dis[6].push_back('R');dis[6].push_back('D');
		dfs(1, 1, 'R');
		if (flag)	cout << "YES" << endl;
		else cout << "NO" << endl;
    }
	return 0;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信