数位DP这个 DP 应该很好理解就是把每个数位拆开单独处理我们用例题讲解。题目P1836P2657P2518P4067P1836这道题可以说是很好理解的一道模板题。对于每种数字单独处理个数时间复杂度其中表示的位数。codell f(ll n,ll x){ ll cnt0,i; for(i1;n/i;i*10){ cntn/i/10*i-(x0)*i; if(xn%(i*10)/i) cnti; else if(xn%(i*10)/i) cntn%i1;//求出单独的数值 } return cnt; } int main(){ scanf(%lld,r),l1; for(int i0;i9;i) sum(f(r,i)-f(l-1,i))*i;//拆开处理 printf(%lld,sum); }P2657数位 dp 开始预处理位数为最高位为的 windy 数个数。转移其中是非负整数且。初始值其中i为非负整数。void init(){ for(int i0;i9;i) dp[1][i]1; for(int i2;i10;i) for(int j0;j9;j) for(int k0;k9;k) if(abs(j-k)2) dp[i][j]dp[i-1][k]; } int work(int x){ memset(a,0,sizeof(a)); int len0,ans0; while(x) a[len]x%10,x/10; for(int i1;ilen-1;i) for(int j1;j9;j) ansdp[i][j]; for(int i1;ia[len];i) ansdp[len][i]; for(int ilen-1;i1;i--){ for(int j0;ja[i]-1;j) if(abs(j-a[i1])2) ansdp[i][j]; if(abs(a[i1]-a[i])2) break; } return ans; } int main(){ init(),cinlr,coutwork(r1)-work(l)endl; }P2518对于一个数把其中的 0 删掉相当于把 0 放到了前面。所以这个问题就是让我们求一下给我们的数的全排列比当前小的有几个。我们假设代表数字有几个。那么用这些来表示全排列但是这样的话________表示我要爆炸。所以我们要用高精度所以我们在想想。假如现在有个位置。我们先把 0 放法放好。之后就只有个位置。然后再放 1。所以答案是。思路和数位 dp 差不多。________表示我复活了。ll cfb(){ ll ans1; int mn; for(int i0;i9;i) if(a[i]) ans*C(m,a[i]),m-a[i]; return ans; } int main(){ while(cinc) if(isdigit(c)) v[n]c-48,a[v[n]]; int nnn; for(int i1;inn;i){ n--; for(int j0;jv[i];j) if(a[j]) a[j]--,anscfb(),a[j]; a[v[i]]--; } printf(%lld,ans); }P4067如本题先把题目转化为求从高位到低位计算这两个值记表示考虑到第位分别表示当前值是否严格小于。然后不难计算。codefor(int i61;i;i--){ ll x(n(i-1))1,y(m(i-1))1,z(k(i-1))1; for(int a0;a2;a) for(int b0;b2;b) for(int c0;c2;c) if(f[i1][a][b][c]||g[i1][a][b][c]) for(int xx0;xx2;xx) for(int yy0;yy2;yy){ ll zzxx^yy; if((axxx)||(byyy)||(czzz)) continue; ll aa(a(xxx)),bb(b(yyy)),cc(c(zzz)); g[i][aa][bb][cc]g[i1][a][b][c], g[i][aa][bb][cc]%p, f[i][aa][bb][cc]f[i1][a][b][c](zz-zp)%p*((1ll(i-1))%p)%p*g[i1][a][b][c]%p, f[i][aa][bb][cc]%p; } }单调队列/单调栈优化单调队列就比如多重背包没有学的可以学一下单调栈单调栈就是单调队列的特殊情况因此不讲。题目CF372CCF372C设为第个烟花的时候在第个区间的最大开心值推导方程可见朴素 dp 方程还是很好推的但是看时间复杂度最大是无法通过的空间复杂度也会爆。先解决空间问题容易想到滚动数组第一维i显然不需要存那么多只需要存下当前和即可滚掉一维即可。同时求的最大值同时​是一个固定的参数 我们可以转换成求的最小值这样可以更加方便操作。我们枚举是无法优化的同时枚举每个位置也是无法避免的所以说我们想如何优化k的遍历因为我们只需要通过在的范围内最小值来更新现在的。既然需要最小值用单调队列优化即可。我们跑两遍从和从跑一遍分别从右和从左更新。code此题请自行书写。凸包凸函数即导数存在单调性的函数。如果导数单调递减称为上凸函数。如果导数单调递增称为下凸函数。如就是典型的下凸函数。如果一个多边形内任意两点连线都不穿过该多边形则该多边形为凸多边形。我们称一个凸多边形为凸包。给定一个点集找到一个最小的凸多边形使得其完全包含这个点集这个凸多边形被称为该点集的凸包。很多时候也把一个凸多边形边上及其内部所有点组成的点集称为凸包。对于点集。则该点集为凸包。闵可夫斯基定义点集和的闵可夫斯基和为。函数(序列) 也可以视作点集对于两个函数其闵可夫斯基和可以定义为或取决于你怎么看待这个函数(序列)。由于凸包有良好的性质所以我们一般只考虑凸包的闵可夫斯基和。若点集合为凸包则其闵可夫斯基和也是凸包。证明取其中。对于对于和中的每一条边在中都存在。通过旋转和平移可以使得中一条边与x 轴平行且经过原点并且使得在 轴之上。此时这条与轴平行的边必在中。同理每条边都在中。WQS 二分WQS 二分用于解决恰好选个的优化问题。核心思想是引入惩罚项将恰好选个的问题转化为不限制个数的问题。如果问题的答案关于个数存在凸性。则可以二分一个斜率另答案由变为此时因为有凸性所以必然也有凸性且在时取到最值。由于关于单调所以也关于单调所以可以通过这个方式求出恰好取个时的答案。题目P2569P1484后记由于我找不到题目因此只好把我十万年前写的陈年老抽代码拿了过来。虽然这篇文章的内容作者也看着头疼但是这还是十分有用的。本篇文章部分题目未给出代码供大家思考周日我休息将在下周一给出解题方法和代码。