鱼C论坛

 找回密码
 立即注册
查看: 1911|回复: 17

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

[复制链接]
发表于 2023-1-24 14:07:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 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
  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]

下一关: 细胞分裂

最佳答案
2023-1-24 21:11:01
本帖最后由 ba21 于 2023-1-24 21:12 编辑
zhangjinxuan 发表于 2023-1-24 20:21
重点是思路,毕竟,python 的大数相乘也比较慢


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

闲着用弄弄,重在参与:
C代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. void getNewNumber(char *a, char *b);
  5. char *MultipyBigNumber(char *a, char *b);
  6. long long mod(char *divisor, long long number);
  7. void swap(char *a, char *b, int i);

  8. int main()
  9. {
  10.     char a[] = "51562165415643212316";
  11.     char b[] = "52213412312166548821";
  12.     int number = 998244353;

  13.     getNewNumber(a, b);

  14.     printf("%lld\n", mod(MultipyBigNumber(a,b), number));


  15.     return 0;
  16. }

  17. // 获取最小乘积所需要的被乘数和乘数
  18. void getNewNumber(char *a, char *b)
  19. {
  20.     int i;
  21.     for (i = 0; i < strlen(a); i++)
  22.     {
  23.         if (a[i] > b[i])
  24.         {
  25.             swap(a, b, i);
  26.         }
  27.     }
  28. }

  29. // 大数相乘
  30. char *MultipyBigNumber(char *a, char *b)
  31. {
  32.         int i, j, x, bitLeft, bitRight;
  33.         int lenA = strlen(a);
  34.         int lenB = strlen(b);
  35.         int len = lenA + lenB;
  36.         char *arr;
  37.         arr = (char*)malloc(sizeof(char)*(len+1));
  38.         arr[len] = '\0';
  39.         arr = &arr[len];

  40.         lenA--;
  41.         lenB--;
  42.         i = x = 0;
  43.         while(i < len - 1 || x != 0)
  44.         {
  45.                 for(j = 0; j <= i; j++)
  46.                 {
  47.                         bitLeft = lenA - i + j;
  48.                         bitRight = lenB - j;
  49.                         if(bitLeft >= 0 && bitRight >= 0)
  50.             {
  51.                 x += (a[bitLeft] - '0') * (b[bitRight] - '0');
  52.                         }

  53.                 }
  54.                 *(--arr) = x % 10 + '0';
  55.                 x /= 10;
  56.                 i++;
  57.         }

  58.         if(*arr++ == '0')
  59.     {
  60.         *arr = '\0';
  61.     }

  62.         return --arr;
  63. }

  64. // 求余数
  65. long long mod(char *divisor, long long number)
  66. {
  67.     long long m=0;
  68.     for(int i=0; i<strlen(divisor); i++){
  69.         m = (m*10+(divisor[i]-'0'))%number;
  70.     }

  71.     return m;
  72. }

  73. // 交换
  74. void swap(char *a, char *b, int i)
  75. {
  76.     a[i] = a[i]^b[i];
  77.     b[i] = a[i]^b[i];
  78.     a[i] = a[i]^b[i];
  79. }

复制代码


python代码
  1. import random

  2. def getNum(n):
  3.     s = ''
  4.     for i in range(n):
  5.         s+=str(random.randint(0, 9))
  6.     return s

  7. n = 200000
  8. a = getNum(n)
  9. b = getNum(n)


  10. lstA = list(a)
  11. lstB = list(b)
  12. for i in range(n):   
  13.     if lstA[i] > lstB[i]:
  14.         lstA[i], lstB[i] = lstB[i], lstA[i]

  15. newA = int(''.join(lstA))
  16. newB = int(''.join(lstB))

  17. print(newA * newB % 998244353)
复制代码

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-1-24 17:28:21 | 显示全部楼层
本帖最后由 ba21 于 2023-1-24 17:32 编辑

弄了个python,结果又是C了。我以为你只搞python呢。算了,不搞了
原理就是把2个数中每一位的最小数挑出来交换。得到的乘积最小。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-24 18:00:59 | 显示全部楼层
ba21 发表于 2023-1-24 17:28
弄了个python,结果又是C了。我以为你只搞python呢。算了,不搞了
原理就是把2个数中每一位的最小数挑出来 ...

python也行
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-24 18:05:37 | 显示全部楼层

python 支持大数相乘,这题用python没意义了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-24 20:21:00 | 显示全部楼层
ba21 发表于 2023-1-24 18:05
python 支持大数相乘,这题用python没意义了。

重点是思路,毕竟,python 的大数相乘也比较慢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-24 21:11:01 | 显示全部楼层    本楼为最佳答案   
本帖最后由 ba21 于 2023-1-24 21:12 编辑
zhangjinxuan 发表于 2023-1-24 20:21
重点是思路,毕竟,python 的大数相乘也比较慢


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

闲着用弄弄,重在参与:
C代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. void getNewNumber(char *a, char *b);
  5. char *MultipyBigNumber(char *a, char *b);
  6. long long mod(char *divisor, long long number);
  7. void swap(char *a, char *b, int i);

  8. int main()
  9. {
  10.     char a[] = "51562165415643212316";
  11.     char b[] = "52213412312166548821";
  12.     int number = 998244353;

  13.     getNewNumber(a, b);

  14.     printf("%lld\n", mod(MultipyBigNumber(a,b), number));


  15.     return 0;
  16. }

  17. // 获取最小乘积所需要的被乘数和乘数
  18. void getNewNumber(char *a, char *b)
  19. {
  20.     int i;
  21.     for (i = 0; i < strlen(a); i++)
  22.     {
  23.         if (a[i] > b[i])
  24.         {
  25.             swap(a, b, i);
  26.         }
  27.     }
  28. }

  29. // 大数相乘
  30. char *MultipyBigNumber(char *a, char *b)
  31. {
  32.         int i, j, x, bitLeft, bitRight;
  33.         int lenA = strlen(a);
  34.         int lenB = strlen(b);
  35.         int len = lenA + lenB;
  36.         char *arr;
  37.         arr = (char*)malloc(sizeof(char)*(len+1));
  38.         arr[len] = '\0';
  39.         arr = &arr[len];

  40.         lenA--;
  41.         lenB--;
  42.         i = x = 0;
  43.         while(i < len - 1 || x != 0)
  44.         {
  45.                 for(j = 0; j <= i; j++)
  46.                 {
  47.                         bitLeft = lenA - i + j;
  48.                         bitRight = lenB - j;
  49.                         if(bitLeft >= 0 && bitRight >= 0)
  50.             {
  51.                 x += (a[bitLeft] - '0') * (b[bitRight] - '0');
  52.                         }

  53.                 }
  54.                 *(--arr) = x % 10 + '0';
  55.                 x /= 10;
  56.                 i++;
  57.         }

  58.         if(*arr++ == '0')
  59.     {
  60.         *arr = '\0';
  61.     }

  62.         return --arr;
  63. }

  64. // 求余数
  65. long long mod(char *divisor, long long number)
  66. {
  67.     long long m=0;
  68.     for(int i=0; i<strlen(divisor); i++){
  69.         m = (m*10+(divisor[i]-'0'))%number;
  70.     }

  71.     return m;
  72. }

  73. // 交换
  74. void swap(char *a, char *b, int i)
  75. {
  76.     a[i] = a[i]^b[i];
  77.     b[i] = a[i]^b[i];
  78.     a[i] = a[i]^b[i];
  79. }

复制代码


python代码
  1. import random

  2. def getNum(n):
  3.     s = ''
  4.     for i in range(n):
  5.         s+=str(random.randint(0, 9))
  6.     return s

  7. n = 200000
  8. a = getNum(n)
  9. b = getNum(n)


  10. lstA = list(a)
  11. lstB = list(b)
  12. for i in range(n):   
  13.     if lstA[i] > lstB[i]:
  14.         lstA[i], lstB[i] = lstB[i], lstA[i]

  15. newA = int(''.join(lstA))
  16. newB = int(''.join(lstB))

  17. print(newA * newB % 998244353)
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zhangjinxuan + 5 + 5 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-24 21:14:45 | 显示全部楼层
ba21 发表于 2023-1-24 21:11
python 的大数相乘使用的是(算法)所以还真不慢。

闲着用弄弄,重在参与:

C的代码效率有待优化

Python的代码过了,恭喜
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-24 21:17:31 | 显示全部楼层
ba21 发表于 2023-1-24 21:11
python 的大数相乘使用的是(算法)所以还真不慢。

闲着用弄弄,重在参与:

我看了看你的代码,其实上,根本就不需要大数相乘,你可以看看题解
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-24 22:04:17 | 显示全部楼层
zhangjinxuan 发表于 2023-1-24 21:17
我看了看你的代码,其实上,根本就不需要大数相乘,你可以看看题解

你的代码不全。
使用你的代码代入数字,结果并不正确。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-24 22:18:20 | 显示全部楼层
ba21 发表于 2023-1-24 22:04
你的代码不全。
使用你的代码代入数字,结果并不正确。

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

这是在做题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-24 22:21:38 | 显示全部楼层
zhangjinxuan 发表于 2023-1-24 22:18
嗯?要输入三个数字哦?第一行的数是位数,第二行是 A,第三行是 B

这是在做题

是的,不正确。
麻烦你介绍下你代码的思路。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-24 23:19:52 | 显示全部楼层
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. int main(void) {
  4.     mpfr_t a, b, c;
  5.     mpfr_inits2(10000000, a, b, c, NULL);
  6.     mpfr_set_str(a, "10", 10, MPFR_RNDD);
  7.     mpfr_set_str(b, "1000000", 10, MPFR_RNDD);
  8.     mpfr_pow(c, a, b, MPFR_RNDD);
  9.     mpfr_printf("%.0Rf\n", c);
  10.     mpfr_clears(a, b, c, NULL);
  11.     mpfr_free_cache();
  12.     return 0;
  13. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-25 09:21:49 | 显示全部楼层
人造人 发表于 2023-1-24 23:19
我C语言也可以使用mpfr这个库实现大数运算,^_^
https://fishc.com.cn/forum.php?mod=redirect&goto=fin ...

哈哈
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-25 09:22:50 | 显示全部楼层
ba21 发表于 2023-1-24 22:21
是的,不正确。
麻烦你介绍下你代码的思路。

就是要不全,防止有些人直接抄答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-25 09:23:23 | 显示全部楼层
ba21 发表于 2023-1-24 22:21
是的,不正确。
麻烦你介绍下你代码的思路。


这个是对的吧:
  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. char a[210001], b[210001];
  4. int n;
  5. long long ans = 0, p = 998244353;

  6. long long eval_ans() {
  7.         long long x = 1, avalue = 0, bvalue = 0;
  8.         for (int i = n; i >= 1; --i) {
  9.                 long long ap = (long long)(a[i] - '0') * x;
  10.                 long long bp = (long long)(b[i] - '0') * x;
  11.                 ap %= p;
  12.                 bp %= p;
  13.                 avalue += ap;
  14.                 bvalue += bp;
  15.                 avalue %= p;
  16.                 bvalue %= p;
  17.                 x *= 10;
  18.                 x %= p;
  19.         }
  20.         return avalue * bvalue % p;
  21. }

  22. int main() {
  23.         scanf("%d%s%s", &n, a + 1, b + 1);
  24.         for (int i = 1; i <= n; ++i) {
  25.                 if (a[i] > b[i]) {
  26.                         swap(a[i], b[i]);
  27.                 }
  28.         }
  29.         printf("%lld", eval_ans());
  30.         return 0;
  31. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-25 17:12:55 | 显示全部楼层

对的,结果是你代码中数组的利用过了0
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-25 19:37:15 | 显示全部楼层
ba21 发表于 2023-1-25 17:12
对的,结果是你代码中数组的利用过了0

我是 1 ~ base
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-2-3 14:07:57 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 17:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表