TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

給定一個長度為 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;
}

Input Format

第一行有兩個整數 NK
第二行有 N 個整數 A1,A2,A3,,AN,依序代表環上的元素。

  • 1KN5105
  • 0Ai109

Output Format

輸出一個數字,代表 K 段的 power AND 起來的最大值。

Sample Input 1

4 2
2 3 4 1

Sample Output 1

3

Sample Input 2

6 3
2 2 2 4 4 4

Sample Output 2

4

Sample Input 3

4 1
0 1 2 3

Sample Output 3

3

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144