中山第二试解题报告

1、青少年联赛(NOIP2011)复赛模拟提高组 Day2（请选手务必仔细阅读本页内容）一、题目概览二、提交源程序文件名三、编译命令（不包含任何优化开关）四、运行内存限制注意事项：1. 文件名（程序名和输入输出文件名）必须使用小写。2. C/C+中函数 main()的返回值类型必须是，程序正常结束时的返回值必须是 0。3.准。评测时采用的机器配置为：CPU P4 1.9GHz，内存 1G，上述时限以此配置为在自测时可根据具体配置调整时限。运行内存上限256M256M256M对于 Pascal 语言fpc at.pasfpc pokasfpc identity.pas对于 C 语言gcc at.c

2、o at.exegoker.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对于 Pascal 语言at.paspokasidentity.pas对于 C 语言at.cpoker.cidentity.c对于 C+语言at.cpppoker.cpentity.cpp中文题目名称高一学堂高二学堂高三楼英文题目名称atPokerIdentity可执行文件名at.exePoker.exeIdentity.exe

3、输入文件名at.inPoker.inIdentity.in输出文件名at.outPoker.outIdentity.out每个测试点时限1 秒1 秒1 秒测试点数目101010每个测试点分值101010比较方式全文比较全文比较全文比较题目类型传统传统传统1.高一学堂(at.pas/p)【原题解】lca，从叶子开始做，每次减或 dfs 序+树状数组。【算法】考虑到部分数据k 比较小，可以用 fi j表示 i 为根的中与 i 距离为j 的结点的个数，可以树形DP 求解。期望得分：60。【笔者补充】题目实际上是求每个结点深度差不超过K 的儿子个数。由于涉及到方面有：深度、求和，大概思路可以想到是先预

4、处理，然后按深度从大到小增删点，再查询某有多少个点。增删点的过程可以通过给点设权值来实现，1 表示这个点存在，0 表示不存在。那么查询某有多少个点就相当于是对某个中点的权值进行求和。与相关可用dfs 序，修改和求和可以用树状数组实现。2.高二学堂(Pokas/p)【题目简述】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 个不同号码。用f

5、i jk表示现在处理完前 i 转移只要使用类似背包的方法即可。，一共用了 j 张，和为k 的方案数。方程为：fi jk=fi jk+fi-1 j-1k-w(i)。其中w(i)为 i 的牌面。为免 MLE，可把第一维省去。期望得分：40。【算法 4】这是Symbol 提出来的方法。如果现在所有的牌面都大于 1，假设有 k张，那么把所有牌面都减小 1，总和减少 k之后，问题显然是等价的；而如果有牌面等于 1，那么只要把这几去掉，剩下的牌面就又都是大于 1 的了。所以可以使用 fi j表示用 j和为 i 的方案数，转移的时候分情况：1）所有牌面大于 1，则 fi j+=fi-j j；2）有牌面等于

6、1，那么这些牌的数量t（4），则 fi j+=fi-j j-t。可以枚举最后就是fn1k的最小值。时间复杂度为O(nk)。期望得分：60。【算法 5】对算法 4 进行优化，考虑到k 比较小，而转移只需要用到前k 层的值。可以把连续k 层的f 压在一个矩阵内，并按一维，最多不超过 k2的是 f1k的值，个。然后每次转移 1 层的 f，也就是如果现在矩阵那么转移一次，矩阵的就变成了f2k+1的值。然后填矩阵就是了。时间复杂度为O(logn*k6)，多组数据下，这个方期望得分：80。由于常数大被卡掉。【算法 6】首先，假设牌面的集合为xi，集合中的每个元素对应一个 ai（4），表示这个牌面用了多少张

7、。那么问题就转化成了求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/p)【算法 1】可能大家一开始想写就是 2（n*n）枚举每一个点是否放上硬币，但是不幸的是，判重是一个艰难的工作。n1，为正整数。其中 Ai 的意义是