14192: 【原4192】异或问题

题目

题目描述

author: Sakiko 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4192

Description

\(N\)个数字，要求选择 \(M\)次 ，每次从 \(N\) 个数中选出两个数 \((Ai,Aj)\) (但不能和之前某次选择相同), 此次选择的得分为 \(A_i \ xor \ A_j\) 。
求最大得分。

Input Format

第一行包含 两个整数 \(N, M\)
接下来一行共 \(N\) 个整数描述 \(N\) 个数字。

OutPut Format

输出一个整数，表示最大得分除以 \(10^9+7\) 的余数

Sample Input

3 2
1 2 3

Sample Output

5

Data Range

对于 20% 的测试数据, \(N≤1000\)
对于 40% 的测试数据, \(N*M≤500000\)
对于 70% 的测试数据, \(N≤10000\)
对于 100% 的测试数据, \(N≤50000, 0≤A_i≤10^9\)

ligongzzz's solution

#include "iostream"
#include "list"
#include "numeric"
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int *nums = new int[n];
    for (int i = 0; i < n; i++)
        nums[i] = i;

    //存储最大数据
    list<int> List;
    List.push_back(0);
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = nums[i] ^ nums[j];
            //插入
            auto p = List.rbegin();
            /*for (; p != List.rend(); p++) {
                if (*p > temp)
                    break;
            }
            if (p != List.rbegin()) {
                List.insert(p.base(), temp);
                if(List.size()>m)
                    List.pop_back();
            }*/
        }
    }

    cout << accumulate(List.begin(), List.end(), 0)%int(1e9+7);

    return 0;
}