哈尔滨理工大学软件学院ACM程序设计全国邀请赛（水题5道）

E:统计子串‘6’的长度,每个长度对答案有（1+cnt）*cnt/2的贡献 ，统计答案。 代码：

#include <bits/stdc++.h> #define ll long long using namespace std; int n,len; char str[200010]; ll quick(ll x) { return (1+x)*x/2; } int main() { scanf("%d",&n); while(n--) { scanf("%d",&len); scanf("%s",str); ll sum=0; ll ge=0; for(int i=0;i<len;i++) { if(str[i]=='6') { ge++; } else { sum+=quick(ge); ge=0; } } sum+=quick(ge); printf("%lld\n",sum); } }

J： 统计奇数个数。。。 代码：

#include <bits/stdc++.h> #define ll long long using namespace std; int main() { int n; while(~scanf("%d",&n)) { ll sum=0; ll a; while(n--) { scanf("%lld",&a); if(a&1) sum++; } printf("%lld\n",sum); } }

H：矩阵快速幂求斐波那契。 代码：

#include<stdio.h> #include<iostream> #include<string.h> using namespace std; #define ll long long int typedef struct Matrix { ll mat[2][2]; }matrix; ll mod=1e9+7; matrix A,B; Matrix matrix_mul(matrix a,matrix b) { matrix c; memset(c.mat,0,sizeof(c.mat)); ll i,j,k; for(ll i=0;i<2;i++) { for(ll j=0;j<2;j++) { for(ll k=0;k<2;k++) { c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; c.mat[i][j]%=mod; } } } return c; } Matrix matrix_quick_power(matrix a,ll k)//矩阵快速幂0.0 { matrix b; memset(b.mat,0,sizeof(b.mat)); for(ll i=0;i<2;i++) b.mat[i][i]=1;//单位矩阵b while(k) { if(k%2==1) { b=matrix_mul(a,b); k-=1; } else { a=matrix_mul(a,a); k/=2; } } return b; } int main() { ll n; while(~scanf("%lld",&n)) { if(n==0)break; n++; A.mat[0][0]=1;A.mat[0][1]=1; A.mat[1][0]=1;A.mat[1][1]=0; B=matrix_quick_power(A,n); cout<<(B.mat[0][1]+mod)%mod<<endl; } }

Ｉ：map记录数字个数。判断求和（我加了个set）

#include <bits/stdc++.h> #define ll long long using namespace std; set<ll>s; set<ll>::iterator it; ll a; map<ll,int>mp; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { s.clear(); mp.clear(); for(int i=0;i<n;i++) { scanf("%lld",&a); s.insert(a); mp[a]++; } ll ans=0; for( it=s.begin();it!=s.end();it++) { ll p=*it; // cout<<p; if(s.count(p+(ll)m)) { ans=ans+mp[p]*mp[p+(ll)m]; } } printf("%lld\n",ans); } }

K：每个糖果的分法都有m种，m^n,快速幂即可 代码：

#include <bits/stdc++.h> #define ll long long using namespace std; ll mod=1e9+7; ll quick(ll x,ll y) { ll ans=1; while(y) { if(y&1) ans=ans%mod*x%mod; x=x%mod*x%mod; y>>=1; } return ans%mod; } int main() { ll n,m; int t; scanf("%d",&t); while(t--) { cin>>n>>m; printf("%lld\n",quick(m,n)); } }