题目 And Matching
题目链接 And Matching
题目大意:
给你一个集合包含0,1,2,, n-1共n(2的整数次幂)个整数,在给你一个数字k(0<=k<=n-1),问能否将这个集合分成n/2组,每组两个整数a和b,并且每组按位与的和等于k?
思路:位运算+构造
这题我刚看到的时候没有上面特别清晰的思路,然后就去推样例,这里给了四个样例
4 0
:0 3
,1 2
4 1
:1 3
,0 2
4 2
:2 3
,0 1
从这几个样例中我们可以找到一个规律
- k == 0 :我们可以让每一个
x(0<=x<n/2)
和n-1-x
(x的补码)配对,这样总和一定是0- 0 < k < n-1 :只需要
k
与n-1
配对,0与k的补码
配对,剩下的还是原来k==0时的配对k == n - 1:n == 4 时,没有解决方案,n >= 8 时,有很多解决方案:
- `n-1`与`n-2`配对,结果是`n-1` - `1`与`n-3`配对,结果是`1` - `0`与`2`配对,结果是`0` - 剩下的和k==0时的配对一样
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
const int N = 1e5 + 10;
int match[N];
bool st[N];
void solve()
{
int n, k;
int cnt = 0;
memset(st, 0, sizeof st);
memset(match, -1, sizeof match);
cin >> n >> k;
if (k == n - 1 && n == 4)
{
puts("-1");
return;
}
if (k == 0)
{
for (int i = 0; i < n / 2; i++)
{
cout << i << " " << n - i - 1 << '\n';
}
return;
}
else if (k < n - 1)
{
match[0] = n - k - 1;
match[n - k - 1] = 0;
match[k] = n - 1;
match[n - 1] = k;
}
else
{
match[n - 1] = n - 2;
match[n - 2] = n - 1;
match[n - 3] = 1;
match[1] = n - 3;
match[0] = 2;
match[2] = 0;
}
for (int i = 0; i < n / 2; i++)
{
if (match[i] != -1)
continue;
match[i] = n - i - 1;
match[n - i - 1] = i;
}
for (int i = 0; i < n; i++)
{
if (st[i])
continue;
st[i] = st[match[i]] = true;
cout << i << " " << match[i] << '\n';
}
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}