# 蚂蚁集团 3-19 研发笔试
# Q1easy
题目描述
小苯看中了一件价值为 p 元的物品，他手里有 1 个 “打折券” 和 1 个 “立减券”。两种优惠券可以都用在物品上，且使用顺序也是任意的。
两种优惠券分别以整数 x 和 y 的方式给出。
打折券：如果当前物品价格为 p，使用后，物品价格变为： 上取整。
立减券：如果当前物品价格为 p，使用后，物品价格变为：。即物品价格立减 y 元，但最多减到 0。
小苯想知道，这件价值为 p 的物品最少可以花多少钱买到。
输入描述
输入包含一行三个正整数 ，分别表示物品的价格，“打折券” 和 “立减券” 的优惠力度。
输出描述
输出包含一行一个整数，表示最少花费。
示例 1
输入
4 70 1
输出
2
说明
可以先使用 “打折券”，价格变为 4 * 70 / 100 = 3（向上取整），再使用立减券，价格减为 2。
思路：分情况考虑就可以了（先打折后降价，先降价后打折），注意结果不小于 0
#include <iostream> | |
using namespace std; | |
typedef long long ll; | |
int main() { | |
ll p, x, y; | |
cin >> p >> x >> y; | |
int t1 = max((p * x + 99) / 100 - y, (ll)0); | |
int t2 = ((p - y) * x + 99) / 100; | |
cout << max(min(t1, t2), 0) << endl; | |
return 0; | |
} |
复杂度分析
- 时间复杂度：
- 空间复杂度：
# Q2easy
题目描述
小红正在训练人工智能，其中人工智能有一个很流行的功能是文字识别。
现在小红拿到了一个矩形图案，她希望你识别一下这个图案中的 '*' 字符表示的是字母 "L" 还是 "T"。你能帮帮她吗？
注：图案可能会旋转或者翻转。
输入描述
第一行输入一个正整数 q，表示共有 q 组询问。
接下来会输入 q 组图案，每组第一行输入两个正整数，代表图案的矩阵行数和列数。
接下来的 n 行，每行输入一个长度为 m 的、仅包含 '.' 和 '*' 的字符串。
保证字母的宽度为 1，且每一笔都是水平或垂直的。
输出描述
输出 q 行，代表每次询问的答案。如果是 L，则输出一个字符 'L'；如果是 T，则输出一个字符 'T'。
示例 1
输入
2
4 4
....
...
...
.
5 6
.....
.....
..*.
.....
......
输出
L
T
说明
第一组询问，可以看成是一个 L 进行了左右翻转而成。
第二组询问，可以看成是一个 T 逆时针旋转了 90 度形成的。
思路：思考一下 L 和 T 有什么不同，我找的规律是 L 必定有一个点会有两个分支，即某个 * 是四个方向有两个方向是由 * 的，而 T 有三个.
#include <iostream> | |
using namespace std; | |
constexpr int N = 110; | |
char g[N][N]; | |
int n, m; | |
int dx[4] = {-1, 1, 0, 0}; | |
int dy[4] = {0, 0, -1, 1}; | |
int get(){ | |
int maxv = 1; | |
for(int i = 0; i < n; i ++ ){ | |
for(int j = 0; j < m; j ++ ){ | |
int x = i, y = j; | |
if(g[x][y] != '*') continue; | |
int cnt = 0; | |
for(int k = 0; k < 4; k ++ ){ | |
int xx = x + dx[k]; | |
int yy = y + dy[k]; | |
if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue; | |
if(g[xx][yy] != '*') continue; | |
cnt ++ ; | |
} | |
maxv = max(maxv, cnt); | |
} | |
} | |
return maxv; | |
} | |
int main() { | |
int q; cin >> q; | |
while(q -- ){ | |
cin >> n >> m; | |
for(int i = 0; i < n; i ++ ){ | |
string s; cin >> s; | |
for(int j = 0; j < m; j ++ ) g[i][j] = s[j]; | |
} | |
cout << (get() == 2 ? 'L' : 'T') << endl; | |
} | |
return 0; | |
} |
复杂度分析
- 时间复杂度：
- 空间复杂度：，除去存储的空间
# Q3medium
题目描述
小苯来到了一座山脉，山脉中有 n 座山，每座山都有一个高度 h_i。有些山之间有路径连接，例如如果 a 号山和 b 号山之间有路径，如果小苯想的话，他可以从 a 山走到 b 山，同样的，也可以从 b 山走到 a 山。
但小苯很懒，如果两座山之间的高度差大于一定的值 k，他就不会走这条路（无论是上山还是下山）。形式化的即：|h_a - h_b| > k 的话，小苯便不会走这条路。
现在他提出了 q 次询问，每次询问他都会给出一组 (a, b, k)，他想知道，如果他从 a 山出发，高度差大于 k 的路径他不走，能否找到一条路使得他能走到 b 山呢，请你帮帮他吧。
输入描述
输入包含 1 + m + q 行。
第一行三个正整数 ，分别表示山脉中山的个数 n，山脉中山与山之间的路径数量 m，小苯的询问次数 q。
接下来一行输入 n 个正整数 ，表示每座山的高度。
接下来 m 行，每行两个正整数 ，表示 u 号山到 v 号山有路径连接。
接下来 q 行，每行三个正整数 ，分别表示小苯每次询问给出的信息。
输出描述
输出包含 q 行，对于每次小苯的询问，如果他可以从 a 走到 b 则输出 "YES"，否则输出 "NO"。
补充说明
注意，输入并不保证同一对山 a,b 中只有一条路径。
示例 1
输入
5 6 5
3 4 3 6 5
1 2
1 3
2 4
3 4
3 5
4 5
1 4 1
1 4 2
1 4 3
3 4 2
1 5 1
输出
NO
YES
YES
YES
NO
思路：离线做法；把所有路径的高度差预先保存下来（放入优先队列），同时把所有的查询预先保存下来。按照查询的高度差从低到高进行处理，每次处理前把小于等于当前高度差的边插入。如果两个节点处于同一个并查集则说明可以互相到达.
/* | |
离线 + 并查集 | |
*/ | |
#include <iostream> | |
#include <queue> | |
#include <vector> | |
#include <algorithm> | |
using namespace std; | |
constexpr int N = 2E5 + 10; | |
int p[N]; | |
int h[N]; | |
struct Node{ | |
int diff; | |
int a, b; | |
}; | |
struct cmp{ | |
bool operator()(const Node&t1, const Node&t2){ | |
return t1.diff > t2.diff; | |
} | |
}; | |
struct Query{ | |
int a, b, k; | |
int index; | |
}query[N]; | |
int find(int x){ | |
if(p[x] == x) return x; | |
return p[x] = find(p[x]); | |
} | |
int main() { | |
int n, m, q; cin >> n >> m >> q; | |
for(int i = 1; i <= n; i ++ ) cin >> h[i]; | |
priority_queue<Node, vector<Node>, cmp> qu; | |
for(int i = 1; i <= m; i ++ ){ | |
int a, b; cin >> a >> b; | |
Node cur; | |
cur.diff = abs(h[a] - h[b]), cur.a = a, cur.b = b; | |
qu.push(cur); | |
} | |
for(int i = 0; i < q; i ++ ){ | |
cin >> query[i].a >> query[i].b >> query[i].k; | |
query[i].index = i; | |
} | |
sort(query, query + q, [](const Query&t1, const Query&t2){ | |
return t1.k < t2.k; | |
}); | |
for(int i = 0; i < N; i ++ ) p[i] = i; | |
vector<int>res(q, 0); | |
for(int i = 0; i < q; i ++ ){ | |
int a = query[i].a, b = query[i].b, k = query[i].k, index = query[i].index; | |
while(!qu.empty() && qu.top().diff <= k){ | |
Node cur = qu.top(); | |
qu.pop(); | |
int px = find(cur.a), py = find(cur.b); | |
if(px == py) continue; | |
p[px] = py; | |
} | |
int pa = find(a), pb = find(b); | |
if(pa == pb) res[index] = 1; | |
else res[index] = 0; | |
} | |
for(int i = 0; i < q; i ++ ) cout << (res[i] == 0 ? "NO" : "YES") << endl; | |
return 0; | |
} |
复杂度分析
- 时间复杂度：
- 空间复杂度：
