线段树 题目链接 Tokitsukaze and Power Battle (easy) 思路 记 $[l, r] = \sum_{i=l}^{r}{a_i}$. 要在 $[L,R]$ 范围内按题意使 $[i,x] - [x+1,j]$最大，贪心的考虑，显然 $x+1=j$，并且 $i=R$.从而，问题可以转化为求 $[L, x-1] - [x,x]$ 最大，也即 $[L, x] ...

在数论领域中，欧拉函数是一种重要的概念，它在解决许多数学问题和密码学中起着关键的作用。本文将介绍欧拉函数的定义、性质、求法 以及一些常见的应用，帮助读者更好地理解和应用欧拉函数。 欧拉函数的定义 欧拉函数，也称为欧拉降幂函数，是指小于或等于正整数 $n$ 的数中与 $n$ 互质 的数的个数。 欧拉函数通常用符号 $\phi(n)$ 表示。 欧拉函数的性质 若 $n$ 为质数，则...

一道概率期望题，赛时以为是不会做的概率 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 ...