UNR滚粗记

orz hhw posted @ 2016年7月19日 09:01 in 做题记录 with tags 比赛 做题记录 uoj , 606 阅读

Cu滚粗,最后时刻被绝杀没抢到抱枕QAQ

笔试

吃完晚饭躺在床上想休息会,没想到睡着了。。7:20才起来,赶紧答笔试,7:29:55惊险交上,挂了1分。。

Day1

T1好难啊不会做

T2好难啊不会做

提答好长啊不想看

回去做T1,发现如果求出每个数左边和右边第一个比它大的数,问题就相当于统计若干段折线的和了。

这个折线怎么统计呢?把它拆成三段吧。。码起来。。

码到一半发现三段折线可以一起统计啊,似乎在前面+1中间两段-1后面再+1就行了?

乱写了一发,调了一会总算过了样例,就没管了。

然后看T2,发现前30分就是个收集卡片的问题?

百度一下,得到了通项公式,直接抄过去

想了想后30分,觉得暴力高斯消元最少也要2^27,弃疗了。。

然后看提答,每个点看了看觉得没什么规律啊。。

手玩了。。好累啊。。大概玩了十几个一分就玩不下去了。。

T2想了想状压DP好像是可以的。。赶紧写了发。。

然后继续提答。。我玩玩玩。。

然后发现T2没有判不合法的情况,赶紧改。。

最后提答也玩不下去了。。GG。。

最后90+60+28滚粗了。。T1没判>模数的数挂了10分、我艹提答竟然不是手玩。。

Day2

T1好难啊不会做

T2好难啊不会做

T3看起来好做点啊。。

想了会,好难啊不会做

回去想T1,觉得可以先倍增套辗转相减摞出gcd,然后根据gcd再倍增摞出答案。。

好像是两个log的?想了会觉得不太好卡,就先写了发。。

样例挂了。。我改改改,总算过样例了。。

然后随手测了个数据,输出了负数。。

我调调调,改得差不多对了,写了个checker

窝草竟然有错,竟然让两个一样的数相减了

改好了继续checker,没错了放着跑咯

思考了下T2,觉得暴力都好难写啊。。

然后思考T3,想了会如何下推标记。好像并没有什么希望

我想

我想

我想

可以线段树上挂链?删除就是删一些线段的链头,然后可以在链中插入?

唉?线段树上套个堆就好啦?哈哈两个log没准就卡过了。。

赶紧写了发,没过样例。。

发现单点删的时候别的点的值也改了。。改好了就过样例了。

然后回来做T2,觉得可以用个DP摞80分啊。。

写了发区间DP,dp[l][r]表示第l个到第r个黑色叶子节点调了会过样例了。。

检查了会似乎也没什么错啊。。感觉这场可以上250啊。。

恩。。弃疗了。。大号交起,吃饭去了。。

回来看评测,似乎抱枕有望啊,T3原来有一发90的,加了读入优化以后变成80了。。

T2竟然只有15分?DP是错的。。骗了15分。。

晚上再回来看,发现小号的T3变成100了。。好神奇。。

但数了数发现是第四名。。滚粗了。。

好辣鸡啊。。一道没炸都没拿到抱枕。。

就当为NOI攒波RP吧。。

 

NOI前根本銫不动题啊....


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter