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

小码匠

发布于 2023-10-31 18:46:19

3510

发布于 2023-10-31 18:46:19

文章被收录于专栏：小码匠和老码农

大家好！我是小码匠。

今天分享的题目是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复制

2
90 36

输出 #1复制

36 90

输入 #2复制

4
3 6 3 6

输出 #2复制

-1 -1 -1 -1

输入 #3复制

5
10 6 9 8 2

输出 #3复制

-1 8 2 2 8

正解

复盘

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

TLE

过去11个测试点

#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代码

// 题目: 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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-10-30，如有侵权请联系 cloudcommunity@tencent.com 删除

int