算法 状压dp | 区间dp | 树形dp
状压dp棋盘型状压, 重点考虑行与行之间的转移. 首先枚举每行可能的状态, 预处理出合法行状态. 可以选择预处理出行与行之间的合法转移 f[i][j]代表处理完前i行, 第i行状态为j的xxx. 转移方程通过枚举前状态k来实现, 看k是否可以合法转移为j 玉米田 : 十字型 + 地图机制 123456789101112131415161718192021222324252627
算法 背包dp
关于”不大于””恰好””至少是”的讨论最标准的背包问题中, 装入背包的体积是要不大于m的, 但有些题目要求装入体积恰好是m, 或者至少是m, 思路一样, 但是初始化和最终获取答案的方式有区别. 12345// 不大于for(int i = 1; i <= n; i ++ ) for(int j = m; j >= v[i]; j -- ) f[j] = max(f[
算法 树状数组|线段树
树状数组 O(logn) 在某个位置上的数加上一个数, 单点修改 求任意某区间的前缀和, 区间查询 如果想用前缀和实现单点修改+区间查询, 需要O(n) + O(1) = O(n), 而树状数组中两种操作都是O(logn). tr[x] = ( x - lowbit(x), x ] , 每个tr[x]代表了这个一个区间内的前缀和 三大操作 : lowbit + add +
算法 差分
普通的差分其实很好理解, 就是将一次区间的加减操作换成了两个点的操作 : 12345void insert(int l, int r, int c, int b[]){ b[l] += c; b[r + 1] -= c;} 假设数组大小为n, 其对时间复杂度的贡献发生在区间操作很多时, 假定操作数为m, 那么差分就可以将时间复杂度O(nm)降到O(n), 一般不
算法 链表相关
将一个链表的前k个节点反转, 返回反转后的头节点 12345678910111213141516ListNode* reverseKList(ListNode* head, int k) { k--; ListNode* prev = nullptr; ListNode* cur = head; ListNode* next = head->next;
非暴力沟通 读书摘录
非暴力沟通帮助我们重新构建表达自己和聆听他人的方式, 使我们的言行不再只是出于自动化反应, 而是牢固地建立在觉察感受和需要的基础上, 做出有意识的回应, 我们既能诚实清晰地表达自己, 也能带着尊重与同理心关注他人, 从而在任何交流中听见自己和他内心深处的呼声. 由衷的给予和接受, 是人类天性所乐见的. 疏离生命的语言道德评判 作比较 推卸责任 要求 贴标签 疏离生命的语言让我们陷入充满评判的
算法 不等式 | 同余 + 破换成链
给定 𝑛 个整数 ℎ𝑖，每次操作会使 ℎ𝑖←ℎ𝑖+𝑎𝑖，求能否在若干次操作后使得 ℎ𝑖 的排名（从大到小）为 𝑡𝑖+1(就是前面有ti个)，如果可以，求最小操作次数，否则输出-1。 这个关键在维护一个区间集, 利用给出的目标排名确定不等式, 每个不等式成立都会给出一个区间, 然后加到这个区间集中 最后得到的区间集如果成立, 就是符合所有不等式的答案 设经过的天数为x 不等
C++线程库使用详解
核心操作线程创建12345678// 需要传入回调函数, 如果有参数紧跟在后面std::thread t1(print_hello, 1); // 当然lambda也可以当作回调函数传进去std::thread t([]() { std::cout << "Hello from lambda thread!" << std::endl;