网站建设二团队,做的怎样 英文网站,软文推广发稿,网站建设怎么用题目如下#xff1a;
杭州人称那些傻乎乎粘嗒嗒的人为 626262#xff08;音#xff1a;laoer#xff09;。 杭州交通管理局经常会扩充一些的士车牌照#xff0c;新近出来一个好消息#xff0c;以后上牌照#xff0c;不再含有不吉利的数字了#xff0c;这样一来#x…题目如下
杭州人称那些傻乎乎粘嗒嗒的人为 626262音laoer。 杭州交通管理局经常会扩充一些的士车牌照新近出来一个好消息以后上牌照不再含有不吉利的数字了这样一来就可以消除个别的士司机和乘客的心理障碍更安全地服务大众。 不吉利的数字为所有含有 444 或 626262 的号码。例如 62315734188891462315 73418 88914623157341888914 都属于不吉利号码。但是611526115261152 虽然含有 666 和 222 但不是 626262 连号所以不属于不吉利数字之列。 你的任务是对于每次给出的一个牌照区间号推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对 n、m0n≤m1000000n、m0n≤m1000000n、m0n≤m1000000如果遇到都是 000 的整数对则输入结束。
Output
对于每个整数对输出一个不含有不吉利数字的统计个数该数值占一行位置。
Sample
Input
1 100
0 0Output
80题目链接
题解 or 思路
数位DP dfs(位置 是否有限制 上一位是否是 666 ) 具体请参考下面的代码。
AC 代码如下
/*
Make it simple and keep self stupid
authorJoanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize(inline) // 如果比赛允许开编译器优化的话可以默写这两段
#include iostream
#include algorithm
#include vector
#include string
#include numeric
#include cstring
#include cmath
#include map
#include unordered_map
#include bitset
#include set
#include random
#include ctime
#include queue
#include stack
#include climits
#define buff \ios::sync_with_stdio(false); \cin.tie(0);
// #define int long long
#define ll long long
#define PII pairint, int
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod 1e9 7;
const int inf 2147483647;
const int N 1000009;
//int Mod(int a,int mod){return (a%modmod)%mod;}
//int lowbit(int x){return x-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res 1 % p;while (k){if (k 1) res Mod(res * a , p);a Mod(a * a , p);k 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int l, r, f[N][2];
int a[N], idx;
int dfs(int pos, bool lim, bool sex)
{if (pos 0)return 1;if (!lim f[pos][sex] ! -1)return f[pos][sex];int len lim ? a[pos] : 9;int ans 0;for (int i 0; i len; i){if (i 4) continue;if (i 2 sex) continue;ans dfs(pos - 1, lim i a[pos], i 6);}if (!lim)f[pos][sex] ans;return ans;
}
int work(int x)
{idx 0;while (x){a[idx] x % 10;x / 10;}return dfs(idx, 1, 0);
}
void solve()
{int x work(l - 1), y work(r);cout y - x \n;
}
int main()
{buff;memset(f, -1, sizeof f);int _ 1;// cin _;while (cin l r, l, r)solve();
}
