枚举
- 枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。
- 枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件：
(1)可预先确定候选答案的数量；
(2)候选答案的范围在求解之前必须有一个确定的集合。- 枚举算法简单粗暴，他暴力的枚举所有可能，尽可能地尝试所有的方法。虽然枚举算法非常暴力，而且速度可能很慢，但确实我们最应该优先考虑的！因为枚举法变成实现最简单，并且得到的结果总是正确的。
- 枚举算法分为循环枚举、子集枚举、排列枚举三种。
例题
[NOIP2011]铺地毯
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入描述
第一行，一个整数n，表示总共有n张地毯。
接下来的n行中，第i+1行表示编号i的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y轴方向的长度。
第n+2行包含两个正整数x和y，表示所求的地面的点的坐标（x，y）。
输出描述
输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
示例一
输入
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
输出
3
说明
如下图，1号地毯用实线表示，2号地毯用虚线表示，3号用双实线表示，覆盖点（2，2）的最上面一张地毯是3号地毯。
备注
对于30%的数据，有n≤2；
对于50%的数据，有0≤a,b,g,k≤100；
对于100%的数据，有0≤n≤10,000，0≤a,b,g,k≤100,000。
- 典型的枚举类型的题目（合适的枚举顺序）
- 初读题目，一般想法就是，从第一个一直枚举到第n个（中间若有满足条件的就直接输出），这道题如果从下往上——就是从被覆盖的地毯一直算到最上面的地毯，开销就比较大。但是这道题，如果从上往下——就是从最上面的地毯开始算，就比较简单而且正确率高
题解
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int main(){
int a[N],b[N],g[N],k[N],n,x,y,num=-1;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
scanf("%d%d",&x,&y);
for(num=n;num>0;--num){
if(a[num-1]<=x&&a[num-1]+g[num-1]>=x&&b[num-1]+k[num-1]>=y&&b[num-1]<=y) break;
}
cout<<num;
}
前缀和
前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。
[NOIP2005]校门外的树
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入描述
第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出描述
包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
示例一
输入
500 3
150 300
100 200
470 471
输出
298
备注
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
- 这道题是比较典型，比较简单的前缀和题目
- 依此累加树数量的状态，最后只需遍历一遍数组即可得到答案
- 注意一下——memset的用法（只能对char数组使用）
题解
#include<bits/stdc++.h>
using namespace std;
int main(){
int L,M,start,end,ans;
char a[10005];
scanf("%d%d",&L,&M);
memset(a, '1', L+1);
for(int i=0;i<M;++i){
scanf("%d%d",&start,&end);
memset(a+start, '0', end-start+1);
}
for(int i=0;i<strlen(a);++i){
if(a[i]=='1')++ans;
}
printf("%d",ans);
}
[CQOI2009]中位数图
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
输入描述
第一行为两个正整数n和b ，第二行为1~n 的排列。
输出描述
输出一个整数，即中位数为b的连续子序列个数。
示例一
输入
7 4
5 7 2 4 3 1 6
输出
4
备注
对于30%的数据中，满足 n \le 100n≤100；
对于60%的数据中，满足 n \le 1000n≤1000；
对于100%的数据中，满足 n \le 100000,1 \le b \le nn≤100000,1≤b≤n。
思路
- 遇到中位数的题首先有2个解法思路：1. 将大于中位数的记为1，小于的记为-1。2. 堆栈
- 明显这道题使用第一种方法，作出前缀和and后缀和即可。
- 不仅要标记好数字，还要设定好中位数子序列的位置关系（数字关系）
题解
#include<iostream>
using namespace std;
int n,b;
int a[100010];
int cnt[200020]; //这个数组用来记录中位数子序列，所以大小应为a[]数组的两倍
int main()
{
scanf("%d%d",&n,&b);
int pos =0;
for(int i =1;i<=n;++i)
{
scanf("%d",&a[i]);
if (a[i] > b) a[i] = 1;
else if (a[i] < b) a[i] = -1;
else pos = i;
}
int ans=0,sum=0;
for(int i=pos-1;i>=1;--i)
{
sum+=a[i]; //作出前缀和
cnt[sum+n]++; //在cnt[]数组标记好大于（小于）中位数的位置，如果sum为负数，那么cnt[]内应该是在n前面，就是小于中位数的位置
if(sum==0)ans++; //如果等于0，说明已经在前缀和满足了一个子序列
}
sum=0; //先清空sum，以免影响后续的循环
for(int i =pos+1;i<=n;++i)
{
sum+=a[i]; //作出后缀和
ans+=cnt[n-sum]; //如果sum>0，说明a[i]是>中位数的，那么在cnt[]中，它就要和n前面的<中位数的位置进行匹配
if(sum==0)ans++;
}
cout<<ans+1; //中位数本身就是一个子序列，所以+1
return 0;
}
后缀和
b[i]=a[i]+a[i+1]+…+a[n-2]+a[n-1];
二维前缀和
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]
[HNOI2003]激光炸弹
一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。
若目标位于爆破正方形的边上，该目标将不会被摧毁。
输入描述
输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。
输出描述
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。
示例一
输入
2 1
0 0 1
1 1 1
输出
1
备注
对于100%的数据，保证 1≤n≤104，0≤xi，yi≤5×103，1≤m≤5×103，1≤vi<100
思路
- 这道题涉及到二维前缀和，但这个知识点在这道题中不算难点
- 这道题难点在于，它需要注意很多细节
- 首先是正方形的边是不会被纳入摧毁价值的，我解决这个问题是将题目中的点都当作一个边长为1的小正方形。最后看边长为R的正方形中有多少个这样的小正方形。
- 确定好 全 正方形（即包含了所有价值点的正方形），筛选出符合题目的正方形（边长为R的正方形）
题解
#include<bits/stdc++.h>
using namespace std;
int main(){
int s[5005][5005];
int n,r,ans=0;
scanf("%d%d",&n,&r);
int max_x=r,max_y=r;
for(int i=0,x,y,v;i<n;++i){
scanf("%d%d%d",&x,&y,&v);
max_x=max(max_x,x+1); //维持最大的正方形
max_y=max(max_y,y+1);
s[x+1][y+1]+=v; //+1的目的：1.方便二维前缀和计算 2.将点化为正方形
}
for(int i=1;i<=max_x;++i){
for(int j=1;j<=max_y;++j) s[i][j]=s[i-1][j]+s[i][j-1]+s[i][j]-s[i-1][j-1];
}
for(int i=r;i<=max_x;++i){
for(int j=r;j<=max_y;++j) ans=max(ans,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]); //筛选出价值最大的、边长为R的正方形
}
printf("%d",ans);
}
差分
差分可以看成前缀和的逆运算。
差分数组
首先给定一个原数组a：a[1], a[2], a[3], a[n];
然后我们构造一个数组b ： b[1] ,b[2] , b[3], b[i];
使得 a[i] = b[1] + b[2 ]+ b[3] +, + b[i]
也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。
考虑如何构造差分b数组？
最为直接的方法：
如下：
a[0 ]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] =a [3] - a[2];
b[n] = a[n] - a[n-1];
我们只要有b数组，通过前缀和运算，就可以在O(n) 的时间内得到a数组 。
二分
题目描述
我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。
但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不关心这个不靠谱的游戏本身了，我们更关心裁判这个薛定谔的记得到底有几个是记得…
现在给出这个健忘的玩家的所有猜测和裁判的所有回答，问裁判最多能有多少次是记得目标数字的，即裁判的回复是符合情况的。
输入描述
第一行包含一个正整数n，表示裁判的回答数（也是玩家的猜数次数）。
接下来n行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。
输出描述
包含一个正整数，为裁判最多有多少个回答是正确的。
示例一
输入
4
5 .
8 +
5 .
8 -
输出
3
说明
当目标数组是5时，5 . 5 . 8 + 这三个回答都是正确的
备注
n≤100000
所有数的大小都小于int类型最大值。
思路
- 这道题涉及到了差分知识点
- 我们可以根据裁判给出的回答得出如果他回答正确的话那么正确的数据应该有哪些。记猜的数为a，如果符号是’.‘说明正确的数据是a；如果符号是’-‘说明正确的数据是[a+1,正无穷大],如果符号是’+'说明正确的数据是[负无穷大,a-1]。把每次说法对应的数据大小加1，在最后遍历所有数据，那么最大的一个就表示取它为目标数字就能得到最多的正确次数
- 通过上一条的做法，来构造差分数组
- 裁判两条相悖的语句会抵消掉其中一句
- 差分的前缀和得到的就是原数组，这里要注意差分数组不可以用int数组存储，因为我们这里用到了负无穷到正无穷，数据量过大，数组存不下。（int数组开辟不了那么多空间）
题解
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,num;
map<int,int> b;
char a;
scanf("%d",&n);
while(n--){
scanf("%d %c",&num,&a);
if(a=='.') ++b[num],--b[num+1]; //此时，num为猜到的数字（先不考虑裁判是否是正确的），所以++b[num]，b[num-1]需要--（因为要中和掉a=='-'的情况）
else if(a=='+') ++b[INT_MIN],--b[num]; //++的是b[INT_MIN]，因为当数据大了，直接选中无穷小就免去了计较小的数
else ++b[num+1]; //当a=='-'，后面的区间的数就要+1（这里b[INT_MAX]也可以）
}
n=num=0;
for(auto i:b){ //这个是for(auto ……)专门用于遍历容器元素的，当题中的这个i带&号时，就可以改变元素内容，没带就改变不了
num+=i.second;
n=max(n,num);
}
printf("%d",n);
}
尺取法
尺取法也叫双指针法
尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。
- 尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到根据其端点得到，那么尺取法便是不可行的
- 首先，明确题目所需要求解的量之后，区间左右端点一般从整个数组的起点开始，之后判断区间是否符合条件再根据实际情况变化区间的端点求解答案
字符串
题号：NC18386
题目描述
小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中，长度最短是多少。
输入描述
一行一个字符串S。只包含小写字母。S的长度不超过106.
输出描述
一行一个数字，代表最短长度。数据保证存在一个合法的S的子串。
示例一
输入
ykjygvedtysvyymzfizzwkjamefxjnrnphqwnfhrnbhwjhqcgqnplodeestu
输出
49
思路
- 这道题典型的尺取知识点
- 令j为右端点，i为左端点，然后在区间内判定是否满足 包含所有的小写字母 这个条件
- 长度即为右端点减去左端点
题解
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int len=s.size(),ans=len+1,alphabet[150]={0},cnt=0,j=0;
for(int i=0;i<len;++i){
while(j<len&&cnt<26){ //如果cnt==26就说明包含了所有小写字母，就退出右端点循环
if(alphabet[s[j]]==0) ++cnt;
++alphabet[s[j]]; //在字母表中为出现的字母标记
++j;
}
if(cnt==26) ans=min(ans,j-i);
--alphabet[s[i]]; //左端点移动，将相应的字母从字母表中移除
if(alphabet[s[i]]==0) --cnt;
}
printf("%d",ans);
}
丢手绢
题号：NC207040
题目描述
“丢、丢、丢手绢，轻轻地放在小朋友的后面，大家不要告诉她，快点快点抓住她，快点快点抓住她。”
牛客幼儿园的小朋友们围成了一个圆圈准备玩丢手绢的游戏，但是小朋友们太小了，不能围成一个均匀的圆圈，即每个小朋友的间隔可能会不一致。为了大家能够愉快的玩耍，我们需要知道离得最远的两个小朋友离得有多远（如果太远的话牛老师就要来帮忙调整队形啦！）。
因为是玩丢手绢，所以小朋友只能沿着圆圈外围跑，所以我们定义两个小朋友的距离为沿着圆圈顺时针走或者逆时针走的最近距离。
输入描述
第一行一个整数N，表示有N个小朋友玩丢手绢的游戏。
接下来的第2到第n行，第i行有一个整数，表示第i-1个小朋友顺时针到第i个小朋友的距离。
最后一行是第N个小朋友顺时针到第一个小朋友的距离。
输出描述
输出一个整数，为离得最远的两个小朋友的距离
示例一
输入
3
1
2
3
输出
3
备注
2≤N≤100000
距离和（圆圈周长）小于等于2147483647
思路
- 不能想当然认为位于中间的同学就是最大的距离，因为你通过尺取法设想一下就可以发现——假如，a–h(中间)的距离为10，那尺取法改变左端点变成b–i 距离为11，就跟一开始设想的不一样
- 运用尺取法，比较简单，由题意可以知道最大距离是不会超过总距离的一半的
- 其次，要注意的是封闭成一个圆形所需的数字关系
题解
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[100005],N,sum;
scanf("%d",&N);
for(int i=1;i<=N;++i) scanf("%d",&a[i]),sum+=a[i];
int j=1,total=0,ans=0;
for(int i=1;i<=N;++i){
while(total<sum/2) total+=a[(j++)%(N+1)]; //%总人数+1得到的总是会属于人生这个区间内，就模拟成一个⚪了
ans=max(ans,min(total,sum-total));
total-=a[i];
}
printf("%d",ans);
}
关于尺取法的总结
- 一般会出现循环嵌套，外边的循环i 作为左端点，里面的循环j 作为右端点，而且一般 j 是不需要复位的
- 右端点的循环结束条件来自题意
- 左端点的循环一般是从头到尾的
状态压缩、递推（枚举）
牛可乐的翻转游戏
题目描述
牛可乐发明了一种新型的翻转游戏！
在一个有 nn 行 mm 列的棋盘上，每个格子摆放有一枚棋子，每一枚棋子的颜色要么是黑色，要么是白色。每次操作牛可乐可以选择一枚棋子，将它的颜色翻转（黑变白，白变黑），同时将这枚棋子上下左右相邻的四枚棋子的颜色翻转（如果对应位置有棋子的话）。
牛可乐想请你帮他判断一下，能否通过多次操作将所有棋子都变成黑色或者白色？如果可以，最小操作次数又是多少呢？
输入描述
第一行两个整数 n，m(1≤n≤ 100,1≤ m≤ 10)n,m(1≤n≤100,1≤m≤10)，代表棋盘的行数和列数。
之后 nn 行，每行 mm 个数字，第 ii 个数字如果为 00 ，代表对应位置的棋子为白色，如果为 11 则为黑色。
输出描述
如果无法将所有棋子变成一个颜色，输出 “Impossible”(不含引号)，否则输出变成一个颜色的最小操作次数。
示例一
输入
4 4
1001
1101
1001
1000
输出
4
思路
- 这道题涉及到状态压缩、递推、枚举的知识点
- 确定了第一行的状态，就可以递推出后面的行的状态
- 二进制枚举
题解
还没有完全明白，等我学会了再放题解吧
枚举、字符串的补充
月月查华华的手机
题目描述
月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的QQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让华华发现，产生猜疑，破坏了他们的友情，月月决定只删华华有可能搭讪的推荐好友。
月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪，当且仅当小姐姐的昵称是他的昵称的子序列。为了方便，华华和小姐姐的昵称只由小写字母构成。为了更加方便，保证小姐姐的昵称长度不会比华华的长。
现在月月要快速的判断出哪些推荐好友要删掉，因为华华快回来了，时间紧迫，月月有点手忙脚乱，所以你赶紧写个程序帮帮她吧！
输入描述
第一行输入一个字符串A表示华华的昵称。
第二行输入一个正整数N表示华华的推荐好友的个数。
接下来N行，每行输入一个字符串Bi表示某个推荐好友的昵称。
输出描述
输出N行，对于第i个推荐好友，如果华华可能向她搭讪，输出Yes，否则输出No。
注意大写，同时也要注意输出效率对算法效率的影响。
示例一
输入
noiauwfaurainairtqltqlmomomo
8
rain
air
tql
ntt
xiaobai
oiiiooo
orzcnzcnznb
ooooo
输出
Yes
Yes
Yes
Yes
No
Yes
No
No
备注
1≤∣A∣≤106，1≤N≤106，1≤∑ Ni=1Bi≤106
思路
- 这道题在我看来可以使用尺取法，只不过具体细节不一样，因为是子序列（某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列）
- 左端点在 华华昵称 字符串上从左往右，右端点是满足子序列后或者遍历完 华华昵称 字符串
- 循环的条件就是 好友昵称 字符串
题解
#include<bits/stdc++.h>
using namespace std;
int main(){
string A;
char t[100005];
int N;
cin>>A>>N;
while(N--){
int m=0;
scanf("%s",t);
for(int i=0;i<A.length();++i){
if(A[i]==t[m]) ++m;
if(m==strlen(t)){
printf("Yes\n");
break;
}
}
if(m<strlen(t)) printf("No\n");
}
}