【codeforces 701C】They Are Everywhere

小鱼儿 2021-10-01 07:08 186阅读 0赞

【题目链接】:[http://codeforces.com/contest/701/problem/C][http_codeforces.com_contest_701_problem_C]

【题意】  
  
让你选择一段最短的区间;  
使得这段区间里面包含所有种类的字符;

【题解】  
  
之前都是用二分写;  
现在会用类似队列的思路写了;  
就是先确定左端点;  
然后右端点右移;  
直到出现所有种类;(这时候右端点就没必要再右移了)  
然后右端点不动,右移左端点;  
然后如果这时候又没有全部种类,就再右移右端点;  
O(N)的复杂度吧  
  
【Number Of WA】  
  
0  
  
【完整代码】

#include <bits/stdc++.h>
    using namespace std;
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define LL long long
    #define rep1(i,a,b) for (int i = a;i <= b;i++)
    #define rep2(i,a,b) for (int i = a;i >= b;i--)
    #define mp make_pair
    #define ps push_back
    #define fi first
    #define se second
    #define rei(x) cin >> x
    #define pri(x) cout << x
    #define ms(x,y) memset(x,y,sizeof x)
    
    typedef pair<int,int> pii;
    typedef pair<LL,LL> pll;
    
    const int dx[9] = {
         0,1,-1,0,0,-1,-1,1,1};
    const int dy[9] = {
         0,0,0,-1,1,-1,1,-1,1};
    const double pi = acos(-1.0);
    const int N = 1e5+100;
    
    map <char,int> dic;
    int n,tot,ans=N;
    char s[N];
    
    int main()
    {
        //freopen("F:\\rush.txt","r",stdin);
        ios::sync_with_stdio(false);
        rei(n);
        rei((s+1));
        rep1(i,1,n)
            if (!dic[s[i]])
            {
                dic[s[i]] = 1;
                tot++;
            }
        dic.clear();
        int l = 1,r = 1,now = 0;
        dic[s[1]] = 1;
        now = 1;
        while (r<=n)
        {
            if (l<=r && now==tot)
            {
                ans = min(ans,r-l+1);
                dic[s[l]]--;
                if (dic[s[l]]==0) now--;
                l++;
            }
            else
            {
                r++;
                if (r<=n)
                {
                    dic[s[r]]++;
                    if (dic[s[r]]==1) now++;
                }
            }
        }
        pri(ans<<endl);
        //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
        return 0;
    }

转载于:https://www.cnblogs.com/AWCXV/p/7626437.html

[http_codeforces.com_contest_701_problem_C]: http://codeforces.com/contest/701/problem/C