国家集训队作业出题互测解题报告apex

1、x解题福州一中April 30, 2012Contents1题意简述22命题思路23考查点24问题分析25数据生成方法46选手得分统计47后记5Appendi7x完整题面A7嬱1题意简述Pn i=1定义数列x1 嬽 嬱, x2k 嬽下嬳种询问。嬽 嬨嬱嬩k+1xk嬨k 嬱嬩，设Sn 嬽xi。有以xk, x2k1嬱嬮 求xn；嬲嬮 判断Sn的符号；嬳嬮 求Sn。2命题思路本题是本人在做一道数学题时想出的。一开始打算利用程序来找规律，后来灵机一动，弄出了一个重要的等式。虽然那道数学题没有完整解出来，不过本人想到可以利用这个等式编一道有意思的题目。这嬳问设计得很有层次性，即使某一问不会做，也很有可能

2、做出其他的询问。而这嬳问又具有联系。3考查点本题主要了选手代数方面的能力，以及分析问题，寻找规律的能力。4问题分析这类问题通常有两种思路。一种是预处理出所有，然后碰到询问直接回答；另一种是对每个询问单独处理。如果采用第一种思路，可以考虑预处理出x1, x2, . . . , xn，以及S1, S2, . . . , Sn，然后就可以以O嬨嬱嬩的时间复杂度回答每个询问。预处理出x1, x2, . . . , xn，可以直接利用数列定义式来完成，时间复杂度是O嬨n嬩。而预处理出前n项和Sn的时间复杂度也是O嬨n嬩的。这个算法的期望得分是嬵嬰分。由于预处理出n以内的所有的时间复杂度下限就是嬊嬨n嬩，

3、这种思路在n很大时无法胜任。因而考虑第二种思路。嬲第一问十分简单。我们直接利用题目所给的数列定义式，就可以求出xn的值了。这一问的时间复杂度是O嬨孬孯孧 n嬩。再看第二问，容易发现，如果解决了第三问，那么第二问也解决了。因而先尝试解决第三问。考虑S4n嬨n 嬱嬩。根据x2k 嬽 xk, x2k1 嬽 嬨嬱嬩k+1xk嬨k 嬱嬩，4nXS4n嬽xii=12n2nXX嬽x嬫x2i12ii=1i=12n2nXXi+1嬽嬨嬱嬩x xiii=1i=12nXi+1嬽嬨嬨嬱嬩x x 嬩iii=1nX嬽嬲x2ii=1nX嬽 嬲xii=1嬽 嬲Sn嬨嬱嬩由式嬨嬱嬩， 立即得到一个快速求Sn的做法： 若嬴 - n

4、， 那么Sn嬽 Sn1 嬫 xn； 否则，Sn 嬽 嬲Sn。这个算法的时间复杂度由下式给出：T 嬨n嬩 嬽 T 嬨n/嬴嬩 嬫 O嬨孬孯孧 n嬩，解得T 嬨n嬩 嬽 O嬨孬孯孧2 n嬩。注意到这个算法有系数嬳，即每次除以嬴，最多要嬳轮。我们还可以对此进行一些优化。注意到2n+2x4n+1 嬫 x4n+2 嬽 嬨嬱嬩x2n+1 x2n+1 嬽 嬰嬨嬲嬩我们可以得到S4n+2 嬽 S4n 嬫 x4n+1 嬫 x4n+2 嬽 S4n嬨嬳嬩这样，我们在每一次除以嬴的时候最多只要算嬱次xn，就消除了系数嬳。有了第三问，第二问显然也可以做到O嬨孬孯孧2 n嬩。不过我们有更优的算法。首先，可以用数学归纳法证

5、明，Sn 嬰。因而，我们只需要找出哪些位置是嬰。嬳容易看出，S2n1 6嬽 嬰。这是因为， 数列xn只含数字嬱和嬭嬱。由于Si+1 嬽 Si 嬫 xi+1，因此Si+1与Si奇偶性不同。而S1 嬽 嬱为奇数，S2n1与S1奇偶性相同，因而也为奇数。而嬰是偶数，故而S2n1 6嬽 嬰。根据式嬨嬱嬩嬨嬳嬩， 以及S2 嬽 嬰, S4 6嬽 嬰， 可以看出Sn 嬽 嬰当且仅当n的嬴进制表示仅含嬰和嬲。这样第二问就做到了O嬨孬孯孧 n嬩。5数据生成方法本题的数据生成方法十分容易，只需要依据数据范围，直接随机生成即可。不过对于询问嬲，仍然遇到了一点问题。注意到在上述分析中提到了询问嬲，回答是嬰的条件。在

6、嬱至嬱嬰18内，回答是嬰的数的个数大概只有嬲29。当在嬱至嬱嬰18范围内随机时，随机到嬰的概率小于嬱嬰9。即使随机嬱嬰5次，存在一个回答是嬰的数的概率仍小于嬰嬮嬰嬱嬥。事实上，对于大的随机数据，所有询问嬲的回答都是正数。因为发生了这种情况，本人对大数据询问嬲的生成进行了一些改动，手造了一些回答是嬰的情况，混合进去，从而避免了全部是正数导致的数据的不全面。6选手得分统计本题对国家队候选队员进行了测试，得分统计如表嬨嬱嬩所示。孔孡孢孬孥 嬱嬺 得分统计本题的平均分大约为嬸嬲嬮嬷分。嬴分数人数嬲嬰嬱嬶嬰嬱嬶嬵嬲嬱嬰嬰嬷7后记本题是一个数列问题。正如来自南京师大附中的同学所言，数列问题往往可以用孯孥孩

7、孳来解决。这里，孯孥孩孳，可参考孛嬱孝，指的是一个整数数列，收录了数以万计的数列，包含了丰富的数列的性质。如果本题可以轻易地用搜索工具搜索到性质，甚至通项，那么本题就显得十分没有意义了。有鉴于此，本人对此数列进行搜索，幸运的是，这个根本没有这个数列。利用知名的搜索引擎进行搜索，也没有发现任何有关这个数列的信息。因而，将此题命制出来十分妥当，没有什么可以钻空子的地方。本题进试后，收到了很好的效果。绝大多数选手都拿到了十分理想的分数，而选手们采取的方法也是花样繁复，争奇斗艳。来自杭州外国语学校的同学，将本文中提到的第三问解法优化至O嬨孬孯孧 n嬩。事实上，只要对中途xn的询问实施时间复杂度。化即可

8、。下面，从另一个角度说明这样做的每一步，同时计算嬲个量：Sn, xn+1。由xn+1可以推出x2n+1和x2n+2，由此又可以推出x4n+1, x4n+2, x4n+3, x4n+4。利用以上四个量， 就可以轻易地由Sn推出S4n嬬S4n+3了。故，求Sn, xn+1，可以化归为求Sbn/4c, xbn/4c+1。这样T 嬨n嬩 嬽S4n+1嬬 S4n+2嬬T 嬨n/嬴嬩嬫 O嬨嬱嬩，因此T 嬨n嬩 嬽 O嬨孬孯孧 n嬩。嬵Refereneger SequenTM(OEISTM)孛孅孂嬯孏孌孝嬮孛嬱孝The On-LineEncyclopediaofhttp:/oeis./嬮嬶Appendix

9、完整题面A孭孥 孌孩孭孩孴嬺 嬱孳嬬 孍孥孭孯孲孹 孌孩孭孩孴嬺 嬱嬲嬸孍孂定义数列x1 嬽 嬱, x2k 嬽 xk, x2k1 嬽 嬨嬱嬩k+1xk嬨k 嬱嬩嬮 存在如下三种类型询问嬮嬱嬮 求xn嬮嬲嬮 判断x1 嬫 x2 嬫 嬫 xn的符号嬮嬳嬮 求x1 嬫 x2 嬫 嬫 xn嬮Task:xInput: stdin第一行包含一个整数q嬬 代表询问的数量嬮 接下来q行嬬 每行两个数c, n嬬 即询问的类型，以及n的值。Output: stdout对于每个询问嬬 输出一行嬬 即对应的负数嬬 输出孜嬭嬢嬬 如果是嬰嬬 输出孜嬰嬢嬮嬮 对于询问嬲嬬 如果是正数嬬 输出孜嬫嬢嬬 如果是Constras有嬱嬰嬥的数据嬬 仅含询问嬱嬮有嬱嬰嬥的数据嬬 仅含询问嬲嬮有嬱嬰嬥的数据嬬