蓝桥杯2022年第十三届省赛真题-X进制减法

3492 阅读 6 评论 0 点赞

原题链接：蓝桥杯2022年第十三届省赛真题-X进制减法

## 解题背景
    1：理解进制的转化算法
    2：理解如何达到最小值
	
### 注意：
       1：如何是使得差值最小呢，我们可以利用dp的思想，要使得整体最小，那么组成他的各个部分也是最小，那么问题就变成了，如何使得各个部分的值最小；
       2：每个部分有对应位上的差值组成，那么，要使得这个差值乘的进制数尽可能小就可以了；
       3：如何使得进制尽可能小呢，进制的区间在2~N之间，那么只需要在这个区间之内，选取能包含a[i]和b[i]两个值的最小进制值就ok了，至此，思路就出来了
    
### 代码
    #include<stdio.h> 
    int a[100005]={0};
    int b[100005]={0};
    int mod= 1000000007;
    int max(int x,int y)
    {
    	return x>y?x:y;
    } 
    int main()
    {
    	//录入数据 
    	int N,Ma,Mb;
    	scanf("%d%d",&N,&Ma);
    	for(int i=Ma;i>=1;i--)
    	{
    		scanf("%d",&a[i]);
    	}
    	scanf("%d",&Mb);
    	for(int i=Mb;i>=1;i--)
    	{
    		scanf("%d",&b[i]);
    	}
    	//处理获取进制数组
    	int jz[100005]={0}; 
    	for(int i=Ma;i>=1;i--)//A-B以A 的位数为标准 
    	{
    		jz[i]=max(max(a[i]+1,b[i]+1),2);//找出对应位置上最小的进位，且进位不小于2 
    		//printf("%d ",jz[i]);
    	}
    	//printf("\n");
    /*	//处理得到对应为的乘数 （超时O（n^2），换一种搞法） 
    	int cs[100005]={0}; 
    	for(int i=Ma;i>=1;i--) 
    	{
    		cs[i]=1;
    		for(int j=i-1;j>=1;j--)//乘数不包括自身进位值 
    		{
    			cs[i]*=jz[j];
    		}
    		//printf("%d ",cs[i]);
    	}
    	//printf("\n");
    	//处理得到最小值的和
    	int sum=0;
    	for(int i=Ma;i>=1;i--)//从高位加起 
    	{
    		sum+=(a[i]-b[i])*cs[i];
    		sum%=mod;
    	}*/
        long long sum=0;
    	for(int i=Ma;i>=2;i--) 
    	{
    		sum=((sum+a[i]-b[i])*jz[i-1])%mod;
    	}
    	sum+=(a[1]-b[1]);
    	printf("%lld\n",sum);
    	return 0;	
    }

0.0分

23 人评分

本文分类：题解列表
浏览次数：3492 次浏览
发布日期：2022-07-12 15:49:20
本文链接：https://blog.dotcpp.com/a/88674

上一篇 > 1859：与2无关的数简单好理解的做法
下一篇 > 1865:换硬币好理解的基础解法（用到递归）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2022年第十三届省赛真题-X进制减法

评论列表共有 6 条评论

发表评论取消回复

蓝桥杯2022年第十三届省赛真题-X进制减法

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 6 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 6 条评论

发表评论取消回复