蚂蚁春招实习笔试题解(0511)

type

status

date

slug

summary

📝 主旨内容

小红的元素取反(贪心)

题目描述：

小红定义一个数组的权值为：正数的元素数量减去负数的元素数量。例如，[1,2,-3,-4,5]的权值是1，[-2,-5]的权值是-2。

现在小红拿到了一个数组，她准备选择恰好k个元素进行取反（同一个元素最多只能取反一次），之后使得数组的权值尽可能大。你能帮帮她吗？

输入描述

第一行输入两个正整数n,k，代表小红拿到的数组和选择的元素数量。第二行输入n个整数ai，用空格隔开。代表小红拿到的数组。1<=k<=n<=10^5 -10^9<=ai<=10^9

输出描述

一个整数，代表操作后数组权值的最大值。

样例输入

样例输出

提示

选择第1、3、4个元素取反，数组变成[5,1,-4,2,3]，权值为3。

💡

这里隐含了零这个特殊数字

💡

优先对负数取反，然后是0，最后才是正数，最后正确计算变化量即可

小红的等腰梯形(模拟)

题目描述:

小红在平面上拿到了四个点，请你判断这四个点是否构成等腰梯形。定义等腰梯形为：四条边分为两对，有一对边平行且不相等，另一对边相等且不平行。

输入描述

第一行输入一个整数q，代表询问次数。接下来的q行，每行输入8个整数p1x,p1y,p2x,p2y,p3x,p3y,p4x,p4y，代表询问的四个点的坐标。

1<=q<=1000

1000<=pix,piy<=1000

输出描述

输出q行。如果询问的答案是等腰梯形，则输出"Yes"。否则输出"No"。

样例输入

样例输出

提示

第一组询问满足等腰梯形的条件。第二组询问的为平行四边形，并不是等腰梯形。
第三组询问的也是等腰梯形。请注意平行的边不一定必须和坐标轴也平行。

💡

按照题意模拟即可，一组对边平行，另一组对边平行且不相等(此时上一组对边必不可能相等了)

💡

需要注意题目并没有按照某种顺序输入点，所以需要枚举三种可能(一个点连接另外三个点)

小红的数组权值和(数学)

小红定义一个数组的权值为，该数组的连续段数量。所谓连续段，即相邻的相同元素均在一个连续段内。例如，[1,1,2,3,3,3,3]的连续段数量为3。

现在小红想知道，长度为n的、元素范围为[1,m]的所有数组的权值之和是多少？

输入描述：

两个正整数n,m，用空格隔开。

1<=n，m<=10^9

输出描述:

长度为n的、元素范围为[1,m]的所有数组的权值之和。由于答案过大，请对10^9+7取模。

样例输入:

样例输出:

提示:

长度为2的、元素范围为[1,3]的数组共有9个，其中[1,1]、[2,2]、[3,3]的权值是1，其余权值是2。因此答案是6*2+3=15

💡

看范围，都是在10^9，一般是得用数学知识，复杂度需要控制在log(n)级别，快速幂

💡

有n个位置，每个位置有m个数，所以一共有m^n种情况，每种情况至少包含权值1，也就是全相等是一段，或者说是一个数形成的

💡

从第二个开始考虑，如何获得更大的权值，那就是和上一个数不相等，概率为(m-1)/m，有n-1个位置，一共m^n种情况，所以总期望贡献是(n-1)*(m-1)/m*m^n

🤗 总结归纳

整体难度中等偏难，第三题直接坐牢

📝 主旨内容

小红的元素取反(贪心)

小红的等腰梯形(模拟)

小红的数组权值和(数学)

🤗 总结归纳

📎 参考文章