当前位置：首页 > news >正文

蓝桥杯训练 k进制数的数位交换问题

news 来源：原创 2024/5/3 15:37:48

问题进入

$k$ 进制数的数位交换问题，就是给出一个 $k$ 进制的数，求出其中任意两个数位交换后的大小

我们先以十进制数 $123$ 为例，假如交换第一位和第二位变成 $213$ 。那么这两个数之间存在什么关系呢，我们注意到百位上本来是 $1$ ，变成了 $2$ 之后原数就要增加 $(2 - 1) * 100$ ；十位上本来是 $2$ ，变成 $1$ 之后原数就要增加 $(1 - 2) * 10$ 。那么再考虑交换前左边的数小于右边的数，就变成了减的较多。总之，拿每一位变化后的数减去变化前的数再乘以该位的权值，不必去考虑谁大谁小，二者相加即是原数变化的值。

我们得出了，假如一个 $k$ 进制数 $n$ （ $n$ 是转换为十进制的大小）的第 $i$ 位和第 $j$ 位( $i$ 在 $j$ 左边)交换，其数位对应权值分别为 $a [i]$ 和 $a [j]$ 。那么交换后的十进制 $m = (i - j) * a [j] + (j - i) * a [j]$

其中数位权值数组这样初始化：

int a[maxn];
int P;       //对P取模，因为每一位可能很大
void init(string s,int k){  //k进制的字符串s
    int m=s.size();
    a[m-1]=1;
    for(int i=m-2;i>=0;i--){
        a[i]=(a[i+1]*k)%P;
    }
}

例题解析

题目链接

这道题是我做蓝桥杯练习时碰到的，之前没注意过这类题，第一次我写的是直接交换，每次去求一个串的值，但是只过了一半的测试，超时了。显然数位交换和求字符串值那里超时了。那怎么优化呢？看了网上，才知道要用到上面提到的数位交换后数的大小变化的性质，简单研究了一番，便知道怎么解决这类问题了。写篇博客加深印象，这种题也可能作为 $I C P C$ 的简单题来出。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string s;
int P;
int a[2010];

void init(){
    int m=s.size();
    a[m-1]=1;
    for(int i=m-2;i>=0;i--){
        a[i]=(a[i+1]*26)%P;  //本来想用快速幂求，但是考虑到最26^2000，只能边乘边模才确保不会溢出
    }
}

int solve(string str){
    int tmp=0;
    for(int i=0;i<str.size();i++){
        tmp=tmp*26+str[i]-'A';
        tmp%=P;
    }
    return tmp;

}
int main()
{
    cin>>s;
    scanf("%d",&P);
    init();
    int flag=1;
    int ans=solve(s);
    if(ans==0){
        flag=0;
        printf("0 0\n");
    }else{
        bool exit=0;
        for(int i=0;i<s.size();i++){
            for(int j=i+1;j<s.size();j++){
                int res=(s[i]-s[j])*a[j]+(s[j]-s[i])*a[i];
                if( (res+ans+P)%P==0 ){
                    printf("%d %d",i+1,j+1);
                    flag=0; exit=1; break;
                }
            }
            if(exit) break;
        }
    }
    if(flag) printf("-1 -1\n");
    return 0;
}