kketchup的小窝

P4905 报纸【题目描述】在 $n\times n$ 的方阵中，称一个点为特殊点当且仅当此点横纵坐标不互质，即 $(i,j)$ 满足 $\gcd(i,j)\ne1$。 一次操作可以任选一个 $1\times 2$ 的矩形并覆盖，矩形不能超出边界，求使所有特殊点都被覆盖的最小操作数。 $n\le 233$（其实可以加强到 $500$）。 【题目解析】看到这个题首先想到打表，不直接输入特殊点，而是固定的，不就是让我们打表吗。 我们直接 $O(n^2\log n)$ 暴力算出所有特殊点的位置，然后标记为 $1$，依赖于 $1$ 的联通块大小会很大，爆搜枚举联通块摆放方案即可（好像爆搜不打表也直接能过）。 附上打好的表（前 $233$，答案为 $ans_n$）： int ans[300]={0,0,1,2,5,6,11,12,19,22,31,32,43,44,57,64,79,80,97,98,117,126,147,148,171,176,201,210,237,238,267,268,299,312,345,356,391,392,429,444,483,484,525,52 ...

Tarjan以前只是背过了板子，很容易忘，所以认真学习一下。 本文记录 $\text{Tarjan}$ 算法在图论中的应用，以备忘和总结。 因为不可抗因素（本人太菜），文章有问题欢迎指出。 “把原理搞明白，不要死记硬背” ——金牌教练找事 强连通分量 强连通，指有向图 $G$ 中任意两个点之间都有路径可达。 强连通分量，指有向图中的极大强连通子图。 前置知识-$\text{dfs}$ 树知周所众，有向图的 $\text{dfs}$ 树中边一般分为 $4$ 种。 随机构造一个有向图（下文中的“父子”关系来源于 $\text{dfs}$ 树）。 图中，黑边为树边，构成 $\text{dfs}$ 树；红边为反祖边，指子孙指向祖先的边；绿边为前向边，指祖先指向子孙的边；蓝边为横叉边，指走到一个访问过的结点，这个结点不是当前结点的祖先，两点之间的边（也就是旁系亲属）。 我们发现，若点 $u$ 是某个强连通分量中 $\text{dfs}$ 时走到的第一个点，那此点一定是这个强连通分量构成子树的根。（若不是，子树中一定有横叉边或者反祖边指向根，与假设“走到的第一个点”矛盾。） Tarjan ...

长链剖分基本定义长剖跟树剖很像，都是链剖分形式。区别在于，重儿子在树剖中定义为子树大小最大的儿子，而长剖中定义为子树深度最大的儿子。顺理成章地，不是重儿子的就是轻儿子，指向重儿子的边为重边，其余为轻边。重边所构成的链成为重链（为区别树剖与长剖，下文使用长链），特殊地，单节点也可作为一条重链。 接下来说说长剖的性质。 性质一：树上所有长链长度和 $O(n)$ 比较好理解，因为一个点只能存在于一条长链。 性质二：任意节点通过长链跳到根，最多跳 $O(\sqrt n)$ 次 因为每次跳到的长链都会比原来的长链长（否则长链就是这个了），所以最坏情况长链长度从 $1$ 到 $\sqrt n$，总共跳 $O(\sqrt n)$ 次。 树上 k 级祖先法 $1$：倍增预处理，复杂度 $O(n\log n)-O(\log n)$。 法 $2$：树剖，跳重链，复杂度 $O(n)-O(\log n)$，加二分可以做到 $O(n\log n)-O(\log\log n)$。 但还不够优秀！长剖做法可以做到 $O(n\log n)-O(1)$。 具体地，我们先倍增预处理 $2^k$ 祖先，还有每个长链 ...

莫比乌斯反演闲话从听说莫反高高仰望，到现在总算理解了皮毛，不禁慨叹。所以，我要珍惜，不留遗憾。 尝试写一篇能让初学莫反的新人可以看懂的文章。 感受推柿子的魅力吧！ 一些约定： $\mu(x)$ 表示莫比乌斯函数。 $(x,y)$ 表示 $\gcd(x,y)$，即最大公约数。 $\left \lfloor a \right \rfloor$ 表示向下取整，即取小于 $a$ 的第一个整数。 $a|b$ 表示整除，$a$ 整除 $b$，也就是 $a$ 是 $b$ 的因数。 $[p]$ 表示若 $p$ 为真则为 $1$，否则为 $0$。 在推式子时，默认取 $n\le m$。 引入莫反，就是通过反演形式更加方便地求函数的值。 原函数 $f$ 有一和函数 $F$，且 $F(n)=\displaystyle\sum_{d|n}f(d)$。我们的目标就是通过 $F$ 求 $f$。 先写几项 $$\begin{aligned}F(1)&=f(1)\\F(2)&=f(1)+f(2)\\F(3)&=f(1)+f(3)\\F(4)&&# ...

数学期望： 在概率论和统计学中，数学期望(mathematic expectation)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。——摘自百度百科不懂？太正常了，百度百科就是不写人话。举个栗子解释一下：在一次膜你赛中，小 z 预估自己有 $0.5$ 的概率考 $300$ 分，$0.3$ 的概率考250分，$0.2$ 的概率考 $200$分，计算方法与加权平均值有些类似，那她得分的数学期望即是： $0.5\times 300+0.3\times 250+0.2\times 200=265pts$。具体地，记第 $i$ 种结果的概率为 $p_i$，结果得分为 $f_i$，那么 $x$ 的期望 $E(x)=\sum_{i=1}^{x}p_i\times f_i$。注意，$\sum_{i=1}^{x}p_i=1$，即所有概率总和必须是 $1$。 Problem1 P4316 绿豆蛙的归宿题意简述给出一张 DAG，保证连通图，随机行走，求 $1$ 到 $n$ 的路径长 ...

CF1840C题解题目描述 题目传送门 $T$ 组数据，每组数据给定 $n$，$k$，$q$ 和一个长度为 $n$ 的数组 $a$，求 $a$ 中长度大于等于 $k$ 且最大值小于等于 $q$ 的序列个数。$\sum{n}\le 2e5$。 题目解析 解法一：数据结构解法 显然可以利用数据结构维护。考虑ST表预处理出区间最大值枚举区间左右端点累计，复杂度 $O(nlogn+n^2)$，需要优化。 再想想，若区间 $[i,j]$ 符合条件，则对于每个 $i\le k\le j$，区间 $[i,k]$ 都符合条件；若区间 $[i,j]$ 不符合，则对于每个 $j<k\le n$，区间 $[i,k]$ 都不符合，答案可二分。所以我们枚举左端点，二分右端点，复杂度 $O(Tnlogn)$。 解法二：数学解法 显然：一个区间符合条件，当且仅当此区间不存在一个 $i\in [i,j]$ 使 $a_i>q$。所以处理每一个 $a_i>q$ 的 $i$，统计区间长度。区间长度为 $m$ 的合法区间贡献即为 $\sum_{i=1}^{m}i$。而这个式子可以预处理，复 ...

[NOI2007] 货币兑换设 $f_i$ 表示第 $i$ 天最大的收益。 初始条件 $f_0=s$，答案 $f_n$。 转移枚举上一个全买券的点 $j$，设 $y$ 表示第 $j$ 天买 $B$ 的数量，解方程。 $Rate_j\times y_j\times a_j+y_j\times b_j=f_j$ 得到 $y_j=\large\frac{f_j}{Rate_j\times a_j+b_j}$ 设 $x$ 表示买 $A$ 的数量，显然 $x_i=Rate_j\times y_i$ 转移方程 $f_i=\max(f_{i-1},\max{a_i\times x_j+b_i\times y_j | j\in[1,i) } )$ 提出 $b_i$，得到 $f_i=\max(f_{i-1},b_i\times \max{\large\frac{a_i}{b_i}\small\times x_j+y_j})$ 发现变成一次函数形式，即对于每个 $x_j,y_j$，查询 $\large\frac{a_i}{b_i}$ 处的最大值即 ...

CF746G 题解闲话：2100的紫？ NOIP 集训，Smeow 讲图论，这是其中一个我觉得很妙的题，所以题解总结一下 qwq。没怎么写过题解，思路混乱请见谅。 传送门 题意：给一棵一共有 $n$ 个点的树，$t+1$ 层。第一层只有一个根节点，给出每层的节点数。已知有 $k$ 个叶子，求任意一种树的构造方案。 Solution：首先考虑构造一条链，满足题目 $t+1$ 层的要求，然后往上面挂节点。如果需要叶子，那么直接挂到这一层链上的节点，否则挂到上一层对应的节点（也是叶子），这样不会增加叶子数量，因为挂到上一层的叶子上会让叶子数量减 $1$，再加上新的，叶子数不变。记得判断无解，节点数不够叶子或有多余非叶子节点，具体实现看代码。第二种思路，先尽可能多地放叶子，再进行调整，把原来连在链上的点放到对应上层叶子减少叶子数，两种思路本质差别不大，这里只提供第一种实现。 const int N=2e5+10;int n,t,k;int a[N],fa[N];vector<int> v[N];//v[i][j]表示第 i 层第 j 个点（设首都是第 0 层） int cnt=1, ...

Splaysplay：伸展树，通过一系列的旋转维护平衡性。 注意，splay不一定是严格的平衡。故操作大部分均摊时间复杂度 $O(logn)$ 分3种情况讨论旋转： $1.$ Zig $or$ Zag $2.$ Zig-Zig $or$ Zag-Zag （一字型，从左偏树到右偏树) $3.$ Zig-Zag $or$ Zag-Zig （之字形转成一字型） 容易发现，旋转后树的中序遍历没有改变 splay的只因本操作旋转 无需分开写左旋右旋 inline void rotate(int x){ int y=t[x].fa; int z=t[y].fa; int k=(rs(y)==x); t[z].son[rs(z)==y]=x; t[x].fa=z; t[y].son[k]=t[x].son[k^1]; t[t[x].son[k^1]].fa=y; t[x].son[k^1]=y; t[y].fa=x; pushup(y); pushup(x);} 查找 与二叉搜索树的查找相同，从根 ...

并查集扩展前言： 本文不再赘述朴素的并查集，主要记录一些并查集的题目做法和并查集算法扩展。 扩域并查集 又称种类并查集。用于处理一些具有多个相互关系的并查集。一般朴素并查集判断是否在同一集合，扩域则判断多个集合的相互关系作用下（一般为排斥关系）是否在同一集合。本质上利用了并查集的传递性。 通俗地，朴素的并查集维护朋友，而扩域并查集可以维护朋友、敌人且满足敌人的敌人是朋友。 带权并查集 在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算。一般来说，带权并查集时只能使用路径压缩优化，不过在比赛中一般不会卡这个。 例题1 [HAOI2016] 食物链题目描述动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。 现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述： 第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。 第二种说法是 2 X Y，表示 ...