已-中第二试解题报告_第1页
已-中第二试解题报告_第2页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

提高组Day2（请选手务必仔细阅读本页内容名名1.511值言C言言fpcfpcfpcCgccat.c–o gccidentity.c–og++at.cppog++poker.cpp–og++identity.cppC/C++main()int0评测时采用的机器配置为：CPUP41.9GHz，内存1G，上述时限以此配置为高一学【原题解lca，从叶子开始做，每次减~dfs序+【算法考虑到部分数据k比较小，可以用f[i][j]表示i为根的中与i距离为j的结DP求解。期望得分：60【笔者补充K由于涉及到方面有：深度、求和，大概思路可以想到是先预处理，然后按深度从大到小增删点，再查询某有多少个点。增删点的过程可以通过给点设权值来实现，1表示这个点存在，0表示不存在。那么查询某有多少个点就相当于是对某个中点的权值进行求和。与相关可用dfs序，修改和求和可以用树状数组实现【题目简述

高二学ΣAi*Xi=n|Ai∈[1,4]&Xi>Xi-1&ΣXi=k&Ai,Xi,n,k∈N求解{Xi}的个数mod1,000,000,009。【算1【算2【算3把牌按数值大小，数值相同的编上4个不同号码w(i)i【4Symbol如果现在所有的牌面都大于1，假设有k’张，那么把所有牌面都减小1k1，那么只要把1f[i][j]ji分情况：1）1f[i][j]+=f[i-j][j]；2）1，那么可以枚举这些牌的数量t（≤4，则f[i][j]+=f[i-j][j-t]。O(nk)。期望得分：60【算5对算法4进行优化，考虑到k比较小，而转移只需要用到前k层的值。可以把连续k层的f压在一个矩阵内，并按一维，最多不超过个。然后每次转移1层的f，也就是如果现在矩阵记录的是f[1~k][]的值，那么转移一次，矩阵记录的就变成了f[2~k+1][时间复杂度为O(logn*k^6)，多组数据下，这个方由于常数大被卡掉期望得分：80。【算6ai（≤4表示这个牌面用了多少张。那么问题就转化成了求Σai*xi=n的正整数解个数，其中x1<x2<…<xm，Σai≤k。由于ai和k都比较小，可以枚举所有情况，再去解方程。而现在约束还是比较多的，得想办法除去约束。yi=xi-x(i-1)，Σbi*yi=nbi≤k。至此，成功把未知数单调这个棘手的约束解决了。接下来，发现bi比较小（≤10，那么可以把bi的lcm算出来，最2520bi*yipi*lcm+qiqibilcm*Σpi+Σqi=n考虑到Σqi还是比较小的（≤3W，可以枚举Σqi的每个可能值，那么pi的方案数就可以用经典的隔板法来计算。而对于Σqi的计算，可以用期望得分：100【算1

高三可能大家一开始想写，就是2^（n*n）枚举每一个点是否放上硬币，但是不幸的是，判重是一个艰难的工作。n<=5的时候，可能很多人会果n=5的时候，就得到分，所以，我只能把分卡到10%。【算2yyn*n的矩阵，22k个点形成AA1+A2+..

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论