1、110601/10183 How Many Fibs? （斐波那契计数）
使用字符数组表示数列，double可以表示300位整数，但会出现精度问题。
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<ctype.h> using namespace std; struct NODE { char dig[150]; }nod[1005]; char a[150],b[150]; void rever(char a[]) { int la=strlen(a); for(int i=0;i<la/2;i++) swap(a[i],a[la-1-i]); } int _strcmp(char a[],char b[]) { int la=strlen(a),lb=strlen(b),i; if(la!=lb)return la<lb?-1:1; for(i=la-1;i>=0;i--) { if(a[i]!=b[i])return a[i]>b[i]?1:-1; } return 0; } int main() { strcpy(nod[1].dig,"1"); strcpy(nod[2].dig,"2"); int i=3,j,cnt,t1,t2; for(;;i++) { int len1=strlen(nod[i-2].dig); int len2=strlen(nod[i-1].dig); cnt=0; for(j=0;j<len1||j<len2;j++) { t1=0; t2=0; if(j<len1) t1=nod[i-2].dig[j]-'0'; if(j<len2) t2=nod[i-1].dig[j]-'0'; nod[i].dig[j]=(t1+t2+cnt)%10+'0'; cnt=(t1+t2+cnt)/10; } if(cnt!=0) nod[i].dig[j++]=cnt+'0'; nod[i].dig[j]=' '; if(j>100)break; } int tot=i; //sort(nod,nod+tot,cmp); while(scanf("%s",a)!=EOF) { scanf("%s",b); if(a[0]=='0'&&b[0]=='0')break; cnt=0; rever(a); rever(b); for(i=0;i<tot;i++) { //printf("%s ",nod[i].dig); if(_strcmp(a,nod[i].dig)>0)continue; if(_strcmp(b,nod[i].dig)<0)break; cnt++; } printf("%d ",cnt); } return 0; }
2、110602/10213 How Many Pieces of Land? （土地分割）
使用了欧拉公式，答案是c(n,2)+c(n,4)+1，因为输入的整数是32位，所以还需要使用高精度，高精度的四则运算主要使用数组表示
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<ctype.h> using namespace std; typedef long long lld; lld n; const int length=1000; int res[length],tr[5][length],ts[length]; void multi(int sa[],int sb[]) { int i,j,x; int st=0,cnt=0,tmp; int num[length]; memset(num,0,sizeof(num)); for(i=0;sb[i]!=-1;i++) { for(j=0;sa[j]!=-1;j++) { tmp=sb[i]*sa[j]; x=num[st+j]; num[st+j]=(x+tmp+cnt)%10; cnt=(x+tmp+cnt)/10; } while(cnt!=0) { x=num[st+j]; num[st+j]=(x+cnt)%10; cnt=(x+cnt)/10; j++; } st++; } i=length-1; while(num[i]==0) { i--; } sa[i+1]=-1; while(i>=0) { sa[i]=num[i]; i--; } } void add(int sa[],int sb[]) { int i,j,cnt=0,ta,tb; bool fa=false,fb=false; for(i=0;!fa||!fb;i++) { ta=sa[i]; tb=sb[i]; if(ta<0)fa=true; if(tb<0)fb=true; ta=ta>0?ta:0; tb=tb>0?tb:0; sa[i]=(ta+tb+cnt)%10; cnt=(ta+tb+cnt)/10; } if(sa[i-1]==0)i--; sa[i]=-1; } void sub(int sa[],int sb[]) { int i,j,ta,tb,cnt=0; bool fa=false,fb=false; for(i=0;!fa||!fb;i++) { ta=sa[i]; tb=sb[i]; if(ta<0)fa=true; if(tb<0)fb=true; ta=ta>0?ta:0; tb=tb>0?tb:0; tb+=cnt; if(ta<tb) { ta+=10; cnt=1; } else cnt=0; sa[i]=ta-tb; } sa[i-1]=-1; } void div(int sa[],int d) { int i=0,tmp=0; while(sa[i]!=-1)i++; bool flag=false; for(i-=1;i>=0;i--) { tmp=tmp*10+sa[i]; if(tmp>=d) { flag=true; printf("%d",tmp/d); tmp=tmp%d; } else { if(flag)printf("0"); } } } void setnum(int sa[],int n) { int i=0; while(n) { sa[i++]=n%10; n/=10; } sa[i]=-1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%lld",&n); int i; if(n<3) { if(n==0) printf("1 "); else printf("%d ",n); continue; } if(n==3) { printf("4 "); continue; } for(i=0;i<=4;i++)memset(tr,0,sizeof(tr)); setnum(tr[1],n); for(i=2;i<=4;i++) { setnum(tr[i],n); multi(tr[i],tr[i-1]); } setnum(ts,6); multi(tr[3],ts); setnum(ts,23); multi(tr[2],ts); setnum(ts,18); multi(tr[1],ts); setnum(ts,24); add(tr[4],ts); add(tr[4],tr[2]); sub(tr[4],tr[3]); sub(tr[4],tr[1]); div(tr[4],24); printf(" "); } return 0; }
3、110603/10198 C ounting （数数）
此题使用动态规划，当N为1000时，答案可以达到407位，所以开数组时需要注意，还有在做大数相加时也需要注意
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; typedef long long lld; const lld INF=1.0e17; struct BigInteger { lld num[30]; void init() { memset(num,0,sizeof(num)); } void add(int t,BigInteger x) { int m=1,i; lld n,cnt=0; if(t==1)m=2; for(i=0;i<30;i++) { n=x.num[i]*m+num[i]+cnt; num[i]=n%INF; cnt=n/INF; } } }dp[1005][1005],ans[1005]; void init() { dp[1][1].init(); dp[1][1].num[0]=2; dp[1][2].init(); dp[1][2].num[0]=1; dp[1][3].init(); dp[1][3].num[0]=1; int i,j; for(i=1;i<1000;i++) { for(j=i;j<=3*i&&j<=1000;j++) { dp[i+1][j+1].add(1,dp[i][j]); dp[i+1][j+2].add(2,dp[i][j]); dp[i+1][j+3].add(3,dp[i][j]); } } for(i=0;i<=1000;i++) { ans[i].init(); for(j=1;j<=i;j++) { ans[i].add(2,dp[j][i]); } } } int main() { int n; init(); while(scanf("%d",&n)!=EOF) //freopen("E:\a.txt","w",stdout); //for(n=1;n<=1000;n++) { int i=29; while(ans[n].num[i]==0)i--; printf("%lld",ans[n].num[i]); i--; while(i>=0) { printf("%017lld",ans[n].num[i]); i--; } printf(" "); } return 0; }