基本熟练掌握。

目录

• 1210. 连号区间数 【枚举 】
• 1236. 递增三元组 【枚举 / 前缀和 / hush定址法】
• 1245. 特别数的和 【简单】
• 1204. 错误票据 【简单】
• 466. 回文日期 【枚举】
• 787. 归并排序 【板子题】
• 1219. 移动距离 【找规律】
• 1229. 日期问题 【枚举】
• 1231. 航班时间 【模拟】
• 788. 逆序对的数量 【板子题】
• 1241. 外卖店优先级 【大模拟题】

1210. 连号区间数 【枚举 】

题目详解

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n; int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=1;i<=n;i++){int l=a[i],r=a[i];for(int j=i;j>=1;j--){l=min(l,a[j]);r=max(r,a[j]);if((r-l)==(i-j)) ans++;}}cout<<ans;return 0; }

1236. 递增三元组 【枚举 / 前缀和 / hush定址法】

https://www.acwing.com/problem/content/1238/

思路: 找中间的数组B 因为选B的话 剩下的A和C之间就没有影响了。
对于数组中的每一个B 的元素 我们只要统计A中小于它的数值有多少个，C中大于它的数值有多少个。
两者相乘，并求其和就为总的个数。

以A来说: 首先用一个数组来统计各个数据的个数。
再用一个数组 求其前缀和。这样就可以得到小于B的数组的元素个数。

y总的思路就是：
先说A(C和A的方法一样，就不赘述),用一个数组来统计各个数字出现的次数。
就是定址法。 再用一个前缀和，来统计每个小于等当前位置的所有的数的出现次数。
最后通过B的数的值来找到对应的前缀和，即找到了小于B的数出现的次数。

1.第一个问题： 为啥要统一加一？
统一加1的目的是为了防止数组越界。
2.第二个问题: 为啥前缀和的for 是从1~N
其实1~N指的是数据范围内 的前缀和。不要以为是 1~n，这只是我们数的个数，并不是数值的大小

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring>using namespace std;const int N=100010;int n; int a[N],b[N],c[N]; int cnt[N],s[N];//统计个数 ， 前缀和 int at[N],ct[N];//小于B的元素个数 大于B的元素个数int main(void) {cin>>n;for(int i=0;i<n;i++) scanf("%d",&a[i]),a[i]++;//统一加1，是为了避免数组越界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]++;for(int i=0;i<n;i++) cnt[a[i]]++;//统计各个数字出现的个数for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];//统计每个数字出现次数的前缀和 s[i] 表示1~i所有的数出现的次数的和for(int i=0;i<n;i++) at[i]=s[b[i]-1];//统计小于B的元素的个数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++) ct[i]=s[N-1]-s[b[i]];long long ans=0;for(int i=0;i<n;i++) ans+=(long long)at[i]*ct[i];cout<<ans<<endl;return 0; } #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],b[N],c[N],n; int cnt1[N],cnt2[N],aa[N],cc[N]; int s[N],ss[N]; long long int ans=0; int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>a[i],a[i]++,cnt1[a[i]]++;for(int i=1;i<=n;i++) cin>>b[i],b[i]++;for(int i=1;i<=n;i++) cin>>c[i],c[i]++,cnt2[c[i]]++;for(int i=1;i<N;i++) s[i]=s[i-1]+cnt1[i];for(int i=1;i<N;i++) ss[i]=ss[i-1]+cnt2[i];for(int i=1;i<=n;i++) aa[i]=s[b[i]-1],cc[i]=ss[N-1]-ss[b[i]];for(int i=1;i<=n;i++) ans+=(long long)aa[i]*cc[i];cout<<ans;return 0; }

1245. 特别数的和 【简单】

#include<bits/stdc++.h> using namespace std; int sum,n; bool judge(int x) {while(x){int t=x%10;if(t==2||t==0||t==1||t==9) return true;x/=10;}return false; } int main(void) {cin>>n;for(int i=1;i<=n;i++) if(judge(i)) sum+=i;cout<<sum;return 0; }

1204. 错误票据 【简单】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,a[N],k,cnt[N]; int main(void) {cin>>n;while(cin>>a[k++]);sort(a,a+k);int l,r;for(int i=0;i<k;i++){if(i&&a[i]-a[i-1]>1) l=a[i]-1;cnt[a[i]]++;if(cnt[a[i]]>1) r=a[i];}cout<<l<<" "<<r;return 0; }

466. 回文日期 【枚举】

https://www.acwing.com/problem/content/468/
暴力方法: 超时了

#include<iostream> #include<string> #include<algorithm> using namespace std; int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int data1,data2; int ans; struct data {int year;int month;int day; }d1,d2; bool judge(int n) {if(n%400==0||n%4==0&&n%100!=0) return true;else return false; } int main(void) {cin>>data1>>data2;d1.year=data1/10000;d2.year=data2/10000;d1.month=data1%10000/100;d2.month=data2%10000/100;d1.day=data1%100;d2.day=data2%100;if(data1==data2)//如果起始和结束的是同一天，特判。不特判的话后面的do while 会陷入死循环{string a;a=to_string(d1.year); if(d1.month<10)a=a+'0'+to_string(d1.month);elsea=a+to_string(d1.month);if(d1.day<10)a=a+'0'+to_string(d1.day);elsea=a+to_string(d1.day);int temp=a.size();for(int i=0;i<temp/2;i++){if(a[i]!=a[temp-1-i]){cout<<0<<endl;return 0;}}cout<<1<<endl;return 0;}do//因为包含起始和结束的日期所以用 do while{bool flag=true;string a;a=to_string(d1.year); if(d1.month<10)a=a+'0'+to_string(d1.month);elsea=a+to_string(d1.month);if(d1.day<10)a=a+'0'+to_string(d1.day);elsea=a+to_string(d1.day);int temp=a.size();for(int i=0;i<temp/2;i++){if(a[i]!=a[temp-1-i]){flag=false;}}d1.day++;if(judge(d1.year)){m[2]=29;}if(d1.day>m[d1.month]){d1.month++;d1.day=1;}if(d1.month==13){d1.month=1;d1.year++;}m[2]=28;if(flag)ans++;}while(d1.year!=d2.year||d1.month!=d2.month||d1.day!=d2.day);cout<<ans<<endl;return 0; }

巧妙的思路: 我们只要枚举前4位，组成回文数字，看是不是合法的日期就可以了。

#include<iostream> using namespace std;int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};bool judge(int n) {if(n%400==0||n%4==0&&n%100!=0) return true;else return false; }int data1,data2; int ans;bool check(int n) {if(judge(n/10000)) m[2]=29;int month=n%10000/100;int day=n%100;if(month==0||month>=13) return false;if(day==0||day>m[month]) return false;return true; } int main(void) {cin>>data1>>data2;for(int i=1000;i<=10000;i++){int temp=i;int x=i;for(int j=0;j<4;j++)//回文数字{temp=temp*10+x%10;x/=10;}if(temp>=data1&&temp<=data2&&check(temp)){ans++;}}cout<<ans<<endl;return 0; } #include<bits/stdc++.h> using namespace std; int l,r,ans; bool flag; int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; bool judge(int x) {if( (x%400==0) || (x%4==0&&x%100!=0)) return true;else return false; } bool check(int x) {string s=to_string(x);string temp=s;reverse(temp.begin(),temp.end());s+=temp;int year=stoi(s.substr(0,4));if(year<1000) return false;int month=stoi(s.substr(4,2));if(month==0||month>=13) return false;if(month==2&&judge(year)) m[2]=29;int day=stoi(s.substr(6,2));if(day<=0||day>m[month]) return false;x=stoi(s);if(x>=l&&x<=r) return true;else return false;m[2]=28; } int main(void) {cin>>l>>r;for(int i=1000;i<=9999;i++){if(check(i)) ans++;if(flag) break;}cout<<ans;return 0; }

787. 归并排序 【板子题】

https://www.acwing.com/problem/content/789/

#include<cstdio> using namespace std; const int N=100010; int a[N]; int 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;int i=l;//左区间的头 int 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(void) {int n; scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);merge_sort(a,0,n-1);for(int i=0;i<n;i++) printf("%d ",a[i]);puts("");return 0; }

1219. 移动距离 【找规律】

思路: 找下标和对应数的规律。

巧妙的一点在于: 整体减1。这样就少了很多的特判。
例如： 如果不整体减1 ， 1的行号=1/6=0 但是 6的行号=6/6=1 这显然不行，我们还得进一步的判断。
但是如果整体减1后 1-1=0/6=0 6-1=5/6=0 这样就少了特判。十分的方便。
一个字: 秒！

#include<iostream> #include<string> #include<cmath> using namespace std; int main(void) {int w,m,n; cin>>w>>m>>n;int x1,y1,x2,y2;m--,n--;//统一减1x1=m/w;x2=n/w;if(x1%2==0)y1=m%w;elsey1=w-1-m%w;if(x2%2==0)y2=n%w;elsey2=w-1-n%w;cout<<abs(x1-x2)+abs(y1-y2)<<endl;return 0; }

精简版:

#include<iostream> #include<string> #include<cmath> using namespace std; int main(void) {int w,m,n; cin>>w>>m>>n;int x1,y1,x2,y2;m--,n--;x1=m/w;x2=n/w;y1=m%w;y2=n%w;if(x1&1) y1=w-1-m%w;//行数是奇数if(x2&1) y2=w-1-n%w;//行数是奇数 cout<<abs(x1-x2)+abs(y1-y2)<<endl;return 0; } #include<bits/stdc++.h> using namespace std; int w,m,n; int x,y,xx,yy; int main(void) {cin>>w>>m>>n;x=(m-1)/w;xx=(n-1)/w;if(x%2==0) y=(m-w*x)%(w+1)-1;else y=w-(m-w*x)%(w+1);if(xx%2==0) yy=(n-w*xx)%(w+1)-1;else yy=w-(n-w*xx)%(w+1);cout<<abs(x-xx)+abs(y-yy);return 0; }

1229. 日期问题 【枚举】

https://www.acwing.com/problem/content/1231/

模拟写法:

#include<cstring> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; bool judge(int year) {if(year%400==0|| (year%4==0&&year%100!=0) ) return true;else return false; } struct date {int year;int month;int day; }d[10]; bool cmp(date a,date b) {if(a.year==b.year){if(a.month==b.month){return a.day<b.day;}return a.month<b.month;}return a.year<b.year; } int main(void) {int x1,x2,x3;scanf("%d/%d/%d",&x1,&x2,&x3);int sum=x1+1900;//x1为年 x2为月 x3为日 int number=0;if(sum>=1960&&sum<=2059){if(judge(sum))m[2]=29; if(x2>=1&&x2<=12){if(x3>=1&&x3<=m[x2]){d[number].year=sum;d[number].month=x2;d[number++].day=x3;}}m[2]=28;}sum=x1+2000;if(sum>=1960&&sum<=2059){if(judge(sum))m[2]=29; if(x2>=1&&x2<=12){if(x3>=1&&x3<=m[x2]){d[number].year=sum;d[number].month=x2;d[number++].day=x3;}}m[2]=28;}int sum2=x3+1900;//x1为月 x2为日 x3为年 if(sum2>=1960&&sum2<=2059){if(judge(sum2))m[2]=29; if(x1>=1&&x1<=12){if(x2>=1&&x2<=m[x1]){d[number].year=sum2;d[number].month=x1;d[number++].day=x2;}}m[2]=28;}sum2=x3+2000;if(sum2>=1960&&sum2<=2059){if(judge(sum2))m[2]=29; if(x1>=1&&x1<=12){if(x2>=1&&x2<=m[x1]){d[number].year=sum2;d[number].month=x1;d[number++].day=x2;}}m[2]=28;}int sum3=x3+1900;//x1为日 x2为月 x3为年 if(sum3>=1960&&sum3<=2059){if(judge(sum3))m[2]=29; if(x2>=1&&x2<=12){if(x1>=1&&x1<=m[x2]){d[number].year=sum3;d[number].month=x2;d[number++].day=x1;}}m[2]=28;}sum3=x3+2000;if(sum3>=1960&&sum3<=2059){if(judge(sum3))m[2]=29; if(x2>=1&&x2<=12){if(x1>=1&&x1<=m[x2]){d[number].year=sum3;d[number].month=x2;d[number++].day=x1;}}m[2]=28;}sort(d,d+number,cmp);printf("%d-%02d-%02d\n",d[0].year,d[0].month,d[0].day);for(int i=1;i<number;i++) {//去重 if( (d[i].year==d[i-1].year) && (d[i].month==d[i-1].month) && (d[i].day==d[i-1].day) )continue;printf("%d-%02d-%02d\n",d[i].year,d[i].month,d[i].day);}return 0; }

枚举写法: 操作简单，枚举所有的日期看是不是，是合法的日期，再看是不是和我们输入的日期相匹配。

#include<cstdio> #include<iostream> #include<string> using namespace std; int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int x1,x2,x3; bool judge(int n) {if(n%400==0|| (n%4==0&&n%100!=0) ) return true;else return false; } bool check(int a,int b,int c) {if(a==x1&&b==x2&&c==x3)return true;return false; } int main(void) {scanf("%d/%d/%d",&x1,&x2,&x3);for(int i=19600101;i<=20591231;i++){int year=i/10000;int month=i%10000/100;int day=i%100;if(judge(year)) m[2]=29;if(month>=1&&month<=12&&day>=1&&day<=m[month])//日期合法 if(check(year%100,month,day)||check(month,day,year%100)||check(day,month,year%100))//匹配 {printf("%d-%02d-%02d\n",year,month,day);}m[2]=28;}return 0; }

1231. 航班时间 【模拟】

https://www.acwing.com/problem/content/1233/

公式: 飞行时间=(两次时间差的和)/2

飞机在飞，由于人为规定的时区导致好像时间变慢或者快了（实际上没有）。这里很像我们高中物理学的运动学知识，我们可以假设一个场景——船在不平静水面行驶，船从一个点出发行驶了s路程后返回原点（期间船速不变），然后告诉我们来回整个过程回到原点的时间是t，问船在静水中行驶s路程需要多长时间。我们可以以水为参考系，那么显然这个时间为 t/2。

方法一:

#include<cstdio> #include<iostream> #include<string>using namespace std;int get_second(int h,int m,int s)//表示从00:00:00 到当前时间的秒数和 {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(void) {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; }

方法二:

#include<bits/stdc++.h> using namespace std; int getTime(void) {int h1,m1,s1,h2,m2,s2,d=0;scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);int time=d*24*3600+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);return time; } int main() {int t;scanf("%d",&t);for(int i = 0; i < t; i++){int time1=getTime();int time2=getTime();int t=(time1+time2)/2;printf("%02d:%02d:%02d\n", t/3600, t/60%60, t%60);}return 0; } #include<bits/stdc++.h> using namespace std; int n; int get() {string s; getline(cin,s);int a,b,c,aa,bb,cc;sscanf(s.c_str(),"%d:%d:%d %d:%d:%d",&a,&b,&c,&aa,&bb,&cc);int sum=0;if(s.find('+')!=-1){string ss=s.substr(s.find('+')+1,1);aa+=stoi(ss)*24;}sum=aa*3600+bb*60+cc-a*3600-b*60-c;return sum; } int main(void) {cin>>n;string s; getline(cin,s);while(n--){int sum=(get()+get())/2;printf("%02d:%02d:%02d\n",sum/3600,(sum%3600)/60,sum%60);}return 0; }

788. 逆序对的数量 【板子题】

https://www.acwing.com/solution/content/2103/

思路: 就是用到了归并排序。归并排序有一个特点就是分割的区间都是有序的，即递增的。

#include<cstdio> #include<iostream> #define LL long long using namespace std; const int N=100100; int a[N],temp[N]; int n; LL res; 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(a[i]<=a[j]) temp[k++]=a[i++];else{res+=mid-i+1;//重中之重temp[k++]=a[j++];}}while(i<=mid) temp[k++]=a[i++];while(j<=r) temp[k++]=a[j++];for(i=l,j=0;i<=r;i++,j++) a[i]=temp[j]; } int main(void) {scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);merge_sort(a,0,n-1); cout<<res;return 0; }

为啥 res+=mid-i-1 ？ 这是因为:
数组a中的i ~ mid的数组是递增数组， 触发条件是a[i] > a[j]，所以i~mid中的数字都比当前a[j]大，
所以左边i ~ mid的数组中有 mid - i + 1个数比a[j] 大

1241. 外卖店优先级 【大模拟题】

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,t,ans; map<int,vector<int> >mp; int st[N]; int main(void) {cin>>n>>m>>t;while(m--){int a,b; cin>>a>>b;mp[b].push_back(a);}for(auto i=1;i<=n;i++){sort(mp[i].begin(),mp[i].end());int score=0,index=0;for(int j=0;j<mp[i].size();j++){int cnt=1;int k=j;while( ( (k+1) < mp[i].size() ) && (mp[i][k]==mp[i][k+1]) ) cnt++,k++;score-=(mp[i][j]-index-1);if(score<0) score=0;if(score<=3) st[i]=0;score+=cnt*2;index=mp[i][j];if(score>5) st[i]=1;j=k;}if(index<t) score-=(t-index);if(score<=3) st[i]=0;}for(int i=1;i<=n;i++) ans+=st[i];cout<<ans;return 0; }

总结

以上是生活随笔为你收集整理的第四章：枚举 模拟 排序习题 【完结】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。