###枚举与搜索-枚举：框定一个范围，遍历其中的所有东西。比如枚举左右端点成为一个区间。-搜索：从一个初始状态出发，一步一步走到相邻的状态，遍历能走到的所有东西。比如走迷宫。本质都是**用各种各样的策略去找东西**####枚举优化1.改变枚举对象：比如说从枚举左右端点改成枚举

基础算法枚举:框定一个范围,遍历其中的所有东西.搜索:从一个初始状态出发,一步一步走到相邻的状态枚举优化:1.改变枚举对象.2.倒叙枚举.3.减少枚举量.题1:颜色统计#include<iostream>usingnamespacestd;constintmaxn=2e5+10;intc[maxn];intvis[maxn];int

全文默认\(p\)为素数。用\(a,b\)代表任意整数，用\(x,y\)代表不是\(p\)的倍数的整数。Lemma0Part1直接的因式分解\[\begin{aligned}&a^n-b^n\\=&(a-b)\sum\limits_{i=0}^{n-1}a^ib^{n-1-i}\end{aligned}\]Part2凑\(a-b\)专用\[\begin{aligne

前置：偏序问题其实算不上前置，但是本篇是对这篇的补充。CDQ分治如果你学过归并排序，那你肯定知道归并排序的做法是先让前后两部分有序，然后进行合并，这与CDQ的思想是差不多的。CDQ的整体仍然是分治，递归处理左右区间，但不同的是，CDQ会考虑左区间对右区间的影响，并对于右区间或者答

原题链接：https://www.luogu.com.cn/problem/P4602题意解读：在一堆果汁中选出若干果汁，使得最小的美味度最大，且总体价格小于等于g，总体体积大于L，求这个最大的美味度。解题思路：显然，应该对答案进行二分，二分到一个美味度x，那么接下来check()函数要做的事，就是在所有美味度>=x的果汁中，查

传送门题目大意依次给定\(n\)个区间，并给定\(q\)个数，每个数依次经过这些区间时若在区间中则加1，问最后每个数变成了多少。做法显然如果直接模拟的话时间复杂度肯定是会炸的。首先我们注意到这道题是可以离线处理的，并且对于所有询问的数，我们如果先对他们排好序，在每个数都

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;intMax,Min,n,t;inta[N],b[N];boolcheck(intx){intlim=Max-x;intL=-1,R;for(inti=1;i<=n;++i){b[i]=a[i];if(a[i]<li

线段树是算法竞赛中常用的用来维护区间信息的数据结构。线段树可以在O(logN)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。建树voidbuild(intk,intl,intr){if(l==k){sum[k]=a[l];return0;

原题链接：https://www.luogu.com.cn/problem/P2839题意解读：求左端点在[a,b]之间，右端点在 [c,d]之间的子区间中，最大的中位数。解题思路：1、直男暴力法枚举左、右端点，然后排序计算中位数，这样的复杂度在n*n*logn，显然不可行。2、渣男巧妙法首先，要重新来看待何为中位数。设一段

简单手摸后发现，答案就是这么一个式子：\[(3^{n-1}-3^{n-2})a_1+(3^{n-2}-3^{n-3})a_1a_2+\dots+(3^1-3^0)a_1a_2\dotsa_{n-1}+a_1a_2\dotsa_n\]啊当然证明也是好证的，对于\(a_1\)这一项，它后面放+或-都会对系数加一，而放*不会影响系数，因此系数就是总数的三分之二。其它前缀

二分查找使用前提：有序数组用红蓝染色法理解二分查找数组中>=某个数的区间(闭区间写法)定义红色区间表示<target的区间，蓝色区间表示>=target的区间，[left,right]区间是还未确定的区间采用闭区间的写法，初始时闭区间范围为[0,n-1],即所有数都不确定，接着取中间下标mid，判断mid和ta

目录绿色通道最大连续和修剪草坪旅行问题绿色通道已经讲了好多遍了（2025/1/11，2024/12/21），现在详细捋一下思路首先上来，最有辨识度的就是“最长”空题段“最小”就是最大值最小——二分答案木材加工闻着味就过来了（详见2024/12/28）但这还和木材加工不太一样，check部分不

[线段树]本质为二叉树用来区间查询，区间修改，单点查询，单点修改运用结构体存储。structnode{ intsum,laze;}tree[N*4];//四倍空间//建树voidbuild_tree(intid,intl,intr){ if(l==r){ tree[id].sum=a[l]; return; } intmid=(l+r)/2; build_tree(id*2,l,mid)

CDQ分治主要用于解决偏序问题。在偏序问题中，以三维偏序居多。它是一种离线算法。其实严格来说，它是一种思想而不是算法。它依赖于归并排序。CDQ分治也可以用于1D/1D动态规划的转移，不过目前暂不涉及。偏序问题什么是偏序？先从一维偏序说起。一维偏序给定\(n\)个点，每个点

"""面试题3：数组中重复的数字在一个长度为n的数组里所有数字都在0~n-1的范围内，某些数字是重复的，找出任意一个重复的数字"""defduplicate1(numbers:list,length:int)->int:"""修改原数组"""ifnumbers==[]orlength<=0:

描述FarmerJohn建造了一个有 N（2≤N≤105)个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x1​,x2​,⋯,xN​（0≤xi​≤109）。他的 C（2≤C≤N）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，FarmerJohn想把这些牛安置在指定的隔间，所

海亮OJ题单维护差分信息P4243[JSOI2009]等差数列若要在序列上处理等差数列，可以考虑差分法。此时，我们不必将差分数组和数列中的元素一一对应（这会影响理解），而是将差分数组中的一个元素和原序列中对应的两个元素关联（我的理解盲区）。这样，使用线段树时，对于（差分数组的下标）区间\([

前言今天zty带来的是P1824进击的奶牛，大家给个赞呗，zty还要上学，发作品会少一点先赞后看养成习惯先赞后看养成习惯演示用编译器及其标准DevC++6.7.5RedpandaC++14正文进击的奶牛题目描述FarmerJohn建造了一个有

LibreOJ-3614Luogu-P9040很好的题。先不考虑区间，先想\(l=1,r=n\)的情况。考虑dp，\(f_i\)表示考虑\([l,r]\)的答案。则容易得到：\[f_i=\max\left\{f_{i-1},f_{i-k}+s_i-s_{i-k}\right\},f_0=0\]其中\(s\)为\(a\)的前缀和。这个转移本身是\(\Theta(n)\)的。遇

斜率优化DP例题HNOI2008玩具装箱朴素dp设\(dp_i\)表示前\(i\)个物品，分若干段的最小代价。状态转移方程为：\[dp_{i}=\min_{j<i}\left\{dp_{j}+\left(i-(j+1)+s_{i}-s_{j}-L\right)^{2}\right\}=\min_{j<i}\left\{dp_{j}+\left(s_{i}-s_{j}+i-j-1-L\right)^{2}\right\}

A.GrasshopperonaLine难度（个人感觉）☆☆☆☆☆Codeif(L%k==0){ans.push_back(1);ans.push_back(L-1);}else{ans.push_back(L);}B.ComparisonString难度（个人感觉）★☆☆☆☆思考：注意到最长链（指一些连续的位置，它们是单调的）是答案的下界，而实际上这是下

简介通过定义势能函数\(\phi(i)\)去描绘整个序列的势能从而推导正确的复杂度。例题P4145上帝造题的七分钟2/花神游历各国典。设\(\phi(i)\)表示第\(i\)个元素的势能。一个元素不停的开根一定会变成\(1\)，不妨将元素\(x\)改写成\(2^k\)的形式。一次开根会将\(

1.解释其实这个东西吧，是分治的分支优点：时间复杂度低，十分简单，方便写，适用绝大多数题目缺点：总有人眼瞎写错（）2.步骤1.在序列中确定中间数2.判断这数是不是，\(<\)的话去左边找，否则去右边找3.重复步骤直到中间数是要求的数字3.例题题目:洛谷P1873方法:朴素算法查找肯定超时，

Description如题，已知一个数列，你需要进行下面三种操作：将某区间每一个数乘上 xx；将某区间每一个数加上 xx；求出某区间每一个数的和。Input第一行包含三个整数 n,q,mn,q,m，分别表示该数列数字的个数、操作的总个数和模数。第二行包含 nn 个用空格分隔的整数，其中第 ii 个

数论函数及定理积性函数附OIWiki链接。定义对于函数\(f(x)\)，满足\(f(1)=1\)且\(\forall\gcd(a,b)=1,f(ab)=f(a)f(b)\)。则\(f(x)\)是积性函数。如果对所有\(a,b\)都成立，\(f(x)\)就是完全积性函数。例子欧拉函数\(\varphi(x)\)是积性函数。欧拉函数定义