Ivanovcraft

摘要： 以下是我个人OI生涯中遇到的坑点的一个小总结，可能是我太菜了，总是掉坑里，请大佬勿喷1，多重背包的转移的循环顺序 //默认每个物品体积为一（不想打码……） //dp[i]表示占用背包容量i所能获得的最大价值 for(int i=1;i<=n;i++) for(int j=sum;j>0;j--) / 阅读全文

摘要： 贪心枚举最后方案中最大的h，设为maxh若某个人i的wi与hi均大于maxh，则此方案不可行若某个人恰有一个属性大于maxh，则可确定他是否换属性剩下的人按wi-hi从大到小排序后贪心选择O(nlogn+n2) 阅读全文

摘要： 转载请注明出处，部分内容引自李煜东《算法竞赛进阶指南》 前置知识： C++、C语言入门 Set是什么 Set是C++STL中提供的容器，set是数学上的集合——具有唯一性，即每个元素只出现一次，而multiset则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同 Set的相关操作 头文件 阅读全文

摘要： 搜索不知道为什么没有人写bfs觉得挺像是标准个bfs的 状态因为要统计次数，不能简单地跳过一个被经过的点这样的话，状态量会爆炸采用记忆化设dp[i][j][k]表示在第k分钟到达点(i,j)的方案数以地点+时间作为状态避免同一状态被反复拓展这样，状态量将减少至最多100*100*15 转移这就比较显 阅读全文

摘要： 一句话题意：在8 * 8的棋盘上，输出用最少步数从起点走到终点的方案数据很小，可以广搜无脑解决定义数据结构体 移动时新旧状态传递 判断是否可以拓展 打标记，入队 完整代码 阅读全文

摘要： 推荐一波数组模拟链表的讲解 这道题呢，数组写的话不好删除（因为后面要接过来），自然想到链表 对于一个果子，我们可以维护其前驱和后继，我们不妨记与一个点相邻的上面的点为其前驱，下面的点为其后继 观察到题目要求我们完成两种操作 1，跳，即遍历链表2，吃，即删除链表中元素 具体来讲删除就是普通的删除，不再 阅读全文

摘要： 做完发现居然没人用map搞映射特意来补充一发 很容易看出这是一道搜索题考虑搜索方案，如果按字符串转移，必须存储每种状态，空间复杂度明显会爆炸观察到每一位之间是互不影响的 考虑使用乘法原理搜索出每一位的情况总数，求它们的连乘积即为答案 时间复杂度O(n2^k)可以看出答案最大可以达到三十的十次方，会爆 阅读全文

摘要： 转载请注明出处，部分内容引自李煜东《算法竞赛进阶指南》 前置知识： C++、C语言入门 Map是什么 Map是从键（key）到值（value）的映射，其内部实现是一棵以key为关键码的红黑树 Map的相关操作 头文件 声明： 像这样： 就像其他需要排序的数据类型一样，key为一个结构体的map，需要 阅读全文

摘要： 拿到题目的第一眼 首先这是一棵n个节点的树（别说你看不出来） 然后对于树上的m条链我们可以选取树上的唯一一条边使它的边权变为0 求处理后最长链的长度 20分 m=1好啦，好像可做一眼望去全是水 只需求出一条链上的所有边并计算边权和及最大边权（暴力往上跳并记录即可）边权和减去最大边权即为答案那么我们就 阅读全文

摘要： 详细的链表讲解很明显的一个链表裸题和普通的链表有一个区别就是这个题可以O(1)插入，O(1)查询然后我们为了方便，采用双向链表，定义s、f作为指针数组更详细的解释见代码 阅读全文