2016-10-07

HDU 5798 Stabilization【异或运算巧妙处理】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5798

题意：

给定$n$个元素，找到最小的非负数$x$，使得序列元素与该数异或后，$\sum_{i=1}^{N-1}(|A[i+1]-A[i]|)$最小。
数据范围：$ 0 \le A[i] \lt 2^{20}, 1 \le n \le 10^5$

分析：

对于异或运算，我们要按位考虑每一位的贡献，那么如何考虑，考虑谁的贡献呢？
分析一下性质，假设有$a_i \lt a_{i+1}$，考虑两个数的二进制表示，假设$a_i与a_{i+1}$最高的不同位为$p_1$，次高的不同位为$p_2$且$a_i$在该位为$1$，显然最初这两位对答案的贡献为$2^{p_1}+2^{p_2}$。
异或$x$后，仅考虑该两位，若$x$在第$p_1$位和第$p_2$位均为$1$或者$0$，异或后相当于两个数正好相反或者不变，那么对答案的贡献依然为$2^{p_1}+2^{p_2}$，而若$x$在第$p_1$位和第$p_2$位不同，那么此时$p_2$位不再和$p_1$位同号，即对答案的贡献为$2^{p_1}-2^{p_2}$。
可以看出无论怎样最高位都会有$2^{p_1}$的贡献，而后面的位的贡献取决于$x$的最高位与当前位是否相等，若相等则有正的贡献，否则为负的贡献。所以我们先处理出异或前每对数每一位的贡献，全部都转化为按位考虑，然后$2^{20}$枚举$x$求出答案，采用$dfs+剪枝\ 1400ms$过~
参考在这里
就是找到与位相关的性质，然后转化为按位考虑，考虑每一位会对答案产生怎样的贡献。

代码：

/*************************************************************************
    > File Name: 5798.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/7 13:14:30
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, maxm = 20 + 5;
int a[maxn];
ll mat[maxm][maxm];
int top;
ll ans;
int res;
void dfs(int deep, ll x, int now)
{
	if(deep == top + 1){
		if(x < ans) ans = x, res = now;
		else if(x == ans) res = min(now, res);
		return;
	}
	if(x > ans) return;
	for(int i = 0; i <= 1; ++i){
		ll tmp = x + mat[deep][deep];
		for(int j = 0; j < deep; ++j){
			if(((now >> j) & 1) == i) tmp += mat[deep][j];
			else tmp -= mat[deep][j];
		}
		dfs(deep + 1, tmp, now + (i << deep));
	}
}
int main (void)
{
	int T;scanf("%d", &T);
	while(T--){
		int n;scanf("%d", &n);
		for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
		memset(mat, 0, sizeof(mat));
		int x, y;
		ans = 0;
		top = 0;
		res = 0;
		for(int i = 0; i < n - 1; ++i){
			x = a[i], y = a[i + 1];
			if(x > y) swap(x, y);
			ans += y - x;
			int deep = 19;
			while(deep && !((y ^ x) >> deep & 1)) deep--;
			for(int j = 0; j <= deep; ++j) mat[deep][j] += (y >> j & 1) - (x >> j & 1) ;
			top = max(top, deep);
		}
		for(int i = 0; i <= top; ++i){
			for(int j = 0; j <= i; ++j){
				mat[i][j] <<= j;
			}
		}
		dfs(0, 0, 0);
		printf("%d %lld\n", res, ans);
	}
	return 0;
}