蓝桥杯第四讲枚举、模拟与排序

2023-11-22 22:00:40

一、枚举

1210. 连号区间数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10005;

int a[N],n,ans;
int Max,Min;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    for(int i=1;i<=n;i++)//两重循环算最值
    {
        Max = a[i],Min = a[i];
        for(int j=i;j<=n;j++)
        {
            Max = max(Max,a[j]);
            Min = min(Min,a[j]);
            if(Max - Min == j-i) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

1236. 递增三元组

1.排序+手写模板二分做法

注意：此处不同与模板二分，此处找的是小于或大于b[j]的第一个数，而不是找它本身，二分循环里无需出现等于号

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;

int n,a[N],b[N],c[N];
LL ans;
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(b,b+n);
    sort(c,c+n);
    for(int j=0;j<n;j++)
    {
        int l=0,r = n-1,x = b[j];
        while(l<r)//向右边二分查找，找到小于b[j]的第一个数
        {
            int mid = l + r + 1>>1;
            if(a[mid] < x) l = mid;
            else r = mid - 1;
        }
        if(a[l] >= x) continue;//找不到的话就枚举下一个b数
        //cout<<"<"<<b[j]<<" "<<l<<" "<<a[l]<<" a"<<endl;
        int i = l;
        l=0,r = n-1,x = b[j];
        while(l<r)//向左边二分查找，找到大于b[j]的第一个数
        {
            int mid = l+r>>1;
            if(c[mid] > x) r = mid;
            else l = mid + 1;
        }
        if(c[l] <= x) continue;//找不到的话就枚举下一个b数
        //cout<<">"<<b[j]<<" "<<l<<" "<<c[l]<<" c"<<endl;
         int k = l;
         ans += (LL)(i+1)*(n-k);//答案可能爆int
    }
    cout<<ans<<endl;
    return 0;
}

2.计数前缀和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;

int n,a[N],b[N],c[N];
int cnt_a[N],cnt_b[N],cnt_c[N];//计数前缀和，表示1~N中每个数出现的次数之和
LL ans;
int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        ++a[i];//因为要计算前缀和，映射到1~N+1较为方便
        ++cnt_a[a[i]];
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
        ++b[i];//因为要计算前缀和，映射到1~N+1较为方便
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&c[i]);
        ++c[i];//因为要计算前缀和，映射到1~N+1较为方便
        ++cnt_c[c[i]];
    }
    for(int i=1;i<=100001;i++)//求前缀和
    {
        cnt_a[i]+=cnt_a[i-1];
        cnt_c[i]+=cnt_c[i-1];
    }
    for(int j=0;j<n;j++)
    {
        int x = b[j];
        ans += (LL)cnt_a[x-1]*(cnt_c[100001] - cnt_c[x]);
    }
    cout<<ans<<endl;
    return 0;
}

466. 回文日期

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans;
int date1,date2;
bool isvalid(int date)
{
    if(date<date1||date>date2) return false; //日期不在范围内
    int year = date / 10000;
    int month = (date % 10000)/100;
    int day = date % 100;
    if(month < 1 ||month > 12) return false;//月份不合法
    if(month!=2 && day > days[month]) return false;//月份不为2，不考虑闰年的情况，天数超出当月的日数
    if(month==2) //特判2月的情况
    {
        int leap = (year%4==0&&year%100!=0) || year%400==0;//是否为闰年
        if(day > 28 + leap) return false;
    }
    return true;
}
int main()
{
    
    cin>>date1>>date2;
    
    for(int i=1000;i<10000;i++) //只枚举年份，推出回文日期，判断是否合法即可
    {
        int date = i,t = i;
        while(t)//创造出回文日期
        {
            date = date*10 + t%10;
            t/=10;
        }
        
        if(isvalid(date)) ans++;//合法答案++
    }
    cout<<ans<<endl;
    return 0;
}

1219. 移动距离

把号码都减去1，映射到0~N-1，模拟C++二维数组表示法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int w,m,n;

int main()
{
    cin>>w>>m>>n;
    --m;
    --n;
    int x1 = m/w,x2 = n/w;
    int y1,y2;
    y1 = x1%2==0?m%w:(w - 1 - m%w);
    y2 = x2%2==0?n%w:(w - 1 - n%w);
    cout<<abs(x1-x2) + abs(y1 - y2)<<endl;
    return 0;
}

1229. 日期问题

枚举范围内所有日期
判断合法性
判断是否为给出的三个数

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

using namespace std;
const int N = 10;

int a,b,c;
int year,month,day,date;
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
void check(int yy,int mm,int dd)
{
    if(mm < 1 || mm > 12) return;
    if(mm!=2 && (dd>days[mm] || dd<1)) return;
    if(mm==2)
    {
        int leap = (yy%4==0&&yy%100!=0)||yy%400==0;
        if(dd > 28 + leap || dd < 1) return;
    }
    if(yy%100==a && mm==b && dd==c || yy%100 == c && mm==b && dd == a || yy%100==c && mm==a && dd==b)
    printf("%04d-%02d-%02d\n",yy,mm,dd);
}
int main()
{
    scanf("%d/%d/%d",&a,&b,&c);
    for(int i=19600101;i<=20591231;i++)
    {
        year = i / 10000,month = (i % 10000)/100,day = i % 100;
        check(year,month,day);
    }
    return 0;
}

1231. 航班时间

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

int T,h1,m1,s1,h2,m2,s2,d;
int h3,m3,s3,h4,m4,s4;
int time1,time2;
char str[100];
int main()
{
    cin>>T;
    cin.getline(str,100);
    while(T--)
    {
        d = 0;
        cin.getline(str,100);
        if(strlen(str)==17)
        {
            sscanf(str,"%d:%d:%d %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2);
        }
        else sscanf(str,"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
        time1 = d*24*3600 + h2*3600 + m2*60 + s2 - (h1*3600 + m1*60 + s1);
        d = 0;
        cin.getline(str,100);
        if(strlen(str)==17)
        {
            sscanf(str,"%d:%d:%d %d:%d:%d",&h3,&m3,&s3,&h4,&m4,&s4);
        }
        else sscanf(str,"%d:%d:%d %d:%d:%d (+%d)",&h3,&m3,&s3,&h4,&m4,&s4,&d);
        time2 = d*24*3600 + h4*3600 + m4*60 + s4 - (h3*3600 + m3*60 + s3);
        int time = (time1+time2)/2;
        printf("%02d:%02d:%02d\n",time/3600,(time%3600)/60,time%60);
    }
    return 0;
}

1241. 外卖店优先级

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5+10;

int n,m,t,ts,id;
struct Shop //表示1~N家店
{
  int pr;//优先级
  int last;//上一次有订单的时刻
  bool st;//是否在优先缓存中
}shop[N];
struct Bill
{
    int t;//订单的时间
    int id;//店铺号
    bool operator<(struct Bill& b) const //重载小于号，排序原则
    {
        if(t!=b.t) return t<b.t;//时间从小到大
        else return id < b.id;//相同店铺号排在一起
    }
}bill[N];
int ans;
int main()
{
    cin>>n>>m>>t;
    for(int i=0;i<m;i++)
    {
        cin>>ts>>id;
        bill[i] = {ts,id};
    }
    
    sort(bill,bill + m);
    for(int i=0;i<m;i++)
    {
        ts = bill[i].t,id = bill[i].id;
        //先计算要减去多少
        int dsc = (ts==shop[id].last?0:(ts - shop[id].last - 1));//与上一订单时刻相等不用减，否则减去last+1~ts-1时段
        shop[id].pr = max(shop[id].pr - dsc,0);//结果比0小还是0
        if(shop[id].pr <= 3) shop[id].st = 0;//维护优先缓存
        
        shop[id].pr += 2;//计算此时刻有订单优先级加法
        if(shop[id].pr > 5) shop[id].st = 1;//维护优先缓存
        shop[id].last = ts;//维护last
    }
    
    for(int i = 1;i <= n;i++) //之前WA了好多次，问题就出在没有处理last到T时刻的无订单时的优先级减法计算
    {
        if(shop[i].last < t)
        {
            int dsc = t - shop[i].last;//减去t+1~last时段无订单时优先级减法计算
            shop[i].pr = max(shop[i].pr - dsc,0);//结果比0小还是0
            if(shop[i].pr<=3) shop[i].st = 0;//维护优先缓存
        }
    }
    for(int i = 1;i <= n;i++)
    {
        if(shop[i].st) ans++;//统计优先缓存中个数
    }
    cout<<ans<<endl;
    return 0;
}

码农公寓

一、枚举

1210. 连号区间数

1236. 递增三元组

1.排序+手写模板二分做法

2.计数前缀和

466. 回文日期

1219. 移动距离

1229. 日期问题

1231. 航班时间

相关文章