C – The Number Of Good Substrings
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\),然后显然的是:如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间,那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\),然后显然的是:如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间,那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
这道题可以离线回答,很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息,然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG,但是我们可以动态开点,然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的,这样空间就可以接受的了。
既然有了很好用的动态开点线段树,我们就可以用树上差分那一套路,在端点和\(LCA\)处打标记,然后考虑从下往上合并答案。合并可以用线段树合并,复杂度为重合部分,差不多就是\(O(\log n)\)。然后就没了,很傻逼的一道题。
这道题挺好的,让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路,大概的维护方法非常像 Floyd。也没啥好说的,看代码吧。
这道题的式子跟 Codeforces 一道 F 题是一样的,让我误以为是 BSGS 之类的玩意,最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的,由于\(k\)很小,所以我们可以考虑计算每一个\(f\)的指数,然后就可以用快速幂来计算这些东西。
这道题我在考场上打了一个错解,还骗到了 30 分。
正常的思路是:在最短路图上找到几个边进行修改。然而,最优的解决方案并不一定出现在最短路图上的边上,也可以通过修改次优边进行解决。所以,这道题其实跟最短路没什么太大关系,即使后面会用到 Djisktra 来求最短路。
我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份,然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\),可以生成一个副本来连接下一层的目标点,也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\),当最后求最短路时,经过这样的一条边可以被认为是修改一条边,且,这个边是单向向下的,所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路,然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。