第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-709 火星人乘法

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-709 火星人乘法

前言

       这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。

关于数学的疑问

蓝桥杯中涉及到的数学说多不多，说少也不少，这里罗列了一下能用到的，其中红色的是【大学C组】会使用到的

1、简单数学(基础运算)

2、位运算

3、线性代数

4、离散数学(组合数学)

5、初等数论(整数的性质)

6、概率论

7、几何

虽然看到了线性代数、离散数学、初等数论，但是对于C组来说不会考的太复杂，会基础就好。

算法训练 火星人乘法

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　21世纪．人类宇航员第一次在火星表面登陆，发现了一些奇妙的图案，经科学家们的研究，猜想其中的某一部分可能为火星人计算两个数相乘的记录，且它们用的是18进制。

　　在这些图案和符号中，他们用类似ASCII来表示数字，具体如下：

　　I 代表 “1” N代表 “10” M代表 “100”

　　H代表 “1000”

　　R代表 “10000”

　　P代表 “100000”

　　K代表 “1000000”

　　T代表 “10000000”

　　上面用“”包含的数字是18进制的数字，如N十M代表“110”（为方便起见，将字符间的加号省略，写为NM），相当于我们所用的十进制数342（342=18x18＋18）。而我们的十进制数401，火星人写为：

　　(401）10=1x（18）10x（18）10+4x（18）10＋5x（1）10=(145）18＝1x（100）18＋4x（10）18＋5x（1）18=IIIIINNNNM

　　（先写低位后写高位）

　　现在使数字a与数字b相乘，火星人的方法是：先用I与b相乘，I在第一行的左边，右边为I与b的积，再用II与b相乘，第二行输出II及II与b的积，每次加倍，依次用IIII、 IIIIIIII等去乘b，直到当各行左边一列的数的和大于等于a为止。

　　例如：

　　a＝IIIIIIIIINN

　　b＝IIIIINNNNNN

　　过程如下：

　　I＊ IIIIINNNNNN

　　II IIIIIIIIIINNNNNNNNNNNN

　　IIII＊ IINNNNNNNH

　　IIIIIIII＊ IIIINNNNNNNNNNNNNNMM

　　IIIIIIIIIIIIIIII IIIIIIIINNNNNNNNNNMM

　　IIIIIIIIIIIIIIN＊ IIIIIIIIIIIIIIIINNMMMMMMMMMMM

　　在左边的一列中取出I、IIII、IIIIIIII、IIIIIIIIIIIIIIN（这四个数之和为a），取出的数紧接输出一个“＊”，这四行对应的右边的四项之和即为a X b，结果为：

　　IIIIIIIIINNNNNNNNNNNNMMMMMMMMMMMMMMM

　　编程完成上述乘法。

输入格式

　　输入文件仅含两行，第一行为“a”，第二行为“b”。（a和 b为我们地球上使用的小于等于32767的正整数）

输出格式

　　输出由若干行组成。每行的左列从上到下依次为：I、II、IIII…，取出的数紧接着输出一个“＊”，右列从上到下依次为：I、II、IIII等与b的乘积，左列与右列之间用一个空格隔开。最后的一行输出“The solution is ：”和最后的积axb。

样例输入

IIIIIIIIINN

IIIIINNNNNN

样例输出

I＊ IIIIINNNNNN

II IIIIIIIIIINNNNNNNNNNNN

IIII＊ IINNNNNNNM

IIIIIIII＊ IIIINNNNNNNNNNNNNNMM

IIIIIIIIIIIIIIII IIIIIIIINNNNNNNNNNMMMMM

IIIIIIIIIIIIIIN＊ IIIIIIIIIIIIIIIINNMMMMMMMMMMM

The solution is：IIIIIIIIINNNNNNNNNNNNMMMMMMMMMMMMMMM

题解：

C++语言

#include<bits/stdc++.h>
using namespace std;
int z[100][100],t=0,q[100][10],w[100];
map<int,char >o;
void init() {
  o[1]='I',o[2]='N',o[3]='M',o[4]='H',o[5]='R',o[6]='P',o[7]='K',o[8]='T';
}
int* sp1(char *p) {
  int i,*g;
  g=(int *)malloc(sizeof(int)*10);
  for (i=0;i<8;i++) g[i]=0;
  while(*p) {
    switch(*p) {
      case 'I': g[0]++;
      break;
      case 'N': g[1]++;
      break;
      case 'M': g[2]++;
      break;
      case 'H': g[3]++;
      break;
      case 'R': g[4]++;
      break;
      case 'P': g[5]++;
      break;
      case 'K': g[6]++;
      break;
      case 'T': g[7]++;
    }
    p++;
  }
  return g;
}
int sp2(int *p) {
  int s=0,f=1,j=8;
  while(j--) {
    s+=(*p)*f;
    p++;
    f*=18;
  }
  return s;
}
int sp4(int *p) {
  int s=0,f=1,j=*p;
  p++;
  while(j--) {
    s+=(*p)*f;
    p++;
    f*=18;
  }
  return s;
}
int* sp3(int x) {
  int i,k=0,*g;
  g=(int *)malloc(sizeof(int)*10);
  for (i=0;i<8;i++) g[i]=0;
  while(1) {
    g[k++]=x%18;
    x/=18;
    if(x==0) break;
  }
  return g;
}
void pk(int *q1,int *q2) {
  int i,j,c[30][100]= {
    0
  }
  ,u,k1,k=0,s=0,c1=0,x,y,x1,*p1,*p2;
  p2=sizeof(q1)<sizeof(q2)?q1:q2;
  x=max(sizeof(q1),sizeof(q2));
  y=min(sizeof(q1),sizeof(q2));
  while(y--) {
    u=0;
    p1=sizeof(q1)>=sizeof(q2)?q1:q2;
    k1=k,x1=x;
    while(x1--) {
      c[k][k1++]=(*(p1)*(*p2)+u)%18;
      u=((*p1)*(*p2)+u)/18;
      if(x1==0) {
        if(u>0) c[k][k1++]=u;
        break;
      }
      p1++;
    }
    c1=max(c1,k1);
    p2++;
    k++;
  }
  u=0;
  for (j=0;j<c1;j++) {
    s=0;
    for (i=0;i<k;i++) s+=c[i][j];
    s+=u;
    u=s/18;
    c[k][j]=s%18;
  }
  if(u>0) c[k][c1++]=u+'0';
  z[t][0]=c1;
  for (i=0;i<c1;i++) z[t][i+1]=c[k][i];
  t++;
}
void put(int k,int f) {
  int i,j;
  for (i=0;i<8;i++) for (j=0;j<q[k+1][i];j++) cout<<o[i+1];
  if(f) cout<<"*";
  cout<<' ';
  for (i=1;i<=z[k][0];i++) for (j=0;j<z[k][i];j++) cout<<o[i];
  cout<<'\n';
}
int main() {
  int sum=0,u1=1,s=0,*x,*y,y1,x1,h,i,j,k;
  char a[100],b[100];
  cin>>a>>b;
  x=sp1(a),y=sp1(b);
  x1=sp2(x);
  u1=1;
  while(1) {
    j=8,h=0,x=sp3(u1);
    pk(x,y);
    while(j--) {
      q[t][h++]=*x;
      x++;
    }
    q[t][8]=u1;
    sum+=u1;
    u1*=2;
    if(sum>=x1) break;
  }
  init();
  for (i=0;i<(1<<t);i++) {
    sum=0;
    for (j=0;j<t;j++) if(i&(1<<j)) sum+=q[j+1][8];
    if(sum==x1) for (j=0;j<t;j++) {
      if(i&(1<<j)) {
        s+=sp4(z[j]);
        put(j,1);
      } else put(j,0);
    }
  }
  printf("The solution is: ");
  x=sp3(s);
  for (i=0;i<8;i++) for (j=0;j<x[i];j++) cout<<o[i+1];
  return 0;
}

总结

没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。