BC158. [NOIP1999]回文数
描述
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
STEP1：87+78 = 165 STEP2：165+561 = 726
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
进制N>10时，使用大写'A'字母表示10，'B'表示11,...,'E'表示16
输入描述
两行，分别为N,M输出描述
STEP=ans示例1
输入:
9 87
输出:
STEP=6
C 解法, 执行用时: 2ms, 内存消耗: 256KB, 提交时间: 2022-07-28
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
char c[100]={0};
bool IsPalindrome(char *a,len)
{
int left=0;
int right=len-1;
while((left)<(right))
{
if(a[left++]!=a[right--])
{
return false;
break;
}
}
return true;
}
int getInt(char n)
{
if(n>='0'&&n<='9')
{
return n-'0';
}
else
{
return n-'A'+10;
}
}
char getChar(int n)
{
if(n>=0&&n<=9)
{
return n+'0';
}
else
{
return n-10+'A';
}
}
void add(char *a,int N,int len)
{
int sum1=0;
int sum2=0;
int tail=0;
int begin=0;
int end=len-1;
int i=0;
while(end>=0)
{
sum1=getInt(a[begin]);
sum2=getInt(a[end]);
c[i]=getChar((sum1+sum2+tail)%N);
tail=(sum1+sum2+tail)/N;
end--;
begin++;
i++;
}
while(tail>0)
{
c[i]=getChar(tail%N);
tail/=N;
i++;
}
}
int main()
{
char a[100]={0};
int N=0;
scanf("%d",&N);
getchar();
scanf("%s",a);
int len=strlen(a);
if(IsPalindrome(a,len))
{
printf("STEP=%d\n",1);
return 1;
}
int count=0;
while(!IsPalindrome(a,len))
{
add(a,N,len);
strcpy(a,c);
len=strlen(c);
count++;
if(count>=31)
{
printf("Impossible!\n");
return 0;
}
}
printf("STEP=%d\n",count);
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2022-07-16
#include<stdio.h>
#include<math.h>
#include<string.h>
long long convert_10(long long n, long long N)//N进制转化为十进制
{
long long ret = 0;
int count = 1;
long long tmp = n;
while (tmp /= 10)
{
count++;
}
int i = 0;
for (i = count - 1; i >= 0; i--)
{
ret += ((long long)(n / pow(10, i)) % 10) * (long long)pow(N, i);
}
return ret;
}
long long convert_N(long long n, long long N)//十进制转化为十进制
{
if (n > N - 1)
{
return convert_N(n / N, N) * 10 + n % N;
}
return n % N;
}
long long convert_N_10(char* p, int N)
{
long long key = 0;
int len = strlen(p);//转化为数组
int i = 0;
if (N == 2)//二进制转化为十进制
{
for (i = len - 1; i >= 0; i--)
{
key += (long long)(p[i] - '0') * pow(2, len - i - 1);
}
}
else if (N == 16)//十六进制转化为十进制
{
for (i = len - 1; i >= 0; i--)
{
if (p[i] >= 'A' && p[i] <= 'F')
{
key += (long long)((p[i] - 55) * pow(16, len - i - 1));//55ACSLL表为A
}
else
{
key += (long long)((p[i] - '0') * pow(16, len - i - 1));
}
}
}
return key;
}
void reverse(char* p)//左右对调
{
int left = 0;
int right = strlen(p) - 1;
while (left < right)
{
char tmp = p[left];
p[left] = p[right];
p[right] = tmp;
left++;
right--;
}
}
void convert_10_N(long long n, char* p, int N)
{
long long tmp = n;
int i = 0;
if (N == 2)
{
while (tmp)
{
p[i++] = (tmp % 2) + '0';
tmp /= 2;
}
}
else if (N == 16)
{
while (tmp)
{
long long ret = tmp;
tmp /= 16;
if (ret % 16 >= 10 && ret % 16 <= 16)
{
p[i++] = ret % 16 - 10 + 'A';
}
else
{
p[i++] = ret % 16 + '0';
}
}
}
reverse(p);
}
int main()
{
long long N = 0;
scanf("%lld", &N);
int count = 0;
if (N > 2 && N <= 10)
{
long long num = 0;
scanf("%lld", &num);
long long value = num;
while (count <= 30)
{
count++;
long long ret1 = value;
long long ret2 = 0;
long long tmp = ret1;
while (tmp)
{
ret2 = ret2 * 10 + tmp % 10;
tmp /= 10;
}
long long key1 = convert_10(ret1, N);
long long key2 = convert_10(ret2, N);
long long ret3 = convert_N(key1 + key2, N);
tmp = ret3;
long long ret4 = 0;
while (tmp)
{
ret4 = ret4 * 10 + tmp % 10;
tmp /= 10;
}
if (ret4 == ret3)
{
break;
}
value = ret3;
}
}
else if (N == 2 || N == 16)
{
char num1[100] = { 0 };
scanf("%s", num1);
int len1 = strlen(num1);
char num2[100] = { 0 };
int i = 0;
int j = 0;
for (i = len1-1; i >= 0; i--)
{
num2[j++] = num1[i];
}
while (count <= 30)
{
count++;
long long key1 = convert_N_10(num1,N);
long long key2 = convert_N_10(num2,N);
char num3[100] = { 0 };
convert_10_N(key1 + key2, num3, N);
char num4[100] = { 0 };
strcpy(num4, num3);
reverse(num4);
if (strcmp(num4, num3) == 0)
{
break;
}
strcpy(num1, num3);
strcpy(num2, num4);
}
}
if (count <= 30)
{
printf("STEP=%d\n", count);
}
else
{
printf("Impossible!\n");
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2022-06-16
#include<stdio.h>
#include<math.h>
#include<string.h>
long long convert_10(long long n, long long N)
{
long long ret = 0;
int count = 1;
long long tmp = n;
while (tmp /= 10)
{
count++;
}
int i = 0;
for (i = count - 1; i >= 0; i--)
{
ret += ((long long)(n / pow(10, i)) % 10) * (long long)pow(N, i);
}
return ret;
}
long long convert_N(long long n, long long N)
{
if (n > N - 1)
{
return convert_N(n / N, N) * 10 + n % N;
}
return n % N;
}
long long convert_N_10(char* p, int N)
{
long long key = 0;
int len = strlen(p);
int i = 0;
if (N == 2)
{
for (i = len - 1; i >= 0; i--)
{
key += (long long)(p[i] - '0') * pow(2, len - i - 1);
}
}
else if (N == 16)
{
for (i = len - 1; i >= 0; i--)
{
if (p[i] >= 'A' && p[i] <= 'F')
{
key += (long long)((p[i] - 55) * pow(16, len - i - 1));
}
else
{
key += (long long)((p[i] - '0') * pow(16, len - i - 1));
}
}
}
return key;
}
void reverse(char* p)
{
int left = 0;
int right = strlen(p) - 1;
while (left < right)
{
char tmp = p[left];
p[left] = p[right];
p[right] = tmp;
left++;
right--;
}
}
void convert_10_N(long long n, char* p, int N)
{
long long tmp = n;
int i = 0;
if (N == 2)
{
while (tmp)
{
p[i++] = (tmp % 2) + '0';
tmp /= 2;
}
}
else if (N == 16)
{
while (tmp)
{
long long ret = tmp;
tmp /= 16;
if (ret % 16 >= 10 && ret % 16 <= 16)
{
p[i++] = ret % 16 - 10 + 'A';
}
else
{
p[i++] = ret % 16 + '0';
}
}
}
reverse(p);
}
int main()
{
long long N = 0;
scanf("%lld", &N);
int count = 0;
if (N > 2 && N <= 10)
{
long long num = 0;
scanf("%lld", &num);
long long value = num;
while (count <= 30)
{
count++;
long long ret1 = value;
long long ret2 = 0;
long long tmp = ret1;
while (tmp)
{
ret2 = ret2 * 10 + tmp % 10;
tmp /= 10;
}
long long key1 = convert_10(ret1, N);
long long key2 = convert_10(ret2, N);
long long ret3 = convert_N(key1 + key2, N);
tmp = ret3;
long long ret4 = 0;
while (tmp)
{
ret4 = ret4 * 10 + tmp % 10;
tmp /= 10;
}
if (ret4 == ret3)
{
break;
}
value = ret3;
}
}
else if (N == 2 || N == 16)
{
char num1[100] = { 0 };
scanf("%s", num1);
int len1 = strlen(num1);
char num2[100] = { 0 };
int i = 0;
int j = 0;
for (i = len1-1; i >= 0; i--)
{
num2[j++] = num1[i];
}
while (count <= 30)
{
count++;
long long key1 = convert_N_10(num1,N);
long long key2 = convert_N_10(num2,N);
char num3[100] = { 0 };
convert_10_N(key1 + key2, num3, N);
char num4[100] = { 0 };
strcpy(num4, num3);
reverse(num4);
if (strcmp(num4, num3) == 0)
{
break;
}
strcpy(num1, num3);
strcpy(num2, num4);
}
}
if (count <= 30)
{
printf("STEP=%d\n", count);
}
else
{
printf("Impossible!\n");
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2022-04-02
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
bool Judge(char*M)//判断函数
{
int n = strlen(M);
for (int i = 0; i < n / 2; i++)
if (M[i] != M[n - i - 1])//只要左边与右边有一个不一样就为假
return false;
return true;
}
void Reverseadd(int N, char*M,char*M_c)
{
int n = strlen(M);
int ret = 0;
int i = 0;
for (i = 0; i < n; i++)
{
char temp = M[i];//存取原数据用于计算进位
M[i] = (M[i] + M_c[n - i - 1] + ret-2*'0') % N+'0';
ret = (temp + M_c[n - i - 1] + ret - 2 * '0') / N;
}
while (ret)
{
M[i] = ret % N+'0';
ret /= N;
i++;
}
}
int main()
{
char M[100] = { 0 };
char M_c[100] = { 0 };
char N;
scanf("%d", &N);
getchar();
scanf("%s", &M);
for (int i = 0; i < strlen(M); i++)
{
if (M[i] >= 'A')
M[i] = M[i] - 'A' + 10+'0';//转化为以’0‘为基准的字符
}
int STEP = 0;
while (STEP++ <= 30)
{
strcpy(M_c, M);
Reverseadd(N, M,M_c);
if (Judge(M))
{
printf("STEP=%d", STEP);
return 0;
}
}
printf("Impossible!");
}
C 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2022-06-16
#include <stdio.h>
#include <string.h>
int judge(char* p)
{
int i = 0;
int len = strlen(p);
while (p[i] == p[len-1-i] && i <= len / 2)
{
i++;
}
if (i > len / 2)
{
return 1;
}
else
{
return 0;
}
}
void add(char* p, char* s,int N)
{
int len = strlen(p);
int ret = 0;
int i = 0;
for (i = 0; i < len; i++)
{
char tmp = p[i];
p[i] = (p[i] + s[i] + ret - 2 * '0') % N + '0';
ret = (tmp + s[i] + ret - 2 * '0') / N;
}
while (ret)
{
//此时i未被置为0,i=len
p[i] = ret % N + '0';
ret /= N;
i++;
}
//此时虽然num数组的顺序颠倒的，但是函数结束后，num_c数组需要被颠倒一下，所以换不换顺序无所谓
//而且不影响判断是否是回文数
}
int main()
{
int N = 0;
scanf("%d", &N);
int count = 0;
char num[100] = { 0 };
char num_c[100] = { 0 };
getchar();
scanf("%s", num);
if (N > 10)
{
int i = 0;
for (i = 0; i < strlen(num); i++)
{
if (num[i] >= 'A')
{
num[i] = num[i] - 'A' + '0'+10;
}
}
}
while (count++ <= 30)
{
int i = 0;
int j = 0;
int len=strlen(num);
for (i = 0,j=len-1; i < len; i++,j--)
{
num_c[j] = num[i];
}
add(num,num_c,N);
if (judge(num))
{
break;
}
}
if (count > 30)
{
printf("Impossible!");
}
else
{
printf("STEP=%d", count);
}
return 0;
}