1.子2023
方法:动态规划
时间复杂度 $O(n)$
拼接字符串和遍历都是线性的时间复杂度
题目链接
https://www.lanqiao.cn/problems/17104/learning/
很容易想到动态规划(状态转移),先将1-2023所有的数字变成字符串拼接起来,再顺序通过保存
2,20,202,2023的数量来进行状态转移
#include<iostream>
using namespace std;
long long dp[5];
//dp[1]表示2,dp[2]表示20,dp[3]表示202,dp[4]表示2023的数量
int main(){
string str="";
for(int i=1;i<=2023;i++) str+=to_string(i);
for(auto x:str){
if(x=='2') dp[1]++,dp[3]+=dp[2];
if(x=='0') dp[2]+=dp[1];
if(x=='3') dp[4]+=dp[3];
}
cout<<dp[4];
return 0;
}
2.双子数
3.班级活动
方法:统计一下不同数字的个数
时间复杂度 $O(n)$
$O(n)$的统计,$O(1)$的计算
题目链接
https://www.lanqiao.cn/problems/17153/learning/
模拟+思维
#include <iostream>
using namespace std;
const int N=1e5+10;
int num[N],a[N],more2,one,res;
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],num[a[i]]++;
for(int i=1;i<=n;i++){
if(num[i]==1) one++;
if(num[i]>=2) more2+=(num[i]-2);
}
if(one>=more2) res=more2+(one-more2)/2;
else res=more2;
cout<<res;
return 0;
}
4.合并数列
方法:双指针模拟一下
时间复杂度 $O(n)$
$O(n)$的遍历a数组,$O(n)$的遍历b数组