給定一個長度為 $N$ 的環狀序列,每個元素都是非負整數。請將這個序列切成 $K$ 個連續段,使得每段的各個元素的 power AND
起來最大。一段的 power 是該段中所有元素的 OR
。
以下的程式是對於這個題目的一個假解。請寫一個程式,使得輸出的內容滿足 Input Format,且會讓以下程式碼獲得 Wrong Answer。你的程式不應該從標準輸入流中讀取任何東西。
#include <bits/stdc++.h> using namespace std; const int magic = 5; const int maxn = 1e6 + 5; int a[maxn], n, k; bool check(int x) { int p = 0; for (int t = 0; t < magic; ++t) { int c = 0, s = 0, last = -1, i = p; for (int j = 0; j < n; ++j) { c |= a[i]; if ((c & x) == x) { ++s; last = i + 1; c = 0; if (last >= n) last = 0; } if ((++i) >= n) i = 0; } if (s >= k) return true; p = last; } return false; } int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); int ans = 0; for (int b = 30; b >= 0; --b) { int x = ans + (1 << b); if (check(x)) ans = x; } printf("%d\n", ans); return 0; }
第一行有兩個整數 $N$ 及 $K$。
第二行有 $N$ 個整數 $A_1, A_2, A_3, \cdots, A_N$,依序代表環上的元素。
輸出一個數字,代表 $K$ 段的 power AND
起來的最大值。
No. | Testdata Range | Score |
---|