11D_Beyonder's Blog

单调队列概述 定义 顾名思义，单调队列是队列内元素为单调递增或递减的队列。 单调队列的特点 单调队列内的元素满足单调性，队列为双端队列，STL\text{STL}STL 提供了类模板 deque\text{deque}deque 。由于 deque\text{deque}deque 速度较慢，一般用数组模拟双端队列。 维护方式 通过双端队列头和尾的进出维护队列内元素的单调性。有删除队头、删除队尾、将元素推入队列三种操作。 维护队列内元素的单调性的本质是，每次操作都将没有潜力的元素从队列中去除，而将有潜力的元素放入队列。因此单调队列的作用就是用来保存一段区间内有潜力的元素。有潜力的元素是指将来可能满足具体问题条件或者能够成为最优解的元素。一般来说，新产生的元素都是有潜力的，可以毫不犹豫地将新产生的元素加入队列中，而只考虑是否要进行删除队头和删除队尾的操作。有句俗语称：比你晚来的还比你强，那你必定就没希望了。因此，如果后遍历到的元素潜力较之于队尾更大，需要果断将队尾删除。 当然，执行删除队头和删除队尾两种操作的条件需要具体问题具体分析。具体问题具体分析，是马克思主义活的灵魂。 单调性定义的 ...

定义 有 NNN 件物品和一个容量为 VVV 的背包。放入第 iii 件物品消耗的体积为 CiC_iCi​，得到的价值是 WiW_iWi​ 。求解在背包容量允许的情况下，能获得的最大价值；即选取 $i_1,i_2,\cdots,i_k$，求 $\max\limits_{\sum\limits_{j=1}^kC_{i_j}\le V}\sum\limits_{j=1}^kW_{i_j}$ 。 基本思路-动态规划 (Dynamic Programming) 暴力枚举 这个问题的特点是，每种物品都只有一件，可以选择放或者不放；即放入背包为 111 ，否则为 000 ，故称 0−10-10−1 背包。按照状态压缩枚举的思想，共有 2N2^N2N 种选取形式，时间复杂度为 O(2N)O(2^N)O(2N) ，时间复杂度是不可接受的。事实上可以利用动态规划的思想，记录有效信息，降低时间复杂度。 状态转移方程 定义 dp[i][j]dp[i][j]dp[i][j] 为在前 iii 个物品中挑选总容量不超过 jjj 的物品时，能够获得的最大价值。 有状态转移方程 dp[i][j]={dp[i−1][j ...

传送门 ↬\looparrowright↬ 题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1n−1n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 111，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有 333 堆果子，数目依次为 1,2,91,2,91,2,9。可以先将 111、222 堆合并，新堆数目为 333，耗费体力为 333。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 121212，耗费体力为 121212。所以多多总共耗费体力为 3+12=153+12=153+12=15 。可以证明 151515 为最小的体力耗费值。 输入格式 输入的第一行是一个整数 n ...

Enter ↬\looparrowright↬ Description Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs NNN (1≤N≤20000)(1 ≤ N ≤ 20000)(1≤N≤20000) planks of wood, each having some integer length Li(1≤Li≤50000)L_i (1 ≤ L_i ≤ 50000)Li​(1≤Li​≤50000) units. He then purchases a single long board just long enough to saw into the NNN planks (i.e., whose length is the sum of the lengths LiL_iLi​). FJ is ignoring the “kerf”, the extra length lost ...

Enter\text{Enter}Enter ↬\looparrowright↬ 题目背景 根据斯诺登事件出的一道水题 题目描述 2013 年 X 月 X 日，俄罗斯办理了斯诺登的护照，于是他混迹于一架开往委内瑞拉的飞机。但是，这件事情太不周密了，因为FBI的间谍早已获悉他的具体位置——但这不是最重要的——最重要的是如果要去委内瑞拉，那么就要经过古巴，而经过古巴的路在美国的掌控之中。 丧心病狂的奥巴马迫降斯诺登的飞机，搜查时却发现，斯诺登杳无踪迹。但是，在据说是斯诺登的座位上，发现了一张纸条。纸条由纯英文构成：Obama is a two five zero.（以 . 结束输出，只有 6 个单词+一个句号，句子开头如没有大写亦为合法）这句话虽然有点无厘头，但是警官陈珺骛发现这是一条极其重要的线索。他在斯诺登截获的一台笔记本中找到了一个 C++ 程序，输入这条句子后立马给出了相对应的密码。陈珺鹜高兴得晕了过去，身为警官的你把字条和程序带上了飞机，准备飞往曼哈顿国际机场，但是在飞机上检查的时候发现——程序被粉碎了！飞机抵达华盛顿只剩5分钟，你必须在这 5 分钟内编写（杜撰）一个程序， ...

Enter ↬\looparrowright↬ A. Road To Zero You are given two integers xxx and yyy. You can perform two types of operations: Pay a dollars and increase or decrease any of these integers by 111. For example, if x=0x=0x=0 and y=7y=7y=7 there are four possible outcomes after this operation:x=0,y=6x=0, y=6x=0,y=6;x=0,y=8x=0, y=8x=0,y=8;x=−1,y=7x=−1, y=7x=−1,y=7;x=1,y=7.x=1, y=7.x=1,y=7. Pay b dollars and increase or decrease both integers by 111. For example, if x=0x=0x=0 and y=7y=7y=7 there are t ...

分层图 概述 一般建图时会给定节点数 nnn 和边数 mmm，然后可以写出利用邻接矩阵、邻接表、链式前向星等等建图的代码。 在构建了一张图的基础上，我们将图再复制 kkk 份，形成了k+1k+1k+1 层图，这就是所谓分层图。可以将分层图理解为多个平行的图。 一般模型的是：在一张图上，可以进行 kkk 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。我们可以构建 k+1k+1k+1 层图，做出一次决策可能意味着跨越层级，一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。 如图，cost\text{cost}cost 就是做出跨越层级的决策后产生的代价。 建图方式 有 nnn 个节点时，[1,n][1,n][1,n] 表示第 $1 $ 层，[1+n,2n][1+n,2n][1+n,2n] 代表第二层，[1+2n,3n][1+2n,3n][1+2n,3n] 代表第三层，[1+(i−1)n,in][1+(i-1)n,in][1+(i−1)n,in] 代表第 iii 层。每一层之间的连边就需要具体问题具体分析了。 分层图最短路 思 ...

传送门 ↬\looparrowright↬ A-最短路 题目描述 牛能在家里遇到了一个问题，他现在想要去找牛可乐并向他请教这个问题，现在他已经知道了牛可乐家的坐标，并且他很容易找到了通往牛可乐家里的最短路（一条直线）。 但是，平面上有一个圆形区域，这个圆形区域内是被诅咒过的地方，所以牛能不能进入这块圆形区域的内部，所以牛能现在找不到通往牛可乐家的最短路了，请帮助他解决这个问题！ 保证牛能家和牛可乐家不在诅咒区域内。 输入描述 第一行四个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​，(x1,y1)(x_1, y_1)(x1​,y1​) 表示牛能家的坐标，(x2,y2)(x_2, y_2)(x2​,y2​) 表示牛可乐家的坐标。 第二行三个整数 x3,y3,rx_3, y_3, rx3​,y3​,r，(x3,y3)(x_3, y_3)(x3​,y3​) 表示被诅咒的圆形区域的位置的圆心坐标，rrr 表示这个圆形区域的半径。 输出描述 在一行中输出牛能从家到牛可乐家的最短路。 示例1 输入 -1 -1 1 1 0 0 1 输出 3 ...

引入 RMQ\text{RMQ}RMQ 问题 RMQ\text{RMQ}RMQ 是英文 Range Maximum/Minimum Query\text{Range Maximum/Minimum Query}Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。一般可用 $\text{ST} $ 表、线段树等数据结构解决。 可重复贡献问题 对于一个运算 opt\text{opt}opt ，如果满足 x opt x=xx \text{ opt } x=xx opt x=x，则对应的区间询问就是一个可重复贡献问题。例如最大值有 max⁡(x,x)=x\max(x,x)=xmax(x,x)=x，最大公约数有 gcd⁡(x,x)=x\gcd(x,x)=xgcd(x,x)=x，所以 RMQ\text{RMQ}RMQ 和区间 GCD\text{GCD}GCD 就是一个可重复贡献问题；而区间和就不具有这个性质，x+x=2xx+x=2xx+x=2x。 ST\text{ST}ST 表 ST\text{ST}ST 表的特点 对于一个静态数组，给出 QQQ 次询问，每次询 ...

最长回文子串 给定一个字符串 SSS，求出其最长回文子串的长度。 改造字符串 回文分为两种情况：奇回文（例如：“aabaa”\text{“aabaa”}“aabaa”）和偶回文（例如：“aabbaa”\text{“aabbaa”}“aabbaa”）。“aabaa”\text{“aabaa”}“aabaa”的回文中心是 “b”\text{“b”}“b”，而“aabbaa”\text{“aabbaa”}“aabbaa”的回文中心是 $\text{“bb”} $。 为了避免两种回文情况的讨论，我们将每两个字符之间插入一个不曾出现的字符，统一改造为奇回文来处理，比如，将 $\text{“accahqiq”}$改造为$\text{“\$#a#c#c#a#h#q#i#q#”}$。开头$\text{“\$"}$为防止数组越界。对于改造后的字符串 SSS，定义数组 p[i]p[i]p[i] 表示以 iii 为中心的最长回文半径。例如： i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 s[i] $ # a # c # c # a # h # q ...