折半搜索求调qwq
查看原帖
折半搜索求调qwq
246331
mystic_qwq楼主2024/8/12 00:44
#include<bits/stdc++.h>
using namespace std;
#define int long long
template<class T>
void smax(T&x,T y){
  if(x<y) x=y;
}
using pii=pair<int,int>;
int n,P,pw[25];
array<int,3> a[25];
map<pii,pii> St;
void dfs1(int u,int x,int y,int z,int st){
  if(u==P){
    pii s={y-x,z-y};
    if(!St.count(s)) St[s]={x,st};
    else smax(St[s],{x,st});
    return;
  }
  auto[p,q,s]=a[u++];
  dfs1(u,x,y+q,z+s,st);
  dfs1(u,x+p,y,z+s,st+pw[u]);
  dfs1(u,x+p,y+q,z,st+2*pw[u]);
}
int ans,ast;
void dfs2(int u,int x,int y,int z,int st){
  if(u==n){
    pii s={x-y,y-z};
    if(!St.count(s)) return;
    auto[X,ST]=St[s];
    //int Y=y+x-y+X,Z=z+y-z+(x-y+X);
    //这说明了 加后的 X,Y,Z 都是同一个数字
    if(X+x>ans) ans=X+x,ast=st+ST;
    return;
  }
  auto[p,q,s]=a[u++];
  dfs2(u,x,y+q,z+s,st);
  dfs2(u,x+p,y,z+s,st+pw[u]);
  dfs2(u,x+p,y+q,z,st+2*pw[u]);
}
void print(){
  if(ans==0) {
    puts("Impossible");
    return;
  }
  for(int i=0;i<n;++i,ast/=3){
    int st=ast%3;
    if(st==0) puts("MW");
    else if(st==1) puts("LW");
    else puts("LM");
  }
}
main(){
  cin>>n;
  for(int i=0;i<n;++i){
    auto&[u,v,w]=a[i];
    cin>>u>>v>>w;
  }
  P=n/2;
  dfs1(0,0,0,0,0);
  dfs2(P,0,0,0,0);
  print();
}

2024/8/12 00:44
加载中...