解题思路

• 核心观察：一次操作在区间内两两对称配对，使每对元素同时变为二者的按位或（OR），元素值只增不减（按位或的单调性与幂等性）。

• 关键结论：通过对相邻长度为2的区间多次操作（如连续对 [1,2]，[2,3]，…，[n-1,n] 以及必要的回扫），任意位置的比特都能沿相邻对传播到整个数组。最终可以把所有元素都提升到全数组按位或

  $$V=\bigvee_{i=1}^{n} a_i$$

  的值。

  • 例：[a,b,c] 先做 [1,2] 得 [a|b,a|b,c]，再做 [2,3] 得 [a|b,(a|b)|c,(a|b)|c]，再做 [1,2] 得 [(a|b)|((a|b)|c),…]=[a|b|c, a|b|c, a|b|c]。

• 上界性：数组任一元素不可能超过全体按位或 V，故“最小元素的最大可能值”至多为 V。

• 可达性：由上面的传播过程可将所有元素都变为 V，因此最小值恰可达到 V。

• 结论：答案就是整数组的按位或。

实现方法：对每组数据，线性扫描按位或所有元素并输出。

复杂度分析

• 时间复杂度：对每组数据 O(n)（一次线性 OR）。
• 空间复杂度：O(1)（常数额外空间）。

代码实现

Python

# 题意：多次对任意区间做对称按位或，最大化数组最小值
# 结论：答案为整数组按位或

import sys

def solve_case(arr):
    # 计算整数组按位或
    v = 0
    for x in arr:
        v |= x
    return v

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    out_lines = []
    for _ in range(t):
        n = int(data[idx]); idx += 1
        # 读取 n 个整数
        a = list(map(int, data[idx:idx+n])); idx += n
        out_lines.append(str(solve_case(a)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 题意：多次对任意区间做对称按位或，最大化数组最小值
// 结论：答案为整数组按位或

import java.io.*;
import java.util.*;

public class Main {

    // 简单快速读入（根据数据量选用，避免 Scanner 过慢）
    static class FastReader {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastReader(InputStream is) { in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    // 计算整数组按位或
    static int solveCase(int[] a) {
        int v = 0;
        for (int x : a) v |= x;
        return v;
    }

    public static void main(String[] args) throws Exception {
        FastReader fr = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int t = fr.nextInt();
        while (t-- > 0) {
            int n = fr.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = fr.nextInt();
            sb.append(solveCase(a)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 题意：多次对任意区间做对称按位或，最大化数组最小值
// 结论：答案为整数组按位或

#include <bits/stdc++.h>
using namespace std;

// 计算整数组按位或
long long solveCase(const vector<long long>& a) {
    long long v = 0;
    for (auto x : a) v |= x;
    return v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; 
    if (!(cin >> t)) return 0;
    while (t--) {
        int n; cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << solveCase(a) << "\n";
    }
    return 0;
}

题目内容

给定一个长度为$n$ 的非负整数数组$(a_1,a_2,…,a_n)(a_1, a_2, \dots, a_n)$。 你可以进行任意次（可以为零次）如下操作：

• 选择一个区间$[l,r](1≤l≤r≤n )$；
• 对区间内的每一个下标 $i$，同时将区间内第$i$个元素替换为它相邻的或更改后的值。 即，首尾、次首、次尾……的元素替换。更具体地，对区间$[l,r][l, r]$内所有满足 $0≤k≤[(r−l)/2]$ 的整数 $k$，将$a_{l+k}$ 和 $a_{r-k}$ 的值同时更新为它们的原值按位 按位或 (OR) 的结果（即$a_{l+k }\ or\ a_{r-k})$。

你的目标是最大化数组的最小元素，即最大化

$min_{1 \le i \le n}\ a_i$

请输出能达到的最大可能值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$t (1 ≦t≦10^5)$表示测试用例组数，每组测试数据描述如下:

第一行输入一个整数$n(1≦n ≦2×10^5)$，表示数组的长度。

第二行输入$n$个整数$a_1,a_2,...,a_n(0 ≦a_i≦10^9)$，表示数组中的元素。

除此之外，保证单个测试文件的$n$之和不超过$2×10^5$

输出描述

对于每组测试数据，新起一行输出一个整数，表示通过若干次操作后，数组最小元素的最大可能值。

样例1

输入

2
3
1 2 3
5 
6 6 6 6 6

输出

3
6

说明

• 数组为{$1,2,3$}，选择区间$[1,2]$数组变为{$3, 3,3$}此时数组最小值最大。