您的位置: 首页  >  IT文章  >  Topcoder SRM632 DIV2 解题报告

Topcoder SRM632 DIV2 解题报告

分类: IT文章 • 2023-12-06 13:27:13

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_back
33 #define MP make_pair
34 
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 RunningAroundPark
47 {
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_back
33 #define MP make_pair
34 
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 PotentialGeometricSequence
47 {
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_back
33 #define MP make_pair
34 
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 1000000007
52 class GoodSubset
53 {
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
",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
",t);
73           }
74            if(goodValue == 1)
75                mp[n][goodValue] -- ;
76            return int(mp[n][goodValue]);
77         }
78 
79 };
View Code

相关推荐