SDKD 2023 Summer Team Contest C 训练赛总结
2023-08-10 13:00 - 18:00
比赛过程
比赛时我们的题目安排是甲负责前4个, 乙负责中间4个, 丙负责后4个; 读题过程中, 乙发现E是个签到题, 随后甲也发现B是个签到题; 随后丙觉得I题有思路便做了标记, 乙觉得F题可以做, 于是也做了标记; 在第一个小时内我们标记了这四个题, 然后丙觉得L的题意很简单, 但是不好优化, 甲看了之后很感兴趣并领了L题, 而乙觉得G题题目要求很简单, 并且感觉是个贪心, 于是找丙一起讨论; 经过半个小时后乙和丙觉得G并不好想于是便放弃了; 再过了半个小时后甲想好了L, 并且找丙去看A题; 于是在剩下的一小时里甲和丙在看A题, 乙在看H题; 开题后甲先写了B题, 结果wa了一发, 于是乙接力去写E题, 在ac后因为甲还是没有找出错, 于是乙继续写F题, 虽然第一发wa了但是好在立马找出错并成功ac; 接下来丙去写I题, 乙去和甲看B题, 在两人讨论后成功把B题也ac了; 此时已经用了一个小时的时间, 之后丙的I题卡住了, 而乙还在想H题, 于是让甲去写L题, 写了半个小时后L题也卡住了, 于是乙接力写H题, 结果wa了一发; 不过好在甲想到了L题错在哪, 丙在最后两分钟成功ac;
【BAPC 2022】题目解析
A - Adjusted Average（Gym - 104020A）
难度 ⭐⭐⭐⭐
【题目描述】
作为您大学生物学和概率课程的学生，您刚刚进行了一项实验，作为实际作业的一部分。然而，您的结果看起来不太好：您曾希望样本的平均值与现在不同。为了改善结果，您决定让一些样本“神奇地消失”（即将它们倒入垃圾桶）。为了不引起老师的怀疑，您可以只删除一些样本。您能达到您想要的平均水平吗？
【题目模型】
给定n个整数ai，最多移除其中的k个，以获得尽可能接近目标x的平均值, n为1500, k为4;
B - Bellevue（Gym - 104020）
难度 ⭐
【题目描述】
任何摄影师都知道，任何好的日落照片都是日落在海面上的。事实上，照片中可见的大海越多，它就越漂亮; 您目前正在访问贝尔维尤岛，并且您想要拍摄一张东方日出或西方日落的照片，并将其提交给贝尔维尤的惊人摄影比赛。通过仔细研究地形图，你找到了岛屿的东西向轮廓。现在您想知道在一张照片中可以捕捉到的最大海洋量，以被水覆盖的视角来衡量。岛屿的轮廓以分段线性函数的形式给出，该函数由 n 点之间的 n−1 线段组成。该岛的起点和终点都在海平面上。作为示例，下图显示了第一个示例案例的概况。请注意，您的镜头视角不够大，无法一次拍摄到岛屿东部和西部的海洋。另外，海平面的视角为 0 度。
【题目模型】
给定1~n中每个坐标的高度hi, 找出所有坐标中和坐标边界(i=1或i=n)高度的连线的角度的最大值; n为5e4;
【解题思路】
签到题, 遍历所有点, 维护与左右边界的角度最大值, 最后左右角度最大值取最大即可, O(n)的复杂度;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define PI acos(-1)
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
PII g[N];
int n;
signed main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> g[i].first >> g[i].second;
}
int st = g[1].first;
int ed = g[n].first;
double lans = 0,rans=0;
for (int i = 1; i <= n; i++){
lans = max(lans, atan2(g[i].second,(g[i].first-st))*180);
rans = max(rans, atan2(g[i].second,(ed-g[i].first))*180);
}
printf("%.8lf", max(rans,lans)/PI);
}
C - Crashing Competition Computer（Gym - 104020C）
难度 ⭐⭐⭐
【题目描述】
您正在为黑客马拉松编写代码，需要解码二进制 ALGOL 打孔卡。您已经想出了最佳解决方案，只需将其输入即可。该解决方案由 c 个字符组成，您的打字速度为每时间单位 1 个字符。然而，您的计算机很容易突然崩溃：在您输入每个字符后，您的计算机就有可能 pp 崩溃，您需要重新开始。崩溃后恢复需要 r 个时间单位，然后您可以从上次保存代码的位置继续输入。您可以随时单击“保存”（需要 t 个时间单位）来保存您的代码，并能够在崩溃后从此时点重新启动。单击“保存”不会导致您的计算机崩溃。确定完成代码需要多少（预期）时间单位。请注意，应在输入最后一个字符后保存代码。
【题目模型】
需要在电脑输入n个字, 输入1个字花费1秒; 并且每输入1个字之后可以花m秒去存档, 因为每输入一个字都有p的概率会崩溃, 恢复时间为k秒, 并且恢复后会回到上次存档的位置, 如果没存档就重新开始; 问输完这n个字的最短时间, 输完后需要存一次档; n为2000, m和k为1e9;
【解题思路】
概率dp, 状态表示dp[i]: 输入i个字所需要的最短时间; 对此我们可以先把dp[i]初始化为一直不存档的情况; 设初始情况为prb[i], prb[i]的计算首先在prb[i-1]的基础上, 有p的概率会崩溃花k秒恢复, 打字需要1秒; 并且我们每次只有(1-p)的概率会通过, 所以计算方程为: prb[i] = (prb[i - 1] + p * k + 1) / (1 - p); 找dp[i]的最小值时我们需要判断要在哪个位置存档, 于是这里的处理和线性dp类似, 假设在j这个点存档, 我们可以把从j到i看作从0到i-j, 因为j~i没有存档, 所以从从j到i所需要的时间就是prb[i-j], 状态转移: dp[i] = min(dp[i], dp[j] +prb[i - j] + m); 这样的复杂度就是二重循环遍历当前点和存档点, 即O(n2);
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4+ 10;
int n, m, k;
double dp[N], prb[N];
double p;
signed main(){
cin >> n >> m >> k >> p;
for (int i = 1; i <= n; i++) {
prb[i] = (prb[i - 1] + p * k+1) / (1 - p);
}
for (int i = 1; i <=n; i++) {
dp[i] = prb[i];
for (int j = 0; j < i; j++) {
dp[i] = min(dp[i], dp[j] +prb[i - j] + m);
}
}
printf("%.9lf", dp[n] + m);
return 0;
}
D - Dividing DNA（Gym - 104020D）
难度 ⭐⭐
【题目描述】
在细菌和蛋白质中心，您拥有大量 DNA。事实上，新的 DNA 链一直在不断出现。为了组织大量数据，您可以通过其唯一的子字符串来识别每部分数据：数据库中尚未出现的子字符串。您的数据库可以快速确定给定的 DNA 片段是否作为子串出现在数据库中。当然，如果在数据库中找到某个 DNA 字符串，它也包含其所有子字符串。现在，您想要确定给定 DNA 片段的唯一性：它包含的不相交子串的最大数量，而数据库中不存在这些子串。给定查询字符串 q1…qn 的长度 n ，您可以反复询问数据库是否包含子字符串 qi…qj−1 。作为示例，请考虑第一个示例交互。在本例中，数据库包含字符串“TGC”和“CT”，查询字符串为“CTGCAA”。它具有唯一性 3 ，因为它可以拆分为新的子字符串“CTGC”、“A”和“A”。新的子字符串“CTGC”不能进一步拆分：例如，不允许细分“CT”和“GC”，因为两个子字符串都出现在数据库中（可能作为子字符串）。请注意，交互中不使用字符串中的实际字符。您最多可以对数据库使用 2n 个查询。
【题目模型】
数据库中已经有若干个字符串, 现在给你一个未知的字符串s, 问s最多可以分成多少个字串并且所有子串都不在数据库中; 本题为交互题, 每次可以询问一个区间, 题目会回答这个区间的字串是否在数据库中, s的长度n为1e4, 最多询问2n次;
【解题思路】
一道贪心的交互题, 如果想把字符串分成尽可能多的子串, 那个我们就从左往右枚举当前字串的右端点, 如果当前子串不在数据库中就答案+1, 把当前节点作为下一个子串的左端点, 可以用双指针去维护每个字串的区间; 这样切出来的子串一定是最多的; 线性地走一遍复杂度为O(n);
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
int n,m,res;
signed main() {
cin >> n;
for(int i=1,j=0;i<=n;i++){
cout<<"? "<<j<<' '<<i<<endl;
string s;
cin>>s;
if(s=="absent"){
res++;
j=i;
}
}
cout<<"! "<<res<<endl;
return 0;
}
E - Equalising Audio（Gym - 104020E）
难度 ⭐
【题目描述】
作为 Balanced Audio Podcast 的无线电工程师，您的工作是始终提供平等的收听体验。您在听众中进行了一项民意调查，他们特别关心响度的波动。为了解决这个问题，您购买了一个变压器来均衡音频，但可惜的是，它的软件在运输过程中被损坏了。你的工作是重写均衡软件。作为输入，变压器获得 n 振幅 a1,…,an ，平均感知响度为 1n∑i=1nai^2 。输出应包含相同的幅度，但通过某些恒定的正因子重新归一化，使得平均感知响度为 x 。有一个例外：应始终保持完全安静。
【题目模型】
给定n个数和一个平均值m, 我们想把n个数等比例地缩小, 使得把n个数的平方加起来后等于m, 问n个数缩小后各为多少;
【解题思路】
签到题, 通过现在的平方和res的平均值和m取比值后开平方就得到了每个数该缩小的倍数, 最后把每个数缩小后输出即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int f[N];
int n, m;
signed main() {
scanf("%lld%lld", &n, &m);
int res = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &f[i]);
res += f[i] * f[i];
}
double x;
if (res == 0) x = 0;
else {
double y = 1.0 * n * m / res;
x = sqrt(y);
}
for (int i = 1; i <= n; i++) {
double a = f[i] * x;
printf("%.9lf ", a);
}
return 0;
}
F - Failing Flagship（Gym - 104020F）
难度 ⭐
【题目描述】
您即将前往下一个“船很酷”大会，出售您的最新小玩意：一种新型指南针。在普通的指南针上，很难读出精确的风向。然而，您的新型指南针可以让您以更高的精度读取风向！显示器最多可以显示 1000 个字符的字符串。不幸的是，你遇到了一些恶劣的天气。经过几个小时的大风大浪后，您终于可以再次查看指南针了。您读出您要去的风向 X ，并知道您需要去哪个风向 Y 。然而，要使船舶转向，您必须在控制系统中输入船舶必须形成的角度。为了回到正确的航线，您必须进行的最小转弯（以度为单位）是多少？风向到度数的转换如下。四个基本风向是 N、E、S 和 W，分别指向 0 、 90 、 180 和 270 度，分别。还有四个风向由两个字母组成：NE、SE、SW 和 NW，分别指向 45 、 135 、 225 和 315 度。风向也可以由 k≥3 字母 l1l2…lk 组成。在这种情况下，最后两个字母表示四个两个字母的风向之一，即 lk−1lk∈{NE,SE,SW,NW} ，其他字母等于其中之一，即 li∈{lk−1,lk} 对于所有 i≤k−2 。该风向恰好指向以下两个风向的中间：风向 l2…lk ，从 l2…lk 开始并沿圆圈向 l1 移动时遇到的最多 k−1 个字母的第一个风向。例如，风向SSSE指向SSE和S的中间，因为S是从SSE向S移动时第一个最多有3个字母的风向，如图1所示。
【题目模型】
给出两个方位, 问两个方位之间较小的那个夹角; 方位最多1000位;
【解题思路】
根据题目给出的图可以找到每个方位变化的规律, 对于方位d, 我们要从后往前看方位的变化, eg: ESSE可以看作是从正N方向开始先往E方向偏转90°, 再往S方向偏转45°, 再往S方向偏转22.5°, 再往E方向偏转11.25°; 每加一个位变化的角度就要除以2, 以N-S位界, 规定E方向的为正, 反之为负; 模拟找出两个方位的角度后再求出两个角度的差值即可; 注意最后结果要求小于等于180°; 模拟复杂度位O(n);
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
double check(string s) {
int len = s.size() - 1;
if (s[len] == 'N') return 0.0;
else if (s[len] == 'S')return 180.0;
else {
double x = 90.0;
double res = 90.0;
bool f, f1;
if (s[len] == 'E') f = true;
else f = false;
for (int i = len - 1; i >= 0; i--) {
x = 1.0 * x / 2;
if (f) {
if (s[i] == 'S') {
res += x;
f1 = true;
}
else if (s[i] == 'N') {
res -= x;
f1 = false;
}
else if (s[i] == 'E') {
if (f1) res -= x;
else res += x;
}
}
else {
if (s[i] == 'S') {
res += x;
f1 = true;
}
else if (s[i] == 'N') {
res -= x;
f1 = false;
}
else if (s[i] == 'W') {
if (f1) res -= x;
else res += x;
}
}
}
if (!f) res = -res;
return res;
}
}
signed main() {
string a, b;
cin >> a >> b;
double n = check(a);
double m = check(b);
double res = abs(n - m);
if (res > 180.0) res = 360.0 - res;
printf("%.9lf", res);
return 0;
}
G - Grinding Gravel（Gym - 104020G）
难度 ⭐⭐⭐⭐
【题目描述】
在翻新花园期间，您决定要一条从街道延伸到前门的碎石路。作为巨石和卵石社区的成员，您希望这条路看起来很完美。您已经有一个用于放置砾石的常规网格，以及一个大容器，其中包含与网格总容量完全相同的砾石。存在一个问题：砾石尚未完全融入网格。每个网格单元具有相同（固定）的容量，并且每块砾石都有一定的重量。您有一块磨石，可用于将石头分割成多个块，但这样做需要时间，因此您需要进行最少次数的分割，以便砾石可以精确地分布在网格上。作为示例，请考虑第一个示例案例。共有三个大小为 8 的网格单元，可以按如下方式填充。将重量 2 和 6 的石头放入第一个单元格中。现在将 7 重量的石头磨成 3 和 4 两块重量。然后另外两个网格单元分别由权重 3,5 和 4,4 填充。
【题目模型】
现在有很多个牌子, 牌子上有一个0~9之间的一个数字; 现在给定一个数n, 问我们至少需要多少个牌子可以把0~n中任意一个数表示出来; n为1e9;
H - House Numbering（Gym - 104020H）
难度 ⭐⭐⭐
【题目描述】
您沉迷于最新的世界模拟游戏：建设完美城市。在当前的游戏中，您创建了一个拥有相同数量街道和十字路口的城市。剩下的就是对每条街道上的房屋进行编号。城市由带有十字路口和街道的连接图表示。每条街道都是两个交叉路口 u 和 v 之间的连接，并且有 h 栋房屋都位于街道的一侧。两个十字路口之间至多有一条街道。有两种方法可以对这条街道上的房屋进行编号：从与交叉路口 u 相邻的门牌号码 1 开始，以交叉路口 h 的门牌号码结束 < b6> ，或门牌号 1 与 v 相邻，门牌号 h 与 u 相邻。为了避免混淆，您需要确保没有交叉路口有两个相邻的房屋具有相同的编号。找到一种方法对每条街道上满足该属性的房屋进行编号（或报告这是不可能的）。
【题目模型】
给定一个有n个点和n条边的无向图, 每条边都有一个权值k, 对于边的两个顶点我们可以将其中一个编号位1, 另一个编号为k; 问是否存在一种编号方式, 可以让每个点都不存在重复的编号; n为1e5, k为1e9;
【解题思路】
首先本题最特殊的地方是点和边的数量相同, 这就意味着该图中一定会存在一个环; 因为环的编号方式只有两种: 顺时针和逆时针, 其他方式在环上都会冲突; 所以我们可以从环入手, 然后从环开始向外发散; 首先我们可以先用dfs去找到组成环的所有节点, 先顺时针编号后再对环上的所有点用dfs向外发散, 因为环上的所有点都有1这个编号, 所有在向外发散时一定时父节点为k, 子节点为1去发散, 在期间如果有冲突就再用逆时针试试, 如果都不行就输出impossible;
这里可以解释一下顺时针和逆时针, 对于环1-2-3-4-1; 我们可以所有边的前者为1, 后者为k, eg: 让1-2中1的编号为1, 2的编号为2; 这称之为顺时针, 反过来就是逆时针; 在代码中也很好实现, 只需要把组成环的所有点顺序反过来之后再走一遍原方程即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
int n, fir;
bool f = false, res = true;
deque<int> cy;
vector<int> v[N];
map<PII, int> id;
map<PII, int> mp;
map<PII, int> sg;
bool st[N];
PII g[N];
void ins(int a, int b, int c) {
sg[{a, b}] = c;
sg[{b, a}] = c;
}
void dfs2(int u, int fa) {
for (int x : v[u]) {
if (st[x]) continue;
if (x == fa) continue;
int a = mp[{u, x}];
if (id[{u, a}]) {
res = false;
return;
}
else {
id[{u, a}]++;
id[{x, 1}]++;
ins(u, x, x);
dfs2(x, u);
if (!res) return;
}
}
}
void solve() {
for (int i = 0; i < cy.size(); i++) {
int a;
if (i == 0) a = mp[{cy.back(), cy[i]}];
else a = mp[{cy[i - 1], cy[i]}];
id[{cy[i], 1}]++;
id[{cy[i], a}]++;
if (i + 1 == cy.size()) ins(cy[i], cy[0], cy[i]);
else ins(cy[i], cy[i + 1], cy[i]);
}
for (int i = 0; i < cy.size(); i++) {
dfs2(cy[i], -1);
}
}
void dfs1(int u, int fa) {
for (int x : v[u]) {
if (x == fa) continue;
if (st[x]) {
fir = x;
f = true;
return;
}
else {
st[x] = true;
cy.push_back(x);
dfs1(x, u);
if (f) return;
st[x] = false;
cy.pop_back();
}
}
}
signed main() {
IOS;
cin >> n;
int u = 1e9;
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
u = min(u, min(a, b));
g[i] = { a,b };
v[a].push_back(b);
v[b].push_back(a);
mp[{a, b}] = c;
mp[{b, a}] = c;
}
st[u] = true;
cy.push_back(u);
dfs1(u, -1);
while (cy.front() != fir) {
st[cy.front()] = false;
cy.pop_front();
}
solve();
if (!res) {
res = true;
sg.clear();
id.clear();
reverse(cy.begin(), cy.end());
solve();
}
if (!res) cout << "impossible";
else {
for (int i = 1; i <= n; i++) {
int a = g[i].first, b = g[i].second;
cout << sg[{a, b}] << ' ';
}
}
return 0;
}
I - Imperfect Imperial Units（Gym - 104020I）
难度 ⭐⭐
【题目描述】
您正在为 Beta 天文学物理会议撰写一篇关于您最近关于灰洞的发现的论文。您的一位合作者进行了大量测量，您希望对其进行分析以得出一些结论。唯一的问题是：数据以多种单位进行测量，令您厌恶的是，它们似乎混合使用了英制和公制系统。为了简化分析，您需要将所有这些测量值转换为不同的单位。
【题目模型】
给定n组不同单位之间的转换关系, 然后再给出m组询问, 问x个单位A可以转换为多少个单位B; 保证从单位A转换为单位B只有一种方式; 最多有100种单位;
【解题思路】
因为需要单位之间的传递, 所以我们可以想到用哈希把单位哈希为数值, 然后再通过建树的方式查找两个单位之间的进率, 每次询问进行一次dfs即可; 另外我还发现有个很有意思的解法, 这个题其实就是问两个点之间的最短路问题, 只不过要把加变成乘, 所以我们可以用folyd算法求出任意两个单位之间的汇率, 询问的时候直接输出即可; 但是两个做法的时间差不多, 就不再多写了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4+ 10;
int n, m, num;
double ans;
int p[N];
map<PII, double> mp;
map<string, int> hx;
vector<int> v[N];
void dfs(int u,int fa, double zh, int res) {
if (u == res) {
ans = zh;
return;
}
for (int x : v[u]) {
if (x == fa) continue;
dfs(x, u, zh * mp[{u, x}], res);
}
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= 1000; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
double a, b;
string c, d, e;
cin >> a >> c >> e >> b >> d;
if (!hx[c]) hx[c] = ++num;
if (!hx[d]) hx[d] = ++num;
mp[{hx[c], hx[d]}] = b;
mp[{hx[d], hx[c]}] = 1.0 / b;
v[hx[c]].push_back(hx[d]);
v[hx[d]].push_back(hx[c]);
}
for (int i = 1; i <= m; i++) {
double a;
string b, c, d;
cin >> a >> b >> d >> c;
ans=0;
dfs(hx[b],0,1, hx[c]);
if(ans==0) cout<<"impossible";
else printf("%.10lg\n", a*ans);
}
return 0;
}
J - Jagged Skyline（Gym - 104020J）
难度 ⭐⭐⭐
【题目描述】
未来就在这里！盒子和包裹中心已决定开始使用无人机运送包裹。作为一家 BrAinPort 公司，第一批货物自然会运往埃因霍温。为了保持飞行逻辑简单，第一个原型机将只飞到最高建筑物的屋顶。起飞后，无人机将拍摄一张 w×hw×h （ 1≤w≤10 000 ， 1≤h≤1018 ）天际线照片，如图1所示。您的任务是确定这张照片中最高建筑物的位置和高度的问题，以便无人机知道要去哪里。您可以使用分类器来确定每个像素是“天空”还是“建筑物”。您可以针对不同的像素多次使用此功能。为了避免不必要的延迟，您最多可以运行分类器 12 000次。确保建筑物不会包含任何悬停部分：每当不在照片底行的像素被分类为建筑物时，其下方的像素也将被分类为建筑物。
【题目模型】
给定一个宽为w，高为h的空间，其中有若干不悬空的建筑物，通过不断地询问某个点是否有建筑物来找到这个空间里最高的建筑物的位置。，w为14，h为1e18，最多询问1200次。
【解题思路】
由于限制询问次数，直接按顺序一个一个查找不是一种好方法，故先将询问横坐标的顺序打乱，按打乱后的顺序来询问，先按打乱后的顺序，来查询高度为一的点有没有建筑物，若有则用二分查找来找到其高度，然后再按打乱后的顺序来询问高度比已知建筑高的点，找到点后再用二分查找得到该建筑的高度，然后更新最高高度，然后再找比最高高度高的点，以此类推，直到无法找到更高建筑或最高的已知建筑的高度已经为h，则输出答案。时间复杂度为O(n)。
K - Kiosk Construction（Gym - 104020K）
难度 ⭐⭐⭐⭐
【题目描述】
您正计划开始一次布置精美的平静露营。您已经购买了一块田地，并将其划分为 h×w 地块网格，并使用从 1 到 h⋅w 对它们进行编号 。然而，您忘记了一件事：您仍然需要将接待亭放置在其中一个地块上。您希望最小化任何客人从接待亭步行到他们的场地的最大距离。然而，客人不会采取最短路径到达他们的场地，而是遵循以下程序，从接待亭开始：查看四个相邻地块的编号。转到数字最接近目标数字的绘图。如果出现平局，则从两个平局地块中，转到编号最接近当前地块编号的地块。重复直到到达目的地。请注意，在某些情况下此过程可能不会终止。给定地块编号，找到接待亭最佳位置的地块编号以及从该亭到任何地块的最大步行距离。如果对于接待亭的每个可能位置，至少有一个图块的上述过程没有终止，则输出这是不可能的。图 1 显示了第三个示例案例：一种解决方案是将自助服务终端放置在地块 4 中，以便其他地块的最大距离为3 。将信息亭放置在地块 7 中不起作用，因为无法从那里到达地块 9
【题目模型】
根据一下三点为给定的露营布局找到最佳的售货亭位置1.看看四个相邻地块的数量。2.转到数字最接近目标编号的图。如果出现平局，则在两个平局图中，转到编号最接近当前地块编号的那个。3.重复1和2直到到达目的地。
L - Lowest Latency（Gym - 104020L）
难度 ⭐⭐⭐
【题目描述】
给定一个由括号组成的序列, 将该序列首尾相连形成一个环, 问我们能否找到一个切割点, 使得在这个位置切开后形成的序列和原序列不同; 切割点不能处于任何一个括号内部, 也就是说要在两个独立的括号之间切;
【题目模型】
给定n个三维坐标, 问其中距离最近的两个点之间的距离; n的范围是1e5;
【解题思路】
1e5的数据范围O(n2^2)的暴力做法肯定是不行; 所以我们想是否可以用二分的思路; 对于所有的坐标, 我们先按横坐标进行排序, 然后进行二分递归, 相当于每次把所有点分成两部分, 最后每个部分就只有两个点; 我们求出两部分各自的最小距离后, 因为这是按横坐标进行分区, 接下来我们再按纵坐标分区再找一遍最小值, 把这两部分合并, 然后再按纵坐标排序, 然后再去找两个点之间的最小值; 这样最后得出来的就是最终的最小值; 这样的复杂度为O(n*logn2);
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+ 10;
int n, m;
struct str{
int x,y,z;
}pos[N];
bool cmpx(str a, str b){
return a.x<b.x;
}
bool cmpy(str a, str b){
return a.y<b.y;
}
double dis(str a, str b){
double c=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
c=sqrt(c);
return c;
}
double solve(int l, int r){
if(l==r) return 1e10;
else if(l==r+1) return dis(pos[l],pos[r]);
int mid=l+r>>1;
double d=min(solve(l,mid),solve(mid+1,r));
str a[N];
int num=0;
for(int i=l;i<=r;i++){
if(abs(pos[i].x - pos[mid].x)<d) a[++num]=pos[i];
}
sort(a+1,a+1+num,cmpy);
for(int i=1;i<=num;i++){
for(int j=1;j<i;j++){
if(abs(a[i].y-a[j].y)>d) continue;
d=min(d,dis(a[i],a[j]));
}
}
return d;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int a,b,c;
cin>>a>>b>>c;
pos[i]={a,b,c};
}
sort(pos+1,pos+1+n,cmpx);
double res=solve(1,n);
printf("%.9lf",res);
return 0;
}