浅谈Codeforces round 217 Summer Reading的两种解法:DP与构造 - c++编程基础

这是在codeforces上参加的第二场比赛了，虽然最后测评的结果显示在房间排名是第二名，但是与第一名的差距之大却是很难看的。这里，简单地报告一下E题Summer Reading的两种解法。比赛完后，看了作者提供的tutorial仍然是一脸雾水，主要是因为误解block为输入中连续的数字块。之后，借鉴了牛人的代码，才知道block其实是指一本书号的数字块。如给定输入序列为0 0 2 2 3 3 0 0 4 4 0，这其中就存在着三个block，即2 2；3 3；4 ；而非两个block（2 2 3 3；4 ；）。

解法一（思想源于作者的tutorial）：

根据作者提供的DP思想，对于每一个block都可以尝试进行向左或向右扩展，如 4 可以向左扩展为 4 4 4 ，然后再向右扩展，就变为了 4 4 4 4 ，并且符号题中所给条件。对于一个特定的block[i]来说，其向左扩展的限制在于其左边的block[i-1]的向右扩展结果，block[i-1]与block[i]间缺少的书号，以及block[i-1]后面紧跟着的0的个数，而其向右扩展的限制在于其向左扩展的结果以及block[i]后面紧跟着的0的个数。

示例：0 0 2 2 3 3 0 0 4 0

block[1] = 2 2，此时已无法向左扩展（即向左扩展0位），因为必须block[1]之前缺少的书号的数目为1（即只有书号1缺失），至少要占据两个0。并且由于block[1]后面没有紧跟着的0，所以向右也无法扩展。

block[2] = 3 3，向左无法扩展，因为block[1]与block[2]之间没有0存在。向右可以扩展1位或者2位，都不会打破题中的限制。

block[3] = 4 4，向左扩展讨论：在block[2]扩展1位的情况下，block[3]向左扩展1位；在block[2]扩展2位的情况下，block[3]向左无扩展（即扩展0位）。向右扩展讨论：在block[3]向左扩展1位或者2位的情况下，block[3]向右扩展1位，或者不扩展。

在block[3]向左不扩展时，block[4]向右扩展1位。

在上述block扩展的过程中，如果有一个block不管是向右扩展几位（包括扩展0位）都无法满足题中条件时，就直接输出-1，并退出执行。否则，就可以利用block的扩展情况进行还原书号序列。

下面用两个数组exLeft和exRight来分别表示每个block的向左扩展情况和向右扩展情况。为了方便，令block[1]之前还存在着一个block[0]。

block[0]：为了不占用block[0]后面的零，令exRight[0][0]= true，exRight[0][1-4] = false

block[1]：exLeft[1][0] = true，exLeft[1][1-4]= false（block[1]无法向左扩展）；同理，exRight[1][0]= true，exRight[1][1-4] = false。

block[2]：exLeft[2][0] = true，exLeft[2][1-4]= false；exRight[2][0-2] = true，exRight[2][3-4]= false（block[2]向右扩展1位或者2位均可）。

block[3]：exLeft[3][0-1] = true，exLeft[3][2-4]= false；exRight[3][0-1] = true，exRight[3][2-4]= false（exRight[3][0] = true对应于exLeft[3][1]= true，而exRight[3][1] = true对应于exLeft[3][0]= true或者exLeft[3][1] = true）。

对于最后一个block，为了使得留出更多的0来填充更大的书号，我们要使用exRight[3][i] = true最小的那个i，即i= 0，但由于此时只剩下一个0，无法完整填充更大的书号，所以i=1。接着寻找可以与exRight[3][1]= true相对应的exLeft[3][j]，然后利用exLeft[3][j]找到可以与其相对应的exRight[2][k]，如此递归下去。对于每个block，利用找到的合适的exLeft和exRight进行向左、向右扩展，完成书号的填充。

在编码过程中，exLeft[i][j]里面可以记录可以与其相对应的一个exRight[i-1][k]中的k值，这样就可以快速向前递归填充了。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             using namespace std; class BLOCK { public: int elem; int numElem; int numZero; public: BLOCK(int _elem = 0, int _numElem = 0, int _numZero = 0) { elem = _elem; numElem = _numElem; numZero = _numZero; } }; int n; vector
            
              note; vector
             
               block; vector
              
                > toLeft, toRight; vector
               
                 ans; bool Work() { block.clear(); block.push_back( BLOCK(0,0,0) ); for(int i = 0; i < n; ++i) { if( !note[i] ) { block.back().numZero++; } else { if( note[i] != block.back().elem ) { block.push_back( BLOCK(note[i], 1, 0) ); } else { block.back().numElem += block.back().numZero + 1; block.back().numZero = 0; } } } toLeft.assign(block.size(), vector
                
                 (5,-1)); toRight.assign(block.size(), vector
                 
                  (5,-1)); toRight[0][0] = 0; for(int i = 1; i < int(block.size()); ++i) { // calculate toLeft[i], which is only related to toRight[i-1] for(int l = 0; l < 5; ++l) { if( l + block[i].numElem > 5 ) continue; for(int r = 0; r < 5 && toLeft[i][l] < 0; ++r) { if( toRight[i-1][r] < 0 ) continue; if( r + l <= block[i-1].numZero ) { int zeros = block[i-1].numZero - l - r; int diff = block[i].elem - block[i-1].elem; diff -= 1; if( zeros >= diff*2 && zeros <= diff*5 ) { toLeft[i][l] = r; } } } } // calculate toRight[i], which is only related to toLeft[i] bool terminal = false; for(int r = 0; r < 5; ++r) { if( r > block[i].numZero ) continue; for(int l = 0; l < 5 && toRight[i][r] < 0; ++l) { if( toLeft[i][l] < 0 ) continue; int num = r + l + block[i].numElem; if( num >= 2 && num <= 5 ) { toRight[i][r] = l; terminal = true; } } } if( !terminal ) return false; } int size = int(block.size()); int pos = 0; while( toRight[size-1][pos] < 0 && pos < 5 ) ++pos; int remain = block.back().numZero - pos; ans.clear(); if( remain == 1 ) { ++pos; if( toRight[size-1][pos] < 0 ) return false; ans.push_back( block.back().elem ); } else if( remain > 1 ) { int val = block.back().elem + 1; if( remain&1 ) { ans.push_back( val ); --remain; } for(int i = 1; i <= remain; ++i) { ans.push_back( val ); if( !(i&1) ) ++val; } reverse(ans.begin(), ans.end()); } int lj, rj = pos; for(int i = size - 1; i > 0; --i) { lj = toRight[i][rj]; int num = lj + rj + block[i].numElem; for(int k = 0; k < num; ++k) ans.push_back( block[i].elem ); rj = toLeft[i][lj]; // cal the position, to which (i-1)th block extends; int zeros = block[i-1].numZero - rj - lj; int numVal = block[i].elem - block[i-1].elem - 1; if( !numVal ) continue; vector
                  
                    temp; int m = zeros/numVal, re = zeros%numVal; int val = block[i-1].elem + 1; for(int k = 1; k <= numVal; ++k) { for(int j = 0; j < m; ++j) temp.push_back( val ); if( k <= re ) temp.push_back( val ); ++val; } reverse(temp.begin(), temp.end()); ans.insert(ans.end(), temp.begin(), temp.end()); } reverse(ans.begin(), ans.end()); cout << ans.back() << endl; for(int i = 0; i < int(ans.size()); ++i) cout << ans[i] << " "; cout << endl; return true; } int main() { ios::sync_with_stdio(false); //freopen("data.tst", "r", stdin); while( cin >> n ) { note.resize( n ); for(int i = 0; i < n; ++i) cin >> note[i]; if( !Work() ) cout << -1 << endl; } return 0; }

解法二：构造解

把Vasya做n天的SummerReading想象成骑车穿过n米的长路。那么Vasya最快的方式是每隔两米，速度就增加1，最慢的方式是每隔五米，速度才增加1。输入中的非零数代表Vasya在此点时的速度。如果这个非零值小于Vasya以最慢的方式达到此点的速度，或者大于Vasya以最快的方式达到此点的速度，那么肯定是不合法的。

示例：0 0 2 2 3 3 0 0 4 4 0

最快方式：1 1 2 2 3 3 4 4 4 4 5

最慢方式：1 1 2 2 3 3 4 4 4 4 4

根据题中要求对于出现的书号，至少要出现两次。所以，对于达到的速度值至少要出现两次。最快的方式里面5只出现一次，为了满足条件，必须减1。最快方式就变成了 1 1 2 2 3 3 4 4 4 4 4。

浅谈Codeforces round 217 Summer Reading的两种解法:DP与构造(一)