蓝桥杯算法提高VIP-函数求值 （C++代码）（官方标答也WA，数据有问题）

解题思路:

这题的数据和数据规模有问题，自己写的没考虑规模，妥妥的超时

注意事项:

参考代码:

#include <iostream>
#include <string>
#include <algorithm>
#include <memory.h>
#include <stdio.h>

#define N 100000

using namespace std;

string intToString(int n)
{
    string str;
    while (n) {
        str += n%10 + '0';
        n /= 10;
    }
    reverse(str.begin(),str.end());
    return str;
}

int getCount(string str)
{
    int oneCount = count(str.begin(),str.end(),'1');
    int twoCount = count(str.begin(),str.end(),'2');
    return oneCount + twoCount;
}

long long F(int n)
{
    long long ans = 0;
    for (int i = 1;i <= n;i++)
    {
        string str = intToString(i);
        ans += getCount(str);
    }
    return ans % 201203;
}

int main()
{
    int n = 0;
    cin >> n;
    cout << F(n) << endl;
    return 0;
}

官方标答：

 
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int main()
{ int i,t=1,l,j;
  int ten[1000],z[1000],a[1000];
  int sum=0;
  char s[1000];
  gets(s);
  ten[0]=1; z[1]=1; 
 for (i=1;i<=100;i++) ten[i]=ten[i-1]*10%20123;
 for (i=2;i<=100;i++)
 z[i]=(z[i-1]+(ten[i-1]+9*ten[i-2]*(i-1))%20123)%20123;
 l=strlen(s);  a[l]=0;
 for (i=l-1;i>=0;i--)
  a[i]=((s[i]-48)*ten[l-i-1]+a[i+1])%20123;
 for (i=0;i<l;i++)
  {
      for (j=0;j<s[i]-48;j++)
      {
        sum=(sum+z[l-i-1]*2)%20123;
        if (j==1||j==2) sum=(sum+ten[l-i-1])%20123;
      }
      if (s[i]=='1'||s[i]=='2') sum=(sum+a[i+1]+1)%20123; 
  }
  cout<<sum<<endl;
    return 0;
}