。

分析：

这是多校的一个题，当时没做出来。学长说让用multiset。

用multiset将每一个数的1<<dim个状态全部保存。假设状态 i, 最远曼哈顿距离应当是 max[i]-min[i], 但如果知道 i 的相反的状态就可以转化成 max[i]+min[(~i)&(1<<dim-1)]. 这和 x-y = x + (-y) 是一个道理.

AC代码如下:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 60000+10;const int dem = 5; //维数const int INF = (1<<29);int dim, x[maxn][dem];int main(){ int n, ord; while(scanf("%d %d", &n, &dim) == 2) { multiset
            
              ms[40]; multiset
             
              ::iterator it; for(int i=1; i<=n; i++) { scanf("%d", &ord); if(ord == 0) { for(int j=0; j
              
               >= 1; } ms[j].insert(s); } } else { //ord == 1 scanf("%d", &ord); for(int j=0; j<1<
               
                >= 1; } it = ms[j].find(s); ms[j].erase(it); } } int ans = 0; for(int j=0; j<(1<