阿里2023.3.26笔试

题目

• 输入一个数组（n <= 2e5），其首尾是相接的，也就是一个循环数组，找出两个切割点，使得切割后的两个子数组的和相等，求有多少种切割方案。

Sample Input
4
-1 2 -1 2
Sample Output
2

• 有n（n <= 1e4）个人，其首尾是相接的，也就是围成一个圆，编号1~n，从第一个人开始循环报数（从1开始，每次加1），如果报的是素数则出列，问最后一个剩下的人的编号是多少？

Sample Input
4
Sample Output
4

• 输入一个长度为n的数组a，你可以操作k次，每次操作取出一个数，并将其除以他的一个素因子。求k次操作之后数组的最小和。其中 1 <= n <= 2e5, 1 <= a[i] <= 2e6

Sample Input
2 1
6 5
Sample Output
7

题解

• 第一题做一个前缀和，然后map一下，从前到后遍历第二个切割点，找map中有多少个总和的一半减去当前前缀和的数，加到答案即可。
• 第二题直接暴力即可。最多要找前1e4 - 1个素数，因为n以内的素数占比大约是1/In(n)，所以不会超时。
• 第三题先用线性筛筛一下2e6以内的素数，得到每个数的最小素因子，然后暴力处理出来2e6内的每一个数的最大素因子，对于每一个数，一定是拿最大的素因子除，优先队列维护一下最大的收益，取k次即可。没交上去，不知道对不对，附上代码。

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 2000005;

int a[200005], is_prime[MAX_N], n, k, min_factor[MAX_N], max_factor[MAX_N];
priority_queue<pair<int,int>, vector<pair<int,int> >,less<pair<int,int> > > que;

void init_prime() {
    for(int i = 1; i < MAX_N; i++) is_prime[i] = true, min_factor[i] = i;
    is_prime[1] = false;
    for(int i = 2; i < MAX_N; i++) {
        if(is_prime[i]) {
            for(int j = 2; j * i < MAX_N; j++) {
                is_prime[i * j] = false;
                min_factor[i * j] = i;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &k);
    init_prime();
    for(int i = 2; i < MAX_N; i++) {
        int maxx = 1, tmp = i;
        while(tmp != 1) {
            maxx = max(maxx, min_factor[tmp]);
            tmp /= min_factor[tmp];
        }
        max_factor[i] = maxx;
    }
    long long sum = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] != 1) que.push(make_pair(a[i] - (a[i] / max_factor[a[i]]), a[i]));
        else que.push(make_pair(0, 1));
    }
    for(int i = 1; i <= k; i++) {
        pair<int, int> t = que.top();
        que.pop();
        sum -= t.first;
        int next_val = t.second - t.first;
        if(next_val != 1) que.push(make_pair(next_val - (next_val / max_factor[next_val]), next_val));
        else que.push(make_pair(0, 1));
    }
    printf("%lld\n", sum);

}