Preface 字符串操作是 OI 中常见的内容 参考 字典树 Trie 定义 像字典一样的树 引入 用边权来表示字符, 每个节点代表一个状态 疑问 如何存储? 当然是 trie[26][26][26]... 实际上会有很多节点空掉, 如果直接那样开会爆炸而且深度有限制! 所以我们动态开点吧 设定一个 tot 来记录总节点, 插入节点时动态开点 trie[Max][26], tot 判定结束? 用 exist[Max] 来记录当前节点是否为结尾节点 实现 constexpr int Max=100000; struct Trie { int trie[Max][26], tot; bool exist[Max]; // 该节点是否为结尾 void insert(char *s, int l) { // 插入字符串 int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!trie[p][c]) trie[p][ ...

转自: 解决 TypeError: Converting circular structure to JSON - JSON.stringify 报错 let cache = []; // 去重数组 let json_str = JSON.stringify(hexo, function (key, value) { if (typeof value === "object" && value !== null) { if (cache.indexOf(value) !== -1) return; cache.push(value); } return value; }); cache = null; //释放cache

Preface Catalan 组合数学 真是一个神奇的东西 Catalan 的精髓是推递推式, 只不过很多问题的递推式会收敛到 Catalan 的递推式(只能说是一种推递推的思想) Start up 二叉树种类 分治的思想, 左+自己+右, 把问题化小 Hn=∑i=1nHn−i⋅Hi−1H_n=\sum_{i=1}^nH_{n-i}\cdot H_{i-1}Hn​=∑i=1n​Hn−i​⋅Hi−1​ 当然, 初始值 H0=H1=1H_0=H_1=1H0​=H1​=1 合法数列 nnn 个 +1+1+1 和 nnn 个 −1-1−1 构成 2n2n2n 项 a1,a2,⋯ ,a2na_1,a_2, \cdots ,a_{2n}a1​,a2​,⋯,a2n​，其部分和满足 a1+a2+⋯+ak≥0(k=1,2,3,⋯ ,2n)a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)a1​+a2​+⋯+ak​≥0(k=1,2,3,⋯,2n) 对与 nnn 该数列为？ 乍一看好像很难, 但是我们仔细分析一下 好像不方便直接得到结果, 那就容斥原理 我们用 ...

Preface hexo serve 连热重载都没有… 找不到可用的, 准备自己写 技术栈 后端监听文件 generate 事件, 通过 Websocket 发送信号 Start up 安装插件 Github: hexo-hotreload npm i hexo-hotreload 插入代码 插入代码操作只在 0.0.1 版本中需要使用 更高版本已实现自动插入 在你想要进行热更新的页面插入 你可以在 url 框内键入 javascript: 并粘贴下面的内容 也可以直接将这些粘贴到 调试控制台 中 var h1=document.getElementsByTagName("h1"),article=document.querySelector("div.e-content")??document.getElementsByTagName("article")[0],title="";for(let k in h1)if(h1[k].className?.includes("title"))title=h1[k].innerText;if(title==="")throw new ...

推导 dp 因为他的炮击范围有点长(两个格子, 横跨两行) 所以得用 iii 表示当前行, jjj 表示当前行的状态, kkk 表示 i-1行的状态, lll 表示 i-2行的状态 getSta: 获取二进制状态中 1 的数量 那么转移方程就是: dpi,j,k=max{dpi−1,k,l+getSta(j)}dp_{i,j,k}=max\{dp_{i-1,k,l}+getSta(j)\}dpi,j,k​=max{dpi−1,k,l​+getSta(j)} 实现 我没有使用其他题解的 枚举+剪枝 的方法, 而是直向着可行方案走 应该是状态压缩中比较优的了(482ms): Record ~: 取反码 如果需要删除第 k+1 位那么只需要 x&~(1<<k) 变量说明 je[]: judge 相当于压缩后的地图 je: judge 相当于压缩后的一行 寻找下一状态 // 当没有下一种状态时返回 false 否则 返回 true 以及修改 sta 为最新状态 bool getNextSta(u_int16_t &sta, const u_int1 ...

Preface 状态压缩 就是把一堆有k种情况的状态压缩成一个k进制数字表示 一般来说是把 bool 压缩为 二进制数字表示 为什么要这么做? 因为转移速度快, 否则转移的时候不仅浪费空间还浪费时间, 这 O(n) 的时间放在题目求解里面不好吗? Start up 以 炮兵阵地 为例 题目题目描述 司令部的将军们打算在 N×MN\times MN×M 的网格地图上部署他们的炮兵部队。 一个 N×MN\times MN×M 的地图由 NNN 行 MMM 列组成，地图的每一格可能是山地（用 H\texttt{H}H 表示），也可能是平原（用 P\texttt{P}P 表示），如下图。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。 图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队 ...

Start up 斜率优化就是 将无法分离的参数 转化为斜率进行单调队列优化 假设现在题目要求最小值 直白点, 就是 fi=min{Yj−KiXj}+Δf_i=min\{Y_j-K_iX_j\}+\Deltafi​=min{Yj​−Ki​Xj​}+Δ 先不要理会变量名称 下标的意思是含有的有关参数(就是要传入, 参与计算/推导的参数) compcompcomp 函数内带有有关 i 的变量, 并且他和 有关 jjj 的变量混合在一起, 无法使用常规方法 但是不难发现, 假设现在来推导单调队列中的更优解 设 jjj 为对头, kkk 为 jjj 下一个元素 排除队头: Yj−KiXj≥Yk−KiXkKi(Xk−Xj)≥Yk−YjKi≥Yk−YjXk−Xj\begin{split} Y_j-K_iX_j &\geq Y_k-K_iX_k \\ K_i(X_k-X_j) &\geq Y_k-Y_j\\ K_i &\geq \frac{Y_k-Y_j}{X_k-X_j} \end{split} Yj​−Ki​Xj​Ki​(Xk​−Xj​)Ki​​≥Yk​−Ki​X ...

转载/借鉴于: 从主方法到 Akra-Bazzi 定理 递归式求解——代入法、递归树与主定理 复杂度 - OI-wiki Start up 首先需要知道递归法求 时间复杂度 T(n) 最朴素的情况是 T(n)=aT(nb)+r(n);(a,b>0)T(n)=aT(\frac{n}{b})+r(n);(a,b>0)T(n)=aT(bn​)+r(n);(a,b>0)(这里使用 r 而非 f 是因为我把渐进成本理解为每层递归的余子项 ) 前置 e.g. T(n)=3T(n4)+Θ(n2)T(n)=3T(\frac{n}{4})+\Theta(n^2)T(n)=3T(4n​)+Θ(n2) 我们先来看最简单的情况: (ccc 是常数) 这里 cn2cn^2cn2 是当前阶段的渐进成本 然后下面的三个 T(n4)T(\frac{n}{4})T(4n​) 则是转移成本 这里不难看出 将这颗树的所有节点的值加起来就是 T(n)T(n)T(n) 如此这般, 将 下面的节点也拆掉 就得到了最终图 树高 设当前迭代到第 kkk 层 每一层都是一次迭代, 我们当然是要最终迭代到 ...

Preface Click to go: Buying Feed G Problem 题目描述约翰开车来到镇上，他要带KKK吨饲料回家。运送饲料是需要花钱的，如果他的车上有XXX吨饲料，每公里就要花费X2X^2X2元，开车D公里就需要D×X2D\times X^2D×X2元。约翰可以从NNN家商店购买饲料，所有商店都在一个坐标轴上，第iii家店的位置是XiX_iXi​，饲料的售价为每吨CiC_iCi​元，库存为FiF_iFi​。 约翰从坐标X=0X=0X=0开始沿坐标轴正方向前进，他家在坐标X=EX=EX=E上。为了带KKK吨饲料回家，约翰最少的花费是多少呢？假设所有商店的库存之和不会少于KKK。 举个例子，假设有三家商店，情况如下所示： 坐标 X=1X=1X=1 X=3X=3X=3 X=4X=4X=4 E=5E=5E=5 库存 111 111 111 售价 111 222 222 如果K=2K=2K=2，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是1+4=51+4=51+4=5，花在商店的钱是2+2=42+2=42+2=4，共需要999 ...

差分约束 x1−x0≤xx2−x1≤xx3−x2≤x\begin{aligned} x_1-x_0\le x\\ x_2-x_1\le x\\ x_3-x_2\le x \end{aligned} x1​−x0​≤xx2​−x1​≤xx3​−x2​≤x​ 形似如此, 等号方向决定了 最短路/最长路 当前情况则是最短路 分层图 在奇偶染色中很好使用 设 i 为偶节点, i+n 为奇节点 又 奇数+1=偶数, 偶数+1=奇数 那么他们的关系就是从偶数到奇数,从奇数到偶数 即 add: u->v+n, u+n->v, v->u+n, v+n->u