【C++板块提升计划】梦想护卫舰 第12期 破译密码
本帖最后由 zhangjinxuan 于 2023-1-25 20:14 编辑上一关：数楼梯
梦想护卫舰 第12期 破译密码
你们走过了楼梯，来到了神庙大门，这门需要密码……
密码门上只有两串数字，而地上有一串文字：
这两串数字位数是相同的，一个是 A， 一个是 B, 有 n 位，1 <= n <= 200000，也是一个合法的十进制数字
现在你可以执行多次这个操作（或者不操作）：
选择一个数字 i ，1 <= i <= n，将 A 从左往右数的第 i 位 与 B 从左往右数的第 i 位交换
A * B 得到的最小值就是密码
但这个数可能很大，所以你还要对 998244353 取余
注意：我们要找的是 A * B 的最小值，请不要最小化余数
输入格式
三行，第一行一个整数 n，第二行是 A，第三行是 B
输出格式
一个整数，表示最小值
输入样例1
2
13
22
输出样例1
276
样例解释1
交换个位（i = 1）,A = 12， B = 23， 12 * 23 = 276，这是最小值了，不可能找到更小的
输入样例2
8
20220122
21002300
输出样例2
54558365
样例解释2
交换个位（i = 1)，十位 (i = 2)，万位 (i = 5)，十万位（i = 6)，A = 20000100, B = 21222322，A * B 998244353 = 54558365
注意：该题非原创，来自 ARC154，链接在这里
static/image/hrline/1.gif
答案与解析
**** Hidden Message *****
最佳战士
名字：ba21
奖励：最佳答案+5鱼币5荣誉
其他说明：使用语言为python
static/image/hrline/1.gif
**** Hidden Message *****
下一关: 细胞分裂
本帖最后由 ba21 于 2023-1-24 17:32 编辑
弄了个python，结果又是C了。我以为你只搞python呢。算了，不搞了
原理就是把2个数中每一位的最小数挑出来交换。得到的乘积最小。 ba21 发表于 2023-1-24 17:28
弄了个python，结果又是C了。我以为你只搞python呢。算了，不搞了
原理就是把2个数中每一位的最小数挑出来 ...
python也行
zhangjinxuan 发表于 2023-1-24 18:00
python也行
python 支持大数相乘，这题用python没意义了。 ba21 发表于 2023-1-24 18:05
python 支持大数相乘，这题用python没意义了。
重点是思路，毕竟，python 的大数相乘也比较慢{:10_284:} 本帖最后由 ba21 于 2023-1-24 21:12 编辑
zhangjinxuan 发表于 2023-1-24 20:21
重点是思路，毕竟，python 的大数相乘也比较慢
python 的大数相乘使用的是（算法）所以还真不慢。
闲着用弄弄，重在参与：
C代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void getNewNumber(char *a, char *b);
char *MultipyBigNumber(char *a, char *b);
long long mod(char *divisor, long long number);
void swap(char *a, char *b, int i);
int main()
{
char a[] = "51562165415643212316";
char b[] = "52213412312166548821";
int number = 998244353;
getNewNumber(a, b);
printf("%lld\n", mod(MultipyBigNumber(a,b), number));
return 0;
}
// 获取最小乘积所需要的被乘数和乘数
void getNewNumber(char *a, char *b)
{
int i;
for (i = 0; i < strlen(a); i++)
{
if (a > b)
{
swap(a, b, i);
}
}
}
// 大数相乘
char *MultipyBigNumber(char *a, char *b)
{
int i, j, x, bitLeft, bitRight;
int lenA = strlen(a);
int lenB = strlen(b);
int len = lenA + lenB;
char *arr;
arr = (char*)malloc(sizeof(char)*(len+1));
arr = '\0';
arr = &arr;
lenA--;
lenB--;
i = x = 0;
while(i < len - 1 || x != 0)
{
for(j = 0; j <= i; j++)
{
bitLeft = lenA - i + j;
bitRight = lenB - j;
if(bitLeft >= 0 && bitRight >= 0)
{
x += (a - '0') * (b - '0');
}
}
*(--arr) = x % 10 + '0';
x /= 10;
i++;
}
if(*arr++ == '0')
{
*arr = '\0';
}
return --arr;
}
// 求余数
long long mod(char *divisor, long long number)
{
long long m=0;
for(int i=0; i<strlen(divisor); i++){
m = (m*10+(divisor-'0'))%number;
}
return m;
}
// 交换
void swap(char *a, char *b, int i)
{
a = a^b;
b = a^b;
a = a^b;
}
python代码
import random
def getNum(n):
s = ''
for i in range(n):
s+=str(random.randint(0, 9))
return s
n = 200000
a = getNum(n)
b = getNum(n)
lstA = list(a)
lstB = list(b)
for i in range(n):
if lstA > lstB:
lstA, lstB = lstB, lstA
newA = int(''.join(lstA))
newB = int(''.join(lstB))
print(newA * newB % 998244353)
ba21 发表于 2023-1-24 21:11
python 的大数相乘使用的是（算法）所以还真不慢。
闲着用弄弄，重在参与：
C的代码效率有待优化{:10_282:}
Python的代码过了，恭喜{:10_256:} ba21 发表于 2023-1-24 21:11
python 的大数相乘使用的是（算法）所以还真不慢。
闲着用弄弄，重在参与：
我看了看你的代码，其实上，根本就不需要大数相乘，你可以看看题解{:10_282:} zhangjinxuan 发表于 2023-1-24 21:17
我看了看你的代码，其实上，根本就不需要大数相乘，你可以看看题解
你的代码不全。
使用你的代码代入数字，结果并不正确。 ba21 发表于 2023-1-24 22:04
你的代码不全。
使用你的代码代入数字，结果并不正确。
嗯？要输入三个数字哦？第一行的数是位数，第二行是 A，第三行是 B
这是在做题 zhangjinxuan 发表于 2023-1-24 22:18
嗯？要输入三个数字哦？第一行的数是位数，第二行是 A，第三行是 B
这是在做题
是的，不正确。
麻烦你介绍下你代码的思路。 zhangjinxuan 发表于 2023-1-24 20:21
重点是思路，毕竟，python 的大数相乘也比较慢
我C语言也可以使用mpfr这个库实现大数运算，^_^
https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=204663&pid=5618893
#include <stdio.h>
#include <mpfr.h>
int main(void) {
mpfr_t a, b, c;
mpfr_inits2(10000000, a, b, c, NULL);
mpfr_set_str(a, "10", 10, MPFR_RNDD);
mpfr_set_str(b, "1000000", 10, MPFR_RNDD);
mpfr_pow(c, a, b, MPFR_RNDD);
mpfr_printf("%.0Rf\n", c);
mpfr_clears(a, b, c, NULL);
mpfr_free_cache();
return 0;
}
人造人 发表于 2023-1-24 23:19
我C语言也可以使用mpfr这个库实现大数运算，^_^
https://fishc.com.cn/forum.php?mod=redirect&goto=fin ...
哈哈{:10_256:} ba21 发表于 2023-1-24 22:21
是的，不正确。
麻烦你介绍下你代码的思路。
就是要不全，防止有些人直接抄答案 ba21 发表于 2023-1-24 22:21
是的，不正确。
麻烦你介绍下你代码的思路。
这个是对的吧：
#include <bits/stdc++.h>
using namespace std;
char a, b;
int n;
long long ans = 0, p = 998244353;
long long eval_ans() {
long long x = 1, avalue = 0, bvalue = 0;
for (int i = n; i >= 1; --i) {
long long ap = (long long)(a - '0') * x;
long long bp = (long long)(b - '0') * x;
ap %= p;
bp %= p;
avalue += ap;
bvalue += bp;
avalue %= p;
bvalue %= p;
x *= 10;
x %= p;
}
return avalue * bvalue % p;
}
int main() {
scanf("%d%s%s", &n, a + 1, b + 1);
for (int i = 1; i <= n; ++i) {
if (a > b) {
swap(a, b);
}
}
printf("%lld", eval_ans());
return 0;
} zhangjinxuan 发表于 2023-1-25 09:23
这个是对的吧：
对的，结果是你代码中数组的利用过了0 ba21 发表于 2023-1-25 17:12
对的，结果是你代码中数组的利用过了0
我是 1 ~ base {:10_284:} {:10_254:}
页:
[1]