新生练习赛(2013.11.9) 解题报告
- 格式：docx
- 大小：69.69 KB
- 文档页数：6
A题
拿k=12举例，若y<=12,那么不存在x,使1/x+1/y=1/k,若y>2*k,那么将出现重复的情况。
所以从k+1~2*k依次枚举y的值；再求x的值，通分之后求得x=(y*k)/(y-k)，判断(y*k)%(k-y)是否等于0, 若等于0那么x=(y*k)/(y-k),输出一个答案。
此题需要注意，每两组测试数据之间有一个空行，不是每组测试数据之后有一个空行。
B题
现将数组排序，在遍历查找
C题
当y=0时有两个解x=0.0000，-0.6058,否则x有两个解一个为正一个为负（有图为证）。
分别二分L=0,R=y和L=-y,R=0，找出两个答案。
D题
画图枚举
1 a
2 b c
3 a c a b
4 b c a b b c a c
5 a c a b b c a c a c a b b c a b
1 b
2 a c
3 b c a b
4 a c a b b c a c
5 b c a b b c a c a c a b b c a b
1 c
2 a b
3 b c a c
4 a c a b b c a b
5 b c a b b c a c a c a b b c a c
当两个城市相同，方案数是6，不相同，方案数是5.
此外，scanf(“%c %c”,&x,&y); 将会吸收上一个输入之后的换行，
可以用getchar()或者定义char x[2],y[2]; scanf(“%s %s”,x,y)来解决。
E题
从1~N依次枚举a1,a2,a3.如果题中条件并且a1+a2+a3>max,那么就让max=a1+a2+a3，max为输出结果。
F题
此题如果没有思路，就先把图画出来，走1步，2步，3步，4步.....然后看f[n]跟f[n-1]有没有关系或者f[n]跟f[n-1],f[n-2]有没有关系....这类递推题实在没思路，就按笨方法一点一点模拟
以下是这道题的推导原理
当N=1时
当N=2时
当N=3时
由此，我们不难看出，对于任何一个起点，最多可以走出3种走法，但最少必须走出2种走法。
那么我们要求出f(n)，实际上转换为如果我们能够得到上一步即f（n-1）有多少个终点是有3种走法的，有多少个点有2种走法的，那么问题就解决了。
a.上一步，即f（n-1）有多少个终点是有3种走法的。
对于N=3时，f(n-1)=f(2), 有3个点A、B、C可以走出3种不同走法的，这3个点是怎么得到的呢？它的存在与N值有没有必然的联系？如果我们能找到它与N之间的关系，问题也就解决了。
有了这样的思路以后，我们不难找到这样的规律：如果f（n-2）存在，即上上步存在，那么从上上步出发的线路里面必然会有一条向上走的线路，而这条向上走的线路在到达f（n-1）之后，向f（n）出发时也必然有左、上、右这三种走法，那么我们就得出了这样的结论：当f（n-2）存在时，f（n-2）的值实际上就等价于f（n-1）有多少个终点是有3种走法。
b. f（n-1）有多少个终点是有2种走法的
对于N=3时，有4个点D、E、F、G可以走出2种不同走法的，这4个点又是怎么得到的呢？它与N值有什么联系呢？实际上我们在解决了上一个问题的时候，这个问题就变得相当容易了，f（n-1）减掉刚才有3种走法的点，剩下的点不就是只有2种走法了吗？即f（n-1）-f（n-2）。
c. 得出f（n）的一般关系式
f(n)=3*f(n-2)+2*(f(n-1)-f(n-2) ) (n>=3)
化简：
f(n)=2*f(n-1)+f(n-2) (n>=3)
有一点需要补充的就是，任何递推题，都会有临界条件。
当N=1时，f(n)=3;,当N=2时，f(n)=7,这些都可以看成是临界条件。
只有当N>=3时，即上上步存在的情况下，就可以得出f(n)的一般通式：f(n)=2*f(n-1)+f(n-2)。
