首页 > 代码库 > Topcoder SRM632 DIV2 解题报告
Topcoder SRM632 DIV2 解题报告
250:乱搞
解题代码:
1 // BEGIN CUT HERE 2 /* 3 4 */ 5 // END CUT HERE 6 #line 7 "RunningAroundPark.cpp" 7 #include <cstdlib> 8 #include <cctype> 9 #include <cstring>10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 #include <vector>14 #include <string>15 #include <iostream>16 #include <sstream>17 #include <map>18 #include <set>19 #include <queue>20 #include <stack>21 #include <fstream>22 #include <numeric>23 #include <iomanip>24 #include <bitset>25 #include <list>26 #include <stdexcept>27 #include <functional>28 #include <utility>29 #include <ctime>30 using namespace std;31 32 #define PB push_back33 #define MP make_pair34 35 #define REP(i,n) for(i=0;i<(n);++i)36 #define FOR(i,l,h) for(i=(l);i<=(h);++i)37 #define FORD(i,h,l) for(i=(h);i>=(l);--i)38 39 typedef vector<int> VI;40 typedef vector<string> VS;41 typedef vector<double> VD;42 typedef long long LL;43 typedef pair<int,int> PII;44 45 46 class RunningAroundPark47 {48 public:49 int numberOfLap(int N, vector <int> d)50 {51 int hs[100];52 memset(hs,0,sizeof(hs));53 int len = d.size();54 int sum = 1;55 for(int i = 1 ;i < len ;i ++)56 {57 if(d[i] <= d[i-1] )58 sum ++ ; 59 }60 return sum ;61 }62 63 64 };
500:给定序列的二进制尾巴0的个数,问你这一序列的子序列可能构成等比数列的可能数。
解题思路:子序列为等比数列的唯一可能性是这个序列二进制后缀0个数为等差数列
解题代码:
1 // BEGIN CUT HERE 2 /* 3 4 */ 5 // END CUT HERE 6 #line 7 "PotentialGeometricSequence.cpp" 7 #include <cstdlib> 8 #include <cctype> 9 #include <cstring>10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 #include <vector>14 #include <string>15 #include <iostream>16 #include <sstream>17 #include <map>18 #include <set>19 #include <queue>20 #include <stack>21 #include <fstream>22 #include <numeric>23 #include <iomanip>24 #include <bitset>25 #include <list>26 #include <stdexcept>27 #include <functional>28 #include <utility>29 #include <ctime>30 using namespace std;31 32 #define PB push_back33 #define MP make_pair34 35 #define REP(i,n) for(i=0;i<(n);++i)36 #define FOR(i,l,h) for(i=(l);i<=(h);++i)37 #define FORD(i,h,l) for(i=(h);i>=(l);--i)38 39 typedef vector<int> VI;40 typedef vector<string> VS;41 typedef vector<double> VD;42 typedef long long LL;43 typedef pair<int,int> PII;44 45 46 class PotentialGeometricSequence47 {48 public:49 int numberOfSubsequences(vector <int> d)50 {51 int len = d.size();52 int sum = len; 53 for(int i = 1 ;i < len ;i ++)54 {55 int temp = d[i] - d[i-1];56 for(int j = i ;j < len ;j ++)57 {58 int ok = 1 ; 59 for(int s = i ;s <= j; s ++)60 {61 if(d[s] - d[s-1] != temp)62 ok = 0 ; 63 }64 if(ok)65 sum ++ ;66 }67 }68 return sum;69 }70 71 72 };
1000:问你100个数选任意多数乘积为K 的总数有多少
解题思路:可以知道 k的约数最多为1000个 ,我们用map背包就行
解题代码:
1 // BEGIN CUT HERE 2 /* 3 4 */ 5 // END CUT HERE 6 #line 7 "GoodSubset.cpp" 7 #include <cstdlib> 8 #include <cctype> 9 #include <cstring>10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 #include <vector>14 #include <string>15 #include <iostream>16 #include <sstream>17 #include <map>18 #include <set>19 #include <queue>20 #include <stack>21 #include <fstream>22 #include <numeric>23 #include <iomanip>24 #include <bitset>25 #include <list>26 #include <stdexcept>27 #include <functional>28 #include <utility>29 #include <ctime>30 using namespace std;31 32 #define PB push_back33 #define MP make_pair34 35 #define REP(i,n) for(i=0;i<(n);++i)36 #define FOR(i,l,h) for(i=(l);i<=(h);++i)37 #define FORD(i,h,l) for(i=(h);i>=(l);--i)38 39 typedef vector<int> VI;40 typedef vector<string> VS;41 typedef vector<double> VD;42 typedef long long LL;43 typedef pair<int,int> PII;44 45 vector <LL>a;46 int num[105];47 int n ; 48 int rn; 49 map <LL,LL> mp[105];50 map <LL,LL> ::iterator it;51 #define M 100000000752 class GoodSubset53 {54 public:55 int numberOfSubsets(int goodValue, vector <int> d)56 {57 for(int i = 0 ;i <=100 ;i ++)58 mp[i].clear();59 mp[0][1] = 1;60 n = d.size();61 for(int i = 1 ;i <=n ;i ++)62 {63 int t = 0 ;64 for( it = mp[i-1].begin();it != mp[i-1].end();it++)65 {66 t ++ ; 67 //printf("%d %lld %lld\n",i,it->first,it->second);68 mp[i][it->first] = (mp[i][it->first] + mp[i-1][it->first])%M;69 if(goodValue % (d[i-1]*it->first) == 0 )70 mp[i][d[i-1]*it->first] = (it->second+mp[i][d[i-1]*it->first])%M;71 }72 // printf("%d\n",t);73 }74 if(goodValue =http://www.mamicode.com/= 1)75 mp[n][goodValue] -- ;76 return int(mp[n][goodValue]);77 }78 79 };
Topcoder SRM632 DIV2 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。