HAOI2013 结束

Standard

又是一年省选时,昨天比赛了一天,比较累,但是结局还好。

比赛的成绩wyfenger第一,我第二,认识的人中进入省队的还有 省实验中学的3个(王梦迪(初三),王宇飞,常跃如),郑外的陈科。

结果出来前比较忐忑,因为毕竟这可能是OI生涯的结尾,不过即使可以参加Noi,也只剩下3个月了。

上午的比赛

前两题很简单,简直是NOIP普及组水平,以至于刚开始看到第2题还以为是最小费用最大流,但问题是没有搞到200的人很多,也许河南真的是没有多少人好好学Oi吧!至于第三题,是和牛棚的灯一摸一样原题!(比赛前我还看到了这题,但是没有写)其实 我已经写出 Gauss-Jordan消元法,但是没有考虑多解的情况,检查了半天不对,所以最后还是写了个暴力,总共230

下午的比赛

下午的比赛比上午难一些,第一个问题可以用线段树Ac,但是形式不太一样,不过不是很难想,想了10分钟,加之看到第二题像是个恶心的搜索……所以就决心搞第一题,写了1h,调试+对拍了1.5h(手动对拍),最后还好100分,否则就很悲剧了,(无力吐槽这题的数据,最裸的暴力算法就可以搞到60分)

而第二题其实可以用最短路做,甚至也有模拟Ac的办法,而我在第一题上花了大部分时间,最后仅仅交了个骗分(输出-1能得30……)

总共130

去年省选比今年质量高多了,难度也大多了。。

今后恐怕就不能用win8了,

第一

还有大约5天就到期了

第二,Noi是在Linux下的,所以只能乖乖的用Ubuntu了。

 

时间已经很少了,水平还差得很远。

NOI2005 维护序列

Standard

中午的时候突然想起NOI2005的维护序列,于是就写了8小时搞出来,3小时写,5小时调,效率真够低的…

这是个很麻烦的问题,我用Splay解决的,首先题目要求的操作有6种,

其中翻转,求最大和比较麻烦.

  1. 对于insert操作,效仿NOI2003的文本编辑器,我直接建了一颗几乎平衡的二叉树,然后塞到Splay中相应的位置(这样快一点点)
  2. delete操作比较简单,找到相应的子树,删去即可.
  3. MakeSame操作:用delta表示要改变成什么,并传递这个值,每次改变delta都覆盖原有的,注意,如果没有delta值,是不能传递或是更改的,否则就会出错,所以我用了一个极小的常量NA表示没有delta值
  4. reverse操作:刚看过去感觉有点奇怪,稍稍思考一下发现reverse操作可以像MakeSame操作那样传递(翻转操作其实就是某棵树中所有的子树位值取反一下(左子树放右边,右子树放左边)),然后向下传递就行了
  5. GetSum也好做,用Sum记录该子树的和,每次MakeSame或者是进行Splay操作后维护一下就好了(Sum=左子树的Sum+右子树的Sum+1)
  6. MaxSum这个比较不好做,但是之前遇到在过线段树上比这个还要麻烦的问题(求某区间所有子串和的和…),就很容易想到了,即LMax表示某子树构成的序列中最大的前缀和是多少RMax表示最大的后缀和是多少,Max_Sum就表示最大子串和是多少,Max_Sum根据LMax和RMax算出就行了

Splay的两个维护函数:deliver()和maintain()

deliver()负责传递树根信息(翻转和MakeSame)

maintain()负责维护Splay的正确性(重新计算相关信息如Sum,LMax…)

我写了6K的代码,花了我很长的时间,然而并没有结束,因为明天还有继续优化代码和算法结构,以便下次再遇到能很快的写出.

最近两周的刷题小记

Standard

今天早上。。出于某种不可抗拒的原因,没心情写题,所以正好小记以下(我是按分类记录,不是按日期记录):

  • 动态规划:
    • SCOI2008 着色方案  很好的题,f[c1][c2][c3][c4][c5][k]表示状态进行转移(上网看)
    • HAOI2010 计数  主要是涉及到 具有不可区别物体的集合的排列(比如重新排列SUCCESS能构成多少种不同的串,公式是(n,k1)*(n-k1,k2)*(n-k1-k2,k3)… = n!/(k1!*k2!…*kn!)其中ki表示某种元素的个数
    • SDOI2010 地精部落  这个题网上说的方法看不太懂,神马之云想的方法是 f[i][j]表示长度为i的序列第1个是j且开始下降的序列个数,g[i][j]表示…且开始上升的序列个数,那么f[i][j]=Sigma(g[i-1][k])k<j,g[i][j]=Sigma(f[i-1][k])k>j,dp的时候记录一下Sigma信息就可以省掉转移的那一维。
    • HAOI2010 最长公共子序列  dp时记录方案数,再容斥掉多计算的即可
    • HAOI2010 软件安装  好题 一开始看不就是个简单的树形依赖背包嘛,写出来才发现图里面竟然有环,不过既然是环,选一个就全都得选,所以缩成点,构成新的图,再在新图里面dp就可以了(注意环连接的要么什么都没有要么是外向树,对于外向树,缩点之后都不可能有前驱,所以连接到0,这样就是棵标准的树了,从0开始dp就行了)
    • 越狱第1季第13集 大神的做法不会,不过好像和我的方法有点像(二分答案,然后检查)
    • 瑰丽华尔兹 又是好题 f[k][y][x]表示第k段的结尾在y行x列的最长滑动距离,转移O(n)的,所以优先队列优化就可以Ac
  • 图论
    • 公路修建 。。。看出来了很简单,裸的最小生成树,不过由于边数太多Kruskal会跪掉,所以只能用Prim了
    • 卡赞群岛 找到双连通分量,缩点然后dp(由于是无向图,缩点之后必然是个无根树,或者是无根树森林,所以可dp。
    • HAOI 软件安装 见上文
  • 贪心
    • SCOI2008 斜堆 很有意思的题,按照斜堆的规则,最后插入的点一定在最左边(也就是便利的时候从不向右转),如果没有根变成左子树的情况,每次找最左边的点,删掉,然后模拟一下就行了(基于字典顺序最小的原则)。考虑上较小元素会替代根的情况,如果我们发现某个极左点没有右子树,那么说明它是叶子结点或者是替代根的元素,此时必须先删它(否则不可能构成目标树),基于最小字典序的原则,这些步骤合在一起就是:每次从根向左找没有右子树的点,一旦发现就把它删掉,并且将它的祖先的左右子树互换,最后倒序输出删点顺序即可(有一个特殊情况,即某点的左子树只有一个叶子结点,而且它没右子树,那么此时删除那个叶子结点(基于字典序最小的原则)),相关拓展见这位大神网志
    • 立春树 树上贪心,比较简单,不说了
  • 数论
    • 双亲数 貌似都是利用容斥搞的,用Mobius函数搞会快点,关于Mobius Function见Noi2010 能量项链,HAOI2011问题B,以及网上各种题解。