P3147 [USACO16OPEN]262144 P  想到合并，自然就想到区间dp，一个被合成的数之前是一个区间，并且由两个数比它小      1    1   1 的区间合成。可麻烦的是，我们并不知道之前的两个区间长度各是多少。这道题不像一般的区间dp，明确地知道一个区间的答案由哪些区间转移。 在这道题，我们只知道要合成ii，就要找到两个紧接着它的两个     i   −   1    i-1   i−1的区间。 既然如此，区间的长度是未知的，那我们设计状态的时候，把区间的长度设为转移的对象。 所以     f   [   i   ]   [   j   ]    f[i][j]   f...

向上取整函数 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 的整数次幂位置上的值作为代表 。当需要其他位置上的值时,我们只需要通过" 任意整数可以表示成若干个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(regis...

P2016 战略游戏  这道题的城堡是一颗树 题中有  注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。  所以定义数组     f   [   i   ]   [   1   /   0   ]    f[i][1/0]   f[i][1/0]表示的是节点i上放士兵或者不放士兵 根据题意,如果当前节点不放置士兵,那么它的子节点必须全部放置士兵,因为要满足士兵可以看到所有的边。 所以有     { }        { }        { }        { }        { }        { }        { }        { }        { }...

树形DP 树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。整体的思路大致就是用树形的结构存储数据。 要学树形DP之前肯定是要先学会树和图的呀，至少先学会链式前向星，不会的话可以看一下我之前写的博客 链接：【图论】图，实现图（三种方式），二分图 详解 树形DP的关键和实现方法是     d   f   s    dfs   dfs。 先找到树根，从树根开始运用      d   f   s    dfs   dfs 递归，跟     d   f   s    dfs   dfs一样先初始化，然后递归到叶子节点上为止，把最底层的      f   [   i   ]   [   j...

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)/2 ...

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

幸运数字Ⅱ  打表即可，观察数据，是一组简单的二叉树的树形结构，所以引申出这一类的题，比如题目为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> #include<algorithm> #include<queue> #include<math.h> #include<...

相似的子串 题目链接  时间限制：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）。第二行一个长度为n的仅...

P3902 递增  尝试转化成已知的问题 : 如果原问题是非严格单调递增，则直接求出      L   I   S    LIS   LIS的⻓度，从n中减去就行了。 注意到这里的     a   i    ai   ai都是整数，      a   i    <    a    i   +   1      a_i < a_{i+1}   ai​<ai+1​ 相当于      a   i    +   1   ≤    a    i   +   1      a_i + 1 ≤a_{i+1}   ai​+1≤ai+1​， 于是       a   1    <    ...

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

目录  最长上升子序列  一、朴素做法     O   (    2   n    )    O(2^n)   O(2n) 二、优化做法     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn) 三、例题引入：P1020 导弹拦截（求最长上升子序列和最长不上升子序列）  1.朴素做法暴力     O   (    n   2    )    O(n^2)   O(n2) 2.树状数组优化     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn) 3.二分优化     O   (   ...