TopCoder-SRM632-DIV1-300pt-PotentialArithmeticSequence-归纳推理+枚举
http://community.topcoder.com/stat?c=problem_statement&pm=13389&rd=16075
比正常的简单题多了50分。说明比平时的简单题要难一些。
考虑输入规模，可以看出枚举并判断所有子序列是可行的。那么关键就是如何判断一个子序列是合法的。
先观察第一组测试用例{0,1,0,2,0,1,0}，可以看出其是0,b1,0,b2...这样交替的。显然两个相邻自然数是奇偶交替的，奇数的那些数字结尾只有0个0.
1）必要条件一：d[i]和d[i+1]必须是0和>0交替的。
对于那些奇数d[i]=0，则其所有位都可以是任意的数，也就是说d[i]=0就能满足任何的奇数限制。
再考虑偶数位：d[i]和d[i+2]，其实只加上了2，那么可以总结出一些约束：当di>1时，加上2后这个数字最后必然就是2。也就是只有一个0。d[i+2]=1。如果不是就是错误的。而di=1时，d[i+2]>1，因为有进位，我们无法对高位做更多的约束。
2）必要条件二：d[i]和d[i+2]需要满足：
if (d[i]>1) d[i+2]=1 反之亦然。
如果只把这两个条件代入会有错误。因为虽然d[i]和d[i+2]满足约束了，但是有可能d[i]与d[i+2*k] (k>1)不满足约束。所以我们需要把必要条件二推广到d[i+2*k]。以找出更多的约束。
方法一样的，d[i+2*k]=d[j]，其在i数字基础上加了2*k,我们求出2*k末尾有多少个0，设为d2k。那么d[j]与d[i]需要满足当d[i]>d2k时，是d2k个0。当d[i]<d2k时，是d[i]个0.当d[i]=d2k时，末尾有>d2k个0.
然后修改必要条件二为：
2)必要条件二：d[i]与d[j](j:j=i+2*k(k>=0)])，需要满足：
if (di!=d2k) dj=min(di,d2k)
else dj>d2k
满足这个条件以后，再考虑一下由于进位也无法对高位做更多约束，即可求得答案。
int m,n; class PotentialArithmeticSequence{ public: vector<int> d;int CalcD(int step){ int num=0;for(int i=0;i<step;i++){num+=2;}int res=0;while(!(num & 1)){res++;num=num>>1;}return res;}bool Check(int p,int q){for(int i=p;i<q;i++){if (i<q-1) {if (!d[i] && !d[i+1]) return false;if (d[i] && d[i+1]) return false;}if (d[i]==0) continue;for(int j=i+2;j<q;j+=2){if (d[j]==0) return false;int k=(j-i)/2;int d2k=CalcD(k);if (d[i]>d2k) {if (d[j]!=d2k) return false;}else if (d[i]<d2k){if (d[j]!=d[i]) return false;}else{ //di==d2kif (d[j]<=d2k) return false;}}}return true;}int numberOfSubsequences(vector <int> d) { this->d=d;n=d.size();int res=0;for(int i=0;i<n;i++) {for(int j=i+1;j<=n;j++){if (Check(i,j)) {res++;}}}return res;} };
转载于:https://www.cnblogs.com/yangsc/p/4052484.html
总结
以上是生活随笔为你收集整理的TopCoder-SRM632-DIV1-300pt-PotentialArithmeticSequence-归纳推理+枚举的全部内容，希望文章能够帮你解决所遇到的问题。
