2013-11-20 08:11

原题传送门http://www.lydsy.com/JudgeOnline/problem.php?id=1026

首先我们用w[i,j]表示最高位是第i位,且是j的windy数个数

那么我们可以写出转移

w[i,j]:=w[i-1,k] abs(k-j)>=2

首先对于询问的a,b区间,我们可以转化成求1-a的个数,1-b的个数,然后差就行了

那么我们要求的就是1-x之间的windy数

假设x一共有len位,那么我们求len-1位以下的windy数可以直接用w算出来,直接

累加w[i,j]就行了

那么我们对于len位的数,只需要改变枚举的上界就好了,相当于固定第i位,求第i+1位的

情况,然后特判下如果abs(c[i]-c[i+1])<2(c[i]为x的第i位)直接退出就行了

 /**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
w :array[..,-..] of longint;
c :array[..] of longint;
a, b :longint; function ask(x:longint):longint;
var
len, Sum, i, j :longint; begin
if x= then exit();
len:=;
while x> do
begin
inc(len);
c[len]:=x mod ;
x:=x div ;
end;
ask:=;
for i:= to len- do
for j:= to do
ask:=ask+w[i,j]; for j:= to c[len]- do
ask:=ask+w[len,j]; for i:=len- downto do
begin
for j:= to c[i]- do
if abs(c[i+]-j)>= then ask:=ask+w[i,j];
if abs(c[i+]-c[i])< then break;
end;
end; procedure main;
var
i, j, k :longint; begin
for i:= to do w[,i]:=;
for i:= to do
for j:= to do
for k:= to do
if abs(j-k)>= then w[i,j]:=w[i,j]+w[i-,k];
readln(a,b);
writeln(ask(b+)-ask(a));
end; begin
main;
end.

最新文章

  1. Linux标准出错重定向导出
  2. epoll 反应堆
  3. SSH(Struts Spring Hibernate开发框架)
  4. SandcastleBuilder-生成帮助文档的时候报错...
  5. Git基础 - git blame
  6. asp.net 微信企业号办公系统-流程设计--流程步骤设置-数据设置
  7. 《Python基础教程(第二版)》学习笔记 -&gt; 第五章 条件、循环 和 其他语句
  8. Android 内存溢出管理与测试
  9. poj1741 bzoj2152
  10. ssh快速登录远程服务器
  11. Redis集群教程(Redis cluster tutorial)
  12. 分享:Java 开发精美艺术二维码
  13. mui 对话框 点击按钮不关闭对话框的办法
  14. 常见问题1:默认div隐藏,点击按钮时出现,再点击时隐藏。
  15. redis面试必问
  16. JSON.parseObject(String str)与JSONObject.parseObject(String str)的区别
  17. SDL相关学习
  18. 在Win7系统下, 使用VS2015 打开带有日文注释程序出现乱码的解决方案
  19. ArchLinux升级后deadbeef无法正常启动的解决办法
  20. IntelliJ IDEA 注册码失效

热门文章

  1. 云计算之路-阿里云上:奇怪的CPU 100%问题
  2. 云计算之路-阿里云上:“黑色1秒”问题与2009年Xen一个补丁的故事
  3. Scala function programming
  4. 国际电话区号SQL
  5. Qt C++ 并发,并行,多线程编程系列1 什么是并发
  6. bzoj1367 可并堆
  7. MySQL训练营02
  8. MVC项目用Windsor注入
  9. ethday04复杂的智能合约
  10. ipfs02笔记