【好题】第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 H-特征值 前缀和+高精度模拟

题

比赛的时候，一看题：害！高精度模拟！冲！
然后就T了。

做题之前要算一下时间复杂度，来判断自己的方法是否合理，不然会浪费大量的时间。

这题的数据范围：500000
如果要高精度加法，数字长度是500000，所以要加500000次，每次加是按位数加，还要乘以500000，总的时间复杂度是500000*500000=2.5x10¹¹ 绝对会TLE

所以要思考一下别的方法。

经过@满满满V 的提醒，我们可以这样看这道题的加法：

1225
 122
  12
+  1
————
1360

很容易可以看出，每一位都是前面位数的前缀和+当前位数的值！
所以我们的做法就可以是：
先前缀和相加，再进位。
第一位可以直接输出！

这样时间复杂度就变为：O(n)（只用一层循环，数据范围500000） 可以过了

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=500000+10;
/*
1225
 122
  12
   1
*/
string a;
int sum[N];//前缀和 
int main()
{
	cin>>a;
	for(int i=0;a[i];i++)
	{
		if(i!=0) sum[i]=sum[i-1]+a[i]-'0';
		else sum[i]=a[i]-'0';
	}
	
	int t=0;
	//从0到a.size()-1
	for(int i=a.size()-1;i>0;i--) 
	{
		sum[i]+=t;
		t=0;
		if(sum[i]>=10)//进位 
		{
			t+=sum[i]/10;
			sum[i]%=10;
		}		
	}
	
	if(t) sum[0]+=t;
	cout<<sum[0];
	
	fir(i,1,a.size()-1) cout<<sum[i];
	return 0;
}