首页 > 代码库 > 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 };
View Code

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 };
View Code

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 };
View Code

 

Topcoder SRM632 DIV2 解题报告