阿里工程研发实习笔试2023-04-03
还记得20年做阿里的笔试题，一个是普通 BFS，一个是普通 set，两三百百刷题量就可以秒杀。
但现在，不仅难度提升，题量还变大，而且还增加了考点巨细无比的选择题。
时过境迁，校招笔试题已经卷到如此地步了，不得不让人唏嘘....
T1 黄牌警告，红牌下场
一个球队有n个球员，已知他们一共接受了x张黄牌，y张红牌。
当一个球员满足以下条件之一时会立刻下场：
1. 接受了2张黄牌
2. 接受了1张红牌
请问已知以上信息的前提下，当前能上场的球员最多有多少人？最少有多少人？共有q次查询。
q <= 1e4, 1 <= n <= 1e9, 0 <= x, y <= 1e9
输入：
4
2 2 1
3 2 0
3 0 2
1000000000 0 0
输出：
1 0
3 2
1 1
1000000000 1000000000
最少很好算，n - int(x / 2) - y 即可。
最大的情况是：将黄牌尽可能的发个每一个人，然后剩余的 x - n 张发给没有发红牌的人（n - y 个里面选择 x - n 个）。
T2 矩阵染色问题
给定一个n行m列的矩阵，其中一些方格被染成了红色，其余方格为初始的白色。
现在定义 f(i, j) 为：若将第i行、第j列的方格染白，当前矩阵的红色连通块数量。
请你求出每个 f(i，j) 的值。
1 <= n,m <= 40
暴力枚举每一个方格，修改后求红色连通块个数（DFS）。求解连通块个数可以参考：https://leetcode.cn/problems/number-of-islands/description/
复杂度 O(n^2m^2)。
T3 权值不超过 k 的连续子数组数量
我们定义一个数组的权值为：所有元素乘积的因子数量。例如，[2,6]的权值为6，因为2*6=12，12有6个因子：11,2,3,4,6,12}
现在给定一个数组，试求该数组有多少连续子数组的权值不小于K？
1 <= n, a_i <= 2e5, 1 <= k <= 1e9
所有元素的乘积的因子数量与质因数分解后的指数有关。
一个数 x 可以被分解为若干个质因数的乘积：
它的因子个数是：
所以，我们通过滑动窗口维护其中所有数字乘积的质因数的指数（用一个数组或哈希表），同时维护因子数量（cnt）。
对于每个右端点 i，维护最小的左端点 j，使得 [i,j] 乘积因子数目小于 k。那么对于 i 来说，共有 j 种方案满足要求，例如 [0, i], [1, i], ... [j-1, i]。
时间复杂度为 ，主要是质因数分解的复杂度。
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
unordered_map<int, int> mp;
ll cnt = 1, res = 0;
auto addv = [&](int x, int t) {
for (int i = 2; i * i <= x; i++) {
while (x % i == 0) {
cnt /= (mp[i] + 1);
mp[i] += t;
cnt *= (mp[i] + 1);
x /= i;
}
}
if (x > 1) {
cnt /= (mp[x] + 1);
mp[x] += t;
cnt *= (mp[x] + 1);
}
};
for (int i = 0, j = 0; i < n; i++) {
cin >> a[i];
addv(a[i], 1);
while (j <= i && cnt >= k) {
addv(a[j], -1);
j++;
}
res += j;
}
cout << res << "\n";
}
#笔试##软件开发2023笔面经##阿里#记录2023年-2024年的笔试、面试问题~
查看4道真题和解析