HNOI2019总结
HNOI2019总结
Day 1
开场看三道题,T1是个计算几何,T2是个操作树加\(border\),T3题意有点复杂。想T1想了半个多小时,发现那个钝角不是很会处理,但是40分暴力应该还是可以写,就是有点麻烦。再想T2,也没什么太好的思路,50分只会操作树\(+kmp+\)乱搞。大概9:00开始认真搞T3,看了看样例,感性理解下好像终结状态全都是连到\(n\),于是写了个爆搜,试了几组,好像是对的。发现\(w=0\)直接用\(n-3-\)与n相连的边的条数就行了,操作一条边也比较好做。写完之后发现\((x,n)\)的边不会再动,所以好像是个树的结构,算一次的话直接树形dp就行了。仔细思考了一下,每次树的一个节点都是一段区间,这个树好像就是一棵类似笛卡尔树的东西,操作某一条线相当于splay了一下,好像求个逆元就可以了。想出来大概10点,写到11点多拍上。然后写了一下T2的暴力\(kmp\)和对拍以及T1的20就下考了。
估分:20+20+100=140
实际:20+50+100=170
HNOI的数据强度可见一斑,肖大佬好像直接用暴力kmp拿了70..
Day 2
开场看三道题,好像都还比较清新。T1数据范围有点像bitset,T2看到\(k|p-1\)觉得应该需要一些原根一类的数学前置知识,T3一开始看有点像\(fft\),后来仔细一想是个最优化问题,只会\(O(n^3)\)暴力dp。感觉T3有点像什么dp优化,以为是要推一些结论然后单调队列,推了很久没推出来。于是先看T2,T2前20分直接暴力dp组合数。后面的很像SHOI的那个组合数问题,我只会\(O(k^2 log)\),当时没有去想fft,就先把暴力写了,去搞T1。先写了个30分,然后推了推发现一个联通块可以直接缩起来,如果是二分图要特殊考虑一下。然后想用这个缩起来后bitset。先把T3暴力写完去手写T1bitset,写完之后发现样例过不了,如果联通块大小为1时会有问题,当时因为考试已经快结束了,也没来得及想,就拿了暴力套了后面这部分交了。
估分:30+20+30=80
实际:30+20+30=80
考完出来说T2是单位根反演加上论文题
T1正解和我想的差不多,只要不往bitset方向想就行了。
T3完全走错方向了,50分贪心就行了
总结
总体来说还行,两天考下来没有挂分。但是D1T1没时间写,D2T1和D2T3稍微想偏了一点都有些遗憾。但是像D1T1的计算几何D2T2的单位根反演都是一些我不太熟悉的内容,还需要多学习。数据结构和一些贪心技巧还是不够熟练。希望能够在接下来的一段时间里补足。希望NOI加油。
计划
接下来的一段时间可能需要补上一些文化课的知识。对于计算几何和一些有关数论的高级知识是我的知识盲区,需要多了解一些这方面的知识。更重要的还是一些对思维能力方面的锻炼,一些基础算法的运用,以及对之前做过的题,考过的试的一些总结。还有之前一直没有做的一些题目,也需要完成。hnoi只是一个开始,接下来要更加努力。
最新文章
- fMRI数据分析处理原理及方法
- Thrift 个人实战--Thrift 的序列化机制
- Apply Root Motion
- Android流量统计TrafficStats类
- C# 通过委托控制进度条以及多线程更新控件
- RMAN_Oracle RMAN的常用Command命令
- C语言,不是从hello world开始
- OC基础12:数字、字符串和集合1
- sed正则表达式
- 判断sqlserver对象是否存在
- 【NOIP2003提高组】加分二叉树
- pytorch数据加载器
- CouchDB客户端开发—Java版
- 正则表达式验证input文本框
- MyBatis-generator-Maven方式
- win7计划任务报该任务映像己损坏或己篡改
- Java中eclipse与命令行向main函数传递参数
- twisted 源码分析一:reactor 单例
- request响应码记录
- angularjs compile vs link
热门文章
- java高精度学习笔记
- PS制作动感酷炫水人街舞照
- PS绘制扁平化风格相机镜头UI图标
- asp.net core Api配置swagger
- 学习笔记:filter_var()函数
- 理解根目录,classpath, getClass().getResourceAsStream和getClass().getClassLoader().getResourceAsStream的区别
- [转帖]AMOLED的技术和OLED有哪些联系和区别
- day 7-14 数据库完整性约束
- Sublime Text3 配置 NodeJs 开发环境
- hadoop的缺点