哈尔滨理工大学软件学院ACM程序设计全国邀请赛（网络同步赛【部分题解】）

蔽队太菜，ABCD都没做出来，好尴一个尬…… 下面就分享一下蔽队做出来的几个题的题解。 E 问你包含字符’6’的子串有多少个。 怎么搞呢？ 就是找每段连续的6有多少个，假设有n个，然后n*(n+1)/2;就是这段的子串数，然后for来扫一遍就好了.其实这个题跟HDU5907是一样的题目。 下面是AC代码：

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<map> using namespace std; #define LL long long char a[200005]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); scanf("%s",a); LL flag=0,s=0; LL sum=0;//需要用long long for(LL i=0;i<n;i++) { if(a[i]=='6'&&flag==0) { flag=1; ++s; continue; } else if(a[i]=='6'&&flag==1) { ++s; continue; } else if(a[i]!='6') { flag=0; sum+=((s*(s+1))/2); s=0; } } sum+=((s*(s+1))/2); printf("%lld\n",sum); } return 0; }

H题 求斐波那契数列的第n项为多少。跟POJ3070这个题基本一样了，我博客里有些，在这里给出链接http://blog.csdn.net/qq_32866009/article/details/51920335

用矩阵快速幂解决的、

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long #define MOD 1000000007 struct Mat { LL a[2][2]; void init() { memset(a,0,sizeof(a)); a[0][0]=1; a[1][1]=1; } }; Mat mul(Mat a,Mat b) { Mat ans; ans.init(); for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { ans.a[i][j]=0; for(int k=0;k<2;k++) { ans.a[i][j]+=a.a[i][k]*b.a[k][j]; } ans.a[i][j]%=MOD; } } return ans; } Mat power(Mat a,LL num) { Mat ans; ans.init(); while(num) { if(num&1) { ans=mul(ans,a); } num/=2; a=mul(a,a); } return ans; } int main() { LL n; while(~scanf("%lld",&n)) { if(n==0) { break; } Mat a,ans; a.a[0][0]=1,a.a[0][1]=1,a.a[1][0]=1,a.a[1][1]=0; ans=power(a,n+1); printf("%lld\n",ans.a[1][0]%MOD); } }

i题，给出一个序列的元素的个数n差一个整数k。 问你这个序列中两个数的差为k的这样的数有多少对。

思路是：先排序，再扣了一下数，存到结构体中（其实不扣也是可以的）。然后再用尺取法搞一下就可以了。 下面是AC代码：

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cmath> #include<stack> #include<queue> #include<map> #include<vector> #define INF 0x3f3f3f3f #define LL long long using namespace std; int a[100004]; struct node { int x,val; }c[100005]; int main() { int n,k; while(~scanf("%d%d",&n,&k)) { int minn=1000000007; int maxn=-1; for(int i=0;i<n;i++) { scanf("%d",&a[i]); if(maxn<a[i]) { maxn=a[i]; } if(minn>a[i]) { minn=a[i]; } } if(maxn-minn<k) { printf("0\n"); continue; } sort(a,a+n); LL sum=0; int cc=0; for(int i=0;i<n;) { int j,cnt=1; for( j=i+1;j<n;j++) { if(a[j]!=a[i]) { break; } cnt++; } c[cc].x=a[i]; c[cc++].val=cnt; i=j; //printf("%d***\n",i); } LL ans=0; int i=0; int j=1; while(j<cc) { if(c[j].x-c[i].x==k) { ans+=c[j].val*c[i].val; j++; } if(c[j].x-c[i].x<k) { j++; } if(c[j].x-c[i].x>k) { i++; } } printf("%lld\n",ans); } return 0; }

J题，就是求奇数的个数有多少个。

下面是AC代码：

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cmath> #include<stack> #include<queue> #include<map> #include<vector> #define INF 0x3f3f3f3f using namespace std; int main() { int n; while(~scanf("%d",&n)) { int sum=0; for(int i = 0; i < n; i++) { long long int k; scanf("%d",&k); if(k%2==1)sum++; } printf("%d\n",sum); } return 0; }

K题，把n个糖果分给m个孩子，总共有多少种分法，而且每个糖果都是不一样的，所以每个糖果分给孩子的话有m种情况，然后总结果数就是m^n.然后用快速幂搞一下就可以了。 下面是AC代码：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define LL long long #define MOD 1000000007 LL quick_mod(LL a,LL b) { LL ans=1; while(b) { if(b&1) { ans=(ans*a)%MOD; b--; } b=b/2; a=a*a%MOD; } return ans; } int main() { LL a,b; int t; scanf("%d",&t); while(t--) { scanf("%lld%lld",&a,&b); if(a==0&&b==0) { break; } LL re=quick_mod(b,a); printf("%lld\n",re%MOD); } return 0; }

L题：就是一个模拟题目，然后要求在这个序列中6的个数有a1个，8的个数有a2个，68的个数有a3个，86的个数有a4个。然后让你求出满足上述条件的最小的数是多少。 先特判不合法的情况，然后再分情况讨论一下就OK了。

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cmath> #include<stack> #include<queue> #include<map> #include<vector> #define INF 0x3f3f3f3f #include<time.h> #include<stdlib.h> using namespace std; int main() { int a,b,c,d; while(~scanf("%d%d%d%d",&a,&b,&c,&d)) { int i; if(c>a||c>b||d>a||d>b) { printf("-1\n"); continue; } if(c+d>=a+b) { printf("-1\n"); continue; } if(abs(c-d)>1) { printf("-1\n"); continue; } if(c>d) { for(int i=0; i<a-d; i++) { printf("6"); } for(int i=0; i<d; i++) { printf("86"); } for(int i=0; i<b-d; i++) { printf("8"); } printf("\n"); } if(d>c) { printf("8"); for(int i=0; i<a-c-1; i++) printf("6"); for(int i=0; i<c; i++) { printf("68"); } for(int i=0; i<b-c-1; i++) { printf("8"); } printf("6"); printf("\n"); } if(d==c) { if(b>a&&a==c) { for(i=0; i<a; i++) { printf("86"); } for(i=0; i<b-d; i++) printf("8"); printf("\n"); } else { for(int i=0; i<a-c-1; i++) printf("6"); for(int i=0; i<c; i++) printf("68"); for(int i=0; i<b-c; i++) printf("8"); printf("6"); printf("\n"); } } } return 0; }