【C++板块提升计划】梦想护卫舰 第12期 破译密码

zhangjinxuan

上一关：数楼梯

梦想护卫舰 第12期 破译密码

你们走过了楼梯，来到了神庙大门，这门需要密码……

密码门上只有两串数字，而地上有一串文字：

这两串数字位数是相同的，一个是 A， 一个是 B, 有 n 位，1 <= n <= 200000，也是一个合法的十进制数字
现在你可以执行多次这个操作（或者不操作）：
选择一个数字 i ，1 <= i <= n，将 A 从左往右数的第 i 位 与 B 从左往右数的第 i 位交换
A * B 得到的最小值就是密码
但这个数可能很大，所以你还要对 998244353 取余
注意：我们要找的是 A * B 的最小值，请不要最小化余数

输入格式
三行，第一行一个整数 n，第二行是 A，第三行是 B

输出格式
一个整数，表示最小值

输入样例1

1. 2
   
2. 13
   
3. 22
   

复制代码

输出样例1

1. 276

复制代码

样例解释1
交换个位（i = 1）,A = 12， B = 23， 12 * 23 = 276，这是最小值了，不可能找到更小的

输入样例2

1. 8
   
2. 20220122
   
3. 21002300
   

复制代码

输出样例2

1. 54558365

复制代码

样例解释2
交换个位（i = 1)，十位 (i = 2)，万位 (i = 5)，十万位（i = 6)，A = 20000100, B = 21222322，A * B 998244353 = 54558365

注意：该题非原创，来自 ARC154，链接在这里

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士
名字：ba21
奖励：最佳答案+5鱼币5荣誉
其他说明：使用语言为python

                               
登录/注册后可看大图

游客，如果您要查看本帖隐藏内容请回复

[/hide]

下一关: 细胞分裂

ba21

弄了个python，结果又是C了。我以为你只搞python呢。算了，不搞了
原理就是把2个数中每一位的最小数挑出来交换。得到的乘积最小。

zhangjinxuan

ba21 发表于 2023-1-24 17:28
弄了个python，结果又是C了。我以为你只搞python呢。算了，不搞了
原理就是把2个数中每一位的最小数挑出来 ...

python也行

ba21

zhangjinxuan 发表于 2023-1-24 18:00
python也行

python 支持大数相乘，这题用python没意义了。

zhangjinxuan

ba21 发表于 2023-1-24 18:05
python 支持大数相乘，这题用python没意义了。

重点是思路，毕竟，python 的大数相乘也比较慢

ba21

zhangjinxuan 发表于 2023-1-24 20:21
重点是思路，毕竟，python 的大数相乘也比较慢

python 的大数相乘使用的是（算法）所以还真不慢。

闲着用弄弄，重在参与：
C代码

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. 
   
6. void getNewNumber(char *a, char *b);
   
7. char *MultipyBigNumber(char *a, char *b);
   
8. long long mod(char *divisor, long long number);
   
9. void swap(char *a, char *b, int i);
   
10. 
    
11. int main()
    
12. {
    
13.     char a[] = "51562165415643212316";
    
14.     char b[] = "52213412312166548821";
    
15.     int number = 998244353;
    
16. 
    
17.     getNewNumber(a, b);
    
18. 
    
19.     printf("%lld\n", mod(MultipyBigNumber(a,b), number));
    
20. 
    
21. 
    
22.     return 0;
    
23. }
    
24. 
    
25. // 获取最小乘积所需要的被乘数和乘数
    
26. void getNewNumber(char *a, char *b)
    
27. {
    
28.     int i;
    
29.     for (i = 0; i < strlen(a); i++)
    
30.     {
    
31.         if (a[i] > b[i])
    
32.         {
    
33.             swap(a, b, i);
    
34.         }
    
35.     }
    
36. }
    
37. 
    
38. // 大数相乘
    
39. char *MultipyBigNumber(char *a, char *b)
    
40. {
    
41.         int i, j, x, bitLeft, bitRight;
    
42.         int lenA = strlen(a);
    
43.         int lenB = strlen(b);
    
44.         int len = lenA + lenB;
    
45.         char *arr;
    
46.         arr = (char*)malloc(sizeof(char)*(len+1));
    
47.         arr[len] = '\0';
    
48.         arr = &arr[len];
    
49. 
    
50.         lenA--;
    
51.         lenB--;
    
52.         i = x = 0;
    
53.         while(i < len - 1 || x != 0)
    
54.         {
    
55.                 for(j = 0; j <= i; j++)
    
56.                 {
    
57.                         bitLeft = lenA - i + j;
    
58.                         bitRight = lenB - j;
    
59.                         if(bitLeft >= 0 && bitRight >= 0)
    
60.             {
    
61.                 x += (a[bitLeft] - '0') * (b[bitRight] - '0');
    
62.                         }
    
63. 
    
64.                 }
    
65.                 *(--arr) = x % 10 + '0';
    
66.                 x /= 10;
    
67.                 i++;
    
68.         }
    
69. 
    
70.         if(*arr++ == '0')
    
71.     {
    
72.         *arr = '\0';
    
73.     }
    
74. 
    
75.         return --arr;
    
76. }
    
77. 
    
78. // 求余数
    
79. long long mod(char *divisor, long long number)
    
80. {
    
81.     long long m=0;
    
82.     for(int i=0; i<strlen(divisor); i++){
    
83.         m = (m*10+(divisor[i]-'0'))%number;
    
84.     }
    
85. 
    
86.     return m;
    
87. }
    
88. 
    
89. // 交换
    
90. void swap(char *a, char *b, int i)
    
91. {
    
92.     a[i] = a[i]^b[i];
    
93.     b[i] = a[i]^b[i];
    
94.     a[i] = a[i]^b[i];
    
95. }
    
96. 
    

复制代码

python代码

1. import random
   
2. 
   
3. def getNum(n):
   
4.     s = ''
   
5.     for i in range(n):
   
6.         s+=str(random.randint(0, 9))
   
7.     return s
   
8. 
   
9. n = 200000
   
10. a = getNum(n)
    
11. b = getNum(n)
    
12. 
    
13. 
    
14. lstA = list(a)
    
15. lstB = list(b)
    
16. for i in range(n):   
    
17.     if lstA[i] > lstB[i]:
    
18.         lstA[i], lstB[i] = lstB[i], lstA[i]
    
19. 
    
20. newA = int(''.join(lstA))
    
21. newB = int(''.join(lstB))
    
22. 
    
23. print(newA * newB % 998244353)
    

复制代码

zhangjinxuan

ba21 发表于 2023-1-24 21:11
python 的大数相乘使用的是（算法）所以还真不慢。

闲着用弄弄，重在参与：

C的代码效率有待优化

Python的代码过了，恭喜

zhangjinxuan

ba21 发表于 2023-1-24 21:11
python 的大数相乘使用的是（算法）所以还真不慢。

闲着用弄弄，重在参与：

我看了看你的代码，其实上，根本就不需要大数相乘，你可以看看题解

ba21

zhangjinxuan 发表于 2023-1-24 21:17
我看了看你的代码，其实上，根本就不需要大数相乘，你可以看看题解

你的代码不全。
使用你的代码代入数字，结果并不正确。

zhangjinxuan

ba21 发表于 2023-1-24 22:04
你的代码不全。
使用你的代码代入数字，结果并不正确。

嗯？要输入三个数字哦？第一行的数是位数，第二行是 A，第三行是 B

这是在做题

ba21

zhangjinxuan 发表于 2023-1-24 22:18
嗯？要输入三个数字哦？第一行的数是位数，第二行是 A，第三行是 B

这是在做题

是的，不正确。
麻烦你介绍下你代码的思路。

人造人

zhangjinxuan 发表于 2023-1-24 20:21
重点是思路，毕竟，python 的大数相乘也比较慢

我C语言也可以使用mpfr这个库实现大数运算，^_^
https://fishc.com.cn/forum.php?m ... 663&pid=5618893

1. #include <stdio.h>
   
2. #include <mpfr.h>
   
3. 
   
4. int main(void) {
   
5.     mpfr_t a, b, c;
   
6.     mpfr_inits2(10000000, a, b, c, NULL);
   
7.     mpfr_set_str(a, "10", 10, MPFR_RNDD);
   
8.     mpfr_set_str(b, "1000000", 10, MPFR_RNDD);
   
9.     mpfr_pow(c, a, b, MPFR_RNDD);
   
10.     mpfr_printf("%.0Rf\n", c);
    
11.     mpfr_clears(a, b, c, NULL);
    
12.     mpfr_free_cache();
    
13.     return 0;
    
14. }
    

复制代码

zhangjinxuan

人造人 发表于 2023-1-24 23:19
我C语言也可以使用mpfr这个库实现大数运算，^_^
https://fishc.com.cn/forum.php?mod=redirect&goto=fin ...

哈哈

zhangjinxuan

ba21 发表于 2023-1-24 22:21
是的，不正确。
麻烦你介绍下你代码的思路。

就是要不全，防止有些人直接抄答案

zhangjinxuan

ba21 发表于 2023-1-24 22:21
是的，不正确。
麻烦你介绍下你代码的思路。

这个是对的吧：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. char a[210001], b[210001];
   
5. int n;
   
6. long long ans = 0, p = 998244353;
   
7. 
   
8. long long eval_ans() {
   
9.         long long x = 1, avalue = 0, bvalue = 0;
   
10.         for (int i = n; i >= 1; --i) {
    
11.                 long long ap = (long long)(a[i] - '0') * x;
    
12.                 long long bp = (long long)(b[i] - '0') * x;
    
13.                 ap %= p;
    
14.                 bp %= p;
    
15.                 avalue += ap;
    
16.                 bvalue += bp;
    
17.                 avalue %= p;
    
18.                 bvalue %= p;
    
19.                 x *= 10;
    
20.                 x %= p;
    
21.         }
    
22.         return avalue * bvalue % p;
    
23. }
    
24. 
    
25. int main() {
    
26.         scanf("%d%s%s", &n, a + 1, b + 1);
    
27.         for (int i = 1; i <= n; ++i) {
    
28.                 if (a[i] > b[i]) {
    
29.                         swap(a[i], b[i]);
    
30.                 }
    
31.         }
    
32.         printf("%lld", eval_ans());
    
33.         return 0;
    
34. }

复制代码

ba21

zhangjinxuan 发表于 2023-1-25 09:23
这个是对的吧：

对的，结果是你代码中数组的利用过了0

zhangjinxuan

ba21 发表于 2023-1-25 17:12
对的，结果是你代码中数组的利用过了0

我是 1 ~ base

元豪