Menu Sidebar
Menu

Codeforces Round #725 (Div. 3)F. Interesting Function

给两个数字l和r, 求从l加到r中间digit的变化个数是多少.

这题用的方法和D一样,就是先求R的答案, 然后减去L的答案, 具体的求法是通过观察: 比如21这个数, 从1->9 是9个1位改变, 9->10是1个2位, 10->19是9个1位改变, 19->20是2个1位改变. 20->21 是1个1位改变, 所以加起来就是21+2, 有次可推,数字123是123+12+1.

Codeforces Round #725 (Div. 3)D. Another Problem About Dividing Numbers

给三个数,a,b,k, 问a和b是不是能在k次(exactly) 下通过整除相等.

这个题情况比较多, 比如a和b互质, 比如k大于a和b. 反正就是交一次就对的都是大神.

这题思路是, 反正a和b一直和某数做整除, 最后就是1, 肯定相等啊, 所以只需要计算有多少质因子在a和b的和中.即可, 剩下就是各种corner cases.

Codeforces Round #725 (Div. 3)C. Number of Pairs

给一组数和l还有r, 求这组数中任意两个数的和在[L,R]中.

先排序, 然后求[0,R], 然后再求[0,L-1], 两个相减即可.

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, 这样可以压缩一维, 四维变成三维

还有, 当计算数字的时候,如果两个人在同一格, 应该只取一次. 其他情况取各自格上的数.

摘花生

给一个2d矩阵, 只能往下往右走, 每个格上有数字, 求最大能拿多少数字.

Determine Whether Matrix Can Be Obtained By Rotation

给两个nxn矩阵, 问是否能通过连续翻转90度得到另一个矩阵.

Codeforces Round #724 (Div. 2)B. Prinzessin der Verurteilung

给一个字符串s, 求字典序最小的字符串没有在s中出现.

这题就是bfs按个试..妈的, 比赛的时候想多了. 浪费时间

Older Posts

书脊

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