solution day2题解.docx

全国信息学奥林匹克联赛（NOIP2011）提高组复赛模拟 Day2广东中山纪念中学全国青少年奥林匹克联赛(NOIP2011)复赛模拟提高组 Day2（请选手务必仔细阅读本页内容）一、题目概览中文题目名称高一学堂高二学堂高三楼英文题目名称atPokerIdentity可执行文件名at.exePoker.exeIdentity.exe输入文件名at.inPoker.inIdentity.in输出文件名at.outPoker.outIdentity.out每个测试点时限1秒1秒1秒测试点数目101010每个测试点分值101010比较方式全文比较全文比较全文比较题目类型传统传统传统二、提交源程序文件名对于Pascal语言at.paspoker.pasidentity.pas对于C语言at.cpoker.cidentity.c对于C+语言at.cpppoker.cppidentity.cpp三、编译命令（不包含任何优化开关）对于Pascal语言fpc at.pasfpc poker.pasfpc identity.pas对于C语言gcc at.c o at.exegcc poker.c o poker.exegcc identity.c o identity.exe对于C+语言g+ at.cpp o at.exeg+ poker.cpp o poker.exeg+ identity.cpp o identity.exe四、运行内存限制运行内存上限256M256M256M注意事项：1. 文件名（程序名和输入输出文件名）必须使用小写。2. C/C+中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3. 全国统一评测时采用的机器配置为：CPU P4 1.9GHz，内存1G，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。1.高一学堂 (at.pas/c/cpp)【原题解】lca，从叶子开始做，每次减或dfs序+树状数组。【暴力算法】考虑到部分数据k比较小，我们可以用fij表示i为根的子树中与i距离为j的结点的个数，可以树形DP求解。期望得分：60。【笔者补充】题目实际上是求每个结点深度差不超过K的儿子个数。由于涉及到方面有：深度、子树求和，大概思路可以想到是先预处理，然后按深度从大到小增删点，再查询某子树有多少个点。增删点的过程可以通过给点设权值来实现，1表示这个点存在，0表示不存在。那么查询某子树有多少个点就相当于是对某个子树中点的权值进行求和。与子树相关可用dfs序，修改和求和可以用树状数组实现。2.高二学堂 (Poker.pas/c/cpp)【题目简述】Ai*Xi=n | Ai1,4 & XiXi-1 & Xi=k & Ai,Xi,n,kN求解Xi的个数 mod 1,000,000,009。【算法1】输出n，不解释。期望得分：10。【算法2】利用上式对Ai和Xi进行搜索，同样不解释。期望得分：20。【算法3】把牌按数值大小编号，数值相同的编上4个不同号码。用fijk表示现在处理完前i张牌，一共用了j张，构成和为k的方案数。转移只要使用类似背包的方法即可。方程为：fijk=fijk+fi-1j-1k-w(i)。其中w(i)为i的牌面。为免MLE，可把第一维省去。期望得分：40。【算法4】这是Symbol提出来的方法。如果现在所有的牌面都大于1，假设有k张，那么把所有牌面都减小1，总和减少k之后，问题显然是等价的；而如果有牌面等于1，那么只要把这几张牌去掉，剩下的牌面就又都是大于1的了。所以可以使用fij表示用j张牌构成和为i的方案数，转移的时候分情况：1）所有牌面大于1，则fij+=fi-jj；2）有牌面等于1，那么我们可以枚举这些牌的数量t（4），则fij+=fi-jj-t。最后答案就是fn1k的最小值。时间复杂度为O(nk)。期望得分：60。【算法5】对算法4进行优化，考虑到k比较小，而转移只需要用到前k层的值。我们可以把连续k层的f压在一个矩阵内，并按一维编号，最多不超过k2个。然后我们每次转移1层的f，也就是如果现在矩阵记录的是f1k的值，那么转移一次，矩阵记录的就变成了f2k+1的值。然后填矩阵就是了。时间复杂度为O(logn*k6)，多组数据下，这个方法会由于常数大被卡掉。期望得分：80。【算法6】首先，假设牌面的集合为xi，集合中的每个元素对应一个ai（4），表示这个牌面用了多少张。那么问题就转化成了求ai*xi=n的正整数解个数，其中x1x2xm，aik。由于ai和k都比较小，我们可以暴力枚举所有情况，再去解方程。而现在约束还是比较多的，我们得想办法除去约束。设yi=xi-x(i-1)，换元后方程变为bi*yi=n的形式，其中bik。至此，我们成功把未知数单调这个棘手的约束解决了。接下来，我们发现bi比较小（10），那么可以把bi的lcm算出来，最多为2520。然后把bi*yi表示成pi*lcm+qi的形式，其中qi必须能被bi整除。现在方程转化为lcm*pi+qi=n。考虑到qi还是比较小的（3W），可以枚举qi的每个可能值，那么pi的方案数就可以用经典的隔板法来计算。而对于qi的计算，我们可以用背包来实现。背包的时候要注意各种细节，而且注意复杂度的把握。期望得分：100。3.高三楼(Identity.pas/c/cpp)【算法1】可能大家一开始想写暴力，暴力就是2（n*n）枚举每一个点是否放上硬币，但是不幸的是，判重是一个艰难的工作。n1，为正整数