求助！！用的字符串，TLE了两个 4 和 10，其他都AC

P1591 阶乘数码

pppwolf @ 2023-06-07 13:25:46

#include <iostream>
#include <cstring>
using namespace std;

void init_string(string &s1, string &s2)
{
  int len1 = s1.size();
  int len2 = s2.size();
  int num = abs(len1 - len2);
  if (len1 < len2)
  {
    while (num--)
    {
      s1 = '0' + s1;
    }
  }
  else if (len1 > len2)
  {
    while (num--)
    {
      s2 = '0' + s2;
    }
  }
}
// 高精度加法
string add(string s1, string s2)
{
  init_string(s1, s2);
  int op = 0; // 进位
  string ans = "";
  for (int i = s1.size() - 1; i >= 0; i--)
  {
    int temp = (s1[i] - '0') + (s2[i] - '0') + op;
    op = temp / 10;
    temp %= 10;
    ans = char(temp + '0') + ans;
  }
  if (op != 0)
    ans = char(op + '0') + ans;
  return ans;
}

// 高精度乘低精度
string mul_low(string s1, int x)
{
  int num = 0;
  string ans = "";
  while (x)
  {
    int temp = x % 10;
    int op = 0;
    string tempstr;
    for (int i = s1.size() - 1; i >= 0; i--)
    {
      int tem = (temp * (s1[i] - '0') + op) % 10;
      op = (temp * (s1[i] - '0') + op) / 10;
      tempstr = char(tem + '0') + tempstr;
    }
    if (op != 0)
      tempstr = char(op + '0') + tempstr;
    for (int i = 0; i < num; i++)
      tempstr += '0';
    ans = add(ans, tempstr);
    x /= 10;
    num++;
  }
  ans.erase(0, ans.find_first_not_of('0')); // 去除前导0
  if (ans.empty())
    ans = "0";
  return ans;
}

int main()
{
  int n;
  cin >> n;
  while (n--)
  {
    int a, b, ans = 0;
    string str = "1";
    cin >> a >> b;
    for (int i = 1; i <= a; i++)
    {
      str = mul_low(str, i);
    }
    for (int i = 0; i < str.size(); i++)
    {
      if (str[i] == char(b + '0'))
        ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

by ninji @ 2023-06-07 14:13:12

记录 @pppwolf

帮你卡到90分

by pppwolf @ 2023-06-07 15:14:02

@ninji 还有一个怎么优化呢

by ninji @ 2023-06-07 15:18:42

@pppwolf 不大清楚。（可以与题解对拍一下）

by ninji @ 2023-06-07 15:24:32

@pppwolf 这我的AC代码：


#include <bits/stdc++.h>
using namespace std;
int a[2600],t,n,q,s;//存放数组
int main()
{
cin>>t;//输入数据组数
for(int k=1;k<=t;k++)
{
    s=0;//归0
    cin>>n>>q;
    memset(a,0,sizeof(a));//别忘了清零！！！
    a[0]=1;//1！=1
    for(int i=1;i<=n;i++)
    {
        int x=0;//进位数
        for(int j=0;j<=2599;j++)
        {
            a[j]=a[j]*i+x;//高精
            x=a[j]/10;//进位
            a[j]%=10;
        }

    }
    bool f=0;//做标记
    for(int j=2599;j>=0;j--)//去除前缀0
    {
        if(a[j]!=0)//非0，开始
        {
            f=1;//标记为真
        }
        if(f)
            //f为真，开始判断
        {
            if(a[j]==q)//相同
            {
                s++;
            }
        }
    }
    cout<<s<<endl;
} 

return 0;
}