[BZOJ] 几道比较有趣的题目

题目一描述

BZOJ 1008: [HNOI2008]越狱 监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

分析 如果直接求的话十分复杂, 而且貌似还要考虑容斥? 这个问题的关键就是转化一下, 求不能发生越狱的状态数, 这个比较好求, 再用总的状态数剪掉即可. 代码

https://code.csdn.net/snippets/615408

题目二描述

BZOJ 2463: [中山市选2009]谁能赢呢？ 小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，，而且两个选手都以最优策略走步，问最后谁能赢？

分析 一开始不明白为什么只是简单的和奇偶性有关系. 找了一些题解发现解释的最清楚的应该是用放骨牌的方法. 任何时候, 小明走一步, 小红走一步, 加起来走了两个格子, 就相当于放了一张2*1的骨牌. 交替的走就相当于交替放置骨牌. 如果n是偶数, 那么一定可以将棋盘铺满骨牌. 先走的就输了. 同理n是奇数的话, 一定有一个空格放不上骨牌, 后走的就输了. 代码

https://code.csdn.net/snippets/615410

题目三描述

BZOJ 1800: [Ahoi2009]fly 飞行棋 给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。

分析 找对角线, 这条对角线一定是圆的直径. 如果有x条对角线的话, 两两组合成矩形, 总个数就是x*(x-1)/2. 如何求一个点有没有对角线相连 到这个点的弧长是圆周长的一半的话连线就是对角线. 代码

https://code.csdn.net/snippets/615411

想说的话

@感谢提供者 : wxjlzbcd

旅行是一种病，当你把身边的人都传染了，