louisfghbvc的部落格

題目連結:   11536.pdf (nsysu.edu.tw)

題目大意:  問說最短的數列，滿足數列包含數字1~K

思路:  Sliding Window, 用map或是queue。因為k很小所以這邊用array當作map。維護一個大小為K的陣列。

假設滿足K，更新最小答案，並移除。假設超過K則不考慮。

代碼:  

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> arr(n);
    arr[0] = 1, arr[1] = 2, arr[2] = 3;
    for(int i = 3; i < n; ++i)
        arr[i] = (arr[i-1] + arr[i-2] + arr[i-3]) % m + 1;

    int mp[105] = {}, mp_size = 0;
    int res = -1;
    for(int r = 0, l = 0; r < n; ++r){
        if(mp_size < k && arr[r] <= k) {
            if(mp[arr[r]]++ == 0) mp_size++;
        }
        if(mp_size == k){
            if(res == -1) res = r-l+1;
            else res = min(res, r-l+1);
            while(mp_size >= k){
                res = min(res, r-l+1);
                int tmp = arr[l++];
                if(tmp > k) continue;
                if(--mp[tmp] == 0) mp_size--;
            }
        }
    }

    if(res < 0){
        cout << "sequence nai\n";
        return;
    }
    cout << res << "\n";
}

int main() {
    int t;
    cin >> t;
    for(int i = 1; i <= t; ++i){
        printf("Case %d: ", i);
        solve();
    }
}