NOI2018解地的题目报告材料

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上，如果na<nb，则标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)，对于本题的数据可以同时MLE 和 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)至此空间复杂度和时间复杂度都降到了可以承受的地步，在具体实现时，要用记忆化搜索和二进制的位运算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的某道题一样，抓狂，后悔没做省选题如果你语文够强，在分析完题目的描述以后应该可以得到这样的结论：以一边为例，则千年虫的外形是一个类似梳子的样子(事实上，HNOI那道题好像就是叫梳子)，就是一段高，一段低而我们要做的，就是添加尽量少的方块，使得外形满足上诉的样子，这样很容易想到dp设dpi,j,s表示前i行，第i行的状态是s (s=0，第i行处于凹的一段；s=1，第i行处于凸的一段)，且第 i行的最终高度是j的状态下最小添加的方块数dpi,j,s=mindpi-1,j,s,dpi-1,k,1-s(s=1,k<j s=O,k>j)+(j-hi)，其中 hi是第 i 行的原始高度时间复杂度是0(n3)的，根据状态转移方程可以把复杂度降到0(n2)但是对于本题的极限数据，这样的复杂度仍然不能令人满意bamboo的BT方法：其实就是减少需要计算的状态量，我将其理解为建立在贪心基础上的dp对于第i行，设它的初始高度为ai，最终高度为bi能够证明的是：bi的取值范围只能是aj,aj+2(|j-i| <2)证明过程非常繁琐，大体思想就是分情况讨论，对于每种情况，或者找到确定的j,或者说明不是最优解(证明过程请参加讲题大会时的ppt，因为情况太多，我只是大概的证明了处在凹的一段)这样对于第i行只需要计算常数个最终长度，而对于每个状态的决策也只有常数个，所以复杂度是0(n)下载：worm.pptDay2 :#1 :最大获利 (profit)NOI历史上第一道网络流的题目（为什么偏偏让我赶上了- -b ）这道题和算法艺术317页那道题几乎一样，郁闷的发现自己看过，更郁闷的是NOI的时候忘了建立模型，将每个用户和中转站看作点，另外添加源点s,汇点t添加下列边： s到中转站i，容量为Pi 用户i到中转站Ai和Bi，容量为a 用户i到t的边，容量为Ci考虑这个模型的割割边不可能是中的边，这保证了解的合法性属于的割边表示付岀的代价属于的割边表示损失的利益显然割的量越小越好，这样这道题就转换成一个最小割的问题根据最大流最小割定理，设sum=习Ci，我们只要求出该网络的最大流maxflow，贝U sum-maxflow 就是最大获利至此我们已经分析出了这道题的模型，但是，让我们看一下9、10两个BT数据吧，你会发现，即使用目前最快的HLPP也会严重 TLE可能你也听说过要用贪心来做一个初始流，然后在这个基础上求最大流但其实不是随便贪都可以的，事实上，对于最后两个点的岀解时间，在很大程度上取决于贪心的初始解与最优解的逼近程度这样的话就需要一个比较好的贪心，这里介绍一下ZhY大牛的贪心砍掉s和t，将模型缩减为一个二分图，并设cpi=第i个点到s或t的那条边的容量，degreei= ECpj（j与i相邻）每次找到一个degree最小的点i，按照degree递增的顺序处理每个与它相邻的点j，在连接i,j的边上进行增广具体实现时需要用heap大概思想就是这样，至于为什么这样我也不太清楚（看的 ZhY的C+的程序，按照这个思想编的，可是 贪心的结果与ZhY的还是有一些差距）接下来，在求得初始流以后该如何求最大流呢？HLPP仍然严重TLE （汗）BFS求最短增广路，最大数据用时6.xx sDFS多路增广（具体实现请参见我的程序），仅仅是能卡着点过（关闭其它耗内存的东西2.xx s，开一个wmplayer 就 TLE）#2 :聪明的导游 （guide）这道题向GHY大牛请教了一种超级 BT的方法首先看最后两个数据，不难发现是一棵树对于一棵树，最优解就是这棵树上的最长路径 对这个问题存在最优方法：从任一点 e岀发，找到e的最远点s，在从s岀发，找到s的最远点t，则s到 t的路径上所有点就是所求证明略过（可以参见信息学奥林匹克竞赛-国际国内分类试题精解（上册）78页）现在的问题是，对于一个任意图（数据1-8 ），如何求得最优解如果可以去掉一些边，使任意图变成一棵树，则可以用上诉方法来求最优解一个大致的算法产生了：在原图的基础上随机生成一棵树，然后求这棵树上的最优解，取其中最优的输岀 考虑以下两种树:显然第一种树的最优解优于第二种树在用DFS生成树的过程中加入一些贪心因素，优先扩展度小的节点在此基础上加入一些随机因素：随机确定根节点对于度数相同的节点，随机交换顺序注意这里节点的度数应不包括后向边，这就要求在DFS的过程中动态更新节点的度数ps.用这种方法应该可以得满分，但我的程序只拿到99分（第2个点9分）#3 :神奇口袋 （bag）这是第二试最简单的一道题，也是这次NOI最简单的一道考察的只是很简单的数学知识 +高精度乘法，可惜看错题了，哭简单一些的描述就是每次随机选择一种颜色的球，将数量+d整个大框架就是乘法原理，对于每次取球，如果没有在Xi中，那么这次操作称为“自由取球”，否则将 颜色y i的球的数量a/此时球的总数 作为乘数乘到结果中，并将颜色yi的球的数量+d，称作“定向取球”可以证明，自由取球对任意球被取到的几率Pi没有影响证明很简单，就不说了这样就可以忽略掉所有的自由取球操作，即每一步都是定向取球剩下的就只是高精度乘法了对于最后分数化简的问题，因为分子分母最多只有20000，所以只要建立一个 20000以内的素数表连高精度除法都不需要，只要先将分子分母都化简掉再高精度乘起来输岀就行了