CCPC-Wannafly Winter Camp Day2 E

发表于 | 更新于 | 阅读次数：
本文字数： 3.2k | 阅读时长 ≈ 3 分钟

Power of Function

这个题重点是读题。看懂函数，函数最终表示的是 n 写成K进制，K进制的值的和加上长度 -2 就是m。

给你一个 ，k,l,r,求K进制下，[l,r]区间内m的最大值。然后输出当m最大时[l,r]区间最大值和最小值。

题解：把l,r转换成K进制， r>l，如果r,l,高位相同，那么求得到最大值M高位肯定也是和这个值一样。然后从第一个位不同开始，想让M值最大，只有两种可能，一种是取r这个值二进制下位减一，然后后面位的全部取 k-1,或者这个位取最大值再继续讨论下一个位。写个DFS就可以，和数位DP有点像。

举个例子 ：k=10 ,l=1001,r=1179.

10进制下 l = 1 0 0 1

r = 1 1 7 9

最前面 1 和 1 是相同的所以要 m最大 肯定 最高位也是 1 b=1 0 0 0

然后从第3位开始dfs(3) 要么这个位取 1， 要么 取 0 后慢慢全取 9，

如果这个位 取 1 就会影响下一个位，所以再DFS（2） 然后发现 要么取7 ，（要么 取 6 后面全为9）

以此类推，最后发现 后面3为 179 099 取得 后面比较大，那么m取最大就是 1099；

还有一些细节要注意，比如 179 ，99是一样打的，因为99只有两位数。还有 0 是没有 比他小1这个数，如果要小1就要向高位借，所以这情况要排除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
int t;
LL k,l,r;
vector<LL> v1,v2,mi,mx;
LL p[2000];
LL dfs(LL pos,bool limit) {
    if(pos==-1)return 0;
    if(limit) {
        LL m1,m2;
        m1=dfs(pos-1,1);
        m2=dfs(pos-1,0);
        m1+=v2[pos];
        m2+=v2[pos]-1;
        if(v2[pos]==0)m2=-1;    //排除 为 r pos位 为0情况 
        if(pos==v2.size()-1&&v2[pos]==1)m2--;  // 最高位为 0 m2要减一
        if(m1>m2) {           
            mx[pos]=mi[pos]=v2[pos];
            return m1;
        } else if(m1==m2) {
            mx[pos]=v2[pos];
            mi[pos]=v2[pos]-1;
            for(int i=0; i<pos; i++) {
                mi[i]=k-1;
            }
            return m2;
        } else {
            mx[pos]=mi[pos]=v2[pos]-1;
            for(int i=0; i<pos; i++) {
                mi[i]=mx[i]=k-1;
            }
            return m2;
        }

    } else {
        return (k-1)*(pos+1);
    }
}
int cas=1;
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld%lld",&k,&l,&r);
        v1.clear();
        v2.clear();
        LL x=r;
        while(x>0) {
            v2.push_back(x%k);
            x/=k;
        }
        x=l;
        while(x>0) {
            v1.push_back(x%k);
            x/=k;
        }
        while(v1.size()<v2.size()) {
            v1.push_back(0);
        }
        p[0]=1;
        for(int i=1; i<v2.size(); i++) {
            p[i]=p[i-1]*k;
        }
        int pos=v2.size()-1;
        mi.resize(v2.size());
        mx.resize(v2.size());
        while(pos>=0) {
            if(v1[pos]==v2[pos]) {
                mi[pos]=mx[pos]=v2[pos];
            } else break;
            pos--;
        }
        if(pos!=-1)dfs(pos,1);
        LL a=0,b=0,m=0,flag=1;
        for(int i=mx.size()-1; i>=0; i--) {
            m+=mx[i];
            if(mx[i]!=0)flag=0;
            if(flag)m--;
            b+=mx[i]*p[i];
            a+=mi[i]*p[i];
        }
        m=m+mx.size()-2;
        printf("Case #%d: %lld %lld %lld\n",cas++,m,a,b);
    }
    return 0;    //看不懂留言0.0，或者加Q3035536707
}