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