TopCoder-SRM632-DIV1-300pt-PotentialArithmeticSequence-归纳推理+枚举
http://community.topcoder.com/stat?c=problem_statement&pm=13389&rd=16075
比正常的簡(jiǎn)單題多了50分。說(shuō)明比平時(shí)的簡(jiǎn)單題要難一些。
考慮輸入規(guī)模，可以看出枚舉并判斷所有子序列是可行的。那么關(guān)鍵就是如何判斷一個(gè)子序列是合法的。
先觀察第一組測(cè)試用例{0,1,0,2,0,1,0}，可以看出其是0,b1,0,b2...這樣交替的。顯然兩個(gè)相鄰自然數(shù)是奇偶交替的，奇數(shù)的那些數(shù)字結(jié)尾只有0個(gè)0.
1）必要條件一：d[i]和d[i+1]必須是0和>0交替的。
對(duì)于那些奇數(shù)d[i]=0，則其所有位都可以是任意的數(shù)，也就是說(shuō)d[i]=0就能滿足任何的奇數(shù)限制。
再考慮偶數(shù)位：d[i]和d[i+2]，其實(shí)只加上了2，那么可以總結(jié)出一些約束：當(dāng)di>1時(shí)，加上2后這個(gè)數(shù)字最后必然就是2。也就是只有一個(gè)0。d[i+2]=1。如果不是就是錯(cuò)誤的。而di=1時(shí)，d[i+2]>1，因?yàn)橛羞M(jìn)位，我們無(wú)法對(duì)高位做更多的約束。
2）必要條件二：d[i]和d[i+2]需要滿足：
if (d[i]>1) d[i+2]=1 反之亦然。
如果只把這兩個(gè)條件代入會(huì)有錯(cuò)誤。因?yàn)殡m然d[i]和d[i+2]滿足約束了，但是有可能d[i]與d[i+2*k] (k>1)不滿足約束。所以我們需要把必要條件二推廣到d[i+2*k]。以找出更多的約束。
方法一樣的，d[i+2*k]=d[j]，其在i數(shù)字基礎(chǔ)上加了2*k,我們求出2*k末尾有多少個(gè)0，設(shè)為d2k。那么d[j]與d[i]需要滿足當(dāng)d[i]>d2k時(shí)，是d2k個(gè)0。當(dāng)d[i]<d2k時(shí)，是d[i]個(gè)0.當(dāng)d[i]=d2k時(shí)，末尾有>d2k個(gè)0.
然后修改必要條件二為：
2)必要條件二：d[i]與d[j](j:j=i+2*k(k>=0)])，需要滿足：
if (di!=d2k)?dj=min(di,d2k)
else dj>d2k
滿足這個(gè)條件以后，再考慮一下由于進(jìn)位也無(wú)法對(duì)高位做更多約束，即可求得答案。
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;} };?
轉(zhuǎn)載于:https://www.cnblogs.com/yangsc/p/4052484.html
總結(jié)
以上是生活随笔為你收集整理的TopCoder-SRM632-DIV1-300pt-PotentialArithmeticSequence-归纳推理+枚举的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
