牛客算法竞赛入门课第一节习题Part2（ Flip Game ~ Subsequence）

Flip Game

题意：

有一个4*4的棋盘，每个格子上都有一个黑白两面的棋子。每次任意选择一个棋子，把这颗棋子和他周围的棋子都反过来。当所有的棋子是同一个颜色时，游戏结束。

问给定的初始状态能否完成游戏，若能，输出最小的反转次数。

思路：

因为是最小的翻转次数，而且我们无法确定如果翻转才是最优解，所以我们只能对每一种状态都枚举他的所有可能状态，BFS求解。

但同时难点在于如何储存当前的状态，如果用数组的话，结合队列不是很好操作。我们可以用二进制表示每个棋子的黑白状态，这样就可以用一个数tmp来表示每一种状态。

当tmp==0或是tmp==1<<16(65535)时游戏结束。

Subsequence

题意：

求一个序列的连续子序列的和>=s的最短长度。

思路：

双指针。

先求一个前缀和数组，因为是连续子序列[l,r]，所以sum[r]-sum[l-1]就是该子序列元素的和。

取两个指针为l,r，初始化均为0。

先不断右移r指针使得区间和>=s，当区间和>=s时不断右移l指针，并且记录r-l的最小值。

矩阵消除游戏

思路：
因为不知道选哪一行哪一列是最优的，而且数据范围也比较友好，就可以二进制枚举选几个行，剩下的都选列。在选择的过程中肯定是选择得分最多的行。