D. Hard Tasks
题意
给出一个数n，询问1-n中有多少对组合(三个数)相加不需要进位
思路
- 1-10有{0,1,2}，{1,2,3}，{2,3,4}共3对
- 10-20有{10,11,12}，{11,12,13}，{12,13,14}共3对
- 20-30有{20,21,22}，{21,22,23}，{22,23,24}共3对
- 30-40有{30,31,32}，{31,32,33}，{32,33,34}共3对
- 40-100有0对
- 综上，1-100有3×4=12对
- 100-200有12对
- 200-300有12对
- 300-400有12对
- 400-1000有0对
- 综上，1-1000有3×4×4=48对
综上，\(1\)-\(10^n\)有\(3×4^{n-1}\)对,只需要枚举每一位的数字求对数再相加即可
性质：当除个位以外的数超过了3，那么相当于进1（注意后面清零），个位则不能超过2
比如： \(ans(140)=ans(200)\)
\(ans(123)=ans(130)\)
\(ans(13)=ans(20)\)
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 110;
const int M = 2e5+10;
LL n,m;
int a[N];
vector<LL> v;
void solve(){
cin >> n;
for(int i = 1; n; i ++){ //获取每一位上的数字
v.push_back(n % 10);
n /= 10;
}
LL ans = 0;
for(int i = 0; i < v.size(); i ++ ){
if(v[i] > 3){
for(int j = i; j >= 0; j --)v[j] = 0;//消去后面的数字(全体进位)
if(i < v.size() - 1){ //进位
v[i+1]++;
}
else{
v.push_back(1);
}
}
else if(v[i] > 2 && i == 0){ //个位
for(int j = i; j >= 0; j --)v[j] = 0;
if(i < v.size() - 1){
v[i+1]++;
}
else{
v.push_back(1);
}
}
}
for(int i = 0; i < v.size(); i ++ ){
if(v[i]){
if(i == 0)ans += min(v[i],3ll);
else ans += min(v[i],3ll)*3*pow(4,max(i-1,0));
}
}
cout << ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}