阿里工程研发实习笔试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";
}