Menu Sidebar
Menu

Archive: June 10, 2021

Codeforces Round #725 (Div. 3)B. Friends and Candies

给一个n个数字的数组, 问最少可以取多少个数字, 使得分配给别的数字(包括自己),后让数组的值全相等. 一共n个数组, 那么全相等, 肯定就是sum % n == 0 才可能. 不然怎么分都分不出来. 然后因为要分给别的数, 所以只需要找到比sum/n大的数字, 即可., 因为反正这些大数都要分了才能变成sum/n, 是吧…..脑筋急转弯

Codeforces Round #725 (Div. 3)A. Stone Game

给一个数组, 可以从两端取数字, 取了就没了, 求最少多少步可以取了最大和最小值. 这题他妈的真费时间, 一共3种取法 (答案给的是四种), 反正我三种做的, 三种是: 从左往右取, 从右往左和两侧取. 这题给了最大值是n, 最小值是1, 所以1/2两种都很好做, 就是第三个, 需要找下两个值的坐标, 然后减去两端就行了.

方格取数

给一个2d矩阵, 里面有数字, 求取两个线上的数字,使得和最大, 只能往下和右走. 这个题我开始以为是greedy, 直接取一次, 再取一次就可以了, 然后感觉是不对的, 因为第一次走如果取了最大的值, 肯定会走过一些不是最大的值的路径, 而这些路径上的值是否就一定没有包含次大的值呢? 这个是不知道的. 所以要同时走才可以. 因为是同时, 相当于两个人在走A: (i1, j1),B: (i2,j2), 那么应该有 2*2四种情况. 所以应该是4维dp..然后看了讨论里,用的是压缩一维的方法, 即: 因为是n*n这么大的个子, 而且还只能往下往右走, 那么最多的步数就是2*n. 那么, 设k为当前步数, 就可以通过i找到j, 因为i+j=k, 比如极限情况下, 先走右到头然后下到头, 就是i=n, k=2*n, j = k-i = 2*n – n = n, 这样可以压缩一维, 四维变成三维 还有, 当计算数字的时候,如果两个人在同一格, 应该只取一次. 其他情况取各自格上的数.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.