解题报告一中_第1页
解题报告一中_第2页
全文预览已结束

下载本文档

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

文档简介

WinniethePooh解题报告中山一中齐小熊很喜欢蜂蜜。但是大千世界上有很多种蜂蜜。吃一罐蜂蜜需要应付下面一些事件：一、发现新蜂蜜！姑且暂时给它一个。所有种类蜂蜜按出现时间依次1，2，…二、说，说他吃A1罐第1类的蜂蜜，吃A2罐第二类的蜂蜜，…，吃Ak罐第k类的蜂蜜（假设现在知道的蜂蜜有k种吧），要从星期S到星期E…三、计划吃A1罐第1类的蜂蜜，吃A2罐第二类的蜂蜜，…，吃Ak罐k类的蜂蜜，现在是星期SAddLearnA0A1A2AkSE，EatA0A1A2AkS对每个Eat询问输出一行，表示要吃到星期几。如果不确定则输出know，如果前面说的话已经了则输出Alreadycrazy输输9Don'tAlready52SaturdayEat3094FridayEat063210SaturdayEat411TimusOnlineJudge,Problem1561,Winniethei类蜂蜜要xi天，对每个LearnA1x1+A2x2+…+Akxk=B(mod不同于一般方程组的是，本题中所考虑的所有方程组均是在模7意义上的。1)2)一个方3)对方程操作，直接完求一个多项式的值时，首先枚举它的值，接着将该多项式连同枚举的值作为一个方程加入，尝试高斯消元，如果存在解则表示当前枚举的值合法。最后，通过解的数目回答问题。但是该实现方法的第三个操作的时间复杂度是O(N3)事实上，每一次都进行高斯消元，其中的浪费是相当大的。设当前有A11x1+A12x2+…+A1kxk=B1(mod7)A21x1+A22x2+…+A2kxk=B2(mod7)A31x1+A32x2+…+A3kxk=B3(mod…Am1x1+Am2x2+…+Amkxk=Bm(mod若当前方程组已经是经过高斯消元的，即对j<i有Aij=0，那么新一个方程，要想当前方程组的性质，需要对新的方程进行消元。该步骤可以在O(N2)0系数项，那么如果新方程的值B0AlreadyCrazy，不然该方程是没有意义的，不管他。否则的话，将该方程加到这样，每一次 操作可在O(N2)的时间内完成断可行性。但是这样的代价太高，试图优化冗余运算。A1x1+A2x2+…+Akxk=p(mod7)0系数项是iAiixi+…+Aikxk=(A1*Aii)x1+(A2*Aii)x2+…+(Ai*Aii-Aii*Ai)xi+…+(Ak*Aii-Aik*Ai)xk=p*Aii-xp值无关，而常数项（等式右边）最终结果必能表示为ap+b的形式。在判断可行性时，可以姑且设出初始的p值，ap+b的p，如果存在多个则询问有多解，如果存在一个则有唯该操作同样经历了对一个方程的消元过程，时间复杂度仍然是O(N2)。消元问题至此已经基本解决。虽然算法的时间复杂度为O(N3)，但可以分析比起一次询问，一次方程的操作会使程序整体运行时间更长，那不妨设有t次未知数操作，1000-t次方程的操作。则总运算

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

温馨提示

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

最新文档

评论

0/150

提交评论