[已解决]【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

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，链接在这里

                               
登录/注册后可看大图

答案与解析

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

[/hide]

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

                               
登录/注册后可看大图

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

[/hide]

下一关: 细胞分裂

最佳答案

月排行榜 / 总排行榜

ba21

2023-1-24 21:11:01

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[i] > b[i])
        {
            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[len] = '\0';
        arr = &arr[len];

        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[bitLeft] - '0') * (b[bitRight] - '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[i]-'0'))%number;
    }

    return m;
}

// 交换
void swap(char *a, char *b, int i)
{
    a[i] = a[i]^b[i];
    b[i] = a[i]^b[i];
    a[i] = a[i]^b[i];
}

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[i] > lstB[i]:
        lstA[i], lstB[i] = lstB[i], lstA[i]

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

print(newA * newB % 998244353)

跳转到最佳答案楼层

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代码

#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[i] > b[i])
        {
            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[len] = '\0';
        arr = &arr[len];

        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[bitLeft] - '0') * (b[bitRight] - '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[i]-'0'))%number;
    }

    return m;
}

// 交换
void swap(char *a, char *b, int i)
{
    a[i] = a[i]^b[i];
    b[i] = a[i]^b[i];
    a[i] = a[i]^b[i];
}

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[i] > lstB[i]:
        lstA[i], lstB[i] = lstB[i], lstA[i]

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

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

#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;
}

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
是的，不正确。
麻烦你介绍下你代码的思路。

这个是对的吧：

#include <bits/stdc++.h>
using namespace std;

char a[210001], b[210001];
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[i] - '0') * x;
                long long bp = (long long)(b[i] - '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[i] > b[i]) {
                        swap(a[i], b[i]);
                }
        }
        printf("%lld", eval_ans());
        return 0;
}

ba21

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

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

zhangjinxuan

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

我是 1 ~ base

元豪