T1
题目描述
给定两个数组A1与A2，其中A2元素各不相同，且都出现在A1中。现需要对A1中的元素进行排序：若该元素出现在A1和A2中，则保持相对顺序与A2相同；若未在A2中出现过，则按照升序排在A1末尾。最后返回排序后的A1。
输入描述
第一行为数组A1，第二行为数组A2，均按空格分割
输出描述
输出排序后A1，按空格分割
示例1
样例输入
1 2 3 4 5 6 7
3 6 5
样例输出
3 6 5 1 2 4 7
示例2
样例输入
12 45
23
样例输出
12 45
示例3
样例输入
1 2 2 3
3 2
样例输出
3 2 2 1
算法
(模拟) $O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
vector<int> a, b;
unordered_map<int, int> cnt;
int main() {
string s;
getline(cin, s);
stringstream A(s);
int x;
while (A >> x) a.push_back(x), cnt[x] ++ ;
getline(cin, s);
stringstream B(s);
while (B >> x) b.push_back(x);
for (auto x: b)
if (cnt[x]) {
while (cnt[x] -- ) {
cout << x << ' ';
}
}
vector<int> c;
for (auto item: cnt) {
int t = item.second;
if (t > 0) {
while (t -- ) c.push_back(item.first);
}
}
sort(c.begin(), c.end());
for (auto x: c) cout << x << ' ';
return 0;
}
T2
题目描述
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为“1”的个数
输入描述
一个正整数
输出描述
2进制表达为1的位数
示例1
样例输入
123
样例输出
6
算法
$O(log(n))$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
unsigned int n;
int low_bit(unsigned int x) {
return x & -x;
}
int main() {
cin >> n;
int ret = 0;
while (n) n -= low_bit(n), ret ++ ;
cout << ret;
return 0;
}
T3
题目描述
有$N$位同学，他们通过这座桥分别需要耗时$n_0$、$n_1$、$n_2$、$n_3$分钟，只有一支手电，并且同时最多只能两个人一起过桥。请给出所有人能够在M分钟内过桥的可能性
输入描述
第一行N
第二行每位同学过桥用时以空格隔开
第三行M
输出描述
1表示能够通过，0表示不能通过
示例1
样例输入
4
1 2 5 10
17
样例输出
1
算法
(贪心) $O(n)$
- 只有一个手电，所以前期两个人过去后一定有一个人要带着手电回来，并且回来的人的速度是最快的那个
- 依据人数分以下几种情况：
- 只有一个人：返回自己的过桥时间
- 剩余两个人：返回较大的过桥时间
- 剩余三个人：假设按过桥时间从小到大排序后为A、B、C，则时间最短的策略为A先带C过桥，A折返，与B一起过桥，时间为$t_A + t_B + t_C$
- 剩余大于等于四个人：考虑最快的两个人A、B和最慢的两个人C、D，即$t_A <= t_B < t_C <= t_D$，存在两种策略（1）A先带C过桥，A折返，A后带D过桥，A折返，时间为$t_C + t_A + t_D + t_A$；（2）A、B一起过桥，A折返，C、D一起过桥，B折返，时间为$t_B + t_A + t_D + t_B$。这两种策略选择较小者，送完最慢的两个人后递归送剩下的其他人
时间复杂度
速度最快的两人可能会多次往返，其他人过去就不会再回来，因此每个点只会被枚举一次，时间复杂度为$O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a;
int dfs(int n) {
if (n == 1) return a[0];
if (n == 2) return a[1];
if (n == 3) return a[0] + a[1] + a[2];
if (2 * a[1] < (a[0] + a[n - 2])) return a[0] + 2 * a[1] + a[n - 1] + dfs(n - 2);
else return 2 * a[0] + a[n - 2] + a[n - 1] + dfs(n - 2);
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++ ) {
int x; cin >> x;
a.push_back(x);
}
cin >> m;
sort(a.begin(), a.end());
int t = dfs(n);
if (t <= m) puts("1");
else puts("0");
return 0;
}
T4
题目描述
小A春节期间在网上搜火车票价格，假设从X市到Y市往返的火车一天有一个班次，且去程和返程不能为同一天。已知搜索引擎的票价缓存结构如下：
M = {
'XY': [10, 15, 12, 14],
'YX': [20, 22, 17, 16]
}
其中XY代表$X \rightarrow Y$市的火车价格，一列每个元素代表当天，+1天，+2天…的票价，请问小A可以搜索到的往返XY最低需要多少钱。
输入描述
输入两行表示$X \rightarrow Y$和$Y \rightarrow X$的价格序列以空格隔开
输出描述
最低价，如果不能有最低价组合返回-1
示例1
样例输入
10 15 12 14
20 22 17 16
样例输出
26
算法
$O(n)$
- 40%
- 可能原因是a、b两个数组不等长
C++ 代码
#include <bits/stdc++.h>
using namespace std;
vector<int> a, b;
int main() {
string s;
getline(cin, s);
stringstream A(s);
int x;
while (A >> x) a.push_back(x);
getline(cin, s);
stringstream B(s);
while (B >> x) b.push_back(x);
int n = a.size(), ret = INT_MAX;
if (n <= 1) puts("-1");
else {
vector<int> f(n, INT_MAX), g(n, INT_MAX);
f[0] = a[0], g[0] = b[0];
for (int i = 1; i < n; i ++ )
f[i] = min(f[i - 1], a[i]);
for (int i = 1; i < n; i ++ )
g[i] = min(g[i - 1], b[i]);
for (int i = 1; i < n; i ++ ) ret = min(ret, b[i] + f[i - 1]);
for (int i = 1; i < n; i ++ ) ret = min(ret, a[i] + g[i - 1]);
cout << ret;
}
return 0;
}
T5
题目描述
小A驾驶一辆汽车准备匀速驶入一段连续的红绿灯路口，已知路段中的每个红绿灯距离路段初始点的距离和红绿灯间隔，请问最高能保持什么样的速度（单位：km/h），才能保证穿过路段时不遇到红灯。（红灯刚跳转为红的那秒钟不允许通行，所有红绿灯在小A刚进入路段的时候均刚跳转为绿灯）
输入描述
已知输入第一行代表最大速度s（单位：km/h），红绿灯个数n
之后每一行输入m、t，m为每个红绿灯距离小A驶入路口的距离（单位：米），t为红绿灯持续时间，每个红绿灯持续t秒绿灯后亮t秒红灯，再重新开始t秒绿灯
输出描述
输出保持的车速（单位：km/h）
示例1
样例输入
50 1
200 15
样例输出
50
示例2
样例输入
50 1
200 10
样例输出
36
算法
$O(s \times n)$
- 从大到小判断是否会被红灯卡住即可，到达的时间处于奇数段可认为在红灯区间内
- 注意单位换算
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
int s, n;
vector<PII> d;
bool check(int mid) {
for (auto c: d) {
int t = c.x * 18 / (mid * 5 * c.y);
if (t & 1) return false;
}
return true;
}
int main() {
cin >> s >> n;
for (int i = 0; i < n; i ++ ) {
int a, b; cin >> a >> b;
d.push_back({a, b});
}
for (int i = s; i > 0; i -- )
if (check(i)) {
cout << i;
break;
}
return 0;
}
