【第006题】题解及代码分享：高位前缀和之AtCoder ARC100

大家好！我是小码匠。

今天分享的题目是ARC100的E题，是一道高维前缀和的题目。

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

离自己的既定目标：

目标：300道
已完成：6道
待完成：294道

已完成目标：

分类	算法	题目
算法基础	前缀和	【第001题】题解分享：湖南省选->激光炸弹
算法基础	差分	【第002题】题解分享：P4552 [Poetize6] IncDec Sequence
算法基础	高维前缀和	【第003题】题解及代码分享：CodeForces 165E Compatible Numbers
算法基础	尺取	【第004题】题解及代码分享：AtCoder ABC326-C
动态规划	动态规划	【第005题】题解及代码分享：AtCoder ABC326-D
算法基础	高维前缀和	【第006题】题解及代码分享：高位前缀和之AtCoder ARC100 - E Or Plus Max

题目描述

给你一个长度为的序列 a，每个，找出最大的a_i a_j（i or j ≤K，0≤i<j<2^n）

输入输出样例

输入 #1复制

代码语言：javascript复制

2
1 2 3 1

输出 #1复制

代码语言：javascript复制

3
4
5

输入 #2复制

代码语言：javascript复制

3
10 71 84 33 6 47 23 25

输出 #2复制

代码语言：javascript复制

输入 #3复制

代码语言：javascript复制

4
75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

输出 #3复制

代码语言：javascript复制

正解

复盘

本周在准备期中考试，题解就略过了，只分享代码。

AC代码

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;

struct node{
    int fn;
    int sn;
} a[1 << 19];

void best_coder() {
    int n;
    cin >> n;
    int m = 1 << n;
    for (int i = 0; i < m;   i) {
        cin >> a[i].fn;
    }

    for (int i = 0; i < n;   i) {
        for (int j = 0; j < m;   j) {
            if (j & 1 << i) {
                int k = j ^ (1 << i);
                if (a[k].fn > a[j].fn) {
                    a[j].sn = max(a[j].fn, a[k].sn);
                    a[j].fn = a[k].fn;
                } else {
                    a[j].sn = max(a[j].sn, a[k].fn);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i < m;   i) {
        ans = max(ans, a[i].fn   a[i].sn);
        cout << ans << 'n';
    }
}

void happy_coder() {

}

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

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}


/**
输入数据

2
1 2 3 1

*/

/**
输出数据

3
4
5

*/

END

max 动态规划基础数据算法

0 人点赞

【第006题】题解及代码分享：高位前缀和之AtCoder ARC100 - E Or Plus Max

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

题目描述

输入输出样例

正解

复盘

AC代码