2016 ShenYang regional online 1007||hdu 5898 odd-even number (数位dp)

题目链接

题意:题意说得一点页不清楚。。。意思在询问在区间[l,r]中满足某条件的数。该条件是,该数的任何一段数字是奇数组成的数串必须有偶数长度,任何一段数字是偶数组成的数串必须由奇数长度。

对于样例1,满足条件的29个数字分别是: 2,4,6,8,11,13,15,17,19,31,33,35,37,39,51,53,55,57,59,71,73,75,77,79,91,93,95,97,99.

对于样例2,满足条件的36的数字分别是:

110,112,114,116,118,

130,132,134,136,138

150,152,154,156,158

170,172,174,176,178

190,192,194,196,198

200,202,204,206,208,220

211,213,215,217,219

 

思路:数位dp.dp[i][j][k]表示长度为i,奇偶性相同的连续由j个,上一个的奇偶性为k.

注意不允许前导0.

其他就是细节了,太久没写数位dp调了好久啊QAQ

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz