Terraced fields

本文主要是介绍Terraced fields，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

*原题链接

• 题意：要求出所有 \(1 \leqslant x\leqslant n\) 的范围内，能整除 \(8\) 的所有数的数字 \(8\) 和 \(6\) 出现的数量。
• 题解：神似数位 \(dp\) 要做的事情，但是因为不连续，所以没有想法。并且数据范围也暗示了是数位dp。然后赛后通过讲解，知道了， \(8\) 是以 \(1000\) 循环，然后发现 \(n\mod 1000\) 是连续的，然后大力分类讨论求解，问题的难点，在于如何把求整除 \(8\) 的数，转化成连续的数。
• 代码：

#include <bits/stdc++.h>
#define inf 0ddddd3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N = 2e5 + 94;
const ld eps = 1e-8;
const ld pi = acos(-1.0);

ll dp[222][222];
ll FORCE[N];

ll JUDGE[N];
ll cnt[10101];
ll judge(ll x) {
    ll ret = 0;
//return 1;
  //  if (JUDGE[x])return JUDGE[x];
   // ll X = x;
    while (x) {
        if (x % 10 == 6 || x % 10 == 8) ret++;
        x /= 10;
    }
    return  ret;
}

ll baoli(ll x) {
    ll ret = 0;
    for (ll i = x; i >=1 ; i--) {
        ret += judge(i);
    }
    return ret;
}
ll force(ll x) {
    ll ret = 0;
    return FORCE[x];
    for (int i = 1; i * 8 <= x; i++) {
        ll num = i * 8;
        ret += judge(num);
    }
    return ret;
}
void init() {
    for (int i = 1; i <= 10010; i ++) {
        judge(i);
    }
    for (int i = 1; i <= 10010; i ++) {
        FORCE[i] = FORCE[i-1];
        if (i%8 == 0)
        FORCE[i] += judge(i);
    }
    for (int i = 1; i <= 19; i ++) {
        ll t = 0;
        for (int j = 1; j <=9; j ++) {
            if (j == 6 || j == 8) {
                t+=(ll)pow(10, i-1) ;
            }
            dp[i][j] = dp[i][0] * (j + 1) + t;
           // cout << "len " << i << " " << j <<  ":  " << dp[i][j] << endl;
            //if (i == 8)return;
           // cout << "baoli  " << (ll)pow(10, i - 1) *  (j + 1) -1<<"  -->  " << baoli((ll)pow(10, i - 1) *  (j + 1) -1) << endl;
        }
        dp[i + 1][0] = dp[i][9]
        ;
    }
    cnt[0] = 1;
    for (int i = 1;i <= 1010;i ++) {
        cnt[i] += cnt[i-1];
        if (i % 8 ==0 )cnt[i] ++ ;
    }
}

ll DP(ll x) {
    vector<ll>nums;
    nums.push_back(1);
    ll X = x;
    ll mod = 1;
    vector<ll>Nums;
    Nums.push_back(10);
    while (x) {
        nums.push_back(x%10);
        x /= 10;
        Nums.push_back(X%mod + 1);
        mod *= 10;
    }
    ll ret = 0;
   // cout << nums[1] << " " << nums[2] << endl;
    for (int i = nums.size()-1; i >= 1; i -- ) {
       // cout << i << "!!" << endl;
        ll dig = nums[i];
        
        if (i == 1) {
            ret += dp[i][dig];
        } else if (dig == 6||dig == 8) {
            //cout << Nums[i]<<"!!!" << endl;
            ret += Nums[i];
            ret += dp[i][dig - 1];
        }
        else if(dig == 0) continue;
        else
        ret += dp[i][dig-1];
    }
    // if (ret != baoli(X)) {
    //     cout << "X  " << X << endl;while(1); 
    // }
    //cout << ret << "?" << endl;
    //cout << baoli(X) << endl;
    return ret * 125 + (X+1) * force(1000);
}
ll getans(ll n) {
    ll ans = 0;
    if (n / 1000 > 0)
        ans = DP(n / 1000 - 1) + force(n % 1000 ) +
              judge(n / 1000) * (cnt[n % 1000]) + (n % 8 == 0 ? 0 : judge(n));
    else
        ans = force(n) + (n % 8 == 0 ? 0 : judge(n));
   // cout << cnt[n%1000] << endl;
   // cout << judge(n/1000) << endl;
  // cout << DP(n/1000-1) << " " << force(n%1000) << " " << judge(n/1000) << " " << cnt[n%1000] << endl;
    return ans;
}
void solve() {
    ll n, x, y;
    cin >> n;
   // while (cin >> n) {cout << getans(n)<<endl;}
    // for (int n = 1; n <= 100000; n ++) {
    //    // DP(n);
    //    // cout << "?";
    //     if (force(n) + ((n%8 == 0) ? 0:judge(n)) == getans(n))continue;
    //     else {
    //         cout << n << endl;
    //         cout << "Baoli(n)" << force(n) + ((n % 8 == 0) ? 0 : judge(n))
    //              << endl;
    //         cout << "getans" << getans(n) << endl;
    //         cout << force(n-1) << endl;
    //         cout << getans(n-1) << endl;
    //         while (1);
    //     }
    // }
    cout << getans(n) << "\n";
}
int main() {
    ll n = 1;
    init();
    ios::sync_with_stdio(0);
    while (cin >> n) {
        while (n--) {
            solve();
        }
    }
    return 0;
}

这篇关于Terraced fields的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！