保山市网站建设_网站建设公司_会员系统_seo优化

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：[P10262 GESP样题 六级] 亲朋数 - 洛谷

【题目描述】

给定一串长度为L LL、由数字0 ∼ 9 0\sim 90∼9组成的数字串S SS。容易知道，它的连续子串共有L ( L + 1 ) 2 \frac{L(L + 1)}22L(L+1)​个。如果某个子串对应的数（允许有前导零）是p pp的倍数，则称该子串为数字串S SS对于p pp的亲朋数。

例如，数字串S SS为“12342 1234212342”、p pp为2 22，则在15 1515个连续子串中，亲朋数有“12 1212”、“1234 12341234”、“12342 1234212342”、“2 22”、“234 234234”、“2342 23422342”、“34 3434”、“342 342342”、“4 44”、“42 4242”、“2 22”共11 1111个。注意其中“2 22”出现了2 22次，但由于其在S SS中的位置不同，记为不同的亲朋数。

现在，告诉你数字串S SS和正整数p pp，你能计算出有多少个亲朋数吗？

【输入】

输入的第一行，包含一个正整数p pp。约定2 ≤ p ≤ 128 2 \leq p \leq 1282≤p≤128。
输入的第二行，包含一个长为L LL的数字串S SS。约定1 ≤ L ≤ 10 6 1 \leq L \leq 10^61≤L≤106。

【输出】

输出一行一个整数表示答案。

【输入样例】

2 102

【输出样例】

5

【算法标签】

《洛谷 P10262 亲朋数》 #动态规划DP# #GESP#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int重新定义为long long类型constintN=150;// 定义常量N，最大模数p的范围intp,f[N],g[N],ans;// p: 模数, f/g: 动态规划数组, ans: 结果计数string s;// 输入的数字字符串signedmain()// 因为使用了#define int long long, 所以用signed main{cin>>p>>s;// 输入模数p和数字字符串sintlen=s.size();// 获取字符串长度s=" "+s;// 在字符串前添加空格，使索引从1开始for(inti=1;i<=len;i++)// 遍历字符串的每个字符{memset(g,0,sizeof(g));// 清空g数组，用于存储当前状态for(intj=0;j<p;j++)// 遍历所有可能的余数{// 状态转移: 从之前的余数j转移到新的余数t// 新的余数t = (j*10 + 当前数字) % pintt=(j*10+s[i]-'0')%p;// 计算新余数g[t]+=f[j];// 从f[j]状态转移到g[t]}// 特殊情况: 当前数字单独构成子串g[(s[i]-'0')%p]++;// 当前数字单独组成的数字对p取模ans+=g[0];// 统计余数为0的子串数量memcpy(f,g,sizeof(g));// 将g数组复制到f数组，用于下一轮迭代}cout<<ans<<endl;// 输出结果return0;}

【运行结果】

2 102 5