8.6 ZR集训模拟赛总结

又是掉分的一天。
且因为题目的区分度很高,所以掉分掉的很多,掉了100pts。
umm…但今天也没有特别满意吧。

T1

看着就很不可做。

考场实在没什么想法,写了个 O ( w i ) O(w^i) O(wi)复杂度的算法。
10pts。
拿到预期分。

考后发现有80个左右的人A了。
柯西不等式或者多项式卷积维护系数都可做。
没学过,所以不太难受。

T2

挺难受的,考场上看出可以维护一下每个询问点的必经路, O ( n 4 ) O(n^4) O(n4) (一定跑不满),写个暴力的50pts。
问题在,我不会求最短路图上的必经路…
麻了。
50变25.

赛后问了问同校oier,其实就是在dij最短路的时候,维护一个cnt数组。

若 d i s [ d q ] + 1 < d i s [ s s ] dis[dq]+1<dis[ss] dis[dq]+1<dis[ss]     c n t [ s s ] = c n t [ d q ] cnt[ss]=cnt[dq] cnt[ss]=cnt[dq];

若 d i s [ d q ] + 1 = = d i s [ s s ] dis[dq]+1==dis[ss] dis[dq]+1==dis[ss]     c n t [ s s ] + = c n t [ d q ] cnt[ss]+=cnt[dq] cnt[ss]+=cnt[dq];

最后乘法原理统计,若 c n t 1 [ 终 点 ] = c n t 1 [ a ] ∗ c n t 2 [ b ] cnt_1[终点]=cnt_1[a]*cnt_2[b] cnt1​[终点]=cnt1​[a]∗cnt2​[b]

c n t 1 cnt_1 cnt1​是从起点跑的最短路, c n t 2 cnt_2 cnt2​是从终点跑的最短路, a a a到 b b b在起点到终点的最短路图上.

那么从起点到终点,则必须经过 a − > b a->b a−>b

100pts的做法是支配树。

T3
写了个无脑trie图还被卡同串不同权值了…
少拿了17pts。

正解貌似是dp思想+由串长得优化思路+SAM优化+数据结构。
磕得不是很懂。

总结

T2 学一下支配树 T3再认真考虑一下,应该都是可订的。
今天10+25+0=35。
最佳的话应该是10+40+17=67(不过T2写法真的想不起来了)
再接再厉吧。

上一篇:进制转化


下一篇:网络排查