A题
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> using namespace std; int a[105]; int main() { int n,m,i; while(cin>>n>>m) { for(i=1;i<=n;i++) cin>>a[i]; int ma=0; for(i=1;i<=n-1;i++) if(a[i]-a[i+1]>ma) ma=a[i]-a[i+1]; ma-=m; if(ma>0) cout<<ma<<endl; else cout<<"0"<<endl; } return 0; }
B题:
找一个串有多少个子串是包含bear的。
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> using namespace std; char a[5005]; char b[5]; int main() { int i; while(cin>>a) { int len=strlen(a); if(len<4) { puts("0"); continue; } long long l,r; long long res=0; int q=1; for(i=0;i<len-3;i++) { b[0]=a[i]; b[1]=a[i+1]; b[2]=a[i+2]; b[3]=a[i+3]; b[4]=‘\0‘; l=q; q++; r=len-i-3; if(strcmp(b,"bear")==0) { //cout<<l<<" "<<r<<endl; res+=l*r; q=1; } } cout<<res<<endl; } return 0; }
C题:
题目大意:很明显的需要素数分解,范围是O(10^7),光筛选素数的复杂度就是O(10^7*log(10^7)),然后后面还需要输入哪些数字,然后查询,查询当然是O(1)的,很显然需要预处理,当时想不开,实际上在筛选的时候就可以预处理,详见代码:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> using namespace std; bool mark[10000005]; int num[10000005]; long long dp[10000005]; void sxprime() { int i; for(i=0;i<=1e7;i++) { mark[i]=true; dp[i]=0; } for(i=2;i<=1e7;i++) { if(mark[i]) { dp[i]+=num[i]; for(int j=i*2;j<=1e7;j+=i) { mark[j]=false; dp[i]+=num[j]; } } } } int main() { int i; int n,m,x; while(~scanf("%d",&n)) { for(i=0;i<=1e7;i++) num[i]=0; while(n--) { scanf("%d",&x); num[x]++; } sxprime(); for(i=1;i<=1e7;i++) dp[i]=dp[i-1]+dp[i]; int l,r; scanf("%d",&m); while(m--) { scanf("%d%d",&l,&r); l=min(l,10000001); r=min(r,10000000); printf("%I64d\n",dp[r]-dp[l-1]); } } return 0; } /* 6 5 5 7 10 14 15 3 2 11 3 12 4 4 7 2 3 5 7 11 4 8 2 8 10 2 123 */
D题是一个状压dp的,
然后E是一个矩阵的快速幂。
暂时没什么想法。
这几天什么也没做。。
就把这个作为除夕的博客了。