2024牛客暑期多校训练营7
J：
J-Ball_2024牛客暑期多校训练营7 (nowcoder.com)
题目大意：
在二维笛卡尔坐标系中，有一根长度为 l的细长棍，宽度可以忽略不计，垂直于 y 轴，左端点位于原点 O(0,0)。
有一个小球，可以看作是一个点，位于 P(x,y)。
现在要确定是否存在一个支点，使得这根细长棍在绕该支点旋转时可以击中小球。请帮 Chino 找出任何满足条件的支点，或者告诉她不存在这样的支点。
若在旋转过程中，细长棍或其端点经过点 P(x,y)，则视为可以击中小球。
解析：
以原点为圆心，半径为l的圆是一个大圆。但是对于圆心位于x轴且x逐渐增大的圆心，其半径为l-x，显然圆变小了。同样，对于x轴上的圆心从l 到0，圆也是逐渐变小的。所以最大的两个圆是以原点为圆心，半径为l的圆，另一个是以(l,0)为圆心，半径为l的圆。也就是对于棍子上任意一个在 (0,l)之间的支点 x0，当支点远离原点或右端点时，棍子旋转所覆盖的圆会逐渐变小。
因此，只需要判断点(x,y)是否位于两个大圆其中一个圆的内部即可，是，那么就是可以击中，否则就不可击中。
#include<bits/stdc++.h>using namespace std;
using ll = long long;int main() {int t; cin >> t;while(t--) {ll l,x,y; cin >> l >> x >> y;if(x*x+y*y<=l*l) cout << "Yes\n" << 0 << '\n';else if((l-x)*(l-x)+y*y <= l*l) cout << "Yes\n" << l << '\n';else cout << "No\n";}return 0;
}
I：
I-Fight Against the Monster_2024牛客暑期多校训练营7 (nowcoder.com)
题目大意：
这道题目需要我们计算击败怪兽所需的最小初始战争机器数量。怪兽的初始生命值为 h，而每台战争机器可以执行两种操作：“战斗”和“制造”：
- 战斗：每次操作可以使怪兽的生命值减少1，但是这台机器之后将无法使用（损坏）。
- 制造：选择 m台机器，同时对它们使用制造功能，可以制造出 k台新机器。每台机器只能被用来制造一次，但之后仍可以进行战斗。
解析：
这个时候 m == k，每次制造机器，机器数量都能够翻倍。
那么如果 h > m 的时候，总存在一个n，使得n*m >= h，这个时候的最小机器初始值是m 。
如果 h < m 的话，只需要h辆机器直接战斗 。
当 m != k 我们知道当怪兽的血量越高，那么初始的机器的数量也就会越多。这个时候我们就可以二分答案，mid表示初始的数量。这样我们可以通过计算对于每个机器都进行制造后的总机器数。如果总机器数要大于等于怪兽的血量，那么就可以减少r，否则就增加l。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll m,h,k;int main() {int T;cin >> T;while (T--) {cin >> m >> k >> h;if(m != k){ll l = 0,r = h;while(l <= r){ll mid = (l + r) >> 1;//Mid 是 最小初始机器数 ll res = mid;// m - k 表示每次制作机器实际消耗的机器数 //(mid-m)/(m-k)表示可以进行多少次完整的制造操作 // (mid-m)/(m-k) + 1是加上初始的m台机器第一次制造 if(mid >= m) res += (( mid - m ) / ( m - k ) + 1 ) * k;if(res >= h) r = mid - 1;else l = mid + 1;}cout << l << '\n';}else cout << min(h,m) << '\n';// 这个时候 m == k，每次制造机器，机器数量都能够翻倍//那么如果 h > m 的时候，总存在一个n，使得n*m >= h，这个时候的最小机器初始值是m // 如果 h < m 的话，只需要h辆机器直接战斗 }return 0;
}