P3147 [USACO16OPEN]262144 P 想到合并，自然就想到区间dp，一个被合成的数之前是一个区间，并且由两个数比它小 1 1 1 的区间合成。可麻烦的是，我们并不知道之前的两个区间长度各是多少。这道题不像一般的区间dp，明确地知道一个区间的答案由哪些区间转移。 在这道题，我们只知道要合成ii，就要找到两个紧接着它的两个 i ...

向上取整函数 ceil() 向下取整函数 floor() 舍尾取整函数 trunc() 这三个函数都在头文件 math.h 中 floor(x)返回的是小于或等于x的最大整数。 ceil(x)返回的是大于x的最小整数。 trunc(x)返回的是x舍取小数位后的整数。 floor()是向负无穷舍入，floor(-5.5) == -6； ceil()是向正无穷舍入，ceil(-5.5) == -5 trunc()是向零取整 trunc(1.9) == 1 trunc(1.4) == 1 trunc(-1.4) == -1 trunc(-1.9) == -1 我们在用除法的时候...

目录 一、倍增算法 二、倍增算法的应用：求LCA（最近公共祖先）附模板题 三、倍增算法的应用：RMQ 问题（ST表）附模板题 一、倍增算法 要了解倍增之前，强烈建议大家先看一下这位大佬对倍增的解释：【白话系列】倍增算法 看完以后相信你已经对倍增有了大致初步的了解，下面给出倍增的定义 倍增 从字面的上意思看就是成倍的增长 ,这是指我们在进行递推时,如果状态空间很大,通常的线性递推无法满足时间和空间复杂度的要求 ,那么我们就可以通过成倍的增长,只递推状态空间中在 2 的整数次幂位置上的值作为代表 。当需要其他位置上的值时,我们只需要通过" 任意整数可以表示成...

P3834 【模板】可持久化线段树 1（主席树） 题解 P3834 【【模板】可持久化线段树 1（主席树）】 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<math.h> #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r)/2 #define over(i,s,t) for(reg...

P2016 战略游戏 这道题的城堡是一颗树 题中有 注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。 所以定义数组 f [ i ] [ 1 / 0 ...

树形DP 树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。整体的思路大致就是用树形的结构存储数据。 要学树形DP之前肯定是要先学会树和图的呀，至少先学会链式前向星，不会的话可以看一下我之前写的博客 链接：【图论】图，实现图（三种方式），二分图 详解 树形DP的关键和实现方法是 d f s dfs ...

undefined reference to ‘WinMain@16’ 意思为提示找不到 WinMain 函数，WinMain是windows程序的入口函数，有几种可能： int main() 写成了 int mian() ，int mani…，即找不到函数。 没写主函数main() 有可能是找不到一个参数字节总数为16个的XXX函数。 建议保存后关闭编译器重开，我的垃圾code::blocks出现这种情况我都是这么干的

P3924 康娜的线段树 我觉得挺难的，マ(ma)ジ(ji)や(ya)ば(ba)く(ku)ね(ne)（不得了了）知道康娜的应该都懂 题解 P3924 【康娜的线段树】 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<math.h> #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r)...

离散化 在一些问题中，我们只关心 n 个数字之间的相对大小关系，而不关心它 们具体是多少。 因此，我们可以用一种叫离散化的技术来将数字映射到 1 ∼ n 的整数， 从而降低问题规模，简化运算。 通常的实现方法是将所有数字排序，然后再重新遍历一遍所有的数字， 通过二分查找找到它们的 “排名”，然后用排名来代替对应的数字。 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<mat...

幸运数字Ⅱ 打表即可，观察数据，是一组简单的二叉树的树形结构，所以引申出这一类的题，比如题目为1，2，3，这三个数，那么就是一个三叉树 0 4 7 44 47 74 77 444 447 474 477 744 747 774 777 然后就可以以很短的代码和复杂度打表求解即可 #include<iostream> #include<stdio.h> #include<string.h> #i...

相似的子串 题目链接 时间限制：C/C++ 4秒，其他语言8秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format:%lld 题目描述 给定一个字符串，要求取出k个位置不相交的子串，且他们之间任意两个的最长公共前缀的长度均不小于x。现在给出k，求最大的x。 两个字符串str1，str2的公共前缀为x指str1和str2的长度均不小于x且这两个字符串的前x个字符对应相同。最长公共前缀即所有的公共前缀里最长的那个，如没有公共前缀则视为最长公共前缀长度为0。 输入描述: 第一行两个正整数n，k（2≤n≤200000，2≤k≤n）。第二行...

P3902 递增 尝试转化成已知的问题 : 如果原问题是非严格单调递增，则直接求出 L I S LIS LIS的⻓度，从n中减去就行了。 注意到这里的 a i ai...

数据结构和算法动态可视化 (Chinese) 刚发现的一个很有意思的网站，可以帮助理解算法和数据结构 数据结构的话基本上都齐了，可以选择翻译成中文

目录 最长上升子序列 一、朴素做法 O ( 2 n ) ...