heyZzz's OI Blog

习题 首先： 要说树状数组，就必须要说 $\operatorname{lowbit}$。 那 $\operatorname{lowbit}$ 是什么呢？ 是一个数的二进制从右往左第一个 $1$ 的值。 例如，$\operatorname{lowbit}(14)$ 是 $2$，$\operatorname{lowbit}(16)$ 是 $16$。 那应该怎么求呢？ 是 $n&-n$，众所周知 $-n$ 是 $n$ 的补码，就是 $n$ 按位取反再加 $1$。 神奇的是，$n$ 这样一取反前面的 $0$ 都成 $1$ 了，再加一，$1$ 又变成 $0$ 了，但取反后第一个 $0$ 就成 $1$ 了，竟跟取反前一模一样！ 这样一来，只要第一个 $1$ 剩下来了。 我们在举个栗子： $6$ 的二进制是 $110$，补码是 $010$，$\operatorname{lowbit}(6)$ 就是 $2$。 $24$ 的二进制是 $11000$，补码是 $01000$，$\operatorname{lowbit}(6)$ 就是 $8$。 之后（进入正题）： 我们有一个数列（随便写的）：...

UB（未定义行为） 未定义行为就是你的代码出现了语言标准没有预料到的代码时，你的代码就会出现一些奇怪的错。 有时你的评测是对的，而这种错误会在 CCF 垃圾的评测环境中暴露出来，没注意到就会爆零。 printf 你一定要看好你输出的和 printf 中的类型是否一样，不然程序会错。 有符号整数溢出也是未定义行为。 返回值非 void 函数一定要有返回！ 错误示范： 1int x(int a){cout<<a;} 正确示范： 1int x(int a){cout<<a; return 1；} 数据结构 RE vector 下标越界。 vector、queue、deque、stack 等为空时进行 pop。 其它 int,long long 除以 $0$ 或模 $0$ 也是未定义行为。 文件读写 都是可以进迷惑行为大赏的。 freopen： 12freopen("题目名.in","r",stdin);freopen("题目名.out","w"...

收到 SH 的邀请，我去了浙大宁理学院打 ACM。 考前 找了同为 XXS 的 ybw，zhw，xzh。 开考！ T1 乱搞，橙题，但是因为行末输出了空格挂了好久。 $\Large \boxed{压力 \color{orange}中}$ T2 看 ybw 没做，先放着。 T3 水题，不用管。 T4 LCA 模版，调了一会儿，过了。但是别人都跳了这题。 T5 看 ybw 没做，先放着。 T6 小模拟，心态有点炸。 $\Large \boxed{压力 \color{red}高}$ T7 水题，不用管。 T8 一眼结论题，但是又调炸了（伏笔）。 T9 水题，不用管。 T10 没人做，超极大模拟，先放着。 又做 T2，发现单调栈忘了，死磕 ST 表，错了，心态爆炸。 $\Large \boxed{压力 \color{red}超高}$ T8 继续调无果。 赛后 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 过 $\color{red}单调栈$ 过 过 $\color{red}分层图$ 过 过 $\color{red}忘特判 r-l+1=2$。 过 $\colo...

食用方法，打开这个玩即可 🎯 游戏目标 扮演一名信息学竞赛选手（OIer），在3年高中生活中： 提升算法能力，争取在 NOIP 拿到省一/国集资格 平衡文化课、心态、体力、人际关系 解锁成就，书写你的 OI 故事 📊 状态面板说明 属性 含义 注意事项 💻 算法能力 你的 OI 水平，决定比赛成绩 >85 可冲省选，>95 有望国集 📚 文化课 学业成绩，避免班主任谈话 <40 会触发"班主任谈话"事件 🧠 心态 心理状态，影响发挥稳定性 <20 会触发"RE/MLE 崩溃"事件 💪 体力 身体状态，归零会强制住院 每回合自动 -2，注意休息 👥 人际关系 与同学/学长的关系 影响随机事件和求助成功率 💰 零花钱 购买书籍、饮料等道具 可通过兼职赚取 🎮 如何操作 基础操作 选择行动：点击下方 4 个行动按钮之一 查看日志：在"游戏日志"标签查看剧情发展 切换标签：点击顶部标签切换【日志/事件/日记/统计】 快捷键 ⚡ 1数字键...

排序的稳定性 排序算法 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 是否稳定 冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ $T$ 选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ $F$ 插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ $T$ 归并排序 $O(n~log~n)$ $O(n~log~n)$ $O(n~log~n)$ $O(n)$ $T$ 快速排序 $O(n~log~n)$ $O(n~log~n)$ $O(n^2)$ $O(log~n)$ $F$ 堆排序 $O(n~log~n)$ $O(n~log~n)$ $O(n~log~n)$ $O(1)$ $F$ 希尔排序 $O(n~log~n)$ $O(n)$ $O(n^2)$ $O(1)$ $F$ 计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(n+k)$ $T$ 基数排序 $O(n \times m)$ $O(n \times m)$ $O(n \times...

题目 T 1 最小生成树。 刚开始的解法 忽略 $tol_a+tol_b$，零分。 之后 设 $tol_x$ 为最小，向所有点建边。 12345int axx=min_element(tol+1,tol+n+1)-tol,tot2=0;for(int i=1;i<=n;i++) if(i!=axx){ if(mp[i*1000000+axx]) tot2+=min(tol[i]+tol[axx],mp[i*1000000+axx]); else tot2+=tol[i]+tol[axx];} 最后 要给整个图建如上的虚拟边： 123int axx=min_element(tol+1,tol+n+1)-tol;for(int i=1;i<=n;i++) if(i!=axx) a[++m]={i,axx,tol[i]+tol[axx]}; 只要跑个 kruskal 就行了。 T 2 暴力跑 dfs 回溯。 选择出这 $n$ 架飞机的降落顺序。 123456789101112void dfs(int d){...

家长直呼太暴力！这些算法可能会被删除 近日，洛谷网络科技有限公司多位用户家长向 @kkksc03 反映，部分算法存在血腥、暴力等不利于青少年儿童的因素出现，要求对相关算法进行整改或被删除。 洛谷网络科技有限公司题目组管理员在接受采访时说道，在最近几天内，洛谷收到了数十条家长来信，声称网站教授的部分算法存在“血腥”、“暴力”等内容。“他们说这些东西会教坏他们家的孩子，要求我们整改这些算法，把这些对小朋友不太好的东西删掉，或者直接把算法删除。” 随着国庆的到来，很多家长直接来到洛谷反映情况。记者在现场随机采访了几位家长，询问他们对这些算法的看法。 刘女士的儿子正在洛谷学习普及组内容。在采访中刘女士告诉记者，希望洛谷停开匈牙利算法。“我看里面讲的都是些一一匹配啊、二分图啊之类的匹配问题，这不是教孩子怎么找npy么？那他以后岂不是学会早恋了？”王先生也有类似的想法。他要求洛谷整改月赛内容。“听说课程里面有‘选妹子’，要是小朋友被女拳打了该怎么办？太危险了！” 认为数据结构太危险、容易伤到孩子，是很多家长的共同心声。王大爷今年已经六十多岁了，却依然专程跑到学校，高呼停止教授Splay树和T...

ST表 ST表它是解决 RMQ 问题（区间最值问题）的一种强有力的工具。 时间复杂度为 $O(n \log n+Q)$。 实现过程 PS：以下讨论的是最大值，最小值同理。 建立一个 $dp$ 数组 $dp_{i,j}$ 表示从 $i$ 开始 $2^j$ 个数中的最大值。 边界为 $dp_{i,0}=a_i$，即从 $i$ 点开始 $2^0$ 个数中的最大值。 我们不难发现 $\max{\max{a_1 … a_{\frac{n}{2}}},\max{a_{\frac{n}{2}} … a_n}}}=\max{a_1…a_n}$。 那状态转移方程为： $dp_{i,j}=\max{dp_{i,j-1},dp_{i+2^{j-1},j-1}}$。 其中 $dp_{i,j-1}$ 是前面一段，$dp_{i+2^{j-1},j-1}$ 是后面一段。 求最值 将该区间分成两个ST表，然后直接维护的小区间，然后二者求最值即可。 就是：$\max{f_{l,k},f[r−(2^k)+1][k]}$。

哈夫曼树： 哈夫曼树可由如下方式构造： 由给定的 $n$ 个权值构造 $n$ 棵仅含有一个根结点的二叉树，记作集合 $F$。 从集合 $F$ 中选取根结点权值最小的两棵二叉树 $T1$，$T2$ 作为左右子树构造新的二叉树 $T3$，新二叉树的根结点为 $T1$，$T2$ 根结点的权值和。 从集合 $F$ 中删除 $T1$，$T2$，将 $T3$ 加入 $F$ 中。 直到 $F$ 中只剩下唯一一棵二叉树为止，这棵树即为哈夫曼树。 建树： 字符 频率 编码 长度 A 35 11 2 B 25 00 2 C 15 01 2 D 15 101 3 E 10 100 3 哈夫曼编码： 哈夫曼编码根据字符在数据中出现的频率来分配不同长度的编码，频率高的字符分配较短的编码，频率低的字符分配较长的编码，从而实现压缩数据的目的，是一种贪心思想。 哈夫曼编码是一种前缀编码，即任一编码都不是其他任何一个编码的前缀。哈夫曼编码即为前缀编码中最短的。 带权路径长度(WPL)。 WPL 是每个编码的长度 $\times$ 频率。 字符 频率 编码 长度 WP...

PS：本文章因篇幅有限，就不讲矩阵乘法和快速幂了。 题目： $$F_n = \left{\begin{aligned} 1 \space (n \le 2) \ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$ 求 $F_n$。 定义一个矩阵$[Base]$，使： $$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}=\begin{bmatrix}F_{n+1},F_{n+2}\end{bmatrix}$$ 那： $$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}^2=\begin{bmatrix}F_{n+2},F_{n+3}\end{bmatrix}$$ $$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatri...