NOI2018解地的题目报告材料
5页1、Day1 :#1 :网络收费 (network)这道题完全不会,当时写了个搜索拿了40分把配对收费规则转化一下,对于任两个用户i,j,设它们的最近公共祖先(LCA)是p如果在p上navnb,则i,j中谁是A谁支付Fi,j的费用如果在p上na nb,则i,j中谁是B谁支付Fi,j的费用这样的转化让点对交费转移到单点交费,为dp提供了前提,且最后的总费用不变整个模型是一棵完全二叉树,设计树形dpdpi,j,k:在点i所管辖的所有用户中,有j个用户为A在i的每个祖先u上,如果nanb,则标0,否则标1,这个数列可以用二进制表示,用k记录在这种情况下的最少花费状态转移方程:其实就是将j个用户分配给i的左右子节点,并更改kdpi,j,k=mindpi.lt,u,k+%s,dpi.rt,j-u,k+%s+%s表示在数列上加入节点i的标号,i.lt、i.rt分别表示i的左右子节点边界:当i是叶节点时,可以根据 k算岀i与其它用户配对收费时所要交的费用,再根据 i的初始情况加上 AB的转化费用复杂度分析:设m=2 n粗略看来,空间复杂度是 0(m3),时间复杂度是 0(m4),对于本题的数据可以同时M
2、LE 和 TLE 了如果你看到这样复杂度就想别的方法了,那我只能同情你了,因为这只是很粗略的复杂度分析把根节点看做第0层,叶节点就是第n层,对于任意的第i层,A用户的个数最多只有 2n-i,而祖先结点只有i个,即k最大只有2i把dpi,j,k的后两维合并成一维,空间复杂度其实只有O(m 2)再看时间复杂度,对于第i层,有2个节点,每个节点的状态数是O(m)的,状态转移的复杂度是 0(2 n-i),所以每层的复杂度是O(m 2)总共有n层,所以状态转移的时间复杂度是O(m 2n)考虑边界,如果是朴素的计算费用,即枚举所有用户(O(m),再算出LCA(O(n),复杂度是O(mn)边界数高达O(m 2),这样计算边界的复杂度就是O(m 3n)!加一些预处理,提前算出所有点的LCA,复杂度是O(m2n)设dpxi,j表示第i个用户,在向上数第j个祖先节点处配对收费时所要交的费用,dpx可以在O(m 2n)的时间内计算岀来计算每个边界时可以根据k在O(n)时间内计算出配对费用,这样计算边界的复杂度降到O(m 2n)至此空间复杂度和时间复杂度都降到了可以承受的地步,在具体实现时,要用记忆化搜索和二
3、进制的位运算ps.说了一大堆,感觉不如直接看我的程序#2 :生日快乐 (happybirthday)这次NOI唯一一道做得比较满意的题目,算法和标准算法完全一样,得分90数据结构就是二叉树,为了使之平衡,这里用treap (当然也可以用splay,不过好像treap比splay快-些)为了记录每个元素排序后的位置,每个节点加num记录该节点为根的子树上的节点总数每次收到一个礼物,将它插入到treap中,根据num可以得到它的位置 pl然后根据男生或女生得到要吃掉的礼物的位置( pl 土L),根据num确定该节点s如果s不存在或者没有果冻,那么tell(-1)否则将s从treap中删除(先把s移到叶节点,然后删除),改变s的果冻数,然后重新插入到treap中注意在操作中更改num的值时间复杂度是O(nlogn)ps.重新编了一下,最后一个数据仍然TLE,大概我的treap写垃圾了 -b#3 :千年虫 (worm)用一个小时看出来是用 dp ,用一个小时优化方程,交上去以后才发现:方程写错了后来听人说这道题和 HNOI的某道题一样,抓狂,后悔没做省选题如果你语文够强,在分析完题目的描述以后
《NOI2018解地的题目报告材料》由会员枫**分享,可在线阅读,更多相关《NOI2018解地的题目报告材料》请在金锄头文库上搜索。
专八翻译练习
闯红灯作文400字精选
学校法制教育讲话稿
生产部年终工作总结(四篇).doc
精选大学迎新活动总结2篇范文
护理实习工作总结标准范本(2篇).doc
2022年高考生物大一轮复习 2.2生物安全与生物伦理考题演练 中图版选修3
关于烘烤副井井口风管动火作业安全措施
初中军训作文15篇
2023年吉林省延边州敦化市沙河沿镇河东村社区工作人员考试模拟题及答案
儿科工作计划范本
免疫和计划免疫优质课比赛教案
经典游戏主机模拟器推荐(精品)
医学基础知识总结
【名校精品】铜仁地区高中阶段教育招生统一考试数学卷(word有答案
小学生志愿精神教育实验方案
涂料项目核准申请
第二章有理数单元测验双向细目表
快递业务员快件处理模拟考试题和答案解析
2022年初中学习计划范文
2023-07-02 6页
2023-05-16 9页
2023-09-27 4页
2022-10-15 8页
2023-07-04 20页
2023-08-14 36页
2022-11-15 2页
2023-03-20 6页
2022-12-09 7页
2023-02-16 3页