试题A:裁纸刀
题意:一张纸上打印了20行22列共440个二维码,至少需要裁多少次可以全部裁出。如下图,2行3列共需要裁9次。
Tag:模拟
难度:☆
思路:根据题意,首先需要额外裁剪4次去除边界。每裁1刀,可以使得纸张数目增加1。最终要变成440二维码,只需要裁剪439 次。总计439+4=443次。
试题B:灭鼠先锋
题意:在2行4列的棋盘中,两人轮流操作,每次可选择在空位上放置1个棋子,或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。
先手存在4种初始局面如下所示,O表示空,X表示已放置。每人均以最优策略放棋子。判断先手胜利(输出V)还是后手胜利(输出L)。
Tag:博弈
难度:☆☆☆
思路:博弈题核心:
只能转移到必胜态的,均为必败态。
可以转移到必败态的,均为必胜态。
只能转移到必胜态的,均为必败态。
可以转移到必败态的,均为必胜态。
1.首先确定最终的必败态:只剩下1个棋子的时候肯定是必败的。
2.利用上述提到的核心,倒推出其他情况属于必败态还是必胜态。
3.注意,给定的4个局面为先手第一步的四种局面,对于此时局面为必胜态,表示的是后手胜。
int main{string s[] = {"XOOOOOOO", "XXOOOOOO", "OXOOOOOO", "OXXOOOOO"};for(int i = 0; i < 4; i++){if(dfs(s[i]))cout