首页 > 代码库 > ZOJ 3962：Seven Segment Display（思维）
ZOJ 3962：Seven Segment Display（思维）
https://vjudge.net/problem/ZOJ-3962
题意：有16种灯，每种灯的花费是灯管数目，代表0~F（十六进制），现在从x开始跳n-1秒，每一秒需要的花费是表示当前的数的花费之和，问n-1秒后这段时间的花费总共是多少。跳到FFFFFFFF之后会跳回00000000.
思路：怀疑人生的题目。如果从平时计算[L,R]的花费，就计算[0,R] - [0,L-1]这样的角度来看，就会好做很多。同样如果跳到1LL<<32之后回到0，也分段考虑。这样写一个函数就可以计算了。
考虑三种东西：
a：跑第i位的时候总共完整跑了几轮的贡献（即0~F）。
b：跑第i位的时候完整跑完之后还剩了多余的几轮的贡献（即0~bit[i]）。
c：跑第i位的时候跑完a和b之后还剩一些多余的秒，这个时候显示器是显示bit[i]的，因此要加上bit[i]*剩余的秒。
a和b每次都停留了1LL<<(4 * i)秒。因此都要乘上这个权。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL MOD = 1LL << 32; 5 int w[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 6, 5, 4, 5, 5, 4 }; 6 LL sum[20]; 7 8 LL solve(LL x) { 9 if(x < 0) return 0;10 LL pw = 1, ans = 0;11 // printf("x : %lld \n", x);12 for(int i = 1; i <= 8; i++, pw <<= 4) {13 LL a = x / (pw * 16) * sum[16]; // 这一位总共完整跑了几轮14 LL b = sum[x / pw % 16]; // 跑完a轮后还有剩余b次15 LL c = (x % pw + 1) * w[x / pw % 16]; // 当前的这一位的这一个数要多加几次,0也算一个所以+116 ans += (a + b) * pw + c; // a和b每次都会停留pw秒17 }18 return ans;19 }20 21 int main() {22 sum[0] = 0;23 for(int i = 1; i <= 16; i++) sum[i] = sum[i-1] + w[i-1];24 int t; scanf("%d", &t);25 while(t--) {26 LL n, x;27 scanf("%lld%llx", &n, &x);28 if((x + n - 1) >= MOD) { // 分成 x 到 FFFFFFFF 和 0 到 (x + n - 1) % MOD29 printf("%lld\n", solve(MOD - 1) - solve(x - 1) + solve(x + n - 1 - MOD));30 } else {31 printf("%lld\n", solve(n + x - 1) - solve(x - 1));32 }33 }34 return 0;35 }36 /*37 338 5 89ABCDEF39 3 FFFFFFFF40 7 0000000041 */
ZOJ 3962：Seven Segment Display（思维）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。