科大讯飞秋招笔试真题 - 字符拼接 字典序最小的字符串拼接 圆心覆盖
字符拼接
题目描述
给定两个由可见字符和空格组成的字符串s和t，其中字符串t的长度为偶数.
请将t的后半部分嫁按到s的未尾，并输出嫁接后的s以及t 的前半部分。
本题字符串的字符集为 ASCIl 码在 32 到 126 之间的字符，即大小写字母、数字、标点符号和空格。
输入
第一行输入一个长度为n (1 ≤n≤ 100)的字符串，s1，s2，…sn。
第二行输入一个长度为 m (2 <= m <= 100)的字符串，t1,t2…tm。保证 m为偶数。
除此之外，保证8和t中只包含可见字符和空格。
输出
第一行输出嫁接后的字符串s。
第二行输出t的前半部分。
示例1
输入
kou yukari输出
kouari yuk示例2
输入
?? (ak90 r)输出
??0 r) (ak9思路和代码
签到题，没有任何难度。
#include<iostream>#include<vector>#include<queue>#include<tuple>#include<limits>usingnamespacestd;usingll=longlong;constll INF=1e18;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;string t;getline(cin,s);getline(cin,t);intn=t.size();// 分割得到t的前半部分string frontPart=t.substr(0,n/2);// 分割得到t的后半部分string backPart=t.substr(n/2);cout<<s+backPart<<endl;cout<<frontPart;return0;}字典序最小的字符串拼接
题目描述
对于给定的长度为n，仅由字符串构成的数组{a1,a2…,an}，每一个字符串都仅由小写字母构成。你需要将全部字符串按照任意顺字拼接成一整个字符串(但是不改变每个字符串内部的顺序)，随后恰好删除其中的一个字符,
请你输出所有可能的拼接结果中，字典序最小的结果。
【名词解释】
字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的字母表顺序，字母序较小的字符串字典序也较小;如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。
输入
第一行输入一个整数n(1 <= n ＜＝ 8)，表示数组的长度。
第二行输入n个字符串a1,a2,……,an (1 <= len(ai)<= 10)，每个字符串仅由小写字母构成。
输出
输出一个字符串，表示所有可能的拼接结果中，字典序最小的结果。
示例1
输入
3 za ba bb输出
ababb思路和代码
思路:枚举 + 栈 + 自定义排序
n <= 10数据范围较小，直接枚举要删除字符位于第i`个字符中，具体逻辑为
- 例如当前要删除字符位于第i个字符串中，使用
单调栈移除指定字符串中首个当前字符ASCII大于下一个字符的位置的字符，形成新的字符串。 - 将第
i个字符串替换删除单个字符之后的字符串 - 进行自定义排序,排序规则为
a +b < b + a,拼接当前情况所能组成的最小字典序字符串。
记录所有枚举情况下所能组成最小字典序的字符串就是结果。
#include <iostream> #include <vector> #include <queue> #include <tuple> #include <limits> #include<algorithm> using namespace std; using ll = long long; const ll INF = 1e18; bool cmp(string &a, string &b) { return a +b < b +a; } // n的数据小直接枚举要删除字符属于哪个字符串 string solve(vector<string>& words) { string res; int n = words.size(); // 枚举要移除字符所在字符串 for (int i = 0; i < n; i++) { vector<string> wordsCopy(words.begin(), words.end()); string tmp = words[i]; int m = tmp.size(); if (m == 1) { wordsCopy[i] = ""; } else { // 类似于单调栈的思路决定删除字符位置 int j = 1; for (; j < m; j++) { if (tmp[j] < tmp[j-1]) { break; } } wordsCopy[i] = tmp.erase(j-1, 1); } // 自定义排序 sort(wordsCopy.begin(), wordsCopy.end(), [](string &a, string &b) { return a +b < b +a; }); string currentRes; for (auto &tmp : wordsCopy) { currentRes += tmp; } if (res.empty() || res > currentRes) { res = currentRes; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<string> words(n); for (int i = 0; i < n; i++) { cin >> words[i]; } string res = solve(words); cout << res; return 0; }圆心覆盖
题目描述
现在需要在坐标平面上以某一点 C 为圆心画一个圆，且该圆心必须位于坐标轴上。
请你找到一个最小的半径r，使得这圆能够覆盖不少于[n/2]个给定点，并输出这个最小半径。
【名词解释】
坐标轴:包含x轴和y轴。x 轴表示形如(x,0)的所有点；y轴表示形如(0,y)的所有点。
覆盖：若点 P 到圆心 c 的欧氏距离不超过圆的半径，则称该圆覆盖点 P。
输入
第一行输入一个整数n (2 ≦n ≦ 10^5)，表示点的数量。
接下来n行，每行输入两个整数
xi，yi（-10^5＜= xi，yi＜＝10^5），表示第i个点的坐标。
输出
输出一个实数，表示能够覆盖至少[n/2]个给定点的、以坐标轴上某点为圆心的最小圆的半径。
误差需要小于10^-6，要求保留6位小数输出。
示例1
输入
4 -1 0 1 0 0 1 100 100输出
1.000000示例2
输入
3 1 0 2 0 50 50输出
0.500000思路和代码
思路：二分 + 差分
- 使用二分枚举半径，检验当前半径是否可以圆心位于坐标轴上并且满足[n/2]点包括内。
- 判断逻辑:假设当前圆心位于x轴，计算每个点能被包含在内的圆心的x轴的范围，使用差分 + 扫描线计算重叠区间个数，如果个数大于 >= [n/2]说明满足。假设圆心位于y轴判断方式类似。
#include<bits/stdc++.h>usingnamespacestd;structEvent{doublepos;inttype;// +1 表示区间开始，-1 表示区间结束booloperator<(constEvent&other)const{if(pos==other.pos)returntype<other.type;returnpos<other.pos;}};intn;vector<pair<int,int>>pts;boolcheck(doubler){intneed=(n+1)/2;vector<Event>events;doubler2=r*r;// 圆心在 x 轴for(auto&p:pts){doublex=p.first,y=p.second;if(r2<1.0*y*y)continue;// 没法覆盖doubledx=sqrt(r2-1.0*y*y);events.push_back({x-dx,+1});events.push_back({x+dx,-1});}// 扫描线sort(events.begin(),events.end());intcur=0;for(auto&e:events){cur+=e.type;if(cur>=need)returntrue;}events.clear();// 圆心在 y 轴for(auto&p:pts){doublex=p.first,y=p.second;if(r2<1.0*x*x)continue;doubledy=sqrt(r2-1.0*x*x);events.push_back({y-dy,+1});events.push_back({y+dy,-1});}sort(events.begin(),events.end());cur=0;for(auto&e:events){cur+=e.type;if(cur>=need)returntrue;}returnfalse;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;pts.resize(n);for(inti=0;i<n;i++){cin>>pts[i].first>>pts[i].second;}// 二分答案doubleL=0,R=0;for(auto&p:pts){doubled=sqrt(1.0*p.first*p.first+1.0*p.second*p.second);R=max(R,d);}for(intiter=0;iter<50;iter++){// 精度二分doublemid=(L+R)/2;if(check(mid))R=mid;elseL=mid;}cout<<fixed<<setprecision(6)<<R<<"\n";return0;}