acwing-蓝桥杯C++ AB组辅导课-模拟、枚举与排序

题目1：连号区间数

题目链接：1210. 连号区间数 - AcWing题库

题意：题目给定一个区间，问有多少个子区间，满足在区间内的数字是连续的，比如像1,2,3就是连续的，1,2,4,就是断开的，从3这里断开。

思路：

暴力做法是枚举区间长度，查看区间是否满足要求，显然复杂度过大。

挖掘题目信息，发现题目给出的数字是一个排列，那么意味着数字不会重复，所以对于一段区间，只需要知道其最小值和最大值，并计算出差值就可以判断区间是否连续。

代码：

#include<bits/stdc++.h>

using namespace std;
int n;
int p[10010];
int main(){
    cin>>n;
    
    for(int i=0;i<n;i++) cin>>p[i];
    int res = 0;
    for(int i=0;i<n;i++){   
        int maxi = p[i],mini = p[i];
        for(int j=i;j<n;j++){
            maxi = max(maxi,p[j]);
            mini = min(mini,p[j]);
            // if(j == 2) cout<<maxi<<" "<<mini<<endl;
            if((maxi-mini) == (j-i)){
                // cout<<"["<<i+1<<","<<j+1<<"]"<<" ";
                res++;
            }
        }
        // cout<<endl;
    }
    cout<<res<<endl;
    
    return 0;
}

题目2：递增三元组

题目链接：1236. 递增三元组 - AcWing题库

题意：给出三个数组，问满足第一个数组中的数字<第二个数组中的数字<第三个数组中的数字的组合有多少。

思路：
暴力做法是枚举每个数组的每个数字，由于每个数组的大小为1e5，时间复杂度明显超限。

若要满足Ai<Bi<Ci，明显Bi起到了桥梁作用，连接了A数组和C数组，所以我们考虑枚举B数组中的元素，发现只要找到小于Bi的A数组中的元素数量和大于Bi的C数组中的元素数量，相乘就是对于Bi元素的答案。对于不同的Bi，累加就是最终答案。注意最终答案个数可能为N^3，所以要使用long long来存储，会爆int。

而求比Bi小/大的数字有多少个，有两种方法。

方法1：前缀和

前缀和本身是判断某个区间的数的和。这里可以用来判断数值从1-Bi个数的和。方法是先使用cnt数组存储每个数值数字的个数，比如cnt[1]表示数值为1的数字有多少个，再使用s数组计算前缀和进行统计，s[n] = cnt[n] + cnt[n-1] ... + cnt[1]。 为了减少边界问题，要令所有数字都加一。

方法2：排序+二分

代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;

int a[N];
int b[N];
int c[N];

int cnt[N];
int s[N];
int as[N],cs[N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i],a[i]++;
    for(int i=0;i<n;i++) cin>>b[i],b[i]++;
    for(int i=0;i<n;i++) cin>>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];
    for(int i=0;i<n;i++) as[i] = s[b[i] - 1];
    
    // cout<<as[1]<<endl;
    
    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]];
    
    long long res = 0;
    
    for(int i=0;i<n;i++){
        // cout<<as[i]<<" "<<cs[i]<<endl;
        res += (long long)as[i]*cs[i];
    }
    
    cout<<res<<endl;
    
    return 0;
}

?题目3：特别数的和

题目链接：1245. 特别数的和 - AcWing题库

题意：计算某个范围内有哪些数字的位中包含'2','0','1','9'，对数字求和。

思路：
循环，取数位，判断。需要注意的点就是，先把数位取出来，再做判断。

代码：

#include<bits/stdc++.h>

using namespace std;

bool check(int num){
    
    while(num){
        int yushu = num%10;
        if(yushu == 2|| yushu == 0|| yushu == 1|| yushu == 9) return true;
        num/=10;
    }
    return false;
    
}

int main(){
    int n;
    cin>>n;
    
    int res = 0;
    
    for(int i=1;i<=n;i++){
        int num = i;
        if(check(num)){
            // cout<<num<<" ";
            res += num;
        }
    }
    cout<<res<<endl;
    
    
    return 0;
    
}

?题目4：错误票据

题目链接：https://www.acwing.com/problem/content/1206/

题意：给出的数字理应是连续且不重复的，但其中存在一个重复的号码，和一个断开的号码，找出来这两个号码。

思路：

先排序，再遍历，重复的号码使用a[i] == a[i-1]判断，断开的号码使用(a[i] -a[i-1]) >= 2判断。

此处需要注意的是题目的读入，由于没有给出每一行数字的数量，可以考虑使用whlie(cin>>a[i])读入。

代码：

#include<bits/stdc++.h>

using namespace std;

int a[100010];
int main(){
    int n;
    cin>>n;
    n = 0;
    int num;
    string line;
    //  getline(cin, line); // 忽略掉第一行的回车
    while(cin>>a[n]){
        n++;
    }
    
    // for(int i=0;i<8;i++) cout<<a[i]<<" ";
    sort(a,a+n);
    
    // cout<<n<<endl;
    
    int res1,res2;
    
    for(int i=1;i<=n;i++){
        if(a[i] == a[i-1]) res1 = a[i];
        else if((a[i]-a[i-1]) >= 2) res2 = a[i]-1;
    }
    
    cout<<res2<<" "<<res1<<endl;
    return 0;
    
}

y总的代码（使用sstream读入）：

#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

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);

        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;
}

题目5：回文日期

题目链接：466. 回文日期 - AcWing题库

题意：题目给出两个日期，问在给出的两个日期之间有多少个日期从字符串的角度看起来是回文的。

思路：

由于题目给出的是两个8位数字，遍历两个数字之间的所有数字的时间复杂度明显过高。

找到题目隐含信息，回文串左边与右边对称，所以只需要枚举左边的年份，时间复杂度在1e4以内，然后根据对称写出右边的月日，再判断日期是否合法即可。由于根据给定日期判断还是比较麻烦，我们可以考虑扩大枚举范围，从0年到9999年全部遍历一遍，找到所有的回文日期，再判断是否处于给定日期期间就能有效降低代码复杂度。

下面用于判断日期是否合法的函数写的很好，可以用来当模板。

代码：

#include<bits/stdc++.h>

using namespace std;

int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (!month || month >= 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;
    if (month == 2)
    {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

int main(){
    
    int date1,date2;
    
    cin>>date1>>date2;
    
    int res = 0;
    
    for(int i=0;i<10000;i++){
        int x = i,r = i;
        for(int j=0;j<4;j++) r = r*10 + x%10,x/=10;
        if(r>=date1&&r<=date2&&check(r)) res++;
        
    }
    
    cout<<res<<endl;
    return 0;
}

习题1：移动举例

题目链接：1219. 移动距离 - AcWing题库

题意：数字按某个宽度依次排列，不过排列的顺序会在每行发生更改，奇数行从左到右，偶数行从右到左，给出两个数字，计算他们两个的曼哈顿距离。

思路：
给出两个数字，假如我们要算他们的曼哈顿距离，首先应该获取他们的坐标，所以先计算出坐标（行号列号），再计算出曼哈顿距离。

需要注意的是要让所有数字减一，目的是为了让每一行的所有数字除以行宽后得到的数字相同，不然每一行的最后一个数字会例外。

代码：
?

#include<bits/stdc++.h>

using namespace std;

int main(){
    
    int w,m,n;
    cin>>w>>m>>n;
    m--;n--;
    int l1,r1,l2,r2;
    
    l1 = m/w; r1 = m%w;
    l2 = n/w; r2 = n%w;
    // cout<<r1<<endl;
    if(l1%2!=0){
        r1 = w-r1-1;    //由于m--,所以需要再减一
    }
    
    if(l2%2!=0){
        r2 = w-r2-1;
    }
    // cout<<l1<<' '<<r1<<endl;
    // cout<<l2<<" "<<r2<<endl;
    cout<<abs(l1-l2)+abs(r1-r2)<<endl;
    return 0;
}

习题2：日期问题

题目链接：1229. 日期问题 - AcWing题库

题意：给出三个数字，给出可能的日期表示的三种日期。

思路：

可以直接特判三种情况是否真正有效，但代码复杂度会高一些。

根据题目，可以考虑直接枚举所有日期（日期都在1960年1月1日至2059年12月31日），代码会更加容易。

代码：

#include<bits/stdc++.h>

int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (!month || month >= 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;
    if (month == 2)
    {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

using namespace std;

int main(){
    
    int a,b,c;
    scanf("%d/%d/%d",&a,&b,&c);
    
    for(int i=19600101;i<=20591231;i++){
        int year = i/10000,month = i%10000/100,day = i%100;
        
        if(check(i)){
            if( year%100 == a && month == b && day == c||
                year%100 == c && month == a && day == b||
                year%100 == c && month == b && day == a
                )
            printf("%d-%02d-%02d\n",year,month,day);
        }
    }
    return 0;
    
}

习题3：航班时间

题目链接：1231. 航班时间 - AcWing题库

题意：意思差不多就是一去一回的时间加起来除2就是答案，时区之间的差值会在往返的过程中消去。这题主要考输入和时间的转换。

思路：
去一回的时间加起来除2，想要统一输入，可以在当天往返的时间后面手动加字符串(+0)便于统一处理。

需要注意的点在于输入，读入数字不会将末尾回车读入，所以后面读入字符串需要先使用getchar()读取回车，注意sscanf的用法，表示从字符串中读入数据。

代码：

#include<bits/stdc++.h>

using namespace std;

int get_time(string date){
    
    if(date.back()!=')') date += " (+0)";
    int h1=0,m1=0,s1=0;
    int h2=0,m2=0,s2=0;
    int day = 0;
    sscanf(date.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&day);
    
    return  h2*3600 + m2*60 + s2 - h1*3600 - m1*60 - s1 + day * 3600 * 24; 
}

int main(){
    
    int n;
    cin>>n;
    string line;
    getchar();
    while(n--){
        string date1,date2;
        getline(cin,date1);
        getline(cin,date2);

        int time = (get_time(date1) + get_time(date2)) /2;
        int h,m,s;
        h = time /3600; m = time %3600/60; s = time %60;
        
        printf("%02d:%02d:%02d\n",h,m,s);
        
    }
    return 0;
    
}

习题4：外卖店优先级

题目链接：1241. 外卖店优先级 - AcWing题库

题意：跟缓存有些相似，某时刻某id有订单，则优先级加二，若当前时刻没有订单，则优先级减一，当优先级大于5的时候进入优先缓存，当优先级小于等于3时移除优先缓存，问到最后的时刻有多少店铺在优先缓存中。

思路：

暴力做法是枚举所有的时刻，每一时刻对所有店铺进行操作，查看是否有该店铺的订单，明显时间复杂度过高。

挖掘题目信息，可以想见并不是所有时刻都有订单，有可能有很多订单都在同一时刻，在一批订单与一批订单之间的空白时间可能并没有订单，这样的时刻我们不必枚举，我们可以直接枚举订单，这样就可以跳过中间的空白时间从而大大减少时间复杂度。

而中间的空白时间应该减少多少的优先级呢，我们考虑使用last数组来存上一次增加优先级的时刻，当前时间减去last数组中的时间就是应该减去的优先级。

需要注意的地方在于边界，score[id] -= t - last[id] -1;中t时刻和last[id]时刻都是有订单的时刻，所以应该计算两个时刻中间的数量（比如2和5中间只有两个数字），而score[i] -= T-last[i];中T时刻是没有订单的，所以不需要减一。

代码：

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int N = 100010;
typedef pair<int,int> PII;

PII order[N];
int score[N];
int last[N];
bool st[N];
int main(){
    int n,m,T;
    cin>>n>>m>>T;
    for(int i=0;i<m;i++) cin>>order[i].x>>order[i].y;
    
    sort(order,order+m);
    
    for(int i=0;i<m;){
        int j = i;
        while(j<m&&order[i] == order[j]) j++;   //j会移动到不相同的点
        int id = order[i].y,t = order[i].x;
        int cnt = j-i;
        i = j;
        score[id] -= t - last[id] -1;
        
        if(score[id] <= 3) st[id] = false;
        if(score[id] < 0) score[id] = 0;
        
        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++)
        if(st[i])   res++;
    cout<<res<<endl;
    
    
    return  0;
}