4.13 | 学习笔记
1.整数拆分为2 的幂的和
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
用数组a[ ]直接记录结果。
从前往后推的时候,有两种可能性,分为a[ 2m+1] 和a[ 2m ];
易知a[ 2m+1 ]=a[ 2m ];
对于a[ 2m ]它的所有拆分方式分为两大类:
1)含有1的,这部分所有方式都去掉1,就得到a[ 2m-1 ]
2)不含有1的,也就是分出的都是2的倍数,那么都除以2,就得到a [m ]
附上AC代码:
#include<bits/stdc++.h> using namespace std; long long int a[1000001]={0,1,2}; long long int t,n; int main() { for(int i=3;i<1000001;i++) { if(i%2)a[i]=a[i-1]; else a[i]=(a[i-2]+a[i/2])%1000000000; } cin>>t; for(int i=0;i<t;i++) { cin>>n; cout<<"case #"<<i<<":\n"<<a[n]<<endl; } return 0; }
2.天气猜猜看问题(或许是第一次接触贪心算法?)、
粘下学长的代码( )
using namespace std; double T; int n; string s[1000]; double t[1000];//? bool jdg[1000];// int i; int main() { cin>>T>>n; for(i=0;i<n;++i)cin>>s[i]; for(i=1;i<n;++i){ if(s[i][0]=='U'){ if(s[i-1][0]=='D')t[i-1]=0,jdg[i-1]=1; } else{ if(s[i-1][0]=='U')t[i-1]=30,jdg[i-1]=1;//贪心算法 } } if(!jdg[0])t[0]= ( s[0][0]=='U'? T+0.1:T-0.1 ); for(i=1;i<n;++i){ if(!jdg[i]){ t[i]=( s[i][0]=='U'? t[i-1]+0.1:t[i-1]-0.1 ); } } printf("%.1f",t[0]); for(i=1;i<n;++i)printf(" %.1f",t[i]); return 0; }
(明天继续学习)
更多精彩