luogu3107

洛谷P3107题面

相对较为模板化的代码 f[i][j][bo1][bo2]记录到第i位,数字num出现了x次(j初始为20,若当前数字不为num,j++;否则j--;最后只要记录j<=20的总和)bo1和bo2就很简单了,上界和前导零

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
#define int long long
string l,r;
int f[][][][],kkk[];
inline int DP(int le,int num1,int num2)
{
int re=,i,bo1,bo2,j,k,bo,pp; memset(f,,sizeof f); f[][][][]=;
//bo1:上界 bo2:前导零
for(i=;i<le;i++)
{
for(j=;j<=;j++)
{
for(bo1=;bo1<;bo1++)
{
for(bo2=;bo2<;bo2++)
{
if(f[i][j][bo1][bo2]==)continue;
for(k=;k<=;k++)
{
if((num2!=-&&(k!=||!bo2)&&k!=num1&&k!=num2)||(bo1&&k>kkk[i]))continue; pp=j;
if(!bo2||k!=)
{
if(num2==-)
{
if(k==num1)pp--;else pp++;
}
else
{
if(k==num1)pp--;else if(k==num2)pp++;
}
}f[i+][pp][bo1&(k==kkk[i])][bo2&(k==)]+=f[i][j][bo1][bo2];
}
}
}
}
}
if(num2==-)
{
for(i=;i<=;i++)for(j=;j<;j++)re+=f[le][i][j][];
}else for(i=;i<;i++)re+=f[le][][i][];
return re;
}
inline int solve(string s)
{
int re=,i,j,le=s.size();
for(i=;i<le;i++) kkk[i]=s[i]-'';
for(i=;i<=;i++) re+=DP(le,i,-);
for(i=;i<;i++)
{
for(j=i+;j<=;j++)re-=DP(le,i,j);
}return re;
}
signed main()
{
int i; cin>>l>>r;
for(i=l.size()-;i>=;i--)
{
if(l[i]=='')l[i]='';else {l[i]--;break;}
}printf("%lld\n",solve(r)-solve(l));
}
上一篇:一款多功能的移动端滚动选择器,支持单选到多选、支持多级级联、提供自定义回调函数、提供update函数二次渲染、重定位函数、兼容pc端拖拽等等..


下一篇:HTML5 拖拽事件