SRM482-創(chuàng)新互聯(lián)

250pt

題意：給定n把鎖，第i輪每間隔i個打開一個木有打開的。問最后打開的事幾

專注于為中小企業(yè)提供網(wǎng)站制作、網(wǎng)站設(shè)計服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)回民免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了近1000家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

思路：直接vector模擬

code：

 1 #line 7 "LockersDivOne.cpp"
 2 #include <cstdlib>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <string>
10 #include <iostream>
11 #include <sstream>
12 #include <map>
13 #include <set>
14 #include <queue>
15 #include <stack>
16 #include <fstream>
17 #include <numeric>
18 #include <iomanip>
19 #include <bitset>
20 #include <list>
21 #include <stdexcept>
22 #include <functional>
23 #include <utility>
24 #include <ctime>
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 
34 typedef vector<int> VI;
35 typedef vector<string> VS;
36 typedef vector<double> VD;
37 typedef long long LL;
38 typedef pair<int,int> PII;
39 
40 class LockersDivOne
41 {
42 public:
43 int get(int n){
44               vector<int> a, b;
45 for (int i = 0; i < n; ++i)
46                   a.push_back(i);
47 int res = 0;
48 for (int i = 2; ; ++i){
49 if (a.size() == 0) break;
50                     b.clear();
51 for (int j = 0; j < a.size(); j++)
52 if (j % i == 0) res = a[j] + 1;
53 else b.push_back(a[j]);
54                     a = b;
55               }
56 return res;
57             
58         }
59 int lastOpened(int N)
60         {
61   return get(N);
62         }
63 };

View Code

500pt

題意：A和B兩個人玩漢諾塔，其中A移動漢諾塔用最快的方法，移動的步數(shù)是2^n-1步，而B用的方法可以保證每種狀態(tài)恰好被訪問到一次，移動的步數(shù)是3^n-1。兩個人移動的偽代碼都給定，問第一個人移動K步后的configuration，按照第二個人的方法需要移動多少步。

思路:先算出最終的狀態(tài)。然后根據(jù)最終的狀態(tài)用遞歸算出答案。

code:

 1 #line 7 "HanoiGoodAndBad.cpp"
 2 #include <cstdlib>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <string>
10 #include <iostream>
11 #include <sstream>
12 #include <map>
13 #include <set>
14 #include <queue>
15 #include <stack>
16 #include <fstream>
17 #include <numeric>
18 #include <iomanip>
19 #include <bitset>
20 #include <list>
21 #include <stdexcept>
22 #include <functional>
23 #include <utility>
24 #include <ctime>
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 
34 typedef vector<int> VI;
35 typedef vector<string> VS;
36 typedef vector<double> VD;
37 typedef long long LL;
38 typedef pair<int,int> PII;
39 int thr[20];
40 
41 class HanoiGoodAndBad
42 {
43 public:
44 int dd, ans;
45 int H[3][25];
46 int top[3];
47 void solve_Dave(int a, int c, int b, int n){
48  if(n > 0){
49   if (dd == 0) return;
50                 solve_Dave(a, b, c, n-1);
51   if (dd == 0) return;
52                 H[c][++top[c]] = n;
53                 H[a][top[a]--] = 0;
54                 --dd;
55                 solve_Dave(b, c, a, n-1);
56             }
57         }
58 void solve_Earl(int a, int c, int b, int n){
59 if (n == 0) return;
60 int P = 0;
61 if (H[1][top[1]] == n) P = 1;
62 if (H[2][top[2]] == n) P = 2;
63               top[P]--;
64 if (P == c){ 
65                       ans += 2 * thr[n-1];
66                       solve_Earl(a, c, b, n-1);
67               }
68 if (P == b){ 
69                       ans += thr[n-1];
70                       solve_Earl(c, a, b, n-1);
71               }
72 if (P == a) solve_Earl(a, c, b, n-1);
73         }
74 int moves(int N, int Dave)
75         {
76              dd = Dave;
77              memset(top, 0, sizeof(top)); 
78              memset(H, 0, sizeof(H)); 
79   for (int i = N; i >= 1; --i)  H[0][++top[0]] = i;
80              solve_Dave(0, 2, 1, N);
81              ans = 0;
82   for (int i = 0; i < 3; ++i)
83 for (int j = 1; j <= top[i]/ 2; ++j)
84                     swap(H[i][j], H[i][top[i]-j+1]);
85              thr[0] = 1;
86   for (int i = 1; i <= 19; ++i) thr[i] = thr[i-1] * 3;
87              solve_Earl(0, 2, 1, N);
88   return ans;
89         }
90 };

View Code

網(wǎng)站欄目：SRM482-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://www.jbt999.com/article32/shhsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營銷型網(wǎng)站建設(shè)、定制開發(fā)、服務(wù)器托管、手機網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、定制網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：[email protected]。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容