首页 > 其他分享 >247 数数2

247 数数2

时间:2024-11-04 12:09:46浏览次数:1  
标签:数数 int long 247 dp include cu

// 603 数数2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/5/problem/247

读入 l,r,请求出 [l,r]中有多少个数字满足数字的各个数位的和是质数。

输入格式
一行两个整数 l,r。

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

样例输入
1 100
样例输出
37
数据范围
对于 100%的数据,保证 1≤l≤r≤1016。
*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>
#include <set>
#include <vector>

using  namespace std;

const int N = 20;
long long dp[N][N][210];
set<int> primes;
long long l, r;

void init() {
	for (int i = 2; i <= 200; i++) {
		int flag = 1;
		for (int j = 2; j * j <= i; j++) {
			if (j != i && i % j == 0) {
				flag = 0;
				break;
			}
		}
		if (1 == flag) {
			primes.insert(i);
		}
	}

	for (int i = 0; i <= 9; i++) dp[0][i][i] = 1;

	for (int x = 1; x < N; x++) {
		for (int i = 0; i <= 9; i++) {
			int de = 1;
			for (int j = 0; j <= 9; j++) {
				for (int k = 0; k <= 200; k++) {
					if(k>=i){
						dp[x][i][k] += dp[x - 1][j][k - i];
					}
				}
			}
		}
	}

	return;
}

long long solve(long long u) {
	long long cu = u;
	vector<int> v;
	while (cu) {
		v.push_back(cu % 10);
		cu /= 10;
	}
	long long ans = 0; int presum = 0;
	for (int i = v.size() - 1; i >= 0; i--) {
		int t = v[i];
		for (int j = t - 1; j >= 0; j--) {
			if (i == v.size() - 1 && j == 0) continue;
			for(int k= 0 ;k<=200;k++){
				if(primes.count(k+ presum) !=0)
					ans += dp[i][j][k];
			}
		}
		if (primes.count(t + presum) && i==0) {
			ans++;
		}
		presum += t;
	}

	for (int i = v.size() - 2; i >= 0; i--) {
		for (int j = 1; j <= 9; j++) {
			for (int k = 0; k <= 200; k++) {
				if (primes.count(k)) {
					ans += dp[i][j][k];
				}
			}
		}
	}


	return ans;
}


int main()
{
	init();
	cin >> l >>   r;
	//cout << solve(r) << endl;
	cout << solve(r) - solve(l - 1) << endl;
	return 0;
}

标签:数数,int,long,247,dp,include,cu
From: https://www.cnblogs.com/itdef/p/18524934

相关文章

  • 《Java核心技术 卷I》参数数量可变的方法
    调用打印方法。。。publicPrintStreamprintf(Stringformat,Object...args){returnformat(format,args);}这里的省略号..是Java代码的一部分,表明这个方法可以接收任意数量的对象(除fmt参数之外)。实际上,printf方法接收两个参数,一个是格式字符串,另......
  • 246 数数
    //602数数.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*http://oj.daimayuan.top/course/5/problem/246读入l,r,请求出[l,r]中有多少个数字满足数字中任意相邻两个数位的差的绝对值不超过2。输入格式一行两个整数l,r。输出格式一行一个整数......
  • 字符串数组转换为整数数组
    在C#中,可以使用Array.ConvertAll方法来将字符串数组转换为整数数组。classProgram{staticvoidMain(string[]args){//案例1://使用Array.ConvertAll方法将字符串数组转换为整数数组//情况1:当确定每个数值......
  • 2024-10-30:或值至少 K 的最短子数组 I。用go语言,给定一个非负整数数组 nums 和一个整
    2024-10-30:或值至少K的最短子数组I。用go语言,给定一个非负整数数组nums和一个整数k,我们需要判断数组中是否存在一个最短的非空子数组,使得该子数组所有元素的按位或(OR)运算结果至少为k。如果找到了这样的子数组,返回其长度;如果不存在,则返回-1。输入:nums=[1,2,3],k=2。......
  • 2024-10-23:最高频率的 ID。用go语言,给定两个长度相等的整数数组 nums 和 freq, 其中num
    2024-10-23:最高频率的ID。用go语言,给定两个长度相等的整数数组nums和freq,其中nums中的每个元素表示一个ID,而freq中的每个元素表示对应ID在此次操作后出现的次数变化。如果freq[i]为正数,则表示在这次操作中nums[i]的ID会增加freq[i]次;如果freq[i]为负数,则表示在这次操作中nums[i......
  • P4247 [清华集训2012]序列操作
    题目描述有一个长度为\(n\)的序列,有三个操作:Iabc表示将\([a,b]\)这一段区间的元素集体增加\(c\);Rab表示将\([a,b]\)区间内所有元素变成相反数;Qabc表示询问\([a,b]\)这一段区间中选择\(c\)个数相乘的所有方案的和\(\mod19940417\)的值。对于100%的数据,\(n\leq500......
  • 90. 几何体顶点颜色数数据
    章节2中介绍过顶点位置、顶点法向量数据,下面给大家介绍顶点颜色.attributes.color数据。顶点位置数据geometry.attributes.position顶点法向量数据geometry.attributes.normal顶点UV数据geometry.attributes.uv顶点颜色数据geometry.attributes.color几何体顶点颜色.attribut......
  • 有一组整数数据,全部除以一个整数a,使得余数是同n种数字,如何计算出这个整数a的全部可能
    使用问心一言生成,然后手动修改。deffind_possible_a_values(data_in,num_n,start=100,max_a=1000):ifmax_aisNone:#如果没有指定上限,则使用数据集中的最大值作为上限的一个粗略估计max_a=max(data_in)possible_a_values=set()dat......
  • 第1关:求解一个整数数组划分为两个子数组问题
    [TOC]求解一个整数数组划分为两个子数组问题任务描述已知由n(n>=2)个整数正整数构成的集合A={ak}(0<=k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中的元素之和分别为S1和S2.设计一个尽可能高效的划分算法,满足|n1-n2|最小且|S1-S2|最大,算法返回|......
  • 手把手实现完善矩阵类(分数数据类型)
    矩阵类功能:矩阵变换分数数据类型使得精度丢失率极低加,减,数乘,矩阵相乘,转置,幂次,初等变换伴随矩阵,逆矩阵,矩阵行列式的值,后方增添/删除矩阵,矩阵的秩获取并输出齐次/非齐次线性方程组的解向量演示:矩阵输出,初等行变换后输出,解向量输出实现矩阵类,如何适应不同数据类型?模板?对......