司法公开网站建设情况汇报,网站开发前台怎么样,做网站框架可用jpg图吗,沈阳网站制作的公司哪家好题意 询问区间[a,b]中的Mirror Number的个数#xff0c;其中Mirror Number是指把它横着翻转后还能表示同样的数字。 思路 注意这个可不是回文数。。除了0,1,8#xff0c;别的数字翻转过后就不是数字了。所以策略就是记忆化按位搜索#xff0c;每位只搜0,1,8#xff0c;最后…题意 询问区间[a,b]中的Mirror Number的个数其中Mirror Number是指把它横着翻转后还能表示同样的数字。 思路 注意这个可不是回文数。。除了0,1,8别的数字翻转过后就不是数字了。所以策略就是记忆化按位搜索每位只搜0,1,8最后再判断是否回文统计即可。这个判断回文是个小麻烦因为它需要和前面的位相比较所以用一个全局数组tmp[]表示枚举的每位的数字。 回过头来我觉得设置全局变量似乎不是一个好方法……它应该会破坏DP数组的区间唯一性…… 代码 [cpp] #include iostream #include cstdio #include cmath #include algorithm #include string #include cstring #include vector #include set #include stack #include queue #define MID(x,y) ((xy)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, end) for (int i begin; i end; i ) using namespace std; typedef long long LL; typedef vector VI; typedef set SETI; typedef queue QI; typedef stack SI; char num[50]; LL dp[47][47][2]; int tmp[50]; LL dfs(int pos, int start, bool flag, bool limit){ if (pos-1) return flag; if (!limit ~dp[pos][start][flag]) return dp[pos][start][flag]; int end limit?(num[pos]-48):9; LL res 0; for (int i 0; i end; i ) if (i 0 || i 1 || i 8){ bool st (startpos i 0); bool next_flag flag; if (flag){ if (!st pos (start1)/2) next_flag (i tmp[start-pos]); } tmp[pos] i; res dfs(pos-1, st?start-1:start, next_flag, limit(iend)); } return limit ? res : dp[pos][start][flag] res; } LL solve(char x[]){ int len strlen(x); for (int i 0; i len; i ){ num[i] x[len-1-i]; } num[len] 0; return dfs(len-1, len-1, 1, 1); } int main(){ //freopen(test.in, r, stdin); //freopen(test.out, w, stdout); int t; char a[50], b[50]; scanf(%d, t); getchar(); MEM(dp, -1); while(t --){ scanf(%s %s, a, b); LL res solve(b)-solve(a); int len strlen(a); bool ok true; for (int i 0; i len; i ){ if ((a[i] ! 0 a[i] ! 1 a[i] ! 8)||(a[i] ! a[len-1-i])){ ok false; break; } } if (ok) res ; printf(%lld\n, res); } return 0; } [/cpp]转载于:https://www.cnblogs.com/AbandonZHANG/p/4114320.html
