算法日记33：15届蓝桥C++B组R格式（快速幂50%/高精度100%）

一、题目

二、题解一：快速幂（50%样例）

1、解题思路：

1）通过题目我们可以采取最朴素的想法就是先模拟题目的说明

2）并且我们发现有乘方出现($\ast 2^n$)，因此我们可以考虑使用快速幂来优化

2、快速幂详解：求解$a^b$

1）对于求解$a^b$，我们最朴素的想法就是暴力枚举

2）但是很明显，我们可以使用倍增的思想，来进行简化操作

• 假设我们需要求$a^8$，我们可以这样简化：
  
• 也就是把其不断拆分成：$a^2$，这样我们就从朴素的计算$8$次–>变为计算$3$次

3）但是假设我们的次方的奇数呢？

• 假设我们现在算 $a$¹³ ，我们可以这样拆：
  
• 也就是说，我们把一个$a$给单独拿出来了，接着把剩下的a¹²继续按照倍增拆分，为了方便计算我们把 $a$ 先存入答案中去
  
• 接下来，我们就可以按照偶数的拆分，来继续拆分了
  
• 此时又出现了奇数，我们又继续按照如上原则进行处理
  

4）但是我们在代码中，是不需要进行这样复杂的操作的，我们可以 使 用 二进制来进行优化

• 我们可以发现$13$的二进制为：
  
• 因为我们只需要判断指数(13)的奇偶性，因此可以通过二进制来进行
• 此时，我们可以发现最后一位为$1$，说明此时指数为奇数，因此我们可以让res*=a,b--
  
• 接着我们让b>>=1，也就是让其b=b/2，接着判断奇偶性
• 但是，此时我们让b/=2了，因此我们的a要变化：a=a*a
  

总结

3、快速幂代码

//快速幂
ll qmi(ll a,ll b)	//a的b次方
{
	ll res=1;
	while(b)
	{	
		//如果b是奇数,那么就拆出一个数到答案中去，并且让b--
		if(b&1) res=res*a,b--;
		a*=a , b>>=1;	//接着让b右移一位继续判断奇偶性，且此时b/=2，因此a=a*a
	}
	return res;
}

4、完整代码实现

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

typedef long long ll;

//快速幂
ll qmi(ll a,ll b) //a的b次方
{
    ll res=1;
    while(b)
    {
        if(b&1)  res=res * a, b--;
        a= a * a , b >>= 1;
    }
    return res;
}

void solve()
{
  ll n;cin>>n;
  double d;cin>>d;

  d*=qmi((ll)2,n);  //快速幂优化
  
  printf("%.f\n",d);
  //cout<<d<<'\n';
  
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int _=1;
  while(_--) solve();  
  return 0;
}

三、题解二：高精度（100%样例）

1、解题思路：

• 通过样例我们可以发现数据十分的庞大，完全超出了数字的范围，因此我们可以考虑使用string->a[]来进行操作
• 因此我们考虑使用高精度算法
  

2、高精度算法：

1）其实，所谓的高精度运算，就是我们小学所学习的竖式运算

2）我们可以发现我们的运算都是从最低位数开始计算的(为了方便进位)，因此我们需要反向存储数据

3）通过计算我们发现，出现了进位，但是我们可以先不处理这个进位而是先存储起来(因为我们的每一位数都是一个数组元素，可以存储很大的元素)

4）接着我们再处理每一位的元素进位即可 （注意此时我们是反向存储，因此我们要反向遍历）

• 举例：$a$中的每一个元素$+$ $b$ 中的每一个元素
  

3、结合题目具体分析：

1）在题目中我们发现出现了小数点，这是非常不好处理的，因此我们可以把它看作整数，且记录小数点的数位3.14*4=12.56->314*4=1256

ll n; //乘以n个2
string d;   //待转换的浮点数

  cin>>n>>d;
  reverse(d.begin(),d.end()); //把s倒叙存储，方便进位 3.14->41.3

  vector<int>D;
  ll dot=d.find('.');	//记录小数点的位数
   for(auto i:d) //把字符串d中的元素放入数组当中
  {
    if(i!='.') D.push_back(i-'0');  //转化为字符
  }

2）此时题目需要我们$\times 2^n$也就是，乘以n个2，因此我们使用高精度乘法来实现

void mul(vector<int>& a,int b)  //a中的所有元素都*b：a*=b
{
  int t=0;  //用t来表示此轮的进位
  for(int i=0;i<a.size();i++)	//依次枚举每一位
  {
    t+=a[i]*b; 		//计算本轮一共变化的数据
    a[i]=t%10;		//把变化数据的个位数给当前位数
    t/=10;		//存储十位数为下一轮的进位
  }
  //如果t不是0，此时最高位还需补充一位
  if(t) a.push_back(t);
}
while(n--) mul(D,2);  //高精度乘法

3）此时我们进行完了第一步：将浮点数乘以$2^n$，接下来我们需要四舍五入，因此需要通过小数点的位数来进行操作

• 在样例中我们的小数点在第$2$位(下标从0开始存储)
• 因此需要四舍五入我们需要看第$1$位（$dot-1$位)
  
• 因此我们通过$dot-1$可以进行第$dot$位(因为我们在数组中没有存储小数点，因此dot位指向个位3)的$+1$操作

void add(vector<int>& a,int k,int b)  //a[k]+b
{
  int t=b;  //用t来表示此轮的进位
  for(int i=k;i<a.size();i++)	//从第k位开始依次枚举每一位
  {
    t+=a[i];		//计算本轮一共变化的数据
    a[i]=t%10;		//把变化数据的个位数给当前位数
    t/=10;		//存储变化数据的十位数为下一轮的进位
  }
  //如果t不是0，表示还需要向最高位进位，此时最高位还需补充一位
  if(t) a.push_back(t);
}

if(D[dot-1]>=5) add(D,dot,1);

4）此时，我们所有的操作都进行完毕，只需进行反向输出即可

for(int i=D.size()-1;i>=dot;i--) cout<<D[i];

4、完整代码实现：

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

const int N=1300;
typedef long long ll;

ll n; //乘以n个2
string d;   //待转换的浮点数

void mul(vector<int>& a,int b)  //a中的所有元素都*b：a*=b
{
  int t=0;  //用t来表示此轮的进位
  for(int i=0;i<a.size();i++)	//依次枚举每一位
  {
    t+=a[i]*b; 		//计算本轮一共变化的数据
    a[i]=t%10;		//把变化数据的个位数给当前位数
    t/=10;		//存储十位数为下一轮的进位
  }
  //如果t不是0，此时最高位还需补充一位
  if(t) a.push_back(t);
}

void add(vector<int>& a,int k,int b)  //a[k]+b
{
  int t=b;  //用t来表示此轮的进位
  for(int i=k;i<a.size();i++)	//从第k位开始依次枚举每一位
  {
    t+=a[i];		//计算本轮一共变化的数据
    a[i]=t%10;		//把变化数据的个位数给当前位数
    t/=10;		//存储变化数据的十位数为下一轮的进位
  }
  //如果t不是0，表示还需要向最高位进位，此时最高位还需补充一位
  if(t) a.push_back(t);
}


void solve()
{
  cin>>n>>d;
  reverse(d.begin(),d.end()); //把s倒叙存储，方便进位 3.14->41.3

  vector<int>D;
  ll dot=d.find('.');
  for(auto i:d) //把字符串d中的元素放入数组当中
  {
    if(i!='.') D.push_back(i-'0');  //转化为字符
  }
  while(n--) mul(D,2);  //高精度乘法

  if(D[dot-1]>=5) add(D,dot,1);

  for(int i=D.size()-1;i>=dot;i--) cout<<D[i];
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int _=1;
  while(_--) solve();  
  return 0;
}