思维、找规律题目汇总

转自：http://hi.baidu.com/liuzhe/blog/item/d2dc0fd10bf1eadb572c843d.html

感想：
1.还是数学有前途
2.猜想很重要
3.暴力打表可以有助于找规律

因为是都是考思维的题，所以大家可以先不看后面的解答，自己试试^_^

ZOJ 3163Apple Pile
POJ 3716Panda's Birthday Present
UVA 11579Triangle Trouble
SGU 417Heavy Disc
HDU 2662Coin

HOJ 11305Desperate Electrician
Timus 1690Army of Mages
SGU 424 Beautiful graph
ECNU 2528MST难题
HOJ 11405Sequence Maker

TOJ 3278Circuit Board
ZOJ 2132The Most Frequent Number
HOJ 11569Bouncing balls
HOJ 11591Tanks a Lot

ZOJ 3243Diamonds

－－－－－－－－－－－－－－－－华丽的分割线－－－－－－－－－－－－－－－－－



ZOJ 3163Apple Pile

这个其实主要是不要被题意吓到，读懂题就可以想到了。证明也很简单，n天坏完、所以最多n-1个，前n-1天一直有好的，所以最少n-1个。。。

POJ 3716Panda's Birthday Present

这个比赛时我暴力的，赛后听说有公式(x+y+10)/7。想想可能是这样：直接猜公式是ax＋ay＋b（因为x和y有对称性），然后用样例解方程组。。。至于为什么是线性的，现在只能说是感觉了。。。哪位大牛有更好的方法告诉我下。。。


UVA 11579Triangle Trouble

这个猜应该叫贪心了，就是排序后枚举连续的3条边构成三角形，记录最大值就是答案。。。

SGU 417Heavy Disc

这种纯高等数学题是第一次看到，绝对是考查灵感的经典题目。。。结果答案居然直接就是ln(x0^2+y0^2)*PI*r^2，直接就猜平均密度相当于圆心处的。。。有一组12位小数的样例，可以来检验这个猜想。至于证明。。。我让班上微积分最牛的同学用了2天，证出来了，用了坐标变换、含参量积分、积分号下求导（还求了2次导），我看着就晕，比赛时看样子是不可能的。。。希望这样简洁的结论能有简洁的证明。。。

HDU 2662Coin

出几组数据就可以猜到a*b-a-b，不过这里还是证明一下吧。

设所求为n，那么n+a、n+b可以用a、b线性表出，而n不可。
所以 n+a=x1*a+y1*b，n+b=x2*a+y2*b
所以 n=(x1-1)*a+y1*b n=x2*a+(y2-1)*b
因为n不能被线性表出，所以x1=0，y2=0
所以 n+a=y1*b，n+b=x2*a
所以 n+a=y1*b，n+a=(x2+1)*a-b
所以 (x2+1)*a-b是b的倍数
因为a、b互质，所以(x2+1)是b的倍数
因为求最小的n，所以选最小的x2值，所以取(x2+1)为b
所以 n+a=b*a-b，n=a*b-a-b
证毕

HOJ 11305Desperate Electrician

因为可以带无数个接头，测无数次。。。所以。。。除了2的情况下测不出来，其他都只要1次，反正电工可以随便接线。。。详细证明见wzc1989的文章

Timus 1690Army of Mages

一看到就想构图，规模很吓人，但是为什么一定有5n个点呢？一定有猫腻。其实根据x，y坐标的奇偶性可以把点分成4类，然后每一类之间一定是可以相互满足条件的。然后一定有一类会有至少n个点，输出n个即可。

SGU 424Beautiful graph

这个题不难，典型的构造。可能感觉全是3角型会边最多，但是实际上n比较大时（n>=6），连1到2，3...n-1，n到2,3,...n-1，这样会最优

ECNU 2528MST难题

暴力打表找规律，规律很简单的。。。
for(i=3;i<=50;i++)
if(i&1)f[i]=2*f[i-1]-2;
else f[i]=2*f[i-1]+2;

printf("%I64d\n",3*f[n]);

HOJ 11405Sequence Maker

暴力打表找规律，这个规律也很简单。。。只有4n-1和4n的才是可行的。。。

TOJ 3278Circuit Board

想法就是，每个点加入树中，一定要有一条父亲连过来的边，这条边有入度种选法，然后把每个点的选法乘起来就是了。。。无圈保证了只有入度种选法；并且个点的选择不同，都将导致不同的结果。。。所以枚举根统计入度相乘即可，注意int会超范围。（实际上可能为根的点只可能有1个，有向无圈的条件太强了 ，都可以排拓扑序了。。。）

ZOJ 2132The Most Frequent Number

经典的思维题。不但要求线性，还要求内存极少。唯一的特别条件就是众数个数大于n/2。实际上让众数与其他数两两相消就可以了。空间只要4个int。记录当前众数，众数频率。如果新的数和众数相同，频率++，如果不同且频率不为0，频率--，频率也为0，让当前数成为众数。

HOJ 11569Bouncing balls

主要有2点：
1.球相撞之后可以看成直接穿越，而不是弹回，因为这个是等价的。也就是说每个球的运动可以看成不受其他球影响
2.每个球的x方向运动与y方向运动也可以分开考虑，互不影响
明确的以上2点，计算就很简单了。。。

HOJ 11591Tanks a Lot

只考虑一个方向，另一个方向同理。如果从某点x朝一个方向走，假设一直可以走下去，我们可以算出每个点相对于起点的油量。注意到这个油量的相对关系是不会变的，而一个合法的走法，是从一个油量为0的起点开始，途中不能有负数油量。那么选哪些点开始走呢？用电势的概念，即选哪些点为0势点，可以使得其他所有点的电势都不小于0？显然选相对电势（油量）最小的那些点即可，其他的点均不合法。

ZOJ 3243Diamonds

lrj出的很厉害的思维题，我的想法是：
1.坐标变换后变为正方型的问题，方便求交
2.第i个正方形（包含前i个点）选定后，一定可以在其内部构造出剩下i-1正方形的可行解（前提是存在解）

所以我的构造方法就是：

for(i=n;i>=1;i--)
1.根据当前正方形应该包含的点求出当前正方形中心的范围，并与上一正方形求交，得到可行区域
2.在可行区域内，任选一个点（由于要求坐标变换回去后是整数，所以x，y同奇偶），作为当前正方形的中心
3.记录变换回去的坐标

输出坐标