Menu Sidebar
Menu

April 2022

Minimum Suffix Flips

给一个string, 里面是0和1, 给一个操作, 可以flip所有在i后的字符, 求最少flip几次. 这题通过观察, 可以发现如果从左往右考虑, 从0到1的flip和从1到0的flip, 其实都不会影响左边已经flip过的字符, 故操作次数只与当前的字符是不是和前一个字符相同有关.

Count Triplets That Can Form Two Arrays of Equal XOR

给一个数组, 有多少组triple(i,j,k), 可以让0<= i < j<k <=n中[i,j),[j,k]的xor相等. 这题挺有意思, 直接做就是O(N^3), 是可以过的. 然后考虑优化到O(N^2), 因为xor是半加符号, 所以可以想到是用presum的方法. 首先建立pre xor数组, 但是怎么用这个数组, 可以考虑一下, xor相等的意思是值为0, 所以如果有一个区间[i,k]中的xor为0, 那么这个区间里的所有j都是答案的选项.

Older Posts

书脊

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