Zerojudge b797 V流星火雨 【DP】
题目大意：多次询问，求一个数的平方拆分个数
$TestCases \leq 40000, n \leq 40000$
平方拆分表示为，把一个数拆分成多个正整数的平方的和。
$Time Limit: 1s, Memory Limit: 32Mb$
【题解】
看起来像一个$O(n \sqrt{n})$的做法
我们先想$f[i,j]$表示，i可以拆分成，最大的数不大于j的个数。
$f[i,j]=\sum_{k=1}^{j} f[i-k \times k, k]$
然后我们发现可以用前缀和搞掉这个k
$f[i,j]=f[i,j-1]+f[i-j\times j,j]$
然后发现MLE了，因为有高精度。
然后我们发现，可以压掉j这维，发现是没有用的。
于是就好啦~
# include <stdio.h>
# include <math.h>
# include <iostream>
# include <algorithm>
# include <string.h>
using namespace std;
const int F=1e8;
struct bn {
int s[8];
bn() {
memset(s,0,sizeof(s));
s[0]=1;
}
bn(int x) {
memset(s,0,sizeof(s));
s[0]=1,s[1]=x;
}
int& operator[](const int i) {
return s[i];
}
friend bn operator +(bn a, bn b) {
bn c;
c[0]=max(a[0],b[0]);
for (int i=1;i<=c[0];++i) {
c[i]+=a[i]+b[i];
if(c[i]>F) {
c[i+1]+=c[i]/F;
c[i]=c[i]%F;
}
}
while(c[c[0]+1]>0) ++c[0];
return c;
}
void prt() {
printf("%d",s[s[0]]);
for (int i=s[0]-1;i>=1;--i) printf("%08d",s[i]);
printf("\n");
}
}f[40001];
struct tat
{
int x,y,id;
}sm[40001];
bool cmp(tat a,tat b){return a.x<b.x;}
int main()
{
int t,g;
for (int i=1;i<=200;++i) f[0]=bn(1);
for (int i=1;i<=200;++i) {
for (int j=i*i;j<=40000;++j)
f[j]=f[j]+f[j-i*i];
}
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
int x;
scanf("%d",&x);
f[x].prt();
}
return 0;
}
2022年8月18日 13:15
AP Inter Model Question Papers 2023 Download, First let’s check out some details and information about the Model Question Papers, in some states it is also referred to as ‘Important Question Papers’, <a href="https://www.li9.in/bieap-1st-year-2nd-year-question-paper/">AP Inter Model Question Paper 2023</a> the Model Question Paper is the paper form of the students in which all the details of the candidates along with the Sample Question Paper and timings including the photograph are mentioned which is carried out in the examination hall and used for verification purpose.
2022年8月18日 13:15
AP Inter Model Question Papers 2023 Download, First let’s check out some details and information about the Model Question Papers, in some states it is also referred to as ‘Important Question Papers’, AP Inter Model Question Paper 2023 the Model Question Paper is the paper form of the students in which all the details of the candidates along with the Sample Question Paper and timings including the photograph are mentioned which is carried out in the examination hall and used for verification purpose,
2023年4月28日 15:40
Board 12th Class Model Paper 2023 Aspirants who had Registered for the Maha Board 12th Class Exam can Download the Previous Paper When Maha Board 12th Announces the Dates to Download the Question Paper. boardmodelpaper.in Board 12th Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board 12th Question Paper.