CF1230 Div.2 全场题解
A - Dawid and Bags of CandiesProblem - A - Codeforces
题意四个数分给两个人，必须分完，每个数只能给一个人，一个人可以拿到多个数，数字不可以被拆分。问能否有一种分配方式使得每个人获得数字的和相等。
题解分类讨论：
三个小的 = 一个大的
最大最小 = 次大次小
B - Ania and MinimizingProblem - B - Codeforces
题意给出一个不含前导零的数字，你可以修改至多 $k$ 次，问修改后结果的最小值是什么
题解第一位优先改成一，其余位改成零
C - Anadi and DominoProblem - C - Codeforces
题意在一个有向图上，摆放多米诺骨牌，要求每个牌朝向同一个点的点数相同，每个牌只能用一次。
题解注意到 $n$ 的数据范围极小。
当 $n\le 6$ 时，最多只有 $15$ 条边，除去（1，1），（2，2）…六条边，每个节点对应一个数，给的边数 $m$ 即为可放置的骨牌数。
当 $n=7$ 时，因为每个顶点出发都只能为 $1\sim 6$，那么，必然第七个顶点会和前面 ...
CF1706 Div.2 全场题解
A - Another String Minimization 问题水
B - Making Towers很显然两个间隔为偶数的相同数字可以连在一起
C - Qpwoeirut And The City奇数显然。偶数可以认为是选择一个偶数前缀和奇数后缀，结束了。
D - Chopping Carrots不难想到枚举最小值然后二分 check，然后优化就是把最小值整除分块。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int , int > pii;typedef unsigned long long ull;namespace FastIO { ...
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+ ...
