一道概率期望题，赛时以为是不会做的概率 dp，赛后发现其实是个很简单的概率期望数学题，只要找到结论推出式子即可，非常简单。 题目大意 一个班有 $n$ 个孩子，其中 $m$ 对是朋友。其中 $i$ 对是朋友，他们的友谊值为 $f_i$ 。 老师要去 $k$ 次远足，每次远足她都会随机、等价、独立地选择一对孩子。如果选择了一对是朋友的孩子，他们的友谊值在 以后的所有远足 中都会增加 $1...

在一个图形中找到它的最大子矩形，是一类很经典的问题。通常是要求在一个大的区域内，有一些特殊点，要求找到区域内不包含特殊点的最大矩形。 这种问题根据数据的特征可以分为两类：区域小，特殊点多；区域大，特殊点少。 区域小，特殊点多的情况，可以开一个二维数组存图，利用“悬线法”解决；区域大，特殊点少的情况，由于区域大，二维数组存不下，可以对于每个点从左向右（从上到下）枚举它的右（左）边界来解决。...

单调队列常用于解决定长区间最值问题（滑动窗口），一般使用一个 deque 来实现。 与单调栈类似，每次向队尾 push 新元素时，新元素显然“离得近”，如果新元素不仅“离得近”，优先级还比当前队尾元素更高（更大/小），那么在以后当前队尾元素必然不可能成为答案，可以将其 pop_back 弹出。由于求解的是区间最值，因此单调队列的队首即为答案，注意每次取出答案前要先检查队首元素是否“过期”，...

单调栈是一种内部元素单调的栈，可以解决“左（右）边 第一个 更大（小）的数”的问题。 单调栈的精髓实际上在于，每次向栈顶 push 新元素时，新元素显然“离得近”，如果新元素不仅“离得近”，优先级还比栈顶元素更高（更大/小），那么在以后当前栈顶元素必然不可能成为答案，因此可以将其弹出。 P4147 玉蟾宫 这道题可以转化成“柱状图中最大的矩形”的模型。我们以每一行为底，求出这个底每个位...

欧拉筛法是一种高效的质数筛法，可以在线性时间内筛出一定范围内的所有质数。它的基本思想是遍历每个数，如果它是质数就把它的倍数都标记为合数。不同于普通的筛法，欧拉筛法在标记合数时采用了质数分解的思想，即每个数只会被最小的质因子筛掉，这样可以保证每个数只被筛一次，从而达到线性复杂度。 简介 筛法进行复杂度优化，所采用的一个惯用思路是：找到一个素数后，就将它的倍数标记为合数，也就是把它的倍数“筛...

树哈希是一种将树映射成整数的方法，常用于判断两棵树是否同构。 树哈希 我们有时需要判断一些树是否同构。这时，选择恰当的哈希方式来将树映射成一个便于储存的哈希值（一般是 32 位或 64 位整数）是一个优秀的方案。 树哈希定义在有根树上。判断无根树同构的时候，可以比较重心为根的哈希值，或者比较每个点为根的哈希值（树的大小相同，对哈希值排序后比较）。 以下是一种树哈希的构造方式： [f...

这是一道博弈论建图题目，通过对两个数组排序并用前缀最大值确定连边关系，反向建图后跑拓扑排序判断最终状态。 题目大意 Infinite Card Game 单卡和双卡在玩纸牌游戏。每张牌都有两个参数：攻击值和防御值。$s$ 能打败 $t$ 当且仅当 $s$ 的攻击值严格大于 $t$ 的防御值。 Monocarp 有 $n$ 张牌，其中第 $i$ 张的攻击值为 $\mathit{ax}_...

这篇博客记录了解决题目 CF1873F Money Trees 的思路和代码，其中使用双指针和二分答案的方法来找到满足条件的最长线段长度。 题目大意 有 $n$ 棵树，每棵树高 $h_i$，有 $a_i$ 个果子。 你可以选一对 $l$ 和 $r$，使得 $h_{i+1}\mid h_i\space(l\le i<r)$ 且 $a_l+a_{l+1}+\dots +a_r\le ...

CF1852B Imbalanced Arrays 题解 题目大意 对于一个给定的长度为 $n$ 的数组 $A$，定义一个长度为 $n$ 的数组 $B$ 是不平衡的当且仅当以下全部条件满足： $-n \leq B_{i} \leq n$ 且 $B_{i} \ne 0$。即每个数在 $[-n,n]$ 内且不为 $0$。 $\forall i,j \in...

CF1824B1 LuoTianyi and the Floating Islands 题解 题目大意 给定一棵 $n$ 个结点的树，现在有 $k(k\le \min(n,3))$ 个结点上有人。 一个结点是好的当且仅当这个点到所有人的距离之和最小。 求在这 $n$ 个点中随机取 $k$ 个点时，好的结点的期望个数，对 $10^9+7$ 取模。 思路 easy 版本的，首先发现，...