方法太厉害了....看了官方题解的做法....然后...想了很久很久才知道他想表达什么....
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } int T,n; LL a[100010],f[25][25],ans1,ans2; int d[25]; void dfs(int s,LL b, LL sum) { if(s==-1) { if(sum<ans1) ans1=sum,ans2=b; else if(sum==ans1) ans2=min(ans2,b); return; } for(d[s]=0;d[s]<=1;d[s]++) { LL t=sum; t=t+f[s][s]; for(int j=19;j>s;j--) { if((d[j]+d[s])%2==0) t=t+f[j][s]; else t=t-f[j][s]; } dfs(s-1,b|(d[s]*(1<<s)),t); } } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); memset(f,0,sizeof f); ans1=0, ans2=0; for(int i=2;i<=n;i++) { ans1=ans1+abs(a[i]-a[i-1]); if(a[i]==a[i-1]) continue; int h=-1; for(int j=19;j>=0;j--) { int x1=0,x2=0; if(a[i]&(1<<j)) x1=1; if(a[i-1]&(1<<j)) x2=1; if(x1==x2) continue; h=j; break; } int x=max(a[i],a[i-1]),y=min(a[i],a[i-1]); for(int j=h;j>=0;j--) { int x1=0,x2=0; if(x&(1<<j)) x1=1; if(y&(1<<j)) x2=1; f[h][j]=f[h][j]+(x1-x2)*(1<<j); } } dfs(19,0,0); printf("%lld %lld ",ans2,ans1); } return 0; }