数圈圈（二维前缀和）

问题分析

前缀和模板题，数字的圈的个数为数字中闭合环的个数，可以打表实现。由于有多组数据，为了避免重复计算，推荐将 1 − 1 0 6 1 -10^6 1−106 图片说明 的圈圈数和前缀和的数组提前初始化，每组数据只需代入前缀和公式计算即可，具体代码如下。

#include
using namespace std;const int maxn=1e6+5;//打表
//题意：每个数字的圈圈，理解成对应余数的标记，对于一个多位数，就是考虑其每一位的圈圈，即从从右到做左依次做模运算的余数
long long record[maxn] = {0};
void solve()
{for(int i = 0;i <= maxn; i++){int temp = i;while(temp != 0){int m = temp % 10;if(m == 0 || m == 4 || m == 6 || m == 9)record[i]++;else if(m == 8)record[i] += 2;temp /= 10;}}
}int main()
{int t;cin >> t;solve();//注意此处调用下while(t --){int a, b;int sum = 0;cin >> a >> b;for(int i = a; i <= b; i++){sum += record[i];}cout << sum << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！