2022省赛B组真题
（时间复杂度：如果1s就要控制在1亿以内）
填空题
1.顺子日期
小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期?
查看代码
查看代码
#include <iostream>
using namespace std;
int main()
{
cout<<"14";
// 请在此输入您的代码
return 0;
}解析：
顺子：连续递增三个数。
年 月 日
2022 01 （20,21,22,23,24,25,26,27,28,29）
2022 12 （30,31）
2022 10 12
2022 1 1 23
所以一共14个。
2.进制转换
九进制转十进制（2022）9=（）10
解析：2+2*9^1+2*9^3=1478
所以：
查看代码
查看代码
#include <iostream>
using namespace std;
int main()
{
// 请在此输入您的代码
cout<<"1478";
return 0;
}程序设计题：
4.刷题统计
https://www.lanqiao.cn/problems/2098/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
查看代码
#include <iostream>
using namespace std;
typedef long long int ll;
int main()
{
// 请在此输入您的代码
ll a,b,n;
cin>>a>>b>>n;
ll sum=0;
ll cnt=0;
ll j=0;
cnt=n/(a*5+b*2);
n-=cnt*(a*5+b*2);
cnt*=7;
while(sum<n){
j++;
if(j<6){
cnt++;
sum+=a;
}
if(j==6){
cnt++;
sum+=b;
}
if(j==7){
cnt++;
sum+=b;
j=0;
}
}
cout<<cnt;
return 0;
}因为数据量大--->所以不能直接while，要先确定大致范围将一周的值捆绑先确定要几周，然后算一下剩余几天。
5.修建灌木
https://www.lanqiao.cn/problems/2107/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
| a1 | a2 | a3 |
| 0 | 1 | 1 |
| 1 | 0 | 2 |
| 2 | 1 | 0 |
| 3 | 2 | 0(返回） |
| 4 | 0 | 1 |
| 0 | 1 | 2 |
| 0（返回） | 2 | 3 |
| 1 | 0 | 4 |
折返时：要停留两次，这棵树砍两遍。
查看代码
#include <iostream>
using namespace std;
int main()
{
// 请在此输入您的代码
int n;
cin>>n;
for(int i=1;i<=n;i++){
if(i<=n/2)cout<<2*(n-i)<<endl;
else{
cout<<2*(i-1)<<endl;
}
}
return 0;
}1.扫雷
https://www.lanqiao.cn/problems/549/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
枚举
核心：八个方向
查看代码
#include <iostream>
using namespace std;
//以这个点为中心 --->八个方向
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
const int N=106;
int a[N][N];
int x[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1)x[i][j]=9;
else{
for(int k=0;k<8;k++){
if(a[i+dx[k]][j+dy[k]]==1){
x[i][j]++;
}
}}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++){
cout<<x[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
6.X进制减法
https://www.lanqiao.cn/problems/2108/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
限制在n进制内其实没用。
本题进制的题意：
例如：最右边是最低位
题目中案例（321）8 10 2
转为10进制是1+2*2+3*10*2=65；
意思是：
（1）最低位不用乘进制，
（2）第二位为2--->因为最低位是2进制所以第二位为1就需要最低位十进制下2所以2*2，
（3）第三位3--->第三位为1需要第二位十进制下10才能进上一位（因为第二位为十进制）--->最低位十进制2向第二位进一位--->所以一共需要3*10*2
算法思路
代码实现：
设置一个base存放进制乘积
每次记得%t
查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
const int N=1e5+6;
int a[N];
int b[N];
const long long int t=1e9+7;
int main(){
cin>>n;
int ma;
cin>>ma;
for(int i=ma;i>=1;i--)cin>>a[i];
int mb;
cin>>mb;
for(int i=mb;i>=1;i--)cin>>b[i];
long long int ans=0;
long long int base=1;
for(int i=1;i<=ma;i++){
ll h=max(2,max(a[i],b[i])+1);
ans=(ans+(a[i]-b[i])*base)%t;
base=base*h%t;
}
cout<<ans;
return 0;
}核心代码：
long long int ans=0;
long long int base=1;
for(int i=1;i<=ma;i++){
ll h=max(2,max(a[i],b[i])+1);//用于更新进制乘积
//防止越界每次都要模t
ans=(ans+(a[i]-b[i])*base)%t;
base=base*h%t;
}
cout<<ans;
算法题：
9.李白将进酒加强版（考点动态规划）
题目：
https://www.lanqiao.cn/problems/2114/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
查看代码
查看代码
#include <iostream>
using namespace std;
typedef long long int ll;
ll t=1e9+7;
ll dp[106][106][106];//dp[i][j][k]--->已遇见i个酒店，j朵花，酒壶里还有k壶酒的方案数
int main()
{
int n,m;
cin>>n>>m;//n个店，m次花
dp[0][0][2]=1;//最初一种
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=m;k++){//壶里面的酒最多为m因为只遇见m朵花喝了m斗酒
if(i&&k%2==0){
dp[i][j][k]=( dp[i][j][k]+dp[i-1][j][k/2])%t;
}
if(j){
dp[i][j][k]=( dp[i][j][k]+dp[i][j-1][k+1])%t;
}
}
}
}
cout<<dp[n][m-1][1];//由这转移回来
// 请在此输入您的代码
return 0;
}10.砍竹子（考点贪心）
题目：
https://www.lanqiao.cn/problems/2117/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
算法思路：
本题最高的竹子最多被砍6次
最高的树1018
查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int a=1e18;
int cnt=0;
while(a>=2){
cnt++;
a=sqrt(a/2+1);
}
cout<<cnt<<endl;
return 0;
}贪心：
先计算所有层数再减掉同层同高的树
本题代码：
查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int m;//所有树的最高层数
ll res;//答案使用魔法次数
ll st[20];//每一层的高度
ll f[200006] [10];//f[i][j]表示下标为i的树的第 j层存放的数值即当前层高度
int main(){
int n;
cin>>n;//n棵树
for(int i=0;i<n;i++){
int top =0;//当前树的层数
ll x;
cin>>x;
while(x>1){//比1小就不砍
st[++top]=x;
x=sqrtl(x/2+1);
}
m=max(m,top);
res+=top;
int k=top;
for(int j=0;j<top;j++) {
f[i][j]=st[k];
k--;
}
}
//相邻树同高减。
for(int i=0;i<m;i++){
for(int j=1;j<n;j++){
if(f[j][i]&&f[j][i]==f[j-1][i])res--;
}
}
cout<<res;
return 0;
}开方案数
函数名 返回值类型
sqrt double
sqrtf float
sqrtl long double
7.统计子矩阵
https://www.lanqiao.cn/problems/2109/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
算法考点：前缀和+双指针
时间复杂度：
如果用上下左右四个维度则为O（n4）--->5004 会超时因为时间限制为1s
所以要优化成O（n3）即合并行，例如a[i][j]表示第j列的第一个元素加到第i个元素（都在第j列行数从1->i）
步骤：
（1）输入每个元素值并求前缀和例如a[i][j]表示第j列的第一个元素加到第i个元素的和
（2）然后枚举上下边界左右边界
上边界i从1->n
下边界j从i->n
左右边界都从1开始，r<=m
左右边界用双指针
l ，r左右指针、
双指针使用原则：l是关于r单增
固定上下边界，左右指针移动卡区间
查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=506;
int a[N][N];
int n,m;//n行m列
ll k;
int main(){
ll res=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];//输入当前元素值
a[i][j]+=a[i-1][j];//该列的第一个元素到这一行元素的和--->前缀和，本身加上一个的和
}
}
//四个边界上下左右，左右用双指针
for(int i=1;i<=n;i++){//上边界
for(int j=i;j<=n;j++){//下边界
int l,r;//左右边界
ll sum=0;
for(l=r=1;r<=m;r++){
sum+=a[j][r]-a[i-1][r];
while(sum>k){
sum-=(a[j][l]-a[i-1][l]);
l++;//超值移动左指针
}
res=res+r-l+1;
}
}
}
cout<<res;
return 0;
}
8.积木画
https://www.lanqiao.cn/problems/2110/learning/?subject_code=1&group_code=4&match_num=13&match_flow=1&origin=cup
