本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-26 19:49:19

喵喵题

题目来自某个不愿透露姓名的同学。

1. 有8节电池，4节有电，4节没电。每次可以测试其中两节是否全都有电，问最少几步能保证找到两节有电的电池。

如果按照分成4组，每组分别测一次，然后在每一组内部测是8步。

但是你可以直接分组为2，3，3然后分别内部枚举，答案是7。

2. 平面上 $n$ 个点，求是否存在一条恰好经过两个点的直线。

结论很简洁，不是全部共线就是存在。

考虑反证。设每一条直线上都存在至少3个点。每一个点都向所有直线做垂线。那么考虑最短的一条垂线（长度为正）AD，垂点是D，与BC垂直（BC是两端），这条垂线所垂的线中间的点（D，根据假设一定不是BC）与和它在垂线的同一侧的另一个点（B或C）与A的连线做的垂线一定更短（∠A一定大于等于90度）。与前提矛盾。

3. 平面上 $n$ 个红点，$n$ 个蓝点，任意3点不共线，任意4点不共圆，求是否存在方案使得红蓝配对，每对点连线互不交。

发现每对点的距离和最短时一定互不交，因为可以把一个交给拆开，长度一定严格变小。

4. 平面上 $n$ 个点，任意3点不共线，任意4点不共圆，有一条直线初始经过恰好一个点，接下来这条直线开始顺时针旋转，当恰好经过恰好两点时脱离初始经过的点，以后来的点为中心继续顺时针旋转。问是否存在初始方案使得每一个点都会被经过至少一次。

发现直线在转的时候，其两侧点的数量不变，且恰好改变一个点在左侧或右侧。

那么直接找一个角度满足这个角度下没有点共线，然后找到正中间那个点，其左右两侧的点数量最多相差1（其实可以无视这里的差，因为另一个满足相同条件的点也能够满足后面的），在这条直线旋转半周后，左边的点全都跑到了右边，右边的点全都到了左边，每一个点都至少被经过了一次。

5. 求 $\sum_{i=0}^n F_i^2$ 。

画图几何分析矩形面积发现其等于 $F_n\times F_{n+1}$ 。

6. 三个有交的圆，每一对相对应的交点相连，连出三条线段。证明三线共点。

唉唉，有点强了。把这三个圆作为赤道（确信）做三个球，显然只有两个点（对称）同时存在于三个球的表面。

也可以先构出两个球，其球面的交是一个垂直于平面的圆。这个圆与新的球面作交显然只会得到点。

7. 平面上有一个面积小于1大于0的不规则图形，定义横纵坐标都为整数的点为格点，证明一定存在一种方案，使得平移这个图形使得没有一个格点被图形包含或位于图形的边缘。

考虑移动格点，如何同时刻画所有格点？

我们先随便定一个点为原点，把所有格点划分出的单位矩形全都割下来叠在一起。把含有图形的部分看作不透明，不含图形的部分看作透明，那么不透明区域面积一定小于1。

然后直接找一个点满足这个点上没有图形（一定存在因为整个单位矩形的面积是1而在这个单位矩形上显示的图形面积一定小于等于原面积），直接把这个点作为原点新建坐标系即可让格点避开所有图形。