https://ac.nowcoder.com/acm/contest/62622/C
c题
从x!作为切入点,阶乘增长的非常快,我们可以枚举x,从而达到固定x,只剩y一个变量,问题转变为一次函数绝对值求最小值的数学问题,显然可以o(1)。
\[13!=6227020800 =6.2270208 × 10^9 \]\[12!=479001600=4.790016 × 10^8 \]对于13的阶乘不超过int 整数范围需要作为常识熟知
- 对于一次函数绝对值求最小值且自变量又被限制在整数,所以我们只需要考虑距离零点最近的左右两个整数点。
- 这两个整数点的数学表达则是零点表达式的下取整函数和上取整函数
- 对于出现上取整函数要注意对于0.x的小数判断,不能直接舍弃,因为上取整可能取成1变为可行解
D题
https://ac.nowcoder.com/acm/contest/62622/D
开始思路错误导致初始化清空clear的范围和后期正确思路不用,但思路正确后忘改了导致debug很久,得到教训:思路一旦错误,最好全部删掉重来,不然一个不小心就会有哪遗漏。
思路错误的原因时是,读题读的不够仔细,k——数组的要求是
思路分析:
-
从微观来看k-数组的要求需要满足a[i]=a[i+k],但如果只停留于此,会在最后计算最大值的时候无法求解或者还得重新思考这里面更深层次的规律,因为需要任意连续k长度的数组sum都相等。
a[i]=a[i+k]其实展现了,对于任意i,j,a[i%k]=a[j%k]的性质。 -
从宏观视角来看是要求下标i(modk)的剩余系组成k个集合,这些集合里的数需要一样并且是和每个集合里的最大数一样。再回头想这样做的合理性,k-数组的定义其实就是要所有modk的剩余系的总和一样。
代码实现过程需要注意: -
1.学习了使用max_element函数,后续另写文章介绍。
-
2.首先操作次数需要满足能让每个剩余系的数都加到这个系得最大值,如果操作次数还有剩余,则选择加到集合元素个数最小得集合中,因为加需要全部加,不然就不能加,一个集合里的所有数需要保持同样大小