每天一道 CodeForces 构造/思维题 (day4)

简介: 每天一道 CodeForces 构造/思维题 (day4)

题目 And Matching

题目链接 And Matching

题目大意:

在这里插入图片描述

给你一个集合包含0,1,2,, n-1共n(2的整数次幂)个整数,在给你一个数字k(0<=k<=n-1),问能否将这个集合分成n/2组,每组两个整数a和b,并且每组按位与的和等于k?

思路:位运算+构造

这题我刚看到的时候没有上面特别清晰的思路,然后就去推样例,这里给了四个样例

  • 4 00 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 :只需要kn-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;
}
相关文章
剑指offer_发散思维---求1+2+3+...+n
剑指offer_发散思维---求1+2+3+...+n
53 0
PTA-基础编程题目集(函数题)
PTA-基础编程题目集(函数题)
167 0
(思维)(必要做题步骤)(皮卡丘与 Codeforces )D - 先来签个到
(思维)(必要做题步骤)(皮卡丘与 Codeforces )D - 先来签个到
102 0
|
人工智能
每天两道 CodeForces 构造/思维题 (day5)
每天两道 CodeForces 构造/思维题 (day5)
每天两道 CodeForces 构造/思维题 (day5)
codeforces1013——D. Chemical table(思维+转化+并查集)
codeforces1013——D. Chemical table(思维+转化+并查集)
84 0
codeforces 1393 —— B. Applejack and Storages (思维)
codeforces 1393 —— B. Applejack and Storages (思维)
87 0
|
人工智能 算法
每天一道 CodeForces 构造/思维题 (day1)
每天一道 CodeForces 构造/思维题 (day1)
每天一道 CodeForces 构造/思维题 (day2)
每天一道 CodeForces 构造/思维题 (day2)