SRM 397(1-250pt)-白红宇

SRM 397(1-250pt)

阅读量：6324 次

发布时间：2019-06-22

本文共 5013 字，大约阅读时间需要 16 分钟。

题意：对于一个长度n的数列（由1-n组成，n <= 8），每次操作可以reverse k个连续的数。问最少多少次操作可以将该数列转化成递增的数列。

解法：就是一个BFS。只是由于最开始学习BFS时写法很复杂，所以直到现在也觉得BFS不好写。然后就在想还有没有别的方法，然后时间就浪费了...最后还是写了个比较冗杂的BFS，150+score。看了官方题解的BFS，真是学习了...一方面是BFS的写法搓，另一方面是不会用C++内置的reverse函数。

tag:BFS

我的代码：

1 // BEGIN CUT HERE  2 /*  3  * Author:  plum rain  4  * score :  5  */  6 /*  7   8  */  9 // END CUT HERE 10 #line 11 "SortingGame.cpp" 11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 #include 
          
            16 #include 
           
             17 #include 
            
              18 #include 
             
               19 #include 
              
                20 #include 
               
                 21 #include 
                
                  22 #include 
                 
                   23 #include 
                  
                    24 #include 
                   
                     25 #include 
                    
                      26 #include 
                     
                       27 #include 
                      
                        28 #include 
                       
                         29 #include 
                        
                          30 #include 
                         
                           31 #include 
                           32 #include 
                           
                             33 #include 
                            
                              34 35 using namespace std; 36 37 #define CLR(x) memset(x, 0, sizeof(x)) 38 #define CLR1(x) memset(x, -1, sizeof(x)) 39 #define PB push_back 40 #define SZ(v) ((int)(v).size()) 41 #define ALL(t) t.begin(),t.end() 42 #define zero(x) (((x)>0?(x):-(x))

VI; 48 typedef vector

VS; 49 typedef vector

VD; 50 typedef pair

pii; 51 typedef long long int64; 52 53 const double eps = 1e-8; 54 const double PI = atan(1.0)*4; 55 const int maxint = 2139062143; 56 57 struct nod{ 58 VI b; 59 int d; 60 }; 61 62 VI b; 63 int n; 64 nod an[1000000]; 65 set

st; 66 VI ans; 67 68 69 int BFS(int k) 70 { 71 if (b == ans) return 0; 72 st.erase(ALL(st)); 73 int l = 0, r = 0; 74 VI ttt; 75 nod tt; tt.d = 1; 76 for (int i = 0; i+k <= n; ++ i){ 77 ttt = b; 78 for (int j = i, t = i+k-1; j < t; ++ j, -- t) 79 swap(ttt[j], ttt[t]); 80 tt.b = ttt; 81 if (!st.count(ttt)){ 82 an[r++] = tt; 83 st.insert(ttt); 84 } 85 } 86 87 while (l < r){ 88 nod tmp = an[l++]; 89 if (tmp.b == ans) return tmp.d; 90 ++ tmp.d; 91 for (int i = 0; i+k <= n; ++ i){ 92 ttt = tmp.b; 93 for (int j = i, t = i+k-1; j < t; ++ j, -- t) 94 swap(ttt[j], ttt[t]); 95 if (!st.count(ttt)){ 96 an[r].b = ttt; 97 an[r++].d = tmp.d; 98 st.insert(ttt); 99 }100 }101 }102 return -1;103 }104 105 class SortingGame106 {107 public:108 int fewestMoves(vector

B, int k){109 b = B; n = b.size();110 ans.clear();111 for (int i = 1; i <= n; ++ i)112 ans.PB(i);113 return BFS (k);114 }115 116 // BEGIN CUT HERE117 public:118 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }119 private:120 template

string print_array(const vector

&V) { ostringstream os; os << "{ "; for (typename vector

::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }121 void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }122 void test_case_0() { int Arr0[] = { 1,2,3}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; int Arg2 = 0; verify_case(0, Arg2, fewestMoves(Arg0, Arg1)); }123 void test_case_1() { int Arr0[] = { 3,2,1}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; int Arg2 = 1; verify_case(1, Arg2, fewestMoves(Arg0, Arg1)); }124 void test_case_2() { int Arr0[] = { 5,4,3,2,1}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; int Arg2 = 10; verify_case(2, Arg2, fewestMoves(Arg0, Arg1)); }125 void test_case_3() { int Arr0[] = { 3,2,4,1,5}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; int Arg2 = -1; verify_case(3, Arg2, fewestMoves(Arg0, Arg1)); }126 void test_case_4() { int Arr0[] = { 7,2,1,6,8,4,3,5}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; int Arg2 = 7; verify_case(4, Arg2, fewestMoves(Arg0, Arg1)); }127 128 // END CUT HERE129 130 };131 132 // BEGIN CUT HERE133 int main()134 {135 // freopen( "a.out" , "w" , stdout ); 136 SortingGame ___test;137 ___test.run_test(-1);138 return 0;139 }140 // END CUT HERE

View Code

官方题解推荐代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 using namespace std; 9 typedef vector
             
               VI;10 11 struct SortingGame {12 int fewestMoves(vector
              
                board, int k) {13 map
               
                 dist;14 dist[board] = 0;15 16 queue
                
                  Q;17 Q.push(board);18 19 int i, N = board.size();20 21 while (!Q.empty()) {22 VI u = Q.front(); Q.pop();23 int d = dist[u];24 25 for (i = 1; i < N; i++)26 if (u[i-1] > u[i]) break;27 if (i == N) return d;28 29 for (i = 0; i + k <= N; i++) {30 VI w = u;31 reverse(w.begin() + i, w.begin() + i + k);32 if (dist.count(w) == 0) {33 dist[w] = d + 1;34 Q.push(w);35 }36 }37 }38 39 return -1; 40 }41 };

View Code

转载于:https://www.cnblogs.com/plumrain/p/srm_397.html

你可能感兴趣的文章