2978. 计算数字之和

如果一次操作后的个位、十位和百位都是0的话，就没有必要再算下去了，这样能够节省很多时间

#include <string>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

int main()
{
    int t;
    cin>>t;

    for(int i=0;i<t;i++){
        long n,n1;
        cin>>n;
        n1=n;
        string n_str=to_string(n);

        long sum=0;
        while(n!=0){
            sum+=(n%10);
            n=n/10;
        }

        int bit0=n_str[n_str.length()-1]-'0';
        int bit1=n_str[n_str.length()-2]-'0';
        int bit2=n_str[n_str.length()-3]-'0';
        long times=n1-n_str.length();

        for(long j=0;j<times;j++){
            if(bit2==0&&bit1==0&bit0==0)
                break;
            int temp=((bit2+bit1)*bit0)%10;
            sum+=temp;
            bit2=bit1;
            bit1=bit0;
            bit0=temp;
        }

        cout<<"case #"<<i<<":"<<endl;
        cout<<sum<<endl;
    }
}

来自渣渣的一点微小的提示
看了楼下的帖子，发现个位为0，就可以break了

来自渣渣的一点微小的提示
首先，把A放在数组里操作方便很多
然后，发现数组最长有10^9位，太长，因此每插入一个新的数，就去掉最高位的一个数，并累加到各个位置数字和中
程序如下：

include

using namespace std;
int T;
deque V;

void solve()
{
string num;
cin>>num;
int ll=num.length();
stringstream ss(num);
int A; ss>>A;

V.clear();
for(int i=0;i<ll;i++) V.push_back(num[i]-‘0’);

int Size=V.size(),ret=0;

while(Size<A)
{
if(V.back()==0 && V[V.size()-2]==0 && V[V.size()-3]==0) break;
V.push_back((V.back()*(V[V.size()-2]+V[V.size()-3]))%10);
ret+=V.front();
V.pop_front();
Size++;
}

for(int i=0;i<V.size();i++) ret+=V[i];
cout<<ret<<endl;
return;
}

int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

由于数字高位要去掉，所以我用了双端队列deque。
然而位数最高10^9，会TLE

一种直接的想法是，如果一个数最右边3位都相同，之后的结果会循环。找一个数组，把最右边3位有没有出现过，在哪里出现的记录下来，类似于循环节处理

然而我是个懒人。

因此，把之后几位输出，发现都是0。

于是优化一下，如果最右边三位都是0，就break，再算下去加了很多0没有意义

AC程序如下：

include

using namespace std;
int T;
deque V;

void solve()
{
string num;
cin>>num;
int ll=num.length();
stringstream ss(num);
int A; ss>>A;

V.clear();
for(int i=0;i<ll;i++) V.push_back(num[i]-‘0’);

int Size=V.size(),ret=0;

while(Size<A)
{
if(V.back()==0 && V[V.size()-2]==0 && V[V.size()-3]==0) break;
V.push_back((V.back()*(V[V.size()-2]+V[V.size()-3]))%10);
ret+=V.front();
V.pop_front();
Size++;
}

for(int i=0;i<V.size();i++) ret+=V[i];
cout<<ret<<endl;
return;
}

int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

没看到动态规划，我来一个

#include <stdio.h>

int how_many_bits(int num);
int solve(int hun,int tens,int sing,int bits);
int sum,num;

int main(void){
  int T;
  scanf("%d",&T);
  for(int i = 0; i < T && printf("case #%d:\n",i)&&scanf("%d",&num);i++){
    int ans = solve((num/100)%10,(num/10)%10,num%10,how_many_bits(num));
    printf("%d\n",ans);
  }
  return 0;
}

int how_many_bits(int num){
  sum = 0;
  int bits = 0;
  do{
    sum += num%10;
    bits++;
  }while(num /= 10);
  return bits;
}

int solve(int hun,int tens,int sing,int bits){
  for(int i = bits; i < num;i++){
    if(sing == 0)
      break;
    int new = ((hun+tens)*sing)%10;
    sum += new;
    hun = tens;tens = sing;sing = new;
  }
  return sum;
}