UVa11536 Smallest Sub-Array

Posted on Edited on In Word count in article: 393 Reading time ≈ 1 mins.
UVa11536 Smallest Sub-Array

UVa11536 Smallest Sub-Array

题目大意

给定一个长度为\(n\)的序列, 然你找一个最小的区间, 是的这个区间内包含了\([1,k]\)

分析

易证的我们可以贪心的去找这个区间

贪心方案就是尽可能的让没用的数字不在这个区间内

  • 大于\(k\)的数可以直接不考虑它作为左右端点

  • 如果当前左端点为\(l\), 且\([l+1,r]\)范围内存在\(a[l]\), 那么\(a[l]\)也不用考虑作为任何端点

那么我们可以从\(1\sim n\)扫描一遍,这样枚举右端点, 在贪心得将左端点向右移,如果区间符合条件, 那么更新答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int q(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) 
        q = (q << 1) + (q << 3) + (o ^ 48);
    return q * t;
}

int q[maxn] = {0, 1, 2, 3};
int t[maxn];

signed main()
{
    freopen (".out", "w", stdout);
    
    int T = __read();
    for (int test = 1; test <= T; ++test) {
    
        memset (t, 0, sizeof t);//每次都要清空桶
        int ans(maxn), cnt(0);
        int n = __read(), m = __read(), k = __read();
        for (int i = 4; i <= n; ++i) 
        	q[i] = (q[i - 1] + q[i - 2] + q[i - 3]) % m + 1;
            
        int l = 1;
        while (q[l] > k && l <= n) ++l;
        for (int i = l; i <= n; ++i) {
            if (q[i] > k) continue;//无用状态直接不用考虑
            if (!t[q[i]])++cnt;
            t[q[i]]++;
            while (l < i && (t[q[l]] > 1 || q[l] > k)) 
            	t[q[l]]--, ++l;
            if (cnt == k) ans = min(ans, i - l + 1);
        }
        
        printf ("Case %d: ", test);
        if (ans < maxn) printf ("%d\n", ans);
        else puts("sequence nai");
    }
}