NOIP2016滚粗记

啦啦啦,第一次写游记~

Day0

早上浪浪浪,开了几盘CS

坐车到衢州,在车上开了几盘 艾萨克,然而好困啊……

到衢二后围观XJ杭二合力A ztr,不是很懂为什么事情会变成这样

晚上开杀人游戏,wcz秒全场,好刚啊

Day1

开题,A题是大模拟,B题一副大数据结构的样子,C题求期望。NOIP还考期望?开始我是不信的

A题mogician,233

水完A题码B,开始我竟然把95分的数据范围看成了10000……然而我想不出(O(n^2))做法……只好去刚正解

貌似要把链拆成两条来看,于是写了一个直接边dfs边求和的东西,测了一下样例发现不对……

于是我就直接上线段树合并了&

水完B题去看C,看了很久还是不懂为什么题目要出成这样,推了一下式子以后写了一发,水过两个样例

看了一下时间,10:10,似乎很稳。

于是去测B题大样例,发现要跑4s,于是走上了卡常的不归路(为啥我每次都要卡常啊……

把vector改成了边表,加上快读后终于在本地卡进了2s,于是写了个(O(n^3))暴力去对拍。

去拍C题,写了个(O(2^n))的暴力,然后随便测了组造的数据,咦怎么是INF,去查程序发现floyd里两层循环把v写成了n……(我也不知道怎么跑出INF的

最后就是拍拍拍了~

出来后听cbh说是可以直接记录所有的和的,只要记录一下进结点前的值就行了,我好zzQAQ,orz cbh

然后感觉颓废了一个下午和晚上QAQ

Day2

意识有点模糊……

开题,A题目测是求因子个数,B题又是一副大数据结构的样子,C题是搜索?

水完A后开始写B题,以为标算是fib堆,写了个pq晾着。

C题,写了个(O(2^n*n^3))的记搜,发现过不了QAQ,想不出更优的做法,于是走上了骗分的不归路。

把m=1,2的情况判了一下,然后加了了个最优性剪枝。

记搜加最优性剪枝……反正就是一些乱口胡出来的东西啦~测了一下极限数据貌似刚好2s?

把它和原来的程序拍起来,看了一下时间,发现已经10:30了,感觉药丸/

上个厕所冷静了下,然后……我貌似知道了标算是(O(m))的

然后稍微整理了一下思路,把B题写好了……

然后,然后我竟然把它编译到了自己……

g++ -g earthworm.cpp -o earthworm.cpp

当时我是mengbi的……当devc++提示程序被修改时我竟然点了yes……

我有种想砸电脑的冲动

于是我重写了一遍……

写完后把它和pq拍着。

在写的过程中发现C题拍出几次问题,一开始没在意以为是精度问题,后来发现原来是最优性剪枝的界有些问题QAQ,改掉

看上去B题C题都拍的挺6,于是改进了一下C题的dmk……

出来后听说C题有(O(2^n*n))的做法……反正我不会啦

我还是太弱啦~

反正最终成绩完全看脸,还有那个CCF的老年测评基……

luogu上是557,100+95+92+100+80+90

常数爆炸啦

在XJ上测余姚数据是600?XJ真快……

原文地址:https://www.cnblogs.com/AwD-/p/6086379.html