UOJ Logo TLEbyc的博客

博客

标签
暂无

非完美算法之 ZJOI2017R2T3 字符串string

2017-04-29 17:40:02 By TLEbyc

众所周知非完美算法的重要性。 然而不要看错题更重要 昨天的二试T3我光荣爆〇。 我写了个后缀树组,然后,写了个ST表。 我潜意识里认为子串l..r的后缀为i..n

哎下面来到正题。 今天我开始订正。 T3没打暴力。于是打了一发,交到uoj上,卧槽30!过了1,6,7三个点。气出血 这充分说明了写namespace以“分开”程序的重要性。 然后,我开始骗分。速度瓶颈,也称速控步,在于瞎jb找后缀的那一段。 于是我用双指针优化,开始i=l,j=l+1,然后开始匹配前缀,到了不匹配的地方,小的那个就是当前的ans(最优的),大的就跳向匹配到的那个位置+1,好像没啥错的。 对拍,拍到第1995组的时候出了偏差:6 1 1 4 1 4 1 4 2 1 6 我就WA了。 于是我把暴力可跑过的用namespace单独做,其它就骗分,80!!!...... 额,心中一万只草泥马飘过。。。。。。 然后,我把我的算法改成正确的姿势后,就是说在某个指针>r时,从另一个指针位置+1开始跑,并维护ans。这样就T成了40。非完美算法是坠吼的。 然后我对着我的骗分搞了点儿magic事情——类似于卡时的骗分。居然就AC了(额外数据T掉了3分). 哎可惜了。我要是智商再高些,第一题的40分推出转移方式便可做的;第三题不用类似卡时的方法,也能骗到80.就是说OI赛制下能80,apio赛制下就AC了。 考省选需要信仰,考NOI系列赛事需要信仰!!!信仰伟大的,非完美算法!!! 代码详见http://blog.csdn.net/chenyanbo1111/article/details/70966830

共 1 篇博客