hdu 4734 F(x)

发布时间:2024年01月20日

F(x)

1

题意

定义一个十进制数的权重 F ( x ) = x n ? 2 n ? 1 + x n ? 1 ? 2 n ? 2 + . . . + x 1 ? 2 0 F(x) = x_n \cdot 2 ^ {n-1} + x_{n-1} \cdot 2 ^ {n-2} + ... + x_1 \cdot 2 ^ 0 F(x)=xn??2n?1+xn?1??2n?2+...+x1??20

给定两个数 A , B A,B A,B,求出 [ 0 , B ] [0,B] [0,B] 中有多少个数的权重不大于 A A A 的权重

思路

可以发现权重最大为 9 × ∑ i = 0 8 2 i = 4599 9 \times \sum_{i=0} ^ {8} 2 ^ i = 4599 9×i=08?2i=4599。如果我们用 p o s pos pos,当前的权重, A A A 的权重来表示限制条件的话,需要数组大小: 10 × 4600 × 4600 = 4.6 × 1 0 8 10 \times 4600 \times 4600 = 4.6 \times 10 ^ 8 10×4600×4600=4.6×108,空间不够。如果我们不存 A A A 的权值,而是每一轮都 m e m s e t memset memset 的话,由于 t t t 最大为 1 0 4 10^4 104,时间复杂度为 1 0 4 × 10 × 4600 = 4.6 × 1 0 8 10 ^ 4 \times 10 \times 4600 = 4.6 \times 10 ^ 8 104×10×4600=4.6×108,时间也不符合要求。

那么我们肯定要转化思想,不妨将限制条件改为: p o s pos pos 个全变化位的条件下,低 p o s pos pos最多还可以拥有的权重的大小,也就是说,我们一开始权重空间初始化为 A A A 的权重,然后往下搜的过程中,减去每一位的权重,如果发现权重变为负数,就不符合。

此时 D P DP DP 状态为: d p [ p o s ] [ l e f t ] dp[pos][left] dp[pos][left] l e f t left left 为可用权重空间大小。因为不管 A A A 的权重多少,如果我们当前剩下的空间一样的话,低位的选择情况也是一样的。通过这样子相减,我们成功将 d p dp dp 数组的维度降低了一维。

时间复杂度: O ( l e n × 4600 ) O(len \times 4600) O(len×4600)

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3e;
const long long INFLL=1e18;

typedef long long ll;

int dp[11][4620];
int num[11];
int two[11];

int dfs(int pos, int left, bool limit){
    if(left < 0) return 0;
    if(!pos) return 1;
    if(!limit && ~dp[pos][left])  return dp[pos][left];
    int res = 0;
    int up = (limit ? num[pos] : 9);
    fore(i, 0, up + 1){
        int nl = left - i * two[pos - 1]; //新空间
        if(nl < 0) continue;
        res += dfs(pos - 1, nl, limit && i == up);
    } 
    if(!limit) dp[pos][left] = res;
    return res;
}

int solve(int x, int A){
    int len = 0;
    while(x){
        num[++len] = x % 10;
        x /= 10;
    }
    int Fa = 0;
    int w = 1;
    while(A){
        Fa += w * (A % 10);
        A /= 10;
        w <<= 1;
    }
    return dfs(len, Fa, true);
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    memset(dp, -1, sizeof(dp));
    two[0] = 1;
    fore(i, 1, 11) two[i] = two[i - 1] * 2;
    int t;
    std::cin >> t;
    fore(Case, 1, t + 1){
        int A, B;
        std::cin >> A >> B;
        std::cout << "Case #" << Case << ": " << solve(B, A) << endl;
    }
    return 0;
}
文章来源:https://blog.csdn.net/m0_73500785/article/details/135718544
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。