草庐IT

2022蓝桥杯--X进制减法

时光巷陌585 2023-07-17 原文

题目链接：P2035 - [蓝桥杯2022初赛] X进制减法 - New Online Judge (ecustacm.cn)http://oj.ecustacm.cn/problem.php?id=2035

【问题描述】

进制规定了数字在数位上逢几进一。

X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！

例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65。

现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。

请你算出 A−B 的结果最小可能是多少。

请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。

输入格式

第一行一个正整数 N，含义如题面所述。

第二行一个正整数 Ma，表示 X进制数 A 的位数。

第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。

第四行一个正整数 Mb，表示 X 进制数 B 的位数。

第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。

请注意，输入中的所有数字都是十进制的。

输出格式

输出一行一个整数，表示 X 进制数 A−B 的结果的最小可能值转换为十进制后再模 1000000007的结果。

数据范围

对于 30% 的数据，N≤10;Ma,Mb≤8，
对于 100% 的数据，2≤N≤1000;1≤Ma,Mb≤100000;A≥B。

输入样例：

11
3
10 4 0
3
1 2 0

输出样例：

94

样例解释

当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。

此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1000000007;
int a[N],b[N],x[N];
int n,ma,mb;
int main()
{
	cin>>n;
	cin>>ma;
	for(int i = 1;i <= ma;i++){
		cin>>a[i];
	}
	cin>>mb;
	for(int i = 1;i <= mb;i++){
		cin>>b[i];
	}
	for(int i = 1;i <= ma / 2;i++){//将数据按低位到高位存放
		swap(a[i],a[ma - i + 1]);
	}
	for(int i = 1;i <= mb / 2;i++){
		swap(b[i],b[mb - i + 1]);
	}
	int k = max(ma,mb);//找出最大位数
	for(int i = 1;i <= k;i++){
		x[i] = max(2,max(a[i],b[i]) + 1);//x数组记录对应位置符合条件的最小的进制数
	}
	ll A = 0,B = 0;
	for(int i = ma;i >= 1;i--){//注意从高位开始计算
		A = (A * x[i] + a[i]) % mod;
	}
	for(int i = mb;i >= 1;i--){
		B = (B * x[i] + b[i]) % mod;
	}
	ll ans = (A - B + mod) % mod; //加mod防止出现负数
	printf("%lld",ans);
	return 0;
}

总结：

1、X进制的理解

321
8102

个位 1 

十位 2 * 2

百位 3 * 10 * 2 

规律：该位数字乘上前面所有进制数。

2、贪心算法

本题要找A - B的最小值，以为A >= B,所以只要找到满足条件的最小进制数（最小为二进制）即可。

蓝桥进制xff0cxff蓝桥杯c++贪心算法

有关2022蓝桥杯--X进制减法的更多相关文章

  1. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  2. Ruby - 如何将消息长度表示为 2 个二进制字节 - 2

    我正在使用Ruby，我正在与一个网络端点通信，该端点在发送消息本身之前需要格式化“header”。header中的第一个字段必须是消息长度，它被定义为网络字节顺序中的2二进制字节消息长度。比如我的消息长度是1024。如何将1024表示为二进制双字节？ 最佳答案 Ruby(以及Perl和Python等)中字节整理的标准工具是pack和unpack。ruby的packisinArray.您的长度应该是两个字节长，并且按网络字节顺序排列，这听起来像是n格式说明符的工作:n|Integer|16-bitunsigned,network(bi

  3. ruby - 如何在 Ruby 中将负整数转换为二进制 - 2

    问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001

  4. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  5. 映宇宙2022年营收63亿元：同比下降三成，毛利率提升4.3个百分点 - 2

    3月26日，映宇宙（HK:03700，即“映客”）发布截至2022年12月31日的2022年度业绩财务报告。财报显示，映宇宙2022年的总营收为63.19亿元，较2021年同期的91.76亿元下降31.1%。2022年，映宇宙的经营亏损为4698.7万元，2021年同期则为净利润4.57亿元；期内亏损（净亏损）为1.68亿元，2021年同期的净利润为4.33亿元；非国际财务报告准则经调整净利润为3.88亿元，2021年同期为4.82亿元，同比下降19.6%。 映宇宙在财报中表示，收入减少主要是由于行业竞争加剧，该集团对旗下产品采取更为谨慎的运营策略以应对市场变化。不过，映宇宙的毛利率则有所提升

  6. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

  7. ruby - 如何在 Ruby 中返回整数的固定长度二进制表示？ - 2

    我知道我可以使用Fixnum#to_s将整数表示为二进制格式的字符串。但是1.to_s(2)生成1而我希望它生成00000001。我怎样才能使所有返回的字符串都以零作为填充到8个字符？我可以使用类似的东西:binary="#{'0'*(8-(1.to_s(2)).size)}#{1.to_s(2)}"if(1.to_s(2)).size但这看起来不是很优雅。 最佳答案 使用字符串格式。"%08b"%1#=>"00000001" 关于ruby-如何在Ruby中返回整数的固定长度二进制表示？

  8. ruby - 在 Ruby 中将字符串转换为十六进制 - 2

    我正在尝试使用Ruby将二进制文件转换为十六进制。目前我有以下内容:File.open(out_name,'w')do|f|f.puts"constunsignedintmodFileSize=#{data.length};"f.puts"constcharmodFile[]={"first_line=truedata.bytes.each_slice(15)do|a|line=a.map{|b|",#{b}"}.joiniffirst_linef.putsline[1..-1]elsef.putslineendfirst_line=falseendf.puts"};"end这是以下代

  9. ruby - 如何从二进制数据的偏移量开始读取？ - 2

    我有一个类似C的结构:SomeStruct:lenVarsstring:namestring:lname#...end我在:Person之前有一堆偏移量和长度。所有偏移量和长度都描述了:Person结构中的数据。如何从指定的偏移量、给定的长度或直到下一个偏移量开始读取数据？ 最佳答案 寻求偏移1234，然后将32个字节读入Strings:open'some-binary-file','r'do|f|f.seek1234s=f.read32#thoinyourcase,somethinglike:o=aBinData_object.r

  10. ruby - 十六进制字符串到 Ruby 中的 signed int 转换 - 2

    如何在ruby​​中将十六进制字符串转换为32位有符号整数？例如a="fb6d8cf1"#hexstring[a].pack('H*').unpack('l')#fromthedocumentationitunpackstoits32bitsignedint它转换为-242455045但实际答案是-76706575你能指出我做错了什么吗？ 最佳答案 您似乎遇到了字节序问题。这给出了期望的结果:[a].pack("H*").unpack("l>")#=>[-76706575]["038a67f90"].pack("H*").unpac

随机推荐