牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

模拟13 题解

A. 矩阵游戏　　通过前40%的部分分，我们发现程序复杂度不能为$O(nk)$。　　设$h(i)$表示第$i$行最终乘的总系数，$l(i)$表示第$i$列。　　考虑每个点$(i,j)$，它对最终答案的贡献是$((i-1)*m+j)*h(i)*l(j)$。　　发现可以拆分为$(i-1)...

线段树映射分块 ST表

2019-08-06

0 409

模拟36 题解

A. 字符题中保证$p_i<=1e5$，还可以很显然地发现当总长度大于$p_{max}+c$，一定不会更优。于是枚举长度的大小。将每一个限制对长度取模。显然如果相邻两个字符所在的区间存在交集，就表示状态非法。于是得到$O(m*p_{max})$的暴力。发现在取模的过程中...

最短路 ST表区间dp dp

2019-09-05

0 381

模拟37 题解

A. 简单的区间看到这种题，一眼就是枚举最值，则确定左右区间，统计跨最值点的答案。维护前缀和后缀和就完了。于是自然地想到用个主席树，还是枚举小的区间，复杂度$O(nlog^2n)$。复杂度证明见模拟31 C.English 正确的算法一定无法避免枚举小区间，已经带了一个log， ...

启发式合并单调栈 ST表桶分治组合计数 dp

2019-09-06

0 502

省选模拟74 题解

A. 签到如果权值在边上，那么问题就简单了，弄一棵生成树，然后对每个环权值塞线性基里就完事了。但是如果权值在点上，这个结论就并不成立了。所以可以联想+手玩发现，如果走一条路径然后回来，造成的贡献是两个端点分别状态取反，中间路径不变。然后可以得到一种构造方法，首先从起点走到终点，然后从...

分块点分治 ST表 bitset 线段树虚树线性基

2020-04-18

0 401

字符串乱写

loj6158 考虑在一个位置放上加号，\(S=A+B\)。若末尾存在 \(0\) ，一定是说 \(A\) 的最后一个数字与 \(B\) 的最后一个数字相加为 \(10\)。（特别的，需要特判二者末尾均为 \(0\) 这个情况）对于进位的问题，其实就是要求 \(A\) 前面的数字与 \(B\) ...

字符串 AC自动机 ST表分块后缀自动机线段树

2020-07-06

0 379