第四范式9.15测开笔试
10分单选+20分多选+70分编程
2道编程题（30+40），全A
- 给定某个正整数n，可以对其进行以下操作：（1）乘以某个正整数；（2）开平方（需要其平方为整数）。求可以变成的最小值，以及到达最小值的最少操作次数。
解法：实质上，最小值是其所有素因数的积。首先对2到n的所有数判断是否为素数。然后，查出n中包含素因数各自的数量。贪心的想法可得：一次乘法操作将所需的一次性乘掉，然后不断开方。假设素因数中某个数的最大个数为x。看看x是否是2的指数，同时看最大个数与最小个数是否相同。按照这两个情况判断是否需要乘法操作。
2. 给定只包含0和1 的字符串。令f为字符串两两相邻值的总和。比如，010101就是01+10+01+10+01。一次操作可以交换相邻元素。已知最多可以操作k次。求操作后的最小f。
解法：其实唯一可以变小的操作，就是：最后一个元素是0，让其和前面最近的一个1交换，这样能令f减小10。所以我们先算，不操作时的f值。然后判断k次操作是否能够将最靠后的1和（假如存在的）最后位置的元素0交换。
类似资料：