给出一个正整数序列,求一个子区间使得这个区间内的数或起来尽可能的大。
或运算指数字按二进制位进行以下运算:
运算规则:
一个序列的子区间指这个序列中连续的一段数字。
牛牛并不关心这个最大值是多少,他只关心所有满足条件的子区间里,最短的子区间长度是多少。
第一行一个正整数,代表这个序列的长度。
接下来一行空格分隔的正整数,用来描述这个序列。
仅一行一个正整数代表答案。
3 1 2 3
1
最大值是,满足条件的子区间为,
所以最短的长度为。
#include <bits/stdc++.h> using namespace std; int nBits = 32; int maxOr = 0; bool passCheck(const vector<int> &bitMap) { for (int b = 0; b < nBits; ++b) { if ((maxOr & (1 << b)) && bitMap[b] <= 0) { // cout << "check bit: " << b << " failed " << endl; return false; } } return true; } vector<int> changeBitOfBound(vector<int> &bitMap, const int val, int c) { for (int b = 0; b < nBits; ++b) { if ((val & (1 << b))) { // cout << "add bit: " << b << endl; bitMap[b] += c; } } return bitMap; } bool passCheckDelta(vector<int> bitMap, int val, int c) { changeBitOfBound(bitMap, val, c); return passCheck(bitMap); } int solve(vector<int> &arr) { maxOr = 0; int len = arr.size(); for (auto &x:arr) { maxOr |= x; } int l = 0, r = 0; int ans = 0x3ffffff; vector<int> Bitmp(nBits, 0); while (r < len) { changeBitOfBound(Bitmp, arr[r], 1); ++r; if(passCheck(Bitmp)) while (l < r && passCheckDelta(Bitmp, arr[l], -1)) { changeBitOfBound(Bitmp, arr[l], -1); ++l; } if (passCheck(Bitmp)) { ans = min(ans, r - l); } } return ans; } int main() { int n; ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; using iiter = istream_iterator<int>; vector<int> a(n); copy_n(iiter(cin), n, begin(a)); cout << solve(a) << endl; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = sc.nextInt(); } sc.close(); // int[] nums = {1,2,3}; System.out.println(minDistance(nums)); } public static int minDistance(int[] nums) { int[] bits = new int[32]; // boolean[] onePosition = new boolean[32]; int n = nums.length; int cur = 0; for (int i = 0; i < n; i++) { cur |= nums[i]; } int cntBits = 0; int tmp = cur; while (tmp > 0) { cntBits += (tmp & 1); tmp >>>= 1; } int min = n; //全部相或肯定是最大值 //滑动窗口:i起始点,j:i作为起始点,能够满足cntBits=0的点 int i = 0, j = 0; while (j < n) { while (j < n && cntBits > 0) { cntBits = calcBit(bits, nums[j], true, cntBits); j++; } if (cntBits > 0) { break; } while (i < j) { if (!canSub(bits, nums[i])) { min = Math.min(min, j - i); break; } cntBits = calcBit(bits, nums[i], false, cntBits); i++; } cntBits = calcBit(bits, nums[i], false, cntBits); i++; } return min; } public static int calcBit(int[] bits, int num, boolean add, int cntBits) { int t = 0; while (num > 0) { if ((num & 1) != 0) { if (add) { if (bits[t] == 0) { cntBits--; } bits[t]++; } else { bits[t]--; if (bits[t] == 0) { cntBits++; } } } t++; num >>>= 1; } return cntBits; } public static boolean canSub(int[] bits, int cur) { int i = 0; while (cur > 0) { if ((cur & 1) != 0 && bits[i] == 1) { return false; } i++; cur >>>= 1; } return true; } }
// 提交时间:2021-10-18 语言:C++ 运行时间: 685 ms 占用内存:4392K #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10, M = 32; int w[N]; inline vector<int> change(vector<int> cnt, int num, int c) { for (int i = 0; i < M; i ++ ) if (num >> i & 1) cnt[i] += c; return cnt; } inline bool check(const vector<int>& cnt, int all) { for (int i = 0; i < M; i ++ ) if ((all >> i & 1) and cnt[i] == 0) return false; return true; } void solve(){ int n; cin >> n; int all = 0; for (int i = 1; i <= n; i ++ ) cin >> w[i], all |= w[i]; int ans = INT_MAX; vector<int> cnt(M, 0); for (int i = 1, j = 1; i <= n; i ++ ) { cnt = move(change(cnt, w[i], 1)); while (j < i and check(cnt, all) and check(change(cnt, w[j], -1), all)) cnt = change(cnt, w[j], -1), j ++ ; if (check(cnt, all)) ans = min(ans, i - j + 1); } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; // cin >> t; t = 1; while (t -- ) solve(); return 0; }
import java.util.Scanner; public class Main { public static int getVal(int[] dp) { int res = 0; for (int i = 0; i < 32; i++) { if (dp[i] != 0) { res |= 1 << i; } } return res; } public static void add(int[] dp, int val){ for (int i = 0; i < 32; i++) { if ((val & (1 << i)) != 0 ) { dp[i] += 1; } } } public static void sub(int[] dp, int val) { for (int i = 0; i < 32; i++) { if ((val & (1 << i)) != 0 ) { dp[i] -= 1; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.nextLine(); String[] text = sc.nextLine().split(" "); int[] arr = new int[text.length]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.parseInt(text[i]); } int target = 0; for (int i : arr) { target |= i; } int[] dp = new int[32]; int left = 0; int ans = arr.length; for (int right = 0; right < arr.length; right++) { add(dp, arr[right]); while (getVal(dp) == target) { ans = Math.min(ans, right - left + 1); sub(dp, arr[left]); left ++; } } System.out.println(ans); } }滑动窗口,用32长度的数组记录状态,最大值是数组所有元素参与或运算的结果,窗口两端用left, right表示,枚举right, 如果该子段符合最大值,记录结果并且left增加。此方法用Python只能提供50%的用例。
# 提交时间:2021-08-03 语言:Pypy3 运行时间: 1818 ms 占用内存:364136K 状态:答案正确 n = int(input()) arr = list(map(int, input().split())) target = 0 targetArr = [0] * 32 for i in range(n): target = target | arr[i] for j in range(32): targetArr[j] = (target >> j) & 1 for i in range(n): temp = [0] * 32 for j in range(32): temp[j] = (arr[i] >> j) & 1 arr[i] = temp def addArr(cur, x): for i in range(32): cur[i] += x[i] def minusArr(cur, x): for i in range(32): cur[i] -= x[i] def checkArr(cur, target): for i in range(32): if cur[i] == 0 and target[i] > 0: return False if cur[i] > 0 and target[i] == 0: return False return True curArr = [0] * 32 j = 0 bestLen = n for i in range(n): addArr(curArr, arr[i]) while j <= i and checkArr(curArr, targetArr): bestLen = min(bestLen, i - j + 1) minusArr(curArr, arr[j]) j += 1 print(bestLen)