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)秒。因此都要乘上这个权。

 #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1LL << ;
int w[] = { , , , , , , , , , , , , , , , };
LL sum[]; LL solve(LL x) {
if(x < ) return ;
LL pw = , ans = ;
// printf("x : %lld \n", x);
for(int i = ; i <= ; i++, pw <<= ) {
LL a = x / (pw * ) * sum[]; // 这一位总共完整跑了几轮
LL b = sum[x / pw % ]; // 跑完a轮后还有剩余b次
LL c = (x % pw + ) * w[x / pw % ]; // 当前的这一位的这一个数要多加几次,0也算一个所以+1
ans += (a + b) * pw + c; // a和b每次都会停留pw秒
}
return ans;
} int main() {
sum[] = ;
for(int i = ; i <= ; i++) sum[i] = sum[i-] + w[i-];
int t; scanf("%d", &t);
while(t--) {
LL n, x;
scanf("%lld%llx", &n, &x);
if((x + n - ) >= MOD) { // 分成 x 到 FFFFFFFF 和 0 到 (x + n - 1) % MOD
printf("%lld\n", solve(MOD - ) - solve(x - ) + solve(x + n - - MOD));
} else {
printf("%lld\n", solve(n + x - ) - solve(x - ));
}
}
return ;
}
/*
3
5 89ABCDEF
3 FFFFFFFF
7 00000000
*/

最新文章

  1. 关于Oracle的疑问
  2. 使用adagio包解决背包问题
  3. save(),saveorupdate()还有marqe()
  4. js弹出对话框的方法总结
  5. Selenium2+python自动化10-登录案例
  6. html meta中的viewport指令
  7. 《android基于andFix的热修复方案》实战篇
  8. 44.Android之Shape设置虚线、圆角和渐变学习
  9. Jmeter java.lang.OutOfMemoryError: GC overhead limit exceeded
  10. PHP实现下载功能之流程分析
  11. How to Build Android Applications Based on FFmpeg by An Example
  12. jqueryMobile
  13. 初始化JQuery方法与(function(){})(para)匿名方法介绍
  14. SQL -- 是否或推断线相交以在其内部的平面
  15. CCF-201503-3-节日
  16. fetch 的控制器和观察者
  17. 搭建C++环境
  18. bzoj4336 骑士的旅行 (树链剖分+multiset)
  19. 安装SQL Server For Linux(Install SQL Server)
  20. 6.26-EL表达式,JSTL标签

热门文章

  1. RGB565与RGB555标志识别位图文件格式
  2. .net core响应缓存
  3. Microsoft.AspNet.SignalR实现弹幕(即时通讯)
  4. C# WPF 中用代码模拟鼠标和键盘的操作
  5. WPF 4 目录树型显示
  6. js 注册事件
  7. ELINK编程器支持芯片详细列表
  8. 采用WebService客户端调用WSDL/SOAP网络报错的解决办法
  9. WPF svg 转 xmal
  10. chrome 里面js提示Provisional headers are shown错误