Seven Segment Display
A seven segment display, or seven segment indicator, is a form of electronic display device for displaying decimal numerals that is an alternative to the more complex dot matrix displays. Seven segment displays are widely used in digital clocks, electronic meters, basic calculators, and other electronic devices that display numerical information.
Edward, a student in Marjar University, is studying the course "Logic and Computer Design Fundamentals" this semester. He bought an eight-digit seven segment display component to make a hexadecimal counter for his course project.
In order to display a hexadecimal number, the seven segment display component needs to consume some electrical energy. The total energy cost for display a hexadecimal number on the component is the sum of the energy cost for displaying each digit of the number. Edward found the following table on the Internet, which describes the energy cost for display each kind of digit.
|
|
|
For example, in order to display the hexadecimal number "5A8BEF67" on the component for one second, 5 + 6 + 7 + 5 + 5 + 4 + 6 + 3 = 41 units of energy will be consumed.
Edward's hexadecimal counter works as follows:
- The counter will only work for n seconds. After n seconds the counter will stop displaying.
- At the beginning of the 1st second, the counter will begin to display a previously configured eight-digit hexadecimal number m.
- At the end of the i-th second (1 ≤ i < n), the number displayed will be increased by 1. If the number displayed will be larger than the hexadecimal number "FFFFFFFF" after increasing, the counter will set the number to 0 and continue displaying.
Given n and m, Edward is interested in the total units of energy consumed by the seven segment display component. Can you help him by working out this problem?
Input
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 105), indicating the number of test cases. For each test case:
The first and only line contains an integer n (1 ≤ n ≤ 109) and a capitalized eight-digit hexadecimal number m (00000000 ≤ m ≤ FFFFFFFF), their meanings are described above.
We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case output one line, indicating the total units of energy consumed by the eight-digit seven segment display component.
Sample Input
3 5 89ABCDEF 3 FFFFFFFF 7 00000000
Sample Output
208 124 327
Hint
For the first test case, the counter will display 5 hexadecimal numbers (89ABCDEF, 89ABCDF0, 89ABCDF1, 89ABCDF2, 89ABCDF3) in 5 seconds. The total units of energy cost is (7 + 6 + 6 + 5 + 4 + 5 + 5 + 4) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 6) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 2) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) = 208.
For the second test case, the counter will display 3 hexadecimal numbers (FFFFFFFF, 00000000, 00000001) in 3 seconds. The total units of energy cost is (4 + 4 + 4 + 4 + 4 + 4 + 4 + 4) + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 6) + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 2) = 124.
题意：
有16种灯，每种灯的花费是灯管数目，代表0~F（十六进制），现在从x开始跳n-1秒，每一秒需要的花费是表示当前的数的花费之和，问n-1秒后这段时间的花费总共是多少。跳到FFFFFFFF之后会跳回00000000.
这里有个小小的技巧（其实也算不上什么技巧了！！），就是用n-1秒的费用减去x-1秒的费用，自然就是x~n-1的费用了。。。（数位dp一般都这么玩的，尤其是区间类型的！）
当然这种还是可以用DP来写的，不过因为判断的条件过多，所以不如记忆化搜索写起来简单，并且数位DP的题目都是有特点的，也就是说几个函数都是可以确定的，无非就是在dfs函数里面的判断条件不同，下面整理一下数位dp的模板
记忆化的数位dp：
通常而言，有三个参数必须 dp( pos, flag, limit )
pos表示当前正在枚举的数位。
flag标志已经枚举的前缀是否某种性质（前面的数位和，是否含有某个数，前一个枚举的数等等。。），当然flag可以有多个。
limit表示当前是否为上限，有时还会记录是否有前导0。
函数也就是一个solve(分割数字）和dfs,而dfs的参数什么的也是都确定的（如上），所以数位DP就简单不少了！
Note：注意初始化要放在多组测试用例外面，不能每次都memset，因为多组测试用例的状态重复，如果每次都memset可能会超时，比如这道题，还有一个问题就是现在对数位DP的时间复杂度问题还是不太了解，不太会算，哪位大神如果知道，望惠诉我！！！
正常数位dp思路：
#include <bits/stdc++.h>
#define LL long long
const LL MAX=0xFFFFFFFF;
using namespace std;
int cost[16]={6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4};
int dig[20];
LL dp[20][1005];///dp[i][j]表示从高位枚举到第i位和为各位的和为sum
LL dfs(int pos,LL sum,bool limit){ ///pos为当前的位，sum是之前位的花费和，limit标记的是当前是否为上限，枚举的位数
if(pos<0) return sum;
if( !limit && dp[pos][sum]!=-1 ) return dp[pos][sum];
int upper = limit ? dig[pos] : 15;
LL tmp=0;
for(int i=0;i<=upper;i++)
tmp+=dfs(pos-1,sum+cost[i],limit&&i==dig[pos]);
if(!limit) dp[pos][sum]=tmp;
return tmp;
}
LL solve(LL n){
for(int i=0;i<8;i++){
dig[i]=n%16;
n/=16;
}
return dfs(7,0,1);
}
int main(){
int T;
LL tmp,x;
memset(dp,-1,sizeof dp);
scanf("%d",&T);
while(T--){
scanf("%lld%llX",&tmp,&x);
if(tmp+x-1>MAX)
printf("%lld
",solve(MAX)-solve(x-1)+solve((tmp+x-1)%MAX -1 )); ///注意细节，尤其是第三个别忘了-1
else
printf("%lld
",solve(tmp+x-1)-solve(x-1));
}
return 0;
}但是自己的第一想法就是一个简单的题目，通过每一位来看
用一下网友的题解，省的自己写了，表说我懒。。。
a：跑第i位的时候总共完整跑了几轮的贡献（即0~F）。
b：跑第i位的时候完整跑完之后还剩了多余的几轮的贡献（即0~bit[i]）。
c：跑第i位的时候跑完a和b之后还剩一些多余的秒，这个时候显示器是显示bit[i]的，因此要加上bit[i]*剩余的秒。
比如1234 （16进制）现在看的是3所在的位，那么就是1234/(16^2)*从0到15花费电量*该位每跳一次的时间（也就是16） + 该位0 1 2 时候的电量，也就是0 1 2每秒花费电量*跳一次需要的时间（也就是16） + 该位为最后一次3的时候的电量，很明显就是下一位0 1 2 3 4一共5秒的时间
直接上代码
#include <bits/stdc++.h>
#define LL long long
const LL MAX=0xFFFFFFFF;
using namespace std;
LL arr[]={6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4};
LL arrs[20];
LL solve(LL x){
LL sum=0;
LL base = 1;
for(int i=0;i<8;i++){
sum = sum + x/(base<<4)*arrs[15]*base; ///亮多少轮 电量
LL nowpnt = x%(base<<4)/base;
sum=sum + arrs[ nowpnt-1 ]*base; ///当前为余数-1
sum=sum + arr[ nowpnt ] * (x%base+1); ///余数的最后一个数
base*=(1<<4);
}
return sum;
}
int main()
{
int T;
scanf("%d",&T);
arrs[0]=6;
for(int i=1;i<16;i++)
arrs[i]=arrs[i-1]+arr[i];
while(T--)
{
LL tmp,x;
scanf("%lld%llx",&tmp,&x);
LL sum=0;
if(tmp+x-1>MAX) ///超过FFFFFFFF的要分隔开看
sum=solve(MAX)-solve(x-1)+solve((tmp+x-1)-MAX-1); ///注意细节处理
else
sum=solve(tmp+x-1)-solve(x-1);
printf("%lld
",sum);
}
}
/*
3
5 89ABCDEF
3 FFFFFFFF
7 00000000
*/