NOI2019 Day2游记
开场T1是个最短路优化建图，边向二维矩形内所有点连，本来可以写树套树的，但是卡空间（128MB），后来发现其实是不用把边都建出来的，只需要用数据结构模拟dijkstra的过程，支持二维区间对一个值取min，查询最小值并删除就可以，正解就是K-D Tree维护集合，复杂度是根号的（然而我不会），最后写了暴力建边、普通最短路（每条边只连向一个点）、矩形只有一维的线段树优化建边三个部分分，拿到72分走人（其实写树套树还有16分的，没时间了。。。）
T2一看就想起了THUSC的Day1T1，一样是形如以x/(x+y)的概率选择x，y/(x+y)的概率选择y 的期望/计数题，那时第一个想法就是打表（对THUSC也是这样），但是想想我还是不要乱来，先推推式子再说，然后推出了个可以O(n2m)dp的式子，然后就可以愉快地写40分暴力了（然而有10分最后没时间写了），结果因为没有预处理0的下降幂调了近一个小时没出来，然后就没时间打表了（最后出场的时候大家都说T2打表可过，自闭了。。。）
最后一小时我才开的T3，先二话不说拿下20分暴力，最后半个多小时一直在想每个点度数为1的部分分，它的数据范围很明显是O(nlogn)的算法，于是去想分治，最后相出个很笨的分治套分治，考后发现外面那层分治完全可以去掉，加个简单的预处理就可以，然鹅我没有想到。。。但是我的算法复杂度似乎没有问题，常数也不大（T3交互题，交互次数卡得很紧），复评时测了最终数据也能过，但是我犯了个更严重的错误，就是把点的标号搞错了（题目标号是0~n-1，我写的是1~n），最后5分钟没时间检查了，结果这个部分分就挂了，不过我前面的暴力没写错，自己手造的数据标号也是0~n-1，然而测样例时交互库竟没报错（神奇），应该是自己手误了，平时写分治都习惯写solve(1,n)，结果写得太急就错了（以后有时间还是要把要注意的地方写下来，特别是题目中与自己编程习惯相违背的条件，方便自己检查），后来发现只要把solve(1,n)改成solve(0,n-1)就可以过，就这样丢了16分，有点可惜。。。
总结：这次要拿的分基本拿到了（虽然也只有基本分），但是还是有些分因为时间不够没拿到，感觉自己速度还是太慢了，写个暴力都要花很久时间（还写不完），最后连正解都没时间写（比如T2），根本还是自己代码能力不够，一些东西还不熟练（比如那个下降幂），自己做题量也不够。
附个考场时间表：前2个小时做T1（72分），2个小时做T2（30分），最后一小时做T3（20分），其实时间也没怎么安排好，但是实在是自己写得太慢了。
备注：K-D Tree的坑还是要找时间填掉，NOI的题也要去落实哈！
最新文章
- Spring源码分析——BeanFactory体系之抽象类、类分析（一）
- 通过淘宝IP地址库获取IP位置
- webform：分页组合查询
- 【bzoj2049】[Sdoi2008]Cave 洞穴勘测 link-cut-tree
- JavaScript简易教程（转）
- json解析转map
- 新写PHP HTTP断点续传类文件代码
- IE标签a嵌套table标签，链接点击无效
- DW8051调试终结
- Python笔记1-20151021
- [转载] Linux五种IO模型
- 结合程序崩溃后的core文件分析bug
- spring的事件驱动模型
- Java BitSet解决海量数据去重
- 开发过程中遇到的问题1--------我们的mysql的查询语句时自己写的，没有用oracle的nextvalue函数。所以这里涉及到了并发的问题。
- LeetCode——1. Two Sum
- java常用API之Date类
- 【文文殿下】洛谷P2408 不同子串个数
- 人生的第一篇blog
- 【BZOJ2306】幸福路径（动态规划，倍增）