P16995 【MX-S15-T1】「DLESS-5」Another OR Problem

好题！

看到这个按位或求 $\max$ 很难不想到按位枚举，但是这个 $\sum{b} = k$ 的限制很烦人，可以考虑能不能知道当 $a$ 固定时，随着 $k$ 的增大，答案的大小变化。

设 $f_k(a)$ 表示

$$\max_{\sum{b} = k}\{ \lor_{i = 1}^{n} (a_i + b_i)\} $$

考虑 $f_k(a)$ 与 $f_{k+1}(a)$ 的大小关系。

设 $c_{i}$ 为 $a_i + b_i$，其中 $\sum b = k$，$\lor_{i = 1}^{n}c_i = f_k(a)$。

考虑分讨：

1. 当二进制下的每一个 $c_i$ 的末尾都为 $1$ 时，可以选择末尾连续 $1$ 的数量最小的 $c_i$ 加一，这样，$f_{k+1}(a) \ge f_{k}(a)$。
2. 当存在二进制下的 $c_i$ 末尾为 $0$，可以直接对这个 $c_i$ 加一，这时，$f_{k+1}(a) \ge f_{k}(a)$。

综上，$f_{k+1}(a) \ge f_{k}(a)$，即数列 $\{f_{k}(a) \}$ 单调不降。

然后就按位枚举，考虑怎么写 $\operatorname{check}(x)$。

如果已经存在 $c_i$ 的第 $x$ 位为 $1$，显然满足条件。

否则如果让 $c_i$ 的第 $x$ 位为 $1$，就需要加上 $2^x - (c_i \bmod 2^x)$，然后选的肯定是这个值最小的，然后判一下就做完了。

这样就能获得 $40$ 分的高分！

考虑正解。

当进行完操作后 $k$ 不为 $0$ 时，说明还有若干位需要被填，假设 $k$ 在二进制下的第 $j$ 位为 $1$，考虑这一个 $2^j$ 加在哪一个 $b_i$ 上。若有一个 $a_i$ 满足在二进制下的第 $i$ 位为 $0$，那么显然可以加在这个 $b_i$ 上，否则选择从第 $j$ 位到最高位连续 $1$ 的个数最小的那一个 $i$ 加上，这是因为 $f_k(a)$ 是单调不降的。

#include<bits/stdc++.h>
const int MAXN = 1e6 + 5;
#define pb push_back
typedef long long LL;

typedef std::pair<int, int> PII;

typedef std::pair<LL, int> PLI;

int n; LL k, a[MAXN], b[MAXN];

LL sum;

inline bool check(int x)
{
	for(int i = 1; i <= n; i++)
		if((a[i] >> x) & 1)
			return 1;
	
	PLI ans = {LLONG_MIN, 0};
	
	for(int i = 1; i <= n; i++)
		ans = std::max(ans, {a[i] % (1ll << x), i});
		
	LL nd = (1ll << x) - ans.first;
//	std::cout << sum << ' ' << nd << ' ' << ans.first << ' ' << (1ll << x) << '\n';
	if(sum + nd <= k)
	{
		sum += nd, a[ans.second] += nd, b[ans.second] += nd;
//		std::cout << x << '\n';
		return 1;
	}
	else return 0;
}

inline void solve()
{
	scanf("%d%lld", &n, &k);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
		
	for(int i = 1; i <= n; i++)
		b[i] = 0;
		
	LL ans = 0; sum = 0;
	
	for(int j = 60; ~j; j--)
		if(check(j))
			ans |= (1ll << j);
			
	k -= sum;
	if(k) for(int j = 60; ~j; j--)
	{
		if(!((k >> j) & 1)) continue;
		
		bool fl = 0;
		
		for(int i = 1; i <= n && !fl; i++)
			if(!((a[i] >> j) & 1))
				a[i] += (1ll << j), b[i] += (1ll << j), fl = 1;
				
		if(fl) continue;
				
		PII ans = {INT_MAX, 0};
		
		for(int i = 1; i <= n; i++)
		{
			LL x = (a[i] >> j);
			
			int cnt = 0;
			while(x)
			{
				if(!(x & 1))
					break;
					
				x >>= 1, cnt++;
			}
			
			ans = std::min(ans, {cnt, i});
		}
		
		a[ans.second] += (1ll << j), b[ans.second] += (1ll << j);
	} 
			
	printf("%lld\n", ans);
	
	for(int i = 1; i <= n; i++)
		printf("%lld%c", b[i], (i == n ? '\n' : ' '));
}

int main()
{
	int c, T;
	scanf("%d%d", &c, &T);
	
	while(T--)
		solve();
		
	return 0;
}