AcWing 蓝桥杯官方题. 48932.2023
原题链接
简单
作者:
YMYS
,
2024-04-02 21:53:18
,
所有人可见
,
阅读 24
//2024.4.2
//赛后补题
//https://www.lanqiao.cn/student/saas/htm1/brush-questions/academy/48932/?bank_id=105&saas_id=412
//ID:48932,2023
/*
思路:填空题做法,这里面ck函数的思想很牛逼,建议看看
*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
//判断是否包含2023
bool ck(int u)
{
vector<int> a;
//把u的每一位数都分别存进vector数组a里,注意这时候个位数在前面存着
while(u)
{
a.push_back(u%10);
u/=10;
}
//我们需要把他反转过来,因为我们要用2 0 2 3 这个顺序去搜索,而不是3 2 0 2这个顺序
reverse(a.begin(),a.end());
//这段代码很牛逼,思想很奇特。时间复杂度O(n)
//因为我们只需要判断是否存在2023即可,所以只要在前面发现了第一个2 我们在之后遍历的时候就不用再考虑第一个2了,直接判断时候找到了0.
//同理找到第一个0之后,我们就可以不用考虑这个0,直接去寻找第二个2
//注意:这里if判断条件里面的那个cnt_x > 0,是为了堵住这种情况:【前面还没找到,就去找后面的】。
int n=a.size();
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<n;i++)
{
if(a[i]==2) cnt1++;
if(a[i]==0 && cnt1>0) cnt2++;
if(a[i]==2 && cnt2>0) cnt3++;
if(a[i]==3 && cnt3>0) return true;
}
return false;
}
int main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//时间复杂度O(n^2),注意不要直接交代码,因为会TLE超时
//自己运行过以后,直接cout答案,这样的话O(1)
int ans=0;
for(int i=12345678;i<=98765432;i++)
{
ans+=ck(i);
}
cout<<(98765432-12345678+1)-ans<<endl;//bool转化为int
return 0;
}