topcoder srm 623解题报告

本文主要是介绍topcoder srm 623解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

详见：http://robotcator.logdown.com/posts/231132-topcoder-srm-623

推荐使用插件greed 2.0，非常使用的插件。但我不知道如何自己添加测试数据，下次再学习下。
Greed 2.0 https://github.com/shivawu/topcoder-greed
250pt
题意：环形跑道上有n棵树，标号为1--n，Alice跑步时记录下一些树的标号。问通过这些编号计算她最少跑了多少圈。
题解：稍微想一下就知道，一圈下来树的编号都是递增的，所以相邻记录非递增则增加一圈，这样圈数最少。

class RunningAroundPark {public:int numberOfLap(int N, vector<int> d) {int cnt = 0;for(int i = 1; i < d.size(); i ++){if(d[i] <= d[i-1]) cnt ++;}return cnt+1;}
};

500pt
题意：有一序列未知a，但给一个序列d，其中d[i]表示a[i]换算为二进制时末尾零的个数。问a中存在多少对（i， j）使得i--j区间的数为几何级数（等比数列，公比为实数）。
题解：考虑数位性质，a[i]与a[i+1]相差d[i+1]-d[i]个零，那么a[i]左移或者右移d[i+1]-d[i]位得到a[i+1]，即乘以2^(d[i+1]-d[i])。所以区间(i, j)中d为等差数列，那么a在相应的区间为等比数列。范围不大，暴力。

class PotentialGeometricSequence {public:int numberOfSubsequences(vector<int> d) {int cnt = 0;for(int l = 3; l <= d.size(); l ++){for(int i = 0; i <= d.size()-l; i ++){int g = d[i+1] - d[i];int flag = 1;for(int j = i+1; j < i+l-1; j ++){if(d[j+1]-d[j] != g) {flag = 0; break;}
           }if(flag == 1) cnt ++;}}return cnt+2*d.size()-1;// 2*d.size()-1分别是序列长度为1,2的时候的（i,j）对数
    }
};

1000 pt
题意：给定集合d,求有多少个d的子集，子集所有元素的积为goodValue。
题解：记忆化搜索。
注意事项：记忆化搜索因为是递归，所以要想清楚递归边界，还有就是如果已存储则直接返回不需要递归计算。

不整除 整除

原谅我不会打整除和不整除符号，把公式弄残了。还望大侠指教。

class GoodSubset {public:map<pair<int, int>, int> m;int dp(int goodValue, vector<int> d, int cur){if(cur == 0){if(goodValue == 1) return 1;else return 0;}if(m.find(make_pair(goodValue, cur)) != m.end()){return m[make_pair(goodValue, cur)];}int ans = 0;if(goodValue%d[cur-1] != 0){return m[make_pair(goodValue, cur)] = dp(goodValue, d, cur-1);}else{ans += dp(goodValue, d, cur-1);ans %= mod;ans += dp(goodValue/d[cur-1], d, cur-1);ans %= mod;return m[make_pair(goodValue, cur)] = ans;}}int numberOfSubsets(int goodValue, vector<int> d) {m.clear();int cnt = dp(goodValue, d, d.size());if(goodValue == 1) cnt --;return cnt;}
};