南通网站建设公司,购物网站服务中心,手机门户网站模板,万能短视频素材库免费传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
问[l,r][l,r][l,r]内有多少个数是非回文数#xff0c;即数字中不存在连续几个数为回文数。 l,r≤1e18l,r\le1e18l,r≤1e18
思路#xff1a;
这么大的范围很明显数位dpdpdp了#xff0c;容易知道当一个数…传送门
文章目录题意思路题意
问[l,r][l,r][l,r]内有多少个数是非回文数即数字中不存在连续几个数为回文数。 l,r≤1e18l,r\le1e18l,r≤1e18
思路
这么大的范围很明显数位dpdpdp了容易知道当一个数为回文数的时候一定存在中间的两位或者三位是回文的所以我们记一下每个数之前的两位让后判断不相等的时候转移即可。 由于前导零会影响答案所以需要加一个leadleadlead判断是否存在前导零。
// Problem: #2683. 「BalticOI 2013」非回文数 Palindrome-Free Numbers
// Contest: LibreOJ
// URL: https://loj.ac/p/2683
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;LL l,r;
int a[100],tot;
LL f[100][20][20][2][2];LL dp(int pos,int pre1,int pre2,int flag,int lead) {if(pos0) {//if(now11) coutpre1 pre2endl;//coutnowendl;return 1;}if(f[pos][pre1][pre2][flag][lead]!-1) return f[pos][pre1][pre2][flag][lead];int xflag? 9:a[pos];LL ans0;for(int i0;ix;i) {if(i1pre1||i1pre2) continue;if(!leadi0) ansdp(pos-1,0,0,flag||ix,lead||i0);else ansdp(pos-1,pre2,i1,flag||ix,lead||i0);}return f[pos][pre1][pre2][flag][lead]ans;
}LL solve(LL x) {tot0;memset(f,-1,sizeof(f));if(x0) return 0;while(x) a[tot]x%10,x/10;return dp(tot,0,0,0,0);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinlr;printf(%lld\n,solve(r)-solve(l-1));return 0;
}
/**/
