Codeforces Round #725 (Div. 3)A. Stone Game
给一个数组, 可以从两端取数字, 取了就没了, 求最少多少步可以取了最大和最小值. 这题他妈的真费时间, 一共3种取法 (答案给的是四种), 反正我三种做的, 三种是: 从左往右取, 从右往左和两侧取. 这题给了最大值是n, 最小值是1, 所以1/2两种都很好做, 就是第三个, 需要找下两个值的坐标, 然后减去两端就行了.
June 2021
方格取数
给一个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按个试..妈的, 比赛的时候想多了. 浪费时间
Codeforces Round #724 (Div. 2)A. Omkar and Bad Story
给一个数组, 问是否可以组成一个数组, 里面的元素包含其中任意两个元素相减的绝对值. 这题, 我上来以为是等差数列什么的呢…结果就是暴力求解..
Educational Codeforces Round 110 (Rated for Div. 2)C. Unstable String
给一个字符串, 里面有0,1和?, ?可以是1或者0, 求这个字符串的子字符串中可以变成1和0 交替出现的字符串的个数. 这题就是counting问题, 做的时候用的dp, 想了半天都有错, 后来想想, ?基本没啥用的地方, 因为0和1交替出现的字符串就两种, 一种是0101或者1010…所以如果我们强制替换奇数位上的1变成0, 0变成1, 那么如果是以上两种, 就会变成0000或者1111, 所以我们只需要用两个指针count一下每个substring是否是答案即可.
Educational Codeforces Round 110 (Rated for Div. 2)B. Array Reodering
给一个数组, 可以reorder这个数组, 求最大数量的pair, 使得gcd(ary[i], ary[j] * 2) >1 where i < j. 这个题就是需要思考, 我暴力的求解了一下, 发现过不了. 这题求一个数和2个倍数的gcd的大于1(非互质)个数. 因为能无限制reorder, 所以主要看这个数是不是2的倍数, 即是否可以被2整除, 如果可以, 假如ary[i] = 4, 那么肯定和 ary[j] * 2的gcd>1, 无论ary[j]是多少. 所以把数字分成两类, 一类是2的倍数, 另一类是非2的倍数, 然后排序下, 找一边即可.
Educational Codeforces Round 110 (Rated for Div. 2)A. Fair Playoff
给四个数, 两两比大小, 求最后的结果是不是两个中较大的.
Egg Drop With 2 Eggs and N Floors
给两个鸡蛋和n层楼, 已知一个鸡蛋从x层楼掉下去不会碎,但是从x+1层就会碎 求最少多少次扔鸡蛋可以知道x是多少. 典型的dp题, 可以用一个memo存当前的状态: 首先, 如果只有一个鸡蛋, 那么测n层楼需要测n次. 这里不用binary search, 因为我们的求的是最少多少次扔鸡蛋, 而binary search不一定能找到正确的解, 最坏情况我们还是要扔n次. 转移方程中, 两个状态是:1. 扔了没有碎, x肯定在当前i floor的上边: drop(egg, floor – i), 2. 扔了碎了, x肯定在当前i floor的下边 drop(egg – 1, i – 1). 因为同样数量的move下,我们需要找的是两个解中, 最”高”的一层所以取两个状态的max. 然后和当前的所有状态中的每个状态取min.