2013-05-12 20:02:58| 人氣1,574| 回應0 | 上一篇 | 下一篇

[UVA][SlidingWindow] 11536 - Smallest Sub-Array

Input

First line of input is an integer T(T<100) that represents the number of test cases. Each case consists of a line containing 3 integers N(2 < N < 1000001), M(0 < M < 1001) and K(1< K < 101). The meaning of these variables is mentioned above.

Output

For each case, output the case number followed by the minimum length of the subsequence. If there is no valid subsequence, output “sequence nai” instead. Look at the sample for exact format.

Sample Input Output for Sample Input

20 12 4

20 12 8

Case 1: 13

Case 2: sequence nai

Problemsetter: Sohel Hafiz

Special Thanks: Md. Arifuzzaman Arif

#include <stdio.h>
int X[1000005] = {0,1,2,3};
int main() {
    int T, cases = 0;
    int N, M, K, i;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d", &N, &M, &K);
        int modM[3005] = {};
        for(i = 0; i < 3005; i++)
            modM[i] = i%M;
        for(i = 4; i <= N; i++) {
            X[i] = X[i-1] + X[i-2] + X[i-3];
            if(X[i] >= M)   X[i] = modM[X[i]];
            X[i] ++;
        }
        int used[105] = {}, d = 0;
        int tail = 1, mndist = 0xfffffff;
        for(i = 1; i <= N; i++) {
            while(tail <= N && d < K) {
                if(X[tail] <= K && used[X[tail]] == 0)
                    d++;
                if(X[tail] <= K)
                    used[X[tail]]++;
                tail++;
            }
            if(tail > N && d < K)
                break;
            if(mndist > tail-i && d == K)
                mndist = tail-i;
            if(X[i] <= K && used[X[i]] == 1)
                d--;
            if(X[i] <= K)
                used[X[i]]--;
        }
        printf("Case %d: ", ++cases);
        if(mndist != 0xfffffff)
            printf("%d\n", mndist);
        else
            puts("sequence nai");
    }
    return 0;
}

為了加速其運算，全部指針化。

#include <stdio.h>
int X[1000005] = {0,1};
int Y[1000005] = {0,1};
int main() {
    int T, cases = 0;
    int N, M, K, i;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d", &N, &M, &K);
        int modM[3005] = {};
        for(i = 0; i < 3005; i++)
            modM[i] = i%M;
        int xi1 = 3, xi2 = 2, xi3 = 1, xi;
        int idx = 2;
        int *p = &X[1], *q = &Y[1], *pp = &X[1], *qq = &Y[1];
        if(2 <= K) *(++p) = 2, *(++q) = 2;
        if(3 <= K) *(++p) = 3, *(++q) = 3;
        for(i = 4; i <= N; i++) {
            xi = xi1 + xi2 + xi3;
            if(xi >= M)   xi = modM[xi];
            xi++;
            if(xi <= K)
                *(++p) = xi, *(++q) = i;
            xi3 = xi2, xi2 = xi1, xi1 = xi;
        }
        *(++q) = N+1;
        int *end = p+1;
        int used[105] = {}, d = 0;
        int mndist = 0xfffffff;
        p = &X[1], q = &Y[1], pp = &X[1], qq = &Y[1];
        for(; pp != end;) {
            while(p != end && d < K) {
                if(used[*p] == 0)
                    d++;
                used[*p]++;
                p++, q++;
            }
            if(p == end && d < K)
                break;
            if(mndist > (*(q-1))-(*qq) && d == K)
                mndist = (*(q-1))-(*qq);
            if(used[*pp] == 1)
                d--;
            used[*pp]--, pp++, qq++;
        }
        printf("Case %d: ", ++cases);
        if(mndist != 0xfffffff)
            printf("%d\n", mndist+1);
        else
            puts("sequence nai");
    }
    return 0;
}

我要檢舉

#11536#Smallest Sub-Array#Sliding Window

台長： Morris

您可能對以下文章有興趣

[UVA] 12366 - King's Poker

[UVA][BFS] 336 - A Node Too Far

[UVA][dp] 12001 - UVa Panel Discussion

[UVA][模擬] 337 - Interpreting Control Sequences

人氣(1,574) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][循環節] 12620 - Fibonacci Sum
此分類上一篇:[UVA][ad-hoc] 11319 - Stupid Sequence

回應(0)