蚂蚁笔试 蚂蚁笔试题 0508
笔试时间：2025年5月8日
往年笔试合集：
第一题：Y串
对于给定的字符串 S1S2…Sn，将其全部奇数位置的字符删除，得到新的字符串 S′，随后将 S′ 反转，得到新的字符串 S′′，最后，将 S′′中的所有小写字母转换为大写字母。
你需要输出最终得到的字符串 S′′。
输入描述
第一行输入一个长度为 1≤len(S)≤105，由大小写字母混合构成的字符串 S。
输出描述
输出最终得到的字符串 S′′。
样例输入
WhilE
样例输出
LH
第一步，删除奇数位置的字符，得到新的字符串S'="hl";
第二步，反转字符串，得到新的字符串S''="lh";
第三步，将S''中的所有小写字母转换为大写字母，得到最终的字符里S''="LH"
参考题解
签到题，模拟即可。先删除奇数位置，得到新字符串，之后将其反转，最后小写转大写即可。
C++：
#include<bits/stdc++.h>
usingnamespacestd;
int main() {
string s;
cin >> s;
string t;
for (int i = 1; i < s.length(); i += 2) {
t += s[i];
}
reverse(t.begin(), t.end());
for (char& c : t) {
if (islower(c)) {
c = toupper(c);
}
}
cout << t;
}
Java：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
StringBuilder t = new StringBuilder();
// 提取每隔一个字符
for (int i = 1; i < s.length(); i += 2) {
t.append(s.charAt(i));
}
// 反转字符串
t.reverse();
// 转换小写字母为大写
for (int i = 0; i < t.length(); i++) {
if (Character.isLowerCase(t.charAt(i))) {
t.setCharAt(i, Character.toUpperCase(t.charAt(i)));
}
}
System.out.println(t);
}
}
Python：
def main():
s = input()
t = ''
# 提取每隔一个字符
for i in range(1, len(s), 2):
t += s[i]
# 反转字符串
t = t[::-1]
# 转换小写字母为大写
t = ''.join([char.upper() if char.islower() else char for char in t])
print(t)
if __name__ == "__main__":
main()
第二题：小红的查询线段
小红有一根长度为 n 的绳子，她在绳子上均匀地画了 n 个点（包括端点），点的编号为 1 ~ n，这样绳子被均分为 n 段。
她现在提出 Q 次查询，每次查询要进行下列操作的其中一种：
操作一：在点 a (1 ≤ a ≤ n) 上画一条红线。
操作二：若把当前画红线的地方全部删掉，询问是否存在长度大于等于 k 的绳子。
不考虑绳子损坏且每次询问都是独立（即假设绳子断裂，但实际上并不是真的断裂），请你回答小红的每次询问。
输入描述
第一行输入两个整数 n, Q (3 ≤ n ≤ 10^9; 1 ≤ Q ≤ 10^5) 代表绳子的长度，小红的操作查询次数。
接下来 Q 行，每行先输入一个整数 op (1 ≤ op ≤ 2) 表示操作查询的类型，随后：
当 op = 1，在后续一行输入一个整数 a (1 ≤ a ≤ n)，表示在 x 处画一条红线。
当 op = 2，在后续一行输入一个整数 k (1 ≤ k ≤ 10^9) 查询若把当前的红线断开，是否存在长度大于等于 k 的绳子的长度。
输出描述
对于每个询问二，若把当前的红线剪断，会存在长度大于等于k的绳子，在一行上输出YES ；否则，直接输出NO。
样例输入
8 7
2 7
1 4
2 4
2 5
1 6
2 3
2 4
样例输出
YES
YES
NO
YES
NO
初始时绳子形象的表示为1-2-3-4-5-6-7-8；
对于第一次操作，由于此前没有画过红线，所以得到一根长度为7的绳子，符合询问；
对于第二次操作，在第四个点的位置画一条红线，得到1-2-3-[4]-5-6-7-8；
对于第三次操作，切断后得到一根长度为3的绳子和一很长度为4的绳子，1-2-3-4和4-5-6-7-8，符合询问；
对于第四次操作，同上，不符合询问:
对于第五次操作，在第六个点的位置画一条红线，得到1-2-3-[4]-5-[6]-7-8;
对于第六次操作，切断后得到一根长度为3的绳子和两根长度为2的绳子，1-2-3-4、4-5-6和6-7-8，符合询问。
参考题解
set+map，利用set维护所有红线的位置，利用map维护每种长度绳子出现的数量。对于操作一，在x处画一条红线，假如x已在set中，说明之前画过红线则跳过。否则在set中二分小于x且最大的红线位置记作lc，大于x且最小的红线记作rc。那么原来的长度rc-lc会被切断成x-lc和rc-x两段，在map中更新对应数量。对于操作二，直接看map中最大的那个长度是否大于等于k即可。
C++：
#include <bits/stdc++.h>
usingnamespacestd;
int main() {
int n, q;
cin >> n >> q;
set<int> st;
map<int, int> mp;
mp[n - 1] = 1;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
x--;
if (st.find(x) != st.end()) {
continue;
}
int lc = 0;
auto it_lc = st.upper_bound(x);
if (it_lc != st.begin()) {
--it_lc;
lc = *it_lc;
}
int rc = n - 1;
auto it_rc = st.upper_bound(x);
if (it_rc != st.end()) {
rc = *it_rc;
}
int sz = rc - lc;
auto map_it = mp.find(sz);
if (map_it != mp.end()) {
if (--map_it->second == 0) {
mp.erase(map_it);
}
}
mp[x - lc]++;
mp[rc - x]++;
st.insert(x);
} else {
int k;
cin >> k;
if (mp.empty() || mp.rbegin()->first < k) {
cout << "NO\n";
} else {
cout << "YES\n";
}
}
}
}
Java：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
Set<Integer> st = new TreeSet<>();
Map<Integer, Integer> mp = new HashMap<>();
mp.put(n - 1, 1);
while (q-- > 0) {
int op = sc.nextInt();
if (op == 1) {
int x = sc.nextInt();
x--;
// 如果 x 已经存在，则跳过
if (st.contains(x)) {
continue;
}
int lc = 0;
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
