四川省选day1

《四川省选day1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOI2009四川省选拔赛试题与解题报告第一试试题与解题报告第一题：生日快乐【问题描述】Windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为X和Y的矩形蛋糕。现在包括Windy，一共有N个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。Windy主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成N块蛋糕，Windy必须切N-1次。为了使得每块蛋糕看起来漂亮，我们要求N块蛋糕的长边与短边的比值的最大值最小。你能帮助Windy求出这个比值么？【输入格式】输入文件cake.in包含三个整

2、数：X，Y，N。【输出格式】输出文件cake.out包含一个浮点数，保留6位小数。【输入样例一】555【输出样例一】1.800000【数据规模和约定】100%的数据，满足1≤X,Y≤10000；1≤N≤10。第二题：游戏【问题描述】windy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，…，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，…，N。如：123456对应的关系为：1->22->

3、33->14->55->46->6windy的操作如下：123456231546312456123546231456312546123456这时，我们就有若干排1到N的排列，上例中有7排。现在Windy想知道，对于所有可能的对应关系，有多少种可能的排数？【输入格式】输入文件game.in包含一个整数，N。【输出格式】输出文件game.out包含一个整数，可能的排数。【输入样例一】3【输出样例一】3【输入样例二】10【输出样例二】16【数据规模和约定】30%的数据，满足1≤N≤10。100%的数据，满足1≤N≤1000。第三题：windy数【

4、问题描述】Windy定义了一种Windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为Windy数。Windy想知道，在A和B之间，包括A和B，总共有多少个Windy数？【输入格式】输入文件Windy.in包含两个整数：A，B。【输出格式】输出文件Windy.out包含一个整数。【输入样例一】110【输出样例一】9【输入样例二】2550【输出样例二】20【数据规模和约定】20%的数据，满足1≤A≤B≤1000000。100%的数据，满足1≤A≤B≤2000000000。【解题报告】第一题:生日快乐仔细分析题目后发现，最终的目标是要把

5、蛋糕切成n块面积一样大的矩形。因此在切的过程中将当前的这一块切成的两块的面积都一定是最终每一块面积的整数倍。这样对于第一刀来说就有2（n-1）种切法，n-1种是横着切的，另外n-1种是竖着切的。对于一块面积为最终矩形k倍的蛋糕来说就有2（k-1）种切法。实际上这些切法中有一半是相同的。比如横着按1:8切和按8:1切没有区别，因此可以只枚举剩的较少的那一块。因为数据范围较小，直接搜索即可。将一大块枚举分割方式之后再分别处理两小块，类似于DP的处理方式。但因为状态是实数，所以不能方便地实现记忆化。参考程序：programcake;varf:ar

6、ray[1..2520,1..2520]ofdouble;done:array[1..2520,1..2520]ofboolean;n,chang,kuan:longint;functionmax(x,y:double):double;beginifx>ythenmax:=xelsemax:=y;end;functionsolve(much,c,k:longint):double;vari,dan:longint;temp:double;beginifdone[c,k]thenexit(f[c,k]);ifmuch=1thenbeginso

7、lve:=(c/2520*chang)/(k/2520*kuan);ifsolve<1thensolve:=1/solve;endelsebeginsolve:=1e30;dan:=cdivmuch;fori:=1tomuch-1dobegintemp:=max(solve(i,dan*i,k),solve(much-i,dan*(much-i),k));iftemp

8、,solve(much-i,c,dan*(much-i)));iftemp