本文从WordPress迁移而来, 查看全部WordPress迁移文章
A.题意:一开始序列有n个不同的数字,每人每次可以选两个数字,作差求绝对值,这个绝对值一定不存在于当前序列中,然后将这个绝对值添加到序列中,直到某一个人,无法找到合法的绝对值插入序列,那么这个人输了,求出胜利的人是谁
- 显然的一个事实就是,一开始序列中最大值为Max,那么无论怎么选,后来产生的绝对值都比这个Max小
- 很天真的一个想法就是,感觉最后1-Max这些数一定都能产生,也就是还需要插入Max - n个数字,那就可以知道最后是谁插入,它就是胜者,写代码,wa
- 很快想到一个数据,3,6,发现这个数据,从一开始,就没办法插入数字(|3-6|=3,无法插入),也就是A一开始就输了,接着又想到了一个特殊的数据,2,4,6,8,发现这个序列,从一开始就没办法插入数字,A一开始就输了。很容易联想到是等差数列,然后接着发现另一个数据9,11,13,15,也是个等差数列,但是最后是可以构造完1-15所有的数字的,为什么都是等差数列,差都是2,但是结果相差这么大呢?于是再思考
- 观察2,4,6,8这种等差数列,发现,d=2,而最小的元素(或最大元素也行)是2,即2 = 1 d,是d的倍数,自然4=2 d,6=3 d,8=4d,很容易发现,对于一个等差数列,如果差是d,并且每个元素都是d的倍数,那么这个等差数列到最后,就会“终止生成”,无法继续扩展,例如 6,9,12,15,很容易发现,这个序列扩展到3,6,9,12,15后就停止了。刚才的序列9,11,13,15,d=2,但是序列的元素并不是d的倍数,所以存在继续扩展的能力
- 现在我们能明确一个结论就是,若一个序列为等差序列,差为d,最大元素Max = m*d,那么这个序列最后的元素个数就是m,分别为d,2d,3d,4d…..md
- 对于给定的序列P,如果最后停止扩展了,得到序列Q,那说明Q序列,一定是一个等差序列,差为d,并且Q中每个元素都是d的倍数,也就是说,P中原有的这些元素,都是d的倍数,那么d就是P中每个元素的公约数,求出d,问题都解决了
1 |
|