阿里2023春招笔试

（Author：DH）

第一题

给定一个环形数组，你需要切两刀，把它切成两段，使得两段的元素之和相等。请问有多少种切割方案？

输入描述

第一行输入一个正整数n，代表环形数组的元素数量。
第二行输入n个正整数ai，代表环形数组的元素。
1<=n<=10^5
-10^9<=ai<=10^9

输出描述

一个整数，代表切割的方案数。

输入

4
1 2 -1 2

输出

2

说明

如下图，共有两种切法：

题解

切成两段且相等，也就是说每一段的值都是sum/2.题意可以转化成求多少个区间的和为sum/2，可以利用前缀和 + 哈希表来求解。

第二题

n个学生围成一圈，编号从1到n。

每个学生将从1开始报数，报到素数的人出列，剩下的人继续报数。试求最终留下来的人的编号是多少。

输入描述

一个正整数n，代表学生的人数。
1<=n<=10^4

输出描述

一个正整数，代表最终留下来的学生编号

输入

4

输出

4

说明

报数流程如下：
1号报1.
2号报2，出队。
3号报3，出队。
4号报4.
1号报5，出队。
最后留下来的是4号。

题解

经典的约瑟夫环问题，额外判断一下素数即可

第三题

给定一个数组，你可以进行最多k次以下操作：

选择一个大于1的元素ai，使得ai除以它的一个素因子p。

试求操作结束后，数组的所有元素之和的最小值是多少

输入描述

第一行输入两个正整数n和k，代表数组大小以及操作次数。
第二行输入n个正整数ai，代表数组的元素。
1<=n,k<=200000
1<=ai<=10^6

输出描述

一个整数，代表操作后的所有元素最小的和。

输入

2 1
5 6

输出

7

说明

只能操作一次，选择一个元素，5/5=1即可，数组变成{1，6}

题解

利用贪心的思想，选k个数字较少数量最大的数

这里可以用堆