#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 114;
int a[N][N][N], b[N][N][N], c[N], n, l, r;
void dfs(int p, int t, int u, int &cnt, int &sum){
if(p == n){
cnt = 1;
sum = 0;
return;
}
if(a[p][t][u] != -1){
cnt = a[p][t][u];
sum = b[p][t][u];
return;
}
int temp = t ? c[p] : 9;
int cnt_2 = 0, sum_2 = 0;
for(int i = 0; i <= temp; i++){
int tt = t && (i == temp);
int uu = u && (i == 0);
int cntt, summ;
dfs(p + 1, tt, uu, cntt, summ);
int num = 0;
if(!uu && i == 6) num += cntt;
num += summ;
cnt_2 += cntt;
sum_2 += num;
}
a[p][t][u] = cnt_2;
b[p][t][u] = sum_2;
cnt = cnt_2;
sum = sum_2;
}
int check(int x){
if(x < 6) return 0;
n = 0;
int temp = x;
while(temp > 0){
c[n++] = temp % 10;
temp /= 10;
}
for(int i = 0; i < n / 2; i++) swap(c[i], c[n - 1 - i]);
for(int i = 0; i < N; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++){
a[i][j][k] = -1;
b[i][j][k] = -1;
}
int cnt, sum;
dfs(0, 1, 1, cnt, sum);
return sum;
}
signed main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
cin >> l >> r;
cout << check(r) - check(l - 1) << '\n';
return 0;
}
5 条评论
-
@ 2025-8-28 19:48:04可笑的是有人取消我的成绩，随便看我的代码
#include<iostream> #include<cstring> using namespace std; typedef long long ll; ll dp[20][20][2]; int digit[20]; ll dfs(int pos, int cnt, bool tight){ if(pos == 0) return cnt; if(dp[pos][cnt][tight] != -1) return dp[pos][cnt][tight]; int limit = tight?digit[pos]:9; ll tot = 0; for(int d = 0; d <= limit; ++d){ bool ntight = tight&&(d==limit); int ncnt = cnt+(d==6); tot += dfs(pos-1, ncnt, ntight); } dp[pos][cnt][tight] = tot; return tot; } ll count(ll x){ if(x < 0) return 0; memset(dp, -1, sizeof(dp)); int len = 0; while(x){ digit[++len] = x%10; x /= 10; } return dfs(len, 0, true); } int main(){ freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); ll L, R; cin >> L >> R; ll ans = count(R)-count(L-1); cout << ans; return 0; }-
@ 2025-8-29 7:05:35
一个数位 DP 能去还超 AI 至于吗
-
-
@ 2025-8-28 19:47:11
王皓轩
#include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; typedef long long ll; ll dp[20][2][2]; string num; ll dfs(int pos, bool tight, bool found) { if (pos == num.length()) { return found ? 1 : 0; } if (dp[pos][tight][found] != -1) { return dp[pos][tight][found]; } int limit = tight ? num[pos] - '0' : 9; ll ans = 0; for (int d = 0; d <= limit; d++) { bool new_tight = tight && (d == limit); bool new_found = found || (d == 6); ans += dfs(pos + 1, new_tight, new_found); } return dp[pos][tight][found] = ans; } ll solve(ll n) { if (n < 0) return 0; num = to_string(n); memset(dp, -1, sizeof(dp)); return dfs(0, true, false); } int main() { freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); ll L, R; cin >> L >> R; ll ansR = solve(R); ll ansL = solve(L - 1); cout << ansR - ansL << endl; return 0; } -
@ 2025-8-28 19:46:37
张佳旭同为AI
#include<iostream> #include<string> #include<cmath> using namespace std; typedef long long ll; ll cnt(ll n) { if (n <= 0) return 0; ll total = 0; string num_str = to_string(n); int length = num_str.length(); for (int position = 0; position < length; position++) { int current_digit = num_str[position] - '0'; ll high_value = 0; for (int i = 0; i < position; i++) { high_value = high_value * 10 + (num_str[i] - '0'); } ll low_value = 0; if (position < length - 1) { string low_str = num_str.substr(position + 1); if (!low_str.empty()) { low_value = stoll(low_str); } } ll power = 1; for (int i = 0; i < length - position - 1; i++) { power *= 10; } if (current_digit > 6) { total += (high_value + 1) * power; } else if (current_digit == 6) { total += high_value * power + low_value + 1; } else { total += high_value * power; } } return total; } int main() { ll L, R; cin >> L >> R; ll count_R = cnt(R); ll count_L_minus = (L > 1) ? cnt(L - 1) : 0; cout << count_R - count_L_minus << endl; return 0; }
- 1