【题解】湖南大学程序设计竞赛新生赛（重现赛）

A. The GCD of Fibonacci Numbers

题意：
给定正整数m,n，求第m个Fibonacci数和第n个Fibonacci数的最大公约数。
解题思路：
当 $m>n$ 时，有 $f_m=f_{n+1}f_{m-n}+f_{m-n-1}f_n$
所以 $GCD(f_m,f_n)=GCD(f_{m-n},f_n)=......=f_{gcd(m,n)}$

B. Xu1024's treasure chest

题意：
给一个数字a，-100000000≤a≤100000000
要求找到两个数字b,c
使得c^2-b^2=b^2-a^2
并且a<b<c, -1000000000≤b,c≤1000000000

题解：
样例是吓唬人的
假设a=1，那么可以手算得到一组解(a,b,c)=(1,5,7)满足条件
所以b=5a，c=7a就可以轻松构造出一组解
只有当a=0才会出现无解的情况
注意下a是负数时对a取个绝对值即可

C. Binbin's treasure map

题意：
给一个平面图，上面有障碍物，平面图以外的区域是相通的
可以选择两个起点，求收集到的钱币数总和

题解：
平面图BFS裸题
数据范围n,m<=500
首先，从每个点开始搜一下，看能否向周围走，能的话就走
因为平面图以外的区域是相通的，就将平面图以外的区域都标志位能走
每走过一个点，就标记一下，下次不走这个点
这样每次就能得到一个连通块的钱币数
取前2个即可

时间复杂度O(nm)
空间复杂度O(nm)

D. CET and miniskirt

解题思路：
结论：
对于所有选项，写下的选项个数 <= 答案中其他选项的个数都成立，则最低分为0。否则最多存在一个写下的选项个数 > 答案中其他选项,此时最低分为这一选项的写下的选项个数-答案中其他选项。

证明：
显然，如果一个选项写下的个数>答案中其他选项个数，那么最低分=写下个数-答案中其他选项个数。可以证明最多只有一个选项会出现写下的个数>答案中其他选项个数。
如果有一个选项写下个数 = 答案中其他选项的个数，那么得零分的方式显然。比如这个选项是A，那么所有答案不是A的题目都写A，然后其他选项都只能填到答案为A的题目了。
如果对于所有选项，写下的选项个数 < 答案中其他选项的个数。随意匹配一对错误答案：比如把A填到答案为B的题目
那么对于A选项，剩余写下的选项个数减1，答案中其他选项个数减1，情况不变
对于选项B，剩余写下的选项个数不变，答案中其他选项个数不变，情况不变
对于选项C,D，剩余写下选项个数不变，答案中其他选项个数减1，可能导致两种情况：

写下选项个数不变 < 答案中其他选项个数
写下选项个数不变 = 答案中其他选项个数
如果是第一种情况，继续匹配错误答案（此时一定可以找到这样一对错误匹配）
如果是第二种情况，很容易构造方案。

E. Days passing

题意：

给出当前星期，求N^M天后是星期几.保证m为6的倍数

解题思路：
解法1：
先求N%7，用字符串来模拟取模运算，然后因为M%6为0，
当N%7==0时，显然，N^M%7=0，所以是同一天
当N%7!=0时，是当前的下一天。
图片说明

F. Kuangyeye's Game

G. Buying keys

题意:
钥匙3元一把十元三把，有n元钱，求刚好花完n元能买到的最小钥匙数量。
题解：贪心。如果当前余额不能被10整除，那就一直买三元一把的钥匙，直到余额小于3或者余额被10整除。如果最后余额不为0，则无解，否则余额全买十元一把。

H. Dice

题目大意：
赌大小，输赢概率都是1/2,从1块钱开始赌。每次若赢则离开游戏，否则持续赌博并把赌注翻倍，最多赌n场，输出赢钱的概率

解题思路：
只要某一场胜利那么就一定能赢钱(等比数列，前n项的和为2^n-1<2^n),所以本题答案等于1-P(一直输) ，一直输的概率为(1/2)^n
复杂度：O(1)

I. Amubulance

题意：
连线，两边每边n个点，问有多少种方法使得A中至少存在一个a连接到了B中的第Ai根线。
因为Ai是个全排列，所以题目可以化简为A中至少存在一个第i条线连接到了B中的第i根线。
解题思路：
题解：
连线方法共有n!种
考虑一个都没连上的情况有多少种记为D
那么答案就是n!-D

怎么得到这个D
当只有1对点的时候，D[1]=0；
当只有2对点的时候，D[2]=1；
当只有3对点的时候，D[3]=2；
对于第4对点，可以看做是D[3]转移而来，D[3]中选一条线断开，分别连上第四对点的两端
也可以是从D[2]中转移而来，可以看做是在D[2]后再加两对点，使它们错开。
这样就可以得到D[n]的转移式了
D[n]=(n-1)*(D[n-1]+D[n-2])
最后答案就是n!-D[n]
时间复杂度O(n)
空间复杂度O(n)
ps：其实就是全错排啦~

J. Fake Nim

题意：

解题思路：
1、考虑只有一堆的情况：
a. 若数目为偶数，则A可以在第一轮取完，A获胜。
b. 若数目为奇数，则A取完后必定剩余奇数颗，此时B可以一次取完，B获胜。

2、考虑n(n>1)堆的情况：
现在A第一轮不可能全部取走，那么在B的回合，只需要使某一堆为奇数个石子，接下来一直不取这一堆，直到最后一次全部取走(这一堆为奇数个所以不可能被A取完)，即可以保证所有石子的最后一个必定被B取走，B获胜。

3、综上：当石子只有一堆且数目为偶数时A获胜，否则B获胜。

4、时间复杂度O(1)。

K. Alice’s Army

题目大意:
给出n个怪物的能力和武器，m个军队的能力、耐久度和武器。三种武器有相互克制的机制，被克制的一方能力暂时下降50%。怪物需要按照编号顺序依次击败。每次只能选择一个军队出战，每次交战后军队耐久度下降一点，当战败或者耐久度为0时需要返回休整，休整后军队耐久度恢复。问最少需要返回几次能打败所有怪物。

解题思路(贪心+模拟+暴力)：
贪心策略：每次都派能打败最多怪物的军队。
证明：若选择一个能击败x只怪物的军队，但是有能击败 $x+k$ 只怪物的军队。那么在后几次对派出的军队作考虑时，需要考虑区间编号为 $[x+1,x+k]∪[x+k+1,n]$ 的怪物。如果选择能击败x+k只怪物的军队，只需要考虑编号区间为 $[x+k+1,n]$ 的怪物。显然选择能击败 $x+k$ 只怪物的军队更优。
模拟注意：
①不管是计算能力值变化或者耐久度变化时都不要直接修改原数组的值，因为都是暂时性变化。
②不要做整数除法。题目中给出50%这个数字已经在暗示这一点。
图片说明
总时间复杂度 $O(n*m)$

L. special numbers

题目大意：
定义一种特殊数，该数字满足可以被小于3个数整除，现在询问 $[L,R]$ 内有多少个这样的数字？
解题思路：
可以对区间内每个数字进行暴力判断，复杂度 $O(nsqrt(n))$
也可以用线性筛得到区间内每个数字是否特殊，然后求一个前缀和就可以 $O(1)$ 处理每个查询