2023第十四届蓝桥杯国赛 C/C++ 大学 B 组
- 说明
- 试题 A: 子 2023
- 试题 B: 双子数
- 试题 C: 班级活动
- 试题 D: 合并数列
- 试题 E: 数三角
- 试题 F: 删边问题
- 试题 G: AB 路线
- 试题 H: 抓娃娃
- 试题 I: 拼数字
- 试题 J: 逃跑
说明
试题 F: 删边问题 没实现
（图片来源网络，侵删）试题 I: 拼数字 不会做
试题 J: 逃跑 不会做
（图片来源网络，侵删）试题 A: 子 2023
本题总分：5 分
【问题描述】
小蓝在黑板上连续写下从 1 到 2023 之间所有的整数，得到了一个数字序列：
S = 12345678910111213 . . . 20222023。
小蓝想知道 S 中有多少种子序列恰好等于 2023？
提示，以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：
1[2]34567891[0]111[2]1[3]14151617181920212223…
1[2]34567891[0]111[2]131415161718192021222[3]…
1[2]34567891[0]111213141516171819[2]021222[3]…
注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对：
1[2]345678910111[2]131415161718192[0]21222[3]…
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
【解释】
动态规划
当遇到字符 ‘2’ 的时候字符串 “2” 的数量+1，字符串 “202” 的数量加上字符串 “20” 的数量
当遇到字符 ‘0’ 的时候字符串 “20” 的数量加上字符串 “2” 的数量
当遇到字符 ‘3’ 的时候字符串 “2023” 的数量加上字符串 “202” 的数量
最后 “2023” 的数量就是答案
【代码】
#include #define int long long using namespace std; signed main(){ int dp[4]={0};//分别代表"2"、"20"、"202"、"2023"的数量 string s; for(int i=1;i//构造string s+=to_string(i); } for(int i=0;i//构造string if(s[i]=='2'){ dp[0]++; dp[2]+=dp[1]; }else if(s[i]=='0'){ dp[1]+=dp[0]; }else if(s[i]=='3'){ dp[3]+=dp[2]; } } cout1,1}; vector for(int i=2;i//欧拉筛求素数 if(f[i]==0){//如果没被标记过，那么i是质数 v.push_back(i); } for(int j=0;j f[v[j]*i]=1;//标记以i为最大因数的数为不是素数（除了1和本身） if(i%v[j]==0){//如果p[j]是i的因数，那么后面的数都不是以i为最大因数的 break; } } } long long ans=0; for(int i=0;i for(int j=i+1;j if(v[i]*v[i]*v[j]*v[j] int n; map int a; cina; ma[a]++; } int sum1=0,sum2=0; for(auto it:ma){ if(it.second=2){ sum1+=it.second-2; }else{ sum2+=it.second; } } if(sum1=sum2){ cout cout int n,m; deque int a; cina; q1.push_back(a); } for(int i=0;i int a; cina; q2.push_back(a); } int ans=0;//记录答案 while(!q1.empty()){ if(q1.front()==q2.front()){//相等直接出队 q1.pop_front(); q2.pop_front(); }else if(q1.front()q2.front()){//q2小就合并q2前面两个 q2[1]+=q2[0]; q2.pop_front(); ans++;//合并次数+1 }else{//q1小就合并q1前面两个 q1[1]+=q1[0]; q1.pop_front(); ans++;//合并次数+1 } } cout int n; cinn; vector int a,b; cinab; v.push_back({a,b}); } int ans=0;//统计答案 for(int i=0;i map int d=(v[i][0]-v[j][0])*(v[i][0]-v[j][0])+(v[i][1]-v[j][1])*(v[i][1]-v[j][1]);//距离的平方，就不开方了 double k=-1; if(v[i][1]-v[j][1]!=0){ k=(double)(v[i][0]-v[j][0])/(v[i][1]-v[j][1]);//斜率 } ans+=ma1[d]; ans-=ma2[{d,k}];//减去共线的数量 ma1[d]++; ma2[{d,k}]++; } } cout0,1,1,0,-1,0,0,-1};//四个方向 signed main(){ cinnmk; for(int i=0;i cins[i]; } memset(ans,0x3f,sizeof ans);//初始化最大值 q.push({0,1,0,0});//{0,1,0,0}分别代表走了0步，第1个相同字母，横坐标，纵坐标 ans[0][0][1]=0; while(!q.empty()){ vector int x=px+f[i][0];//下一个点的坐标 int y=py+f[i][1]; if(x=0&&x//得符合条件 if(s[px][py]==s[x][y]){//字母相同的情况 if(v[1]==k)continue;//到k了就不能走了 if(ans[x][y][v[1]+1]v[0]+1){//有更优的，更新 ans[x][y][v[1]+1]=v[0]+1; q.push({v[0]+1,v[1]+1,x,y}); } } else{//字母不相同的情况 if(v[1]!=k)continue;//不到k不能走不同字母 if(ans[x][y][1]v[0]+1){//有更优的，更新 ans[x][y][1]=v[0]+1; q.push({v[0]+1,1,x,y}); } } } } } int mi=ans[0][0][0]; for(int i=1;i mi=min(mi,ans[n-1][m-1][i]);//记录到达终点的最小值 } if(mi==ans[0][0][0]){ cout cout cinnm; for(int i=0;i int a,b; cinab; arr[(a+b)]++;//实际是 (a+b)/2*2 } for(int i=1;i arr[i]+=arr[i-1];//前缀和 } for(int i=0;i int a,b; cinab; a*=2; b*=2; cout
