【算法介绍】Boruvka 算法
算法简介：乌眼Boruvka 算法是一个不常用的计算最小生成树的算法，通过不断地合并一个一个的连通块使用贪心的思想在 log 的复杂度求出结果。
算法演示：鸦羽算法流程：心魔我们首先想到，对于点 u 和 v ，如果 v 是点 u 所有边中距离最短的点，那么这条边一定在最小生成树中。
那么不难做出第一步：把最短的边连起来，这样子就会把他们变成很多个连通块。这样的连通块最多有 n 个。
接下来，我们把每一个连通块都看成一个点，那么继续找出最短的那条边一直重复，这样的当我们把所有的连通块都变成一个连通块的时候，就得到了最优解。
每一次至少变成原来的二分之一，复杂度就是 $O(n+\cfrac n 2 + \cfrac n 4 + …)$ 也就是 $O(m\log n)$ 其中 m 是边的数量
算法例题：彻证大秦为你打开题目传送门
这道题目的话，是一个完全图，完全图的特点就在于边特别多，像 kruskal 算法这种按照边作为复杂度的东西，显而易见就是会超时的，所以说这是候我们的 boruvka 就上场了。我们发现这种位运算的操作可以通过一些数据结构维护，但是这样的操作过程似乎不可以用 kru ...
【历题回顾】CSP-S 2023 初赛程序题详解
感觉简单了这次
第十六题123456789101112131415#include <iostream>using namespace std;unsigned short f(unsigned short x) { x ^= x << 6; x ^= x >> 8; return x;}int main() { unsigned short x; cin >> x; unsigned short y = f(x); cout << y << endl; return 0;}
假设输入的 $x$ 是不超过 $65535$ 的自然数，完成下面的判断题和单选题：
判断题
当输入非零时，输出一定不为零。（）
解析：
异或操作左移右移不会搞掉我们原来有的 1，判对
（2 分）将 f 函数的输入参数的类型改为 unsigned int，程序的输出不变。（）
解析：
肯定一不一样，这种左移右移会自然溢出的东西，内存翻了倍可不是开玩笑 ...
【历题回顾】CSP-S 2022 初赛程序题详解
难度适中。
第十六题123456789101112131415161718192021222324252627282930313233#include <iostream> #include <string> #include <vector> using namespace std; int f(const string &s, const string &t) { int n = s.length(), m = t.length(); vector<int> shift(128, m + 1); int i, j; for (j = 0; j < m; j++) shift[t[j]] = m - j; for (i =0; i<= n - m; i += shift[s[i + m]]){ j =0; while(j < m && s[i +j] == t[j]) j++; ...
【历题回顾】CSP-S 2021 初赛程序题详解
这次的题目有点玄学（对于我这种数学不好的）所以说我就只能把所有的程序题都讲了~ （谁叫选择题那么简单！
我们还是老规矩尽量的模拟我做题时候的思路
第十六题1234567891011121314151617181920212223242526272829#include<iostream>#include <cmath>using namespace std;// 反三角函数，反余弦，cos(60) = 0.6 , acos(0.5) = 60, 60 在弧度制是 π / 3const double r = acos(0.5);int a1,b1,c1,d1;int a2,b2,c2,d2;inline int sq(const int x) { return x * x; }inline int cu(const int x) { return x * x * x; }int main() { cout.flags(ios::fixed); cout.precision(4); cin > ...
【历题回顾】CSP-S 2020 初赛后三题详解
最后三题似乎是有点代表性的难题，就挑着讲一讲罢，毕竟我基础的选择题都全对了后面的程序前两题也是一点小失误丢分不大，，，，
第十八题首先我们浅浅的看一看代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136// 这道题的编写者手写了几个数据结构，我们要注意一下。// 下面模拟一下顺序查看代码的过程#include <iostream>#include <queue>using namespace std;const in ...
【算法介绍】斜率优化优化动态规划
算法简介：猫爪冻冻这里我们讲的是斜率优化DP。需要用到较多的数学知识，算是 DP 优化中比较难的东西了。这里会尽量的去把它讲详细起来。斜率优化 DP 从字面上来讲就是通过斜率优化这个DP算法。接下来就从一个斜率优化的入门例题讲解下来。
算法演示：猎人射术例题选讲：猫尾隐藏菜单大秦 为你打开 题目传送门
有 $N$ 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 $N$ 个任务分成若干批，每一批包含连续的若干个任务。从时刻 $0$ 开始，任务被分批加工，执行第 $i$ 个任务所需的时间是 $T_i$ 。另外，在每批任务开始前，机器需要 $S$ 的启动时间，故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。
一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$ 。
请为机器规划一个分组方案，使得总费用最小。
部分分
数值
第一档
$n\le5\times10^3,1\le t_i,c_i\le100$
第二档
$n\le1 ...
【拾题杂谈】SP9084 Journey to Mars
题面大秦为你打开题目传送门
题目描述给你一个环形跑道，一开始你只能走 $0$ 公里（如果你选择了从第 $i$ 个节点开始的话，那就是 $p_i$ 公里），第 $i$ 个节点可以让你多走 $p_i$ 公里，第 $i$ 个节点距离下一个节点有 $d_i$ 公里。对于每一个节点，如果能从他出发顺时针或逆时针走遍所有空间站，输出 TAK 否则输出 NIE 。
思路那么遇到这种环上的问题，第一步就是破环为链。这样的话可以免去这个跳一圈算来算去的事情。
然后再看看题目，如果起始点一样的话顺时针和逆时针其实就是反过来算的关系，所以说我们就考虑一个方向，然后到时候反过来做一遍就可以了。那么方便起见先考虑顺时针。
那么根据上面我稍微缩减了的题面，从某一个节点加完油出来，到达下一个节点的这个过程，其实就是 $p_i - d_i$ 这样的过程。正的 $p_i$ 是加的油量，负的 $d_i$ 表示走这么一段路我们会花掉那么多的油量。
也就是说，这个点的贡献我们可以认为就是 $p_i - d_i$ 。那么我们一开始的油量是 $0$ 这样一个一个经过节点的过程，其实就是求前缀和的过程，如果某一刻前缀和小于等于 ...
【算法模板】洛谷P1886 滑动窗口
模板：单调队列首先给出自己封装好的模板吧。
12345678910111213141516template<typename T, unsigned int N, bool (*func)(T, T)>class MQueue {private : pair<T , int >q[N]; int hd, tl, len;public : inline void clear(int len) { this->len = len; hd = 0, tl = -1; } inline int size() { return tl - hd + 1; } inline bool empty() { return hd > tl; } inline void push(pair<T, int> ele) { while(!empty() && (*func)(ele.first, q[tl].first) ...
【算法介绍】单调队列优化动态规划
算法简介：寒苦回向首先看名字就知道这是一个基于 单调队列 的动态规划，请先确保对于这个基础知识点理解无误再阅读下面的文章。
单调队列优化 DP 基于一些题目的单调性使用单调队列以达到降低 DP 维度等的优化作用。
算法演示：起死回骸首先，为了保证大家对于单调队列的理解我们首先以一道单调队列的题目来回顾一下。
例题选讲 · 壹：冻冻回魂夜题目描述大秦 为你打开 题目传送门
一个含有 n 项的数列，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 m 项则从第 1 个数开始，若前面没有数则输出 0 。
这道题首先肯定是一眼单调队列了，为了断掉各位数据结构大神的念想 RMQ 是不可能的（似乎卡常也可以哎貌似）。我们就按照这个单调队列的思路走就是了具体是真没什么难度。
代码也不放了。
那么接下来就是单调队列优化DP的内容了。
例题选讲 · 贰：云来古剑法首先我们大可以先了解动态规划优化 DP 的原理。我们想到，单调队列中有这样的一个处理流程：
在窗口内处理的这些决策，有两种情况：
被排除的不合格决策。内层循环j排除的不合格决策，在外层循环i增大时，需要重复排除。
未被排除的 ...
【拾题杂谈】LuoguP1352 没有上司的舞会
题面大秦为你打开题目传送门
题目描述某大学有 $n$ 个职员，编号为 $1\ldots n$。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式输入的第一行是一个整数 $n$。
第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$。
第 $(n + 2)$ 到第 $2n$ 行，每行输入一对整数 $l, k$，代表 $k$ 是 $l$ 的直接上司。
输出格式输出一行一个整数代表最大的快乐指数。
样例 #1样例输入 #11234567891011121314711111111 32 36 47 44 53 5
样例输出 #115
提示数据规模与约定对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10 ...
