文章目录
- 前言
- 一、连号区间数（枚举）
- 二、递增三元组（前缀和/sort+二分/双指针）
- 三、特别数的和（模拟）
- 四、 错误票据（排序、模拟）
- 五、回文日期（枚举、模拟）
- 六、归并排序
- 七、移动距离（模拟）
- 八、日期问题（枚举）
- 九、航班时间
- 十、外卖店优先级（模拟）
- 十一、逆序对数量（归并排序）
前言
枚举和模拟是蓝桥杯出现最多的内容。然后排序的话，不会去考察快排的手写，但是会考查归并排序。在蓝桥杯考察线段树的时候，大部分是用暴力来写。贪心和数论在蓝桥杯中考察的还是比较多的。
一、连号区间数（枚举）
任意门
判断一段数是不是连号区间：就是最大的数-最小的数=R-L，这样子就能判断是不是连续区间。
做这一类题目的时候，我们首先先去思考一下这种题目的纯暴力方法应该怎么写，然后，我们再去思考一下应该怎么优化。
#include <iostream>
#include <cstdio>
#include<algorithm>
using namespace std;
const int N=10010,INF=100000000;
int n;
int a[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int res=0;
for(int i=0;i<n;i++)
{
int minv=INF,maxv=-INF;//这里就是一般初始化最大值为负无穷，初始化最小值为正无穷
for(int j=i;j<n;j++)
{
minv=min(minv,a[j]);
maxv=max(maxv,a[j]);
if(maxv-minv==j-i)res++;
}
}
cout<<res<<endl;
return 0;
}
感觉其实这个的思维也是很巧妙！
二、递增三元组（前缀和/sort+二分/双指针）
任意门
即有多少个ai<bi,多少个bi<ci。
以bi为中心
方法一：前缀和（其思想就是以空间换时间）
方法二：sort+二分
方法三：双指针
前缀和
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
typedef long long LL;
int n;
int a[N],b[N],c[N];
int as[N];//as[i]表示在A[]中有多少个数小于b[i]
int cs[N];//cs[i]表示在C[]中有多少个数大于b[i]
int cnt[N],s[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]),a[i]++;//a[i]就是严格大于0的
for(int i=0;i<n;i++)
scanf("%d",&b[i]),b[i]++;
for(int i=0;i<n;i++)
scanf("%d",&c[i]),c[i]++;
//求as[]
for(int i=0;i<n;i++)cnt[a[i]]++;
for(int i=1;i<N;i++)s[i]=s[i-1]+cnt[i];
for(int i=0;i<n;i++)as[i]=s[b[i]-1];
//求cs[]
memset(cnt,0,sizeof cnt);
memset(s,0,sizeof s);
for(int i=0;i<n;i++)cnt[c[i]]++;
for(int i=1;i<N;i++)s[i]=s[i-1]+cnt[i];
for(int i=0;i<n;i++)cs[i]=s[N-1]-s[b[i]];
//枚举每个b[i]
LL res=0;
for(int i=0;i<n;i++)res+=(LL)as[i]*cs[i];
cout<<res<<endl;
return 0;
}
二分
lower_bound找出a中第一个大于等于当前元素的下标
upper_bound找出c中第一个大于当前元素的下标
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
typedef long long LL;
int n;
int a[N],b[N],c[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
for(int i=0;i<n;i++)
scanf("%d",&c[i]);
sort(a,a+n);
sort(c,c+n);
LL ans=0;
for(int i=0;i<n;i++)
{
LL aa=0,cc=0;
if(b[i]>a[0])aa=lower_bound(a,a+n,b[i])-a;
else continue;
if(b[i]<c[n-1])cc=upper_bound(c,c+n,b[i])-c;
else continue;
ans+=aa*(n-cc);
}
cout<<ans;
return 0;
}
三、特别数的和（模拟）
任意门
这道题的n比较小，所以可以用无脑暴力写，但是如果n比较大的话，所以可以数位dp来写，但是非常的麻烦。
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int ans=0;
bool judge(int i)
{
while(i)
{
int k=i%10;
if(k==2||k==0||k==1||k==9)
return true;
i/=10;
}
return false;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
if(judge(i)==true)
ans+=i;
}
cout<<ans;
return 0;
}
四、 错误票据（排序、模拟）
任意门
1、这一道题难得不是有多少个数，而是有多少行！
2、暴力思路很简单。
3、这里是排序的写法。set是一个动态的有序序列
4、我们也可以忽略那个第一个行数，我们可以一直读下去，直到读到空为止，这样子会比较简便。while(scanf(、、、)!=EOF)
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
const int N=10010;
int n;
int a[N];
int main()
{
int cnt;
cin>>cnt;
string line;
getline(cin,line);//忽略掉第一行的回车!!!
while(cnt--)
{
getline(cin,line);
stringstream ssin(line);//相当于scanf
while(ssin>>a[n])n++;
}
sort(a,a+n);
int res1,res2;
for(int i=1;i<n;i++)
{
if(a[i]==a[i-1])res2=a[i];//重号
else if(a[i]>=a[i-1]+2)res1=a[i]-1;//断号
}
cout<<res1<<" "<<res2<<endl;
return 0;
}
五、回文日期（枚举、模拟）
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_valid(int date)
{
int year=date/10000;
int month=date%10000/100;
int day=date%100;
if(month==0||month>12)return false;
if(day==0||month!=2&&day>days[month])return false;
if(month==2)
{
int leap=year%100&&year%4||year%400;
if(day>28+leap)return false;
}
return true;
}
int main()
{
int date1,date2;
cin>>date1>>date2;
int res=0;
for(int i=1000;i<10000;i++)
{
int date=i,x=i;
for(int j=0;j<4;j++)
date=date*10+x%10,x/=10;
if(date1<=date&&date<=date2&&check_valid(date))res++;
}
cout<<res;
return 0;
}
当然，我觉得这种方法并不是最好的，我觉得最好的是，判断年份，然后再判断是否成立。
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_valid(int date)
{
int year=date/10000;
int month=date%10000/100;
int day=date%100;
if(month==0||month>12)return false;
if(day==0||month!=2&&day>days[month])return false;
if(month==2)
{
int leap=year%100&&year%4||year%400;
if(day>28+leap)return false;
}
return true;
}
int transfer(int i)
{
int m=i,n;
while(m)
{
n=m%10;
i=i*10+n;
m/=10;
}
return i;
}
int main()
{
int date1,date2;
cin>>date1>>date2;
int s=date1/10000,e=date2/10000;
int res=0;
for(int i=s;i<=e;i++)
{
int x=transfer(i);
// cout<<x<<endl;
if(date1<=x&&date2>=x&&check_valid(x))res++;
}
cout<<res;
return 0;
}
六、归并排序
任意门
归并排序–分治
①确定分界点mid //这里和快排不一样的就是
②递归排序，left，right
③归并–合二为一★
（其实也就是）
也是一种双指针算法
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
const int N=10000010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
if(l>=r)return;
int mid=l+r>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
if(q[i]<=q[j])tmp[k++]=q[i++];
else tmp[k++]=q[j++];
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
for(i =l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++)printf("%d ",q[i]);
return 0;
}
七、移动距离（模拟）
任意门
问我们这两个编号的曼哈顿距离是多少（折线的距离，欧几里得距离就是直线的距离）
我们在这里把每一个数都-1，这样子的话，我们就可以得到：行号 n/w m/w
------列号 n%w m%w if(n/w是奇数）w-1-n%w
本质上是一维数组，我们找到他真实坐标。
考试的时候至少得把样例给过了，然后手动写一些自己所给的代码。
ps:位运算（&、|）的优先级比较低
+、-大于>>、<<大于&,|
C++运算符优先级
sizeof是一个运算符，而不是一个函数，所以后面不需要加括号
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int main()
{
int w,m,n;
cin>>w>>m>>n;
m--;n--;
int x1=m/w,x2=n/w;
int y1=m%w,y2=n%w;
if((x1&1)==1)y1=w-1-y1;
if(x2%2)y2=w-1-y2;
cout<<abs(x1-x2)+abs(y1-y2)<<endl;
return 0;
}
八、日期问题（枚举）
任意门
cin/cout是流式输入输出，printf/scanf是格式化输入输出
像有固定格式的时候，我们使用格式化输入输出会比较方便
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_valid(int year,int month,int day)
{
if(month==0||month>12)return false;
if(day==0)return false;
if(month!=2)
{if(day>days[month])return false;}
else {
int leap=year%100&&year%4==0||year%400==0;//判断是平年还是闰年
if(day>28+leap)return false;
}
return true;
}
int main()
{
int a,b,c;
scanf("%d/%d/%d",&a,&b,&c);//格式化输入
for(int date=19600101;date<=20591231;date++)
{
int year=date/10000,month=date%10000/100,day=date%100;
if(check_valid(year,month,day))
{
// if(year==2045&&month==12)cout<<date<<endl;
if(year%100==a&&month==b&&day==c||//年月日
month==a&&day==b&&year%100==c||//月日年
day==a&&month==b&&year%100==c) //日月年
printf("%d-%02d-%02d\n",year,month,day);//输出格式为两位，不足以0补齐
}
}
return 0;
}
九、航班时间
任意门
往西飞，飞行的时长是相差+时差。往东飞，飞行的时长是相差-时差
计算的区时=已知区时－（已知区时的时区-要计算区时的时区）
飞过去的时间t1=t+△h
飞回来的时间t2=t-△h
所以真实飞的时间=(t1+t2)/2
c_str()返回的是字符串数组的一个表现形式
sscanf他是格式化读取
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int get_second(int h,int m,int s)
{
return h*3600+m*60+s;
}
int get_time()
{
string line;
getline(cin,line);
if(line.back()!=')')line+="(+0)";//这个字符串的最后
int h1,m1,s1,h2,m2,s2,d;
sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
return get_second(h2,m2,s2)-get_second(h1,m1,s1)+d*24*3600;//算他们的时间秒数
}
int main()
{
int n;
scanf("%d",&n);
string line;
getline(cin,line);
while(n--)
{
int time=(get_time()+get_time())/2;
int hour=time/3600,minute=time%3600/60,second=time%60;
printf("%02d:%02d:%02d\n",hour,minute,second);
}
return 0;
}
十、外卖店优先级（模拟）
· 我们可以把两个订单之间的问题全部统一到下一次购买订单出现的时候来处理。如果是最后一段的话，那我们就同意到最后的T时刻来处理。
· 这样子的好处，我们就每次可以只考虑有订单的店，没有订单的店我们可以统一处理，这样子我们就少了一般的规模。
· 将所有订单按时间顺序排序，枚举每个订单，每一次处理一批订单,id,t,cnt
score[i]表示第i个店铺当前的优先级
last[i]表示第i个店铺上一次订单的时刻
st[i]表示第i个店铺当前是否处于优先缓存中
这里的T时刻就是最后时间
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=100010;
int n,m,T;
int score[N],last[N];
bool st[N];
PII order[N];
int main()
{
scanf("%d%d%d",&n,&m,&T);
for(int i=0;i<m;i++)scanf("%d%d",&order[i].x,&order[i].y);
sort(order,order+m);
for(int i=0;i<m;)
{
int j=i;
while(j<m&&order[j]==order[i])j++;
int t=order[i].x,id=order[i].y,cnt=j-i;
i=j;
score[id]-=t-last[id]-1;
if(score[id]<0)score[id]=0;
if(score[id]<=3)st[id]=false;
score[id]+=cnt*2;
if(score[id]>5)st[id]=true;
last[id]=t;
}
for(int i=1;i<=n;i++)
if(last[i]<T)
{
score[i]-=T-last[i];
if(score[i]<=3)st[i]=false;
}
int res=0;
for(int i=1;i<=n;i++)
res+=st[i];
printf("%d\n",res);
return 0;
}
十一、逆序对数量（归并排序）
任意门
1
0
5
10^5
105
∗
1
0
5
*10^5
∗105
/
2
=
5
∗
1
0
9
/2=5*10^9
/2=5∗109
这个样子会爆int，所以我们还是要用long long来存
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
const int N=100010;
long long int res=0;
int cmp[N];
long long merge_sort(int q[],int l,int r)
{
if(l>=r)return 0;
int mid=l+r>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j])
{
cmp[k++]=q[i++];
}
else
{
res+=mid-i+1;
cmp[k++]=q[j++];
}
}
while(i<=mid)cmp[k++]=q[i++];
while(j<=r)cmp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++)
q[i]=cmp[j];
}
int main()
{
int n;
cin>>n;
int q[N];
for(int i=0;i<n;i++)
scanf("%d",&q[i]);
merge_sort(q,0,n-1);
cout<<res<<endl;
return 0;
}