每天一道 CodeForces 构造/思维题 （day4）_codeforce 简单构造题

题目 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73