【第003题】题解及代码分享：CodeForces 165E Compatible Numbers，一通瞎打，TLE了

大家好！我是小码匠。

今天分享的题目是CodeForces 165 E题， 是2024赛季所刷的第3题。

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

• 目标：300道
• 已完成：3道
• 待完成：297道

分类	算法	题目
算法基础	前缀和	【第001题】题解分享：湖南省选->激光炸弹
算法基础	差分	【第002题】题解分享：P4552 [Poetize6] IncDec Sequence
算法基础	高维前缀和	【第003题】题解及代码分享：CodeForces 165E Compatible Number

前置知识

• 高维前缀和

题目描述

有两个整数a,b。如果a&b=0，那么我们称a与b是相容的。比如90(1011010)与36(100100)相容。给出一个序列a ，你的任务是对于每个

a_i

，找到在序列中与之相容的

a_j

。如果找不到这样的数，输出-1。贡献者：An_Account

输入输出样例

输入 #1复制

代码语言：javascript复制

2
90 36

输出 #1复制

代码语言：javascript复制

36 90

输入 #2复制

代码语言：javascript复制

4
3 6 3 6

输出 #2复制

代码语言：javascript复制

-1 -1 -1 -1

输入 #3复制

代码语言：javascript复制

5
10 6 9 8 2

输出 #3复制

代码语言：javascript复制

-1 8 2 2 8

正解

复盘

• 学艺不精，上来快速打了一个TLE板代码，华丽丽的TLE了，11个点TLE了。
• 明明是高维前缀和，自己瞎搞，自然TLE了。

TLE

• 过去11个测试点

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;

void best_coder() {
    int n;
    cin >> n;
    vector<int> a(n   1);
    vector<int> ans(n   1, -1);
    for (int i = 0; i < n;   i) {
        cin >> a[i];
    }
    for (int i = 0; i < n;   i) {
        for(int j = 0; j < n && ans[i] == -1;   j) {
            if (i == j) {
                continue;
            }
            if ((a[i] & a[j]) == 0) {
                ans[i] = a[j];
            }
        }
        cout << ans[i] << " ";
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

AC代码

代码语言：javascript复制

// 题目: CF165E Compatible Numbers
// 链接: https://www.luogu.com.cn/problem/CF165E
// 难度: 提高 /省选−
// 题解: https://www.luogu.com.cn/problem/solution/CF165E
#include <bits/stdc  .h>

using namespace std;

int ans[1 << 22];

void best_coder() {
    int n;
    cin >> n;
    vector<int> a(n   2);
    for (int i = 0; i < n;   i) {
        cin >> a[i];
        ans[a[i]] = a[i];
    }
    for (int i = 0; i < 22;   i) {
        for (int j = 0; j < (1 << 22);   j) {
            if (j & (1 << i) && ans[j ^ (1 << i)]) {
                 ans[j] = ans[j ^ (1 << i)];
            }
        }
    }
    for (int i = 0; i < n;   i) {
        if (ans[a[i] ^ ((1 << 22) - 1)] > 0) {
            cout << ans[a[i] ^ ((1 << 22) - 1)] << " ";
        } else {
            cout << -1 << ' ';
        }
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

END

int numbers 基础 算法 效率

0 人点赞