solution day2题解

《solution day2题解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国信息学奥林匹克联赛（NOIP2011）提高组复赛模拟Day2广东中山纪念中学全国青少年奥林匹克联赛(NOIP2011)复赛模拟提高组Day2（请选手务必仔细阅读本页内容）一、题目概览中文题目名称高一学堂高二学堂高三楼英文题目名称atPokerIdentity可执行文件名at.exePoker.exeIdentity.exe输入文件名at.inPoker.inIdentity.in输出文件名at.outPoker.outIdentity.out每个测试点时限1秒1秒1秒测试点数目101010每个测试点分值101010比较方式全文比较全

2、文比较全文比较题目类型传统传统传统二、提交源程序文件名对于Pascal语言at.paspoker.pasidentity.pas对于C语言at.cpoker.cidentity.c对于C++语言at.cpppoker.cppidentity.cpp三、编译命令（不包含任何优化开关）对于Pascal语言fpcat.pasfpcpoker.pasfpcidentity.pas对于C语言gccat.c–oat.exegccpoker.c–opoker.exegccidentity.c–oidentity.exe对于C++语言g++at.cpp

3、–oat.exeg++poker.cpp–opoker.exeg++identity.cpp–oidentity.exe四、运行内存限制运行内存上限256M256M256M注意事项：1.文件名（程序名和输入输出文件名）必须使用小写。2.C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3.全国统一评测时采用的机器配置为：CPUP41.9GHz，内存1G，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。全国信息学奥林匹克联赛（NOIP2011）提高组复赛模拟Day2广东中山纪念中学1.高一学堂

4、(at.pas/c/cpp)【原题解】lca，从叶子开始做，每次减~或dfs序+树状数组。【暴力算法】考虑到部分数据k比较小，我们可以用f[i][j]表示i为根的子树中与i距离为j的结点的个数，可以树形DP求解。期望得分：60。【笔者补充】题目实际上是求每个结点深度差不超过K的儿子个数。由于涉及到方面有：深度、子树求和，大概思路可以想到是先预处理，然后按深度从大到小增删点，再查询某子树有多少个点。增删点的过程可以通过给点设权值来实现，1表示这个点存在，0表示不存在。那么查询某子树有多少个点就相当于是对某个子树中点的权值进行求和。与子树相

5、关可用dfs序，修改和求和可以用树状数组实现。全国信息学奥林匹克联赛（NOIP2011）提高组复赛模拟Day2广东中山纪念中学2.高二学堂(Poker.pas/c/cpp)【题目简述】ΣAi*Xi=n

6、Ai∈[1,4]&Xi>Xi-1&ΣXi=k&Ai,Xi,n,k∈N求解{Xi}的个数mod1,000,000,009。【算法1】输出n，不解释。。。期望得分：10。【算法2】利用上式对Ai和Xi进行搜索，同样不解释。。。期望得分：20。【算法3】把牌按数值大小编号，数值相同的编上4个不同号码。用f[i][j][k]表示现在处理完前i张牌

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

8、，则f[i][j]+=f[i-j][j]；2）有牌面等于1，那么我们可以枚举这些牌的数量t（≤4），则f[i][j]+=f[i-j][j-t]。最后答案就是f[n][1~k]的最小值。时间复杂度为O(nk)。期望得分：60。【算法5】对算法4进行优化，考虑到k比较小，而转移只需要用到前k层的值。我们可以把连续k层的f压在一个矩阵内，并按一维编号，最多不超过k^2个。然后我们每次转移1层的f，也就是如果现在矩阵记录的是f[1~k][]的值，那么转移一次，矩阵记录的就变成了f[2~k+1][]的值。然后填矩阵就是了。时间复杂度为O(logn

9、*k^6)，多组数据下，这个方法会由于常数大被卡掉。期望得分：80。全国信息学奥林匹克联赛（NOIP2011）提高组复赛模拟Day2广东中山纪念中学【算法6】首先，假设牌面的集合为{xi}，集合中的每个元素