給定一個長度為 $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 |
---|
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 262144 | 262144 |