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