icpc从零开始的学习笔记

前言

博主是一名在校大一新生，从高考结束后就开始准备算法竞赛，大概用一个半月学习了c++入门，(没有系统学习c语言，bushi).我现在已经走到了大一上的期末，但是回首这个学期，才发现其实自己躺平太多，平时又放不下游戏。目前的进度是leetcode190,cf130,我想对以后的自己说一声：无论结果如何，这一场没白来。(2022/12/01)

以下将记录我的学习的算法，既是总结，也是希望读者能有所收获。

我的学习路线不固定，更倾向广学习。

1，数位dp（2022/12/01）

数位dp是我今天学习的内容，个人觉得数位dp绕过了大整数逐个讨论而只对整体连续的数组进行高效化记忆化搜索。

下面我将从三点讨论数位dp的使用

首先是引入例题

洛谷p4999，烦人的数学作业

其题目大意为

给定l,r;

l<=le18,r<=le18;

求l,r区间内所有的整数的逐位数字相加之和

当然这里有非数位dp的解法但鉴于介绍数位dp,请学有余力的读者可以了解一下其他解法

首先是思路

1，前缀和思想

分别计算从零开始的l,r的结果然后相减。

2，数学分解

对任意一个整数，可以求取每位中的数字的出现次数，然后进行加权求和

3，细节处理

题干中要求

对结果进行模le9+7

现在提出数位dp模版

int a[20],len;
ll dp[20][...];
ll dfs(int pos,...,int limit){
ll ans=0;
if(!pos)return ...
ll &d=dp[pos][...];
if(!limit&&d!=-1)return d;
for(int I=0;i<=(limit?a[pos]:9);I++){
ans+=dfs(pos-1,...,limit&&a[pos]==v);
}
if(!limit)d=ans;
return ans;
}
ll f(ll x){
len=0;
memset(dp,-1,sizeof(dp));
memset(a,0,sizeof(a));
while(x)a[++len]=x%10,x/=10;
return dfs(len,...,1);
}

 现在让我们开始学习模版内容

这时候有读者可能会说，一上来就是模版，这样好吗（bushi);

在我看来了解模版要更有利于规范化代码写作，而且模版中可以了解到代码中的精髓所在。

现在让我们回到正题

首先是f(x)函数部分

f(x)函数内部是将任意整数进行数位拆分

接下来是介绍dfs函数部分

pos 是当前讨论到的数位，而limit是判断数位是否可取全还是取本位以下

limit 的转移为 limit&&a[pos]==i;//a[pos]为数位拆分的数组。

即本位取到最大可取数，则limit可传递到下一位。

而使用的数组为dp也是考虑到使用了记忆化搜索的思想

若访问到已经求取的数位，则可以返回其结果；

而内循环则是遍历所有的可以取的数并深搜。

在本题中要可以加入一个比较常见的参数 lead

其意义为前导零的有无；

最后我们可以进行本题的思路转代码；

首先是

遍历所有的i从1到9；

分别对当前的数位讨论是否符合i;

用find来记录要找的i;

用cnt来记录上一个的结果，否则当pos为零时返回值不清楚；

ans为答案，同时dfs返回结果前要取mod，否则可能会溢出（别问我为什么，我dbug这好久）

dfs结果乘上对应位的i后相加每次也进行取mod;

后得出结果。

总结

数位dp是记忆化搜索，没有状态转移方程的深入分析，学习难度中等。

 下面是我已经学过的一些算法，仅列出来，尚未具体文章。

1，快速幂，矩阵快速幂。

2，狄利克雷卷积。

3，带懒惰标记的线段树。

4，并查集，

5，二维前缀和。

最后

以上就是落寞钢铁侠为你收集整理的icpc从零开始的学习笔记的全部内容，希望文章能够帮你解决icpc从零开始的学习笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。