Codeforces #228 D2D / D1B：Fox and Minimal path - c++编程基础

第一次做这种题目，参考了作者的 Editorial ，主要思想将 k 看成2进制形式，再采用分层的思想构造图，第一层为（1），第二层为（1,1），第三层为（1,1,2），第四层为（1,1,2,4），第五层（1,1,2,4,8），以此类推，最多分32层即可。

代码：

// Fox and Minimal path

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         using namespace std; typedef pair
                        
                          pii; typedef long long llong; typedef pair
                         
                           pll; #define mkp make_pair bool G[1001][1001]; int b[32]; inline void addEdge(int i, int j) { G[i][j] = G[j][i] = true; } int main() { //#define LOCAL // 提交时注释掉 #ifdef LOCAL freopen(data.txt, r, stdin); #endif int k; while (cin >> k) { memset(G, 0, sizeof(G)); int temp = k; for (int i = 0; i < 32; i++) { b[i] = temp & 1; temp >>= 1; } int mxbit = 0; for (int i = 31; i >= 0; i--) { if (b[i]) { mxbit = i; break; } } int layers = mxbit + 2; addEdge(1, 3); addEdge(1, 4); int id = 3; int last_id = 3; for (int i = 2; i < layers; i++) { for (int j = 0; j < i; j++) { addEdge(id + j, id + j + i); addEdge(id + j, id + i + i); } id += i; last_id = id; } for (int i = 0; i <= mxbit; i++) { if (b[i]) { addEdge(last_id + i + 1, 2); } } printf(%d , last_id + layers - 1); for (int i = 1; i <= last_id + layers - 1; i++) { for (int j = 1; j <= last_id + layers - 1; j++) { if (G[i][j] ) { printf(Y); } else { printf(N); } } printf( ); } } return 0; }