P8870 [传智杯 #5 初赛] B-莲子的机械动力学 题解
hh20080501hh · · 题解
洛谷P8870 莲子的机械动力学
题面在这~
“题目背景和题目描述的两个题面是完全等价的，您可以选择阅读其中一部分。”
显而易见，第二个题面比第一个题面更好理解，故下面对第二个题面进行分析。
分析：
- 题目意思很好理解，定义一个新的进制数，这个数的进制是可变的，第
i 位上的数为i+1 进制。（注意：个位为第1 位，而不是第0 位哦） - 所有的数据保证
m,n\le200000 ，经过一番计算可以得出，显而易见，不可能用long long来储存，一定一定会爆掉（int更不可能了），就算使用__int128也不可以哟~。 - 那我们就不得不写一份高精度加法了。
不喜欢高精度高精加法模板：
还是挺好写的，但是我决定还是把正常的模板贴过来#include <bits/stdc++.h> using namespace std; vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) return add(B, A); vector<int> C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); auto C = add(A, B); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }先别急这仅仅是个模板，肯定是过不了的
过得了就见鬼了。
那么这道题的正确写法与模板到底差什么呢？ 让我们回顾一下题意，显而易见：
- 模板中的是十进制，也就是逢
10 进1 。 - 这道题是变进制，是逢
i 进i+1 。 - 逢
10 进1 与逢i+1 进1 肯定是有区别的。
不过万幸的是，这道题仅仅只有进位与模板不一样，加是一模一样滴。
正确做法：
#include <bits/stdc++.h>
using namespace std;
int n , m;
int a[200010] , b[200010];
vector <int> a1 , b1;
vector <int> add(vector<int> &A , vector<int> &B)
{
if (A.size()<B.size())
{
return add(B , A);
}
vector<int> C;
C.clear();
for (int i=0 ; i<A.size() ; i++)
{
int t=A[i];
if (i<B.size())
{
t+=B[i];
}
C.push_back(t);
}
for (int i=0 ; i<C.size() ; i++)
{
if (C[i]>=i+2) //判断是否需要进位
{
C[i] -= (i+2);
if (i+1<C.size()) //如果当前位进位之后
{ //不会超出C的范围，就往前进位
C[i+1]++;
}
else//如果当前位进位会超出C的范围，就给C再
{ //要个地方进位
C.push_back(1);
break;
}
}
}
return C;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i=0 ; i<n ; i++)
{
cin >> a[i];
}
for (int i=0 ; i<m ; i++)
{
cin >> b[i];
}
for (int i=n-1 ; i>=0 ; i--)
{
a1.push_back(a[i]);
}
for (int i=m-1 ; i>=0 ; i--)
{
b1.push_back(b[i]);
}
auto c = add(a1 , b1);
for (int i=c.size()-1 ; i>=0 ; i--)
{
cout << c[i] << " ";
}
return 0;
}除了输入方式稍微有点点改变之外，唯一的改变就是进位了，这里我们将进位分开处理，不仅好写、好处理，而且还快！ 分开进位在高精度乘法时可以感受到比边算边进位的好处，会快一些。
为什么进位是
第一次写题解，如有写的不清楚的地方请见谅，希望审核大大能通过我的题解，第三次了，求求给我过了吧