# 題目: UVa 11536 - Smallest Sub-Array

# 題目說明

建構出按照一定規則的數字序列
找出包含所有1 - K的最短子序列

序列的規則如下:

• x1 = 1
• x2 = 2
• x3 = 3
• xi = (xi-1 + xi-2 + xi-3) % M + 1

---

INPUT:
第一行有一個整數T，代表有幾筆資料
每筆資料有3個整數N 、 M 、 K

1. N代表數字序列的長度
2. M代表xi取M的餘數
3. K代表目標數字

---

OUTPUT:
輸出最短子序列的長度
如果不存在，則輸出sequence nai

# 解題方法

按照N的大小先建構數字序列，以G儲存
從頭開始遍歷G，計算每個符合條件(<=K)的數字數量
如果為第1次新增，則將cnt + 1，當cnt = K，則找到一個符合條件的子序列
比對是否比其他序列更短，並盡可能的縮減序列(從頭開始刪除)

# 參考程式碼

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    // fast io
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T, N, M, K, cases = 0;
    vector<int> G;
    vector<int> check;

    cin >> T;
    while (T--)
    {
        cin >> N >> M >> K;

        // init
        G.assign(N + 1, 0);
        G[1] = 1, G[2] = 2, G[3] = 3;
        for (int i = 4; i <= N; ++i) G[i] = (G[i - 1] + G[i - 2] + G[i - 3]) % M + 1;
        check.assign(K + 1, 0);

        // find the smallest subsequence
        int result = N + 1;
        for (int i = 1, f = 1, cnt = 0; i <= N; ++i)
        {
            if (G[i] > K) continue;
            else if (++check[G[i]] == 1) ++cnt;

            while (f <= i && cnt == K)
            {
                if (G[f++] > K) continue;

                result = min(result, i - f + 2);
                if (--check[G[f - 1]] == 0) --cnt;
            }
        }

        cout << "Case " << ++cases << ": ";
        if (result == N + 1) cout << "sequence nai\n";
        else cout << result << "\n";
    }

    return 0;
}

# 參考資料

https://blog.csdn.net/keshuai19940722/article/details/18883357