CodeForces #213 (Div. 2) A,B,C 解题报告

发布时间:2014-10-23 23:27:44
来源:分享查询网

A.Good Number 题意:         给了一个整数K(0<=k<9)..若一个正整数a(1<=a<=10^9所有的数位都是由0~k的数组成并且0~k每个数都出现了.那么这个数是Good Number..现在给出N(1<=N<=100)个a..问有多少个Good Number... 题解:         关键是题目看懂..是必须0~k每个都要出现... Program: #include<iostream> #include<stdio.h> #include<string.h> #include<queue> #include<stack> #include<algorithm> #include<cmath> #include<set> #include<map> #define ll long long #define oo 2000005 #define MAXN 4050000 #define pi acos(-1.0) #define esp 1e-30 using namespace std; bool s[10]; bool judge(int x,int k) { memset(s,false,sizeof(s)); while (x) s[x%10]=true,x/=10; for (x=0;x<=k;x++) if (!s[x]) return false; return true; } int main() { int n,x,k,ans; scanf("%d%d",&n,&k),ans=0; while (n--) { scanf("%d",&x); ans+=judge(x,k); } printf("%d\n",ans); return 0; } B. The Fibonacci Segment   题意:         给了一列N个数(N<=10^5)...每个数0<=ai<=10^9....          Segment [l, r] (1 ≤ l ≤ r ≤ n) is good if ai = ai - 1 + ai - 2, for all i (l + 2 ≤ i ≤ r),Let's define len([l, r]) = r - l + 1, len([l, r]) is the length of the segment [l, r]. Segment [l1, r1], is longer than segment [l2, r2], iflen([l1, r1]) > len([l2, r2]). 题解:         扫一遍过去就出来了...注意特判N=1,N=2 Program: #include<iostream> #include<stdio.h> #include<string.h> #include<queue> #include<stack> #include<algorithm> #include<cmath> #include<set> #include<map> #define ll long long #define oo 1<<30 #define MAXN 100005 #define pi acos(-1.0) #define esp 1e-30 using namespace std; int a[MAXN]; int main() { int n,l,i,ans; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); if (n==1) { puts("1"); return 0; } if (n==2) { puts("2"); return 0; } ans=0,l=1; for (i=3;i<=n;i++) if (a[i]!=a[i-1]+a[i-2]) { ans=max(ans,i-l); l=i-1; } ans=max(ans,i-l); printf("%d\n",ans); return 0; } C. Matrix   题意:         给了一列N个数,(1<=N<=4000)...每个数是0~9...定义一个生成举证的运算bij=si*sj..其中b是生成矩阵,s是原数列...现在给出一个数a..问矩阵b中有多少个子矩阵的所有元素之和为a.. 题解:         理解了是如何生成的..题目就不难...大致思想是先预处理前缀和...排序放在数组中..然后美剧两个端点l,r..算出之间的数之和x=(s[l]+s[l+1]+...+s[r-1]+s[r])..若x为a的约数..那么用二分在预处理出的数组中快速找出有多少个a/x..就可以得到解了...特别值得注意的是x=0或者a=0的情况..要特殊讨论...         方法不够优..TLE边缘..而且比赛后的judge也给我TLE了..赛后做了小部分修改才飘过的... Program: #include<iostream> #include<stdio.h> #include<string.h> #include<queue> #include<stack> #include<algorithm> #include<cmath> #include<set> #include<map> #define ll long long #define oo 1000000007 #define MAXN 4005 #define MAXM 20000000 #define esp 1e-30 using namespace std; ll H[MAXM],A[MAXN]; char s[MAXN]; ll bsearch(ll x,ll n) { int l=0,r=n+1,mid; while (r-l>1) { mid=l+r>>1; if (H[mid]<=x) l=mid; else r=mid; } return l; } int main() { int a,n,i,num,l,r,x,t; ll ans; scanf("%d%s",&a,s+1),n=strlen(s+1); for (i=1;i<=n;i++) A[i]=s[i]-'0'; num=0; for (l=1;l<=n;l++) { x=0; for (r=l;r<=n;r++) x+=A[r],H[++num]=x; } sort(H+1,H+1+num); ans=0; for (l=1;l<=n;l++) { x=0; for (r=l;r<=n;r++) { x+=A[r]; if (!x) { if (!a) ans+=num; continue; } else { if (a%x) continue; t=a/x; } ans+=bsearch(t,num)-bsearch(t-1,num); } } printf("%I64d\n",ans); // system("pause"); return 0; }

返回顶部
查看电脑版