首页 > NOIP2015解题报告 By ljt12138

NOIP2015解题报告 By ljt12138

Day1t1 幻方

练过的一道题,简单模拟,用二维数组存储,ij两个游标记录横纵坐标,利用题目条件改变坐标直到填入n个数即可。复杂度O(n^2) AC

Day2t2 图的最小环

首先抽象出图论模型。每个人对应点,传输对应边。因为自己的生日只可能出自于自己,所以结束对应最小环长度。

最小环可以用tarjan算法O(nlogn)求得。但实际上这道题目是有O(n)算法的。我们考虑使用dfs搜索找环并加入一个剪枝。剪枝的关键在于: 每个联通分量内至多有一个环。这个可以用反证法证明。这样,我们对于每一个计算过的点记录,下次搜到不必重复计算。因为不可能出现没有找过的环。

存储结构使用数组即可,因为每个点的出度都为1。注意不能从没有入度的点开始搜,因为有的联通分量可能整体是一个环。

(我剪枝没在dfs里做被卡一个点)

Day1t3

条件过于繁杂,暴力过30

Day2t1 据说是二分

去除石头本质上是合并了两个长度,从而让最短的边最长。没有想到好办法,只用heap+贪心混了20分。

Day2t2 搜索

爆零不说了

Day2t3

这种题首先考虑过部分分。首先m=1可以贪心,稳拿20分。剩下部分仍然考虑贪心。因为有很多链状结构,最优值很可能就是最大值。故去除最大边。最后共得30分。

总结

自我感觉木有砸,基本是最好水平的表现了。同时总结一些经验

1 不要拗在一个题上

2 不要因为暴力分少就懒得打(我想会做Day2t3 20分而懒得写的选手大有人在)。事实证明,除了少数神犇,大多数人的差距都在暴力得分上。

3 重视玄学!!例如string玄学,dev迷之自动加载头文件等等。

4 小心无脑错误 比如没有删调试语句,输出xxx.ans等等。

5 努力骗部分分 事实证明 出题人是懒的,数据是水的。

转载于:https://www.cnblogs.com/ljt12138/p/6684398.html

更多相关:

  • 原文出处: 韩昊    1 2 3 4 5 6 7 8 9 10 作 者:韩 昊 知 乎:Heinrich 微 博:@花生油工人 知乎专栏:与时间无关的故事   谨以此文献给大连海事大学的吴楠老师,柳晓鸣老师,王新年老师以及张晶泊老师。   转载的同学请保留上面这句话,谢谢。如果还能保留文章来源就更感激不尽了。 我保证这篇文章...

  • 原文出处: 韩昊   我保证这篇文章和你以前看过的所有文章都不同,这是 2012 年还在果壳的时候写的,但是当时没有来得及写完就出国了……于是拖了两年,嗯,我是拖延症患者…… 这篇文章的核心思想就是: 要让读者在不看任何数学公式的情况下理解傅里叶分析。 傅里叶分析不仅仅是一个数学工具,更是一种可以彻底颠覆一个人以前世界观的思维...

  • 很多Linux高手都喜欢使用screen命令,screen命令可以使你轻松地使用一个终端控制其他终端。尽管screen本身是一个非常有用的工具,byobu作为screen的增强版本,比screen更加好用而且美观,并且提供有用的信息和快捷的热键。 想象一下这样一个场景:你通过Secure Shell(ssh)链接到一个服务器,并...

  • NarrowbandPrimary Synchronization Signal时域位置每1个SFN存在一个NPSSSFNSubframeSymbol长度每个SFN5最后11个symbol11个symbols频域位置NB-IOT下行带宽固定180kHz,一个PRB,12个子载波。...

  •  [h1]反斜杠只能够阻止一个字符  [h2]位于键盘的左上角,和~公用一个键。...