P2657 [SCOI2009]windy数题解

2021-03-07 19:32

阅读：393

标签：line display for 如何 memset getc operator sum while

CSDN同步

原题链接

简要题意：

一个 相邻两个数字差的绝对值都 \(\geq 2\) 且不含前导零 的数被称为 “windy数”。问从 \(a\) 到 \(b\) 的 “windy数”的个数。

首先，我们考虑 \(1\) ~ \(n\) 的 “windy数” 的个数怎么求。

用 \(f_{i,j}\) 表示有 \(i\) 位，最高位为 \(j\) 的方案数。

那么，从 \(i-1 \rightarrow i\) 只需要在 最高位前面拼上合法的一位。

即：

\[f_{i,j} = \sum_{k=0}^9 f_{i-1,k} [\operatorname{abs}{j,k} \geq 2] \]

\(k\) 即枚举合法的数字。

对于 \(i=1\) 的情况，\(f_{i,j} = 1\). 则：

\[ f_{i,j} = \begin{cases} \sum_{k=0}^9 f_{i-1,k} [\operatorname{abs}{j,k} \geq 2] , i \not = 1 \1 , i = 1 \\end{cases} \]

如何求答案呢？

我们分为三类：

位数比 \(n\) 小的数。
位数和 \(n\) 一样，但最高位比 \(n\) 小的数。
位数和最高位都和 \(n\) 一样，但比 \(n\) 小的数。

第一部分，答案为（\(len\) 为 \(x\) 的位数）

\[\sum_{i=1}^{len-1} \sum_{j=1}^9 f_{i,j} \]

第二部分则枚举最高位即可。

第三部分有点复杂，只需要枚举位数和次高位即可。

时间复杂度：\(O(\operatorname{siz}^2{n})\).

实际得分：\(100pts\).

#pragma GCC optimize(2)
#include
using namespace std;

inline int read(){char ch=getchar(); int f=1; while(ch‘9‘) {if(ch==‘-‘) f=-f; ch=getchar();}
	int x=0; while(ch>=‘0‘ && ch=2) f[i][j]+=f[i-1][k]; //求出 f
	printf("%d\n",calc(m+1)-calc(n));	
	return 0;
}

P2657 [SCOI2009]windy数题解

标签：line display for 如何 memset getc operator sum while

原文地址：https://www.cnblogs.com/bifanwen/p/12819052.html

上一篇：jQuery封装的ajax方法、发送jsonp请求、ajax全局事件、restful风格的api、获取XML数据

下一篇：luogu P2627 [USACO11OPEN]Mowing the Lawn G 单调队列优化dp

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：P2657 [SCOI2009]windy数题解
文章链接：http://soscw.com/essay/61479.html

亲，登录后才可以留言！

P2657 [SCOI2009]windy数题解

评论

热门文章

推荐文章

最新文章

置顶文章

P2657 [SCOI2009]windy数 题解

评论

热门文章

推荐文章

最新文章

置顶文章

P2657 [SCOI2009]windy数题解