2022百度之星程序设计大赛 - 复赛 1001 子序列

56 阅读 0 评论 37 点赞

我是靠谱客的博主风中雨，最近开发中收集的这篇文章主要介绍2022百度之星程序设计大赛 - 复赛 1001 子序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

problem

在这里插入图片描述
度度熊有一个大小为 nn 的整数数组 a_1,a_2,cdots,a_na
1

,a
2

,⋯,a
n

。

数组 a_1,a_2,cdots,a_na
1

,a
2

,⋯,a
n

的一个子序列 a_{b_1},a_{b_2},cdots,a_{b_k}a
b
1

,a
b
2

,⋯,a
b
k

是非空的递增子序列当且仅当 kgeq 1k≥1，且对于任意的 i in [1,k-1]i∈[1,k−1]，有 b_i<b_{i+1},a_{b_i}<a_{b_{i+1}}b
i

<b
i+1

,a
b
i

<a
b
i+1

。

她需要将这个数组分成若干个非空的递增子序列，满足每个位置都在这些子序列中出现恰好一次。

定义一个序列 c_1,c_2,cdots ,c_mc
1

,c
2

,⋯,c
m

的价值为 c_1oplus c_2oplus cdots oplus c_mc
1

⊕c
2

⊕⋯⊕c
m

，即所有数按位异或后的结果。对于一个数组 aa 的子序列划分方案，其价值定义为所有子序列价值的代数和。

度度熊想知道所有符合上述要求的划分方案中，划分方案的最大价值。

格式
输入格式：
第一行一个整数 n(1le n le 10^5)n(1≤n≤10
5
)，表示数组的长度。
第二行 nn 个整数，为 a_1,a_2,cdots,a_n(0le a_ile 10^9)a
1

,a
2

,⋯,a
n

(0≤a
i

≤10
9
)，表示这个数组。

输出格式：
一行一个整数，表示所有符合要求的划分方案的最大值。

样例 1
输入：
2 1 2
输出：
3
说明：

solution

发现结论，直接全部加起来输出即可。

记得开longlong，不然会WA

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    int n;  cin>>n;
    LL sum = 0;
    for(int i = 1; i <= n; i++){
        LL x;  cin>>x;
        sum += x;
    }
    cout<<sum<<"n";
    return 0;
}