题解：P12420 【MX-X12-T3】「ALFR Round 5」变换

前言

很有趣的一道题，但是样例有点水（TAT）。

正篇

首先题面是要求

x~\&~m = x

，那么也就是在二进制下

x

为

1

的位置，在

m

的对应位置也必须是

1

。那么考虑枚举

m

的二进制的

1

的位置，对于每一位计算可以产生的贡献并计算答案。首先，知周所众，异或这个运算相同为

0

不同为

1

。那么肯定要么在某一位进行一次操作，要么不进行操作（因为偶数次操作就等于不做操作，奇数次操作等于做一次操作）。那么如果现在这一位异或起来为

0

那么就需要做一次操作，来使其变为

1

来增加答案，如果已经是

1

了就不需要做操作了，根据这个结论就可以写出满分代码了。

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll t;
ll n, m, k;
ll a[1000006];
void work()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	ll x = 0;
	for(int i = 0; i < 31; i++)
	{
		if((m & (1 << i)) == 0)
			continue;
		ll cnt = 0;
		for(int j = 1; j <= n; j++)
			cnt += ((a[j] & (1 << i)) > 0);
		if(cnt % 2 == 0)
    		for(int j = 1; j <= n; j++)
                if((a[j] & (1 << i)) == 0)
                {
                    a[j] |= (1 << i);
                    break;
                }
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++)
	    ans ^= a[i];
	cout << ans << "\n";
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);     cout.tie(0);
	ll t;
	cin >> t;
	while(t--)
		work();
	return 0;
}

题解：P12420 【MX-X12-T3】「ALFR Round 5」变换

文章操作

前言

正篇

相关推荐

评论

题解：P12420 【MX-X12-T3】「ALFR Round 5」变换