单链表 AcWing 826. 单链表 实现一个单链表，链表初始为空，支持三种操作： 向链表头插入一个数； 删除第 kkk 个插入的数后面的数； 在第 kkk 个插入的数后插入一个数。 现在要对该链表进行 MMM 次操作，进行完所有操作后，从头到尾输出整个链表。 注意:题目中第 kkk 个插入的数并不是指当前链表的第 kkk 个数。例如操作过程中一共插入了 nnn 个数，则按照插入的时间顺序，这 nnn 个数依次为：第 111 个插入的数，第 222 个插入的数，…第 nnn 个插入的数。 输入格式 第一行包含整数 MMM，表示操作次数。 接下来 MMM 行，每行包含一个操作命令，操作命令可能为以下几种： H x，表示向链表头插入一个数 xxx。 D k，表示删除第 kkk 个插入的数后面的数（当 kkk 为 000 时，表示删除头结点）。 I k x，表示在第 kkk 个插入的数后面插入一个数 xxx（此操作中 kkk 均大于 000）。 输出格式 共一行，将整个链表从头到尾输出。 数据范围 1≤M≤1000001 \le M \le 1000001≤M≤100000 所有操 ...

笔者之前体验过 NexT 主题，由于

本讲代码模板：https://www.acwing.com/blog/content/277/ 快速排序 AcWing 785. 快速排序 给定你一个长度为 nnn 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行，第一行包含整数 nnn。 第二行包含 nnn 个整数（所有整数均在 1∼1091 \sim 10^91∼109 范围内），表示整个数列。 输出格式 输出共一行，包含 nnn 个整数，表示排好序的数列。 数据范围 1≤n≤1000001 \le n \le 1000001≤n≤100000 输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5 题解 123456789101112131415161718192021222324252627#include <iostream>using namespace std;const int kN = 1e5 + 10;int a[kN];void quick_sort(int l, int r) { if (l >= ...

数位DP 问题 往往是求一个区间中满足某种性质的数的个数。 技巧1 [X, Y] -> f(Y) - f(X - 1), f(N)：求0(或1)到N中满足性质的数个数 技巧2 树 易错点： main()中不执行init() 不能正确判断是否需要处理前导0，只有Windy数这种题型需排除前导0（第一层左支只能取1∼an−1−11\sim a_{n-1}-11∼an−1​−1） 不能判断n等于0时返回0还是1 AcWing 1081. 度的数量 求给定区间 [X,Y][X,Y][X,Y] 中满足下列条件的整数个数：这个数恰好等于 KKK 个互不相等的 BBB 的整数次幂之和。 例如，设 X=15,Y=20,K=2,B=2X = 15, Y = 20, K = 2, B = 2X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意： 17=24+2017 = 2^4 + 2^017=24+20 18=24+2118 = 2^4 + 2^118=24+21 20=24+2220 = 2^4 + 2^220=24+22 输入格式 第一行包含两个整数 XXX 和 YYY， ...

一般ACM或者笔试题的时间限制是1秒或2秒。 在这种情况下，C++代码中的操作次数控制在 107∼10810^7\sim 10^8107∼108 为最佳。 由数据范围反推算法复杂度以及算法内容 下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择： 数据范围 时间复杂度 算法 n≤30n\le 30n≤30 指数级别 dfs+剪枝、状态压缩dp n≤100n\le 100n≤100 O(n3)O(n^3)O(n3) floyd、dp、高斯消元 n≤1000n\le 1000n≤1000 O(n2)O(n^2)O(n2) dp、二分、朴素版dijkstra、朴素版Prim、Bellman-Ford n≤10,000n\le 10,000n≤10,000 O(n⋅n)O(n\cdot \sqrt n)O(n⋅n​) 块状链表、分块、莫队 n≤100,000n\le 100,000n≤100,000 O(n⋅logn)O(n\cdot logn)O(n⋅logn) 各种sort、线段树、树状数组、set/map、heap、、拓扑排序、dijkstra+h ...

贪心题型困难之处在于既无固定模板，也无固定套路。 往往需要先猜（做题经验很重要），然后证明方法的正确性（平时靠数学证明，笔试靠提交AC哈哈哈） 区间问题 AcWing 905. 区间选点 难度：简单 题目描述 给定N个闭区间[ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数N，表示区间数。 接下来N行，每行包含两个整数ai,bi，表示一个区间的两个端点。 输出格式 输出一个整数，表示所需的点的最小数量。 数据范围 1≤N≤105,1≤N≤10^5,1≤N≤105, −109≤ai≤bi≤109−10^9≤ai≤bi≤10^9−109≤ai≤bi≤109 12345678910输入样例：3-1 12 43 5输出样例：2 贪心 做法 将每个区间按右端点从小到大排序 从前往后枚举每个区间 若已包含点，则pass 否则(区间左端点 > 该点)，选择当前区间的右断端点 证明：求得点数为cnt，答案数为ans，即证cnt = ans ans < ...

背包问题 背包问题 每个物品数量 状态转移函数 01背包 1 f(i,j)=max(f(i−1,j),f(i−1,j−v)+w)f(i, j) = max(f(i -1, j), f(i -1, j - v) + w)f(i,j)=max(f(i−1,j),f(i−1,j−v)+w) 完全背包 无限 f(i,j)=max(f(i−1,j),f(i,j−v)+w)f(i, j) = max(f(i -1, j), f(i, j - v) + w)f(i,j)=max(f(i−1,j),f(i,j−v)+w) 多重背包 sis_isi​ 把物品i打包成logsilogs_ilogsi​个物品, 转化为01背包 分组背包 每组里只能选1个 f(i,j)=max(f(i−1,j−v(i,k))+w(i,k)),k=0,..,sif(i, j) = max(f(i - 1, j - v(i, k)) + w(i, k)), k = 0,..,s_if(i,j)=max(f(i−1,j−v(i,k))+w(i,k)),k=0,..,si​ 阎式DP法： 状态表示 ...

参考《Google 开源项目风格指南》 李开复这样评价这份指南：”我认为这是地球上最好的一份C++编程规范，没有之一，建议广大国内外IT研究使用。“ 视频推荐 Google编程风格指南学习 - 第一期 视频质量很高，可惜只有一期。 精华就在作者做的这张表中： 总结

AcWing版《剑指offer》的刷题笔记。 Week 1 找出数组中重复的数字★ 给定一个长度为 nnn 的整数数组 nums，数组中所有的数字都在 0∼n−10 \sim n - 10∼n−1 的范围内。 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。 请找出数组中任意一个重复的数字。 注意：如果某些数字不在 0∼n−10 \sim n - 10∼n−1 的范围内，或数组中不包含重复数字，则返回 -1； 数据范围 0≤n≤10000 \le n \le 10000≤n≤1000 样例 给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。 返回 2 或 3。 原地哈希 时间复杂度： O(n)O(n)O(n) 思路 nums[i] 的值为 nums[i], 而 nums[nums[i]] 元素的下标位置为 nums[i], 每次swap后nums[i]被放到下标为nums[i]的位置处(而i处的值nums[i]会变化)，因此不会死循环, while可以结束 while结束的条件是: nums[i] == nums[nums[i]] ...

笔者原计划在原博客中增加评论功能，以及让Google和百度收录自己的博客，没想到踩坑花了差不多整个上午+下午的时间，故写篇博客记录一下踩过的坑。 主要参考了 谢同学的博客 : : Hexo专栏 和一些官方文档，下面介绍一些自己踩过的坑： 搭建Waline 评论-Vercel设置环境变量时输错名 问题描述：在Vercel添加环境变量进行Redeploy后点击visit就可以前往评论页面了，结果登陆和注册都返回500（未初始），最后发现是环境变量名写错了。 解决方法：Vercel添加环境变量时，名称不是Lean Cloud而是对应的Vercel Environment名（自己应该早点想到：环境变量不都是大写字母和_组合的样子） Lean Cloud Vercel Environment AppID LEAN_ID AppKey LEAN_KEY MasterKey LEAN_MASTER_KEY 升级next至版本8以支持Waline 问题描述：在next的配置文件中添加waline支持后，发现执行hexo g && hexo s后报错，通过检 ...