CF1699 Div.2 全场题解
A - The Third Three Number 问题Problem - A - Codeforces
题意给你一个整数 $n$，请输出三个数 $a, b, c$ 满足 $(a\oplus b) + (a\oplus c) + (b\oplus c) = n$。
题解考虑异或的性质 $(x\oplus x)=0,(x\oplus 0) = x$。
则很快可以得到若 $a=x,b=x,c=0$ 的情况下，原式的结果即为 $2x$。
那么直接输出 n/2 n/2 0 即可。
但是上述结论很显然只对于偶数成立，在样例中 $n$ 为奇数的只有一个，表现为无解。那么是否能证明所有的奇数都能证明无解呢？
对于二进制的末位进行考虑。发现不论是 $1,1,1$、$1,1,0$、$1,0,0$、$0,0,0$ 最后的末位之和都是偶数，也就是说，如果是奇数的 $n$，是永远不可能找到一个合法的 $a,b,c$ 来表示的。证毕。
B - Almost Ternary MatrixProblem - B - Codeforces
题意构造一个 $n\times m$ 的矩阵，满足要求：对于矩阵上任意一个 ...
【奇技淫巧】inline 的机制
书接上文
简单来说我认识了一个大佬，他对于 inline 的观点是：在单个文件的编译中，从语言的角度来讲，inline没有任何作用
所以说，他认为，inline 完全没有任何作用，我们加 inline 是没有任何意义的。
对于 GCC（我们的编译器）的官方文档：
GCC does not inline any functions when not optimizing unless you specify the ‘always_inline’ attribute for the functionTranslate : 你标了inline它也不会内联，它只认gnu::always_inline
在编译器开了优化时，内联不内联完全取决于编译器自己想法而不是看 inline 标记；而在编译器没有开优化时，他是不会做任何内联的；只有你指定 [[gnu::always_inline]] 才会“强制”让编译器内联
inline 的主要作用，并不是内联，而是允许重复定义。
这里所谓的重复定义，指的是：
一个可执行文件，经链接后一个符号的定义只能出现一次，这叫做单一定义原则（ODR）
但 i ...
【拾题杂谈】LuoguP3679 [CERC2016] 二分毯 Bipartite Blanket
题目大意大秦为你打开题目传送门
题目描述在二分图中，所有点被划分成了两个不相交的集合 $A$ 和 $B$，每条边都恰好连接着某个 $A$ 和某个 $B$。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配 $M$ 覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是 $M$ 中至少一条边的端点。
给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。
给定一个参数 $t$，请统计有多少点集 $V$，满足 $V$ 的权值不小于 $t$，且 $V$ 被至少一个匹配 $M$ 覆盖。
输入格式第一行包含两个正整数 $n,m$，分别表示 $A$ 集合的点数和 $B$ 集合的点数。
接下来 $n$ 行，每行 $m$ 个 01 字符，其中第 $i$ 行第 $j$ 列为 $1$ 表示 $A_i$ 和 $B_j$ 之间有一条边。
接下来一行包含 $n$ 个正整数 $v_1,v_2,\cdots,v_n$，分别表示 $A$ 中每个点的权值。
接下来一行包含 $m$ 个正整数 $w_1,w_2,\cdots,w_m$，分别表示 $B$ 中每个点的权值。
最后一行 ...
【算法介绍】李超线段树
文章总览：百脉甘津宁神久李超线段树，是一种维护带斜率的线段信息的线段树，早就听说了，所以今天跑过来填坑了。李超线段树也是属于线段树的变种，主要的应用也就是刚刚说的维护带斜率线段。并且因为他能维护这种特殊的几何结构，也可以用来编写斜率优化DP，所以说也算是比较重要的数据结构了。
下为本文大纲：
李超线段树推导
李超线段树模板
李超树应用基础
李超数应用斜优
算法推导：壶中洞天云螭眠
李超线段树推导
主要思想：云吟那么刚刚也说了，李超线段树就是一种维护带斜率的线段的线段树，一般来说查询的都是在一条垂直于 $x$ 轴的是线上我们插入的线段与其的交点中最顶端（纵坐标最大）的那一个。
很显然，我们对于每一个节点，只需要存储我们查询的时候的答案（我们将其称之为优势线段）即可。现在的问题是如何快速处理这个所谓的优势线段。
不难想到分类讨论处理插入的情况。如果插入的情况搞定了，查询就是易如反掌。
基础结构：雷音有了大概的思路，我们可以考虑以什么样的载体来存储这个李超线段树。很显然我们面对的是一个非常大的区间，毕竟每个线段的左右端点可以到 $x$ 轴很远很远的地方，那么这种时候我们就只有一种选择： ...
【奇技淫巧】费用流杂题选讲
T1 - Farm Tour题目传送门
题目大意现在有 $N$ 个节点，有 $M$ 条边，要从 $1$ 走到 $N$ 然后再回到 $1$。要求走的边不能重复，求最短路径。
解题思路很简单，我们直接把这个图作为网络的一部分，然后另外开一个源点和汇点，发送 2 的流量，走出来的一个最小费用最大流就是我们想要的答案。
正确代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149 ...
【算法介绍】点分治算法
文章总览：一心二用之术这个算法其实之前写过，但是写的一塌糊涂，所以说这里重新写了。这篇文章的主要内容是点分治算法，另外会额外拓展一些点分树的内容。点分治很显然就是基于点的分支，其详细内容会在下文介绍，大体分类属于树分治。本文讲述点分治与点分树，树分治就还剩下一个边分治了，接下来是本文大纲：
点分治思想
点分治例题
点分树思想
点分树例题
算法推导：理清逃跑路线那么还是来介绍一下点分治的概念。点分治呢其实是一种基于点在树上的分治，它基于点与树上路径的关系来快速统计一些树上路径的信息。在点分治中，路径可以分为两类：
经过当前根的。这个又可以分为端点为根或者两个端点都不为根。
不经过当前根的。
显然第一类中的第二个情况是可以通过第一个情况造成了两个链拼接而成，而不经过当前根的我们需要接下去递归处理，所以说这里是关于点分治正确性的一些简单证明。
然后我们来思考一个问题，点分治的分治逻辑是什么。因为说一般来讲树都是无根树，我们递归的顺序可以非常明显的影响到我们的复杂度。这个就不难想到是用重心了，因为重心每一次可以排除掉这棵树 $1/2$ 的大小，大大节约了我们的复杂度，这样的话点分治除去 ...
【奇技淫巧】斜率优化DP的几何理解
之前是讲过斜率优化DP的，只不过那时候还没有学过计算几何，所以说讲的不是很深，所以说这里来介绍一下如何从几何意义上也就凸包的角度理解斜率优化DP。
友情链接：
【算法介绍】斜率优化优化动态规划 | 祝馀宫
从例题出发题目传送门
题目大意给出 $N$ 个单词，每个单词有个非负权值 $a_i$，现在要将它们分成连续的若干段，每段的代价为此段单词的权值和的平方，还要加一个常数 $M$，即 $(\sum a_i)^2+M$。现在想求出一种最优方案，使得总费用之和最小。
解题思路首先我们进行一个暴力的推导，也就是最原始的转移方程式。
这个不难，我们对于 $i$ 只需要枚举一个断点即可，规定 $j$ 属于上一段的部分：
dp[i]=\min_{0\le j\lt i}\{dp[j] + (sum[i]-sum[j])^2 +M\}这个的转移显然是 $O(n^2)$ 的，接下来我们要对其进行优化，那么这就是斜率优化了。首先我们对于这个式子进行一些简单的移项，可以得到下面这个：
\begin{aligned}
dp[i]&=dp[j] + (sum[i]-sum[j])^2 +M\\
dp[i ...
【奇技淫巧】你真的会导嘛？
导数还是太有用了，这下不得不学了。导数的定义就是很简单的，一个函数每一个点上的斜率。这个斜率的求法其实本质上就是一个极限思想，推导也很简单，直接就是用斜率的计算公式即可。
f'(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x) - f(x)}{\Delta x}这篇文章主要是记一写导数的公式和易错点，不然我也容易忘。
特殊函数的导数从最基础的开始。
常数函数常数函数的斜率处处为 $0$，带入上面的公式也可以知道。
幂函数
f(x)=x^a\longrightarrow f'(x)=ax^{a-1}证明：
\begin{aligned}
f'(x)&=\lim_{\Delta x\rightarrow 0}\frac{(x+\Delta x)^a-x^a}{\Delta x}\\
&=x^a\lim_{\Delta x\rightarrow 0}\frac{(1+\frac{\Delta x}{x})^a-1}{\Delta x}\\
&=x^a\lim_{\Delta x\rightarrow 0}\frac{e^{a\ln(1+ ...
【奇技淫巧】网络流杂题选讲&上下界网络流
最近在做网络流的题目，接下来说几个我做到感觉有点意思题目。网络流问题其实全是模板，但是难就难在如何把问题抽象成网络流模型。
T1 - 狼抓兔子题目传送门
我是觉得这题的题面很史所以放过来。题目让我们求在能一网打尽的前提下，设置尽可能少的狼。这个所谓的一网打尽，其实是指我们选中一些边以后，不论 $S$ 到 $T$ 怎么走，都必须经过我们选中的边。如果了解了这个，那么就是模板的最小割了（你怎么知道我一开始没看懂在网上查了一圈题解全都是“一眼模板”）
T2 - 蜥蜴题目传送门
这题是一道经典的拆点题。因为石柱是有高度的，这个高度相当于是一个限制，所以说我们很容易就可以想到把一个石柱拆为两个点：一个称为石柱的顶端，一个称为石柱的底端。
那么我们可以这样理解题目中的几类操作：
放蜥蜴：建立超级源点 $S$，对于任意有蜥蜴的石柱，建立从 $S$ 到这个石柱顶端容量为 $1$ 的边。容量为 $1$ 是因为这个点只有一只蜥蜴，所以我们放也只能放一只。
石柱：对于每一个有高度的石柱，从石柱顶端连接到石柱底端，容量为高度。这样的话从这个石柱通过的蜥蜴数量就有了限制。
石柱互通：对于任意一对能够互相抵达的 ...
【算法介绍】2-SAT 问题
文章总览：高大的背影2-SAT 一开始觉得听玄学的，学了之后有感觉没什么好写，这篇文章简单说一下罢。
SAT 问题的定义
SAT 问题的解法
SAT 问题的例题
SAT 问题的细节
经典模型：紧紧的拥抱
SAT 问题的定义
首先我们了解一下 SAT 问题的定义。SAT 是英文单词适定性（Satisfiability）的简称，一般来说对于 k - 适定性问题，我们都简称为 k-SAT，这篇文章要讲的就是 2-SAT 问题，这是因为当 $k>2$ 的时候 k-SAT 问题是 NPC 问题（但是好像也有解决 k-SAT 的算法）总而言之，这里研究的是 2-SAT 问题。
简单的概括最基础的 2-SAT 的核心，就是对于 $n$ 个二元组。且存在一些形如 $\langle a,b\rangle$ 的矛盾关系，这代表 $a,b$ 不能被同时选中，这里保证 $a,b$ 不属于同一个二元组。问题就是要问存不存在一种方案，使得每一个二元组都选择出一个元素并且不出现矛盾的情况，有时还会让你输出具体的方案，显然方案是不唯一的。
其实这个问题其实并不难看出是可以抽象为图论的，有人的第一直觉就是二 ...