弗莱

用户名：1435075261

访问量：6036

签　名：

马梅，我还喜欢你，是不是有点可笑

等　　级
排　　名	1193
经　　验	2988
参赛次数	0
文章发表	27
年　　龄	0
在职情况	学生
学　　校	野鸡大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届国赛真题-天干地支（C语言直译法）
浏览：396

数据结构-链表的基本操作
浏览：146

蓝桥杯算法提高VIP-夺宝奇兵（C语言，动态规划）
浏览：56

你可能喜欢

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

　　作者: 弗莱　　　　发表时间：2022-07-12 15:49:20 浏览：3225　|　评论：6　

原题链接：蓝桥杯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分

47 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

dotcpp0744752

为什么最后用long long啊

2024-03-14 17:27:03

kich

太感谢了，终于懂了

2024-02-06 13:25:37

不爱敲代码的菜鸡

想问一下大佬 每一位的差值都保证是正数吗 题目只给出A > B 如果某些位A[i] < B[i] 那么该位的权值是不是要取给出的最大进制 在求该位的差值会得到一个负值 要比取A[i]+1缩小差值更大吧

2023-10-05 22:29:44

白笈云泽

为什么数组要多设置几位

2023-03-30 23:49:12

膜拜

2023-03-15 20:33:51

查克芝士

orz

2022-10-05 21:28:38

弗莱

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C二级辅导-同因查找（C语言代码）

C二级辅导-等差数列（C++代码）

回文数字（C++代码）

众数问题（C++代码）

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

评论区

精彩推荐

【偶数求和】（C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

简单的a+b （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

分糖果（C++代码）

最长单词（C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

1908题解

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

弗莱

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C二级辅导-同因查找 （C语言代码）

C二级辅导-等差数列 （C++代码）

回文数字 （C++代码）

众数问题 （C++代码）

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

评论区

精彩推荐

【偶数求和】 （C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

简单的a+b （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

分糖果 （C++代码）

最长单词 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

1908题解

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-同因查找（C语言代码）

C二级辅导-等差数列（C++代码）

回文数字（C++代码）

众数问题（C++代码）

　　评论区

【偶数求和】（C语言代码）记得sum的归零时机

分糖果（C++代码）

最长单词（C语言代码）