codeforces思维题专练2

CodeForces - 1354B A - Ternary String
( 法一:dp\ 线性dp的思路,找到距离每个位置最近a..b..c的序列的长度，取最小值,如果有元素没有出现过输出0 )

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int t;cin>>t;
    while(t--)
    {
        string s;cin>>s;
        int ans,a,b,c;
        ans=a=b=c=1e9;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='1')
                a=i;
            else if(s[i]=='2')
                b=i;
            else
                c=i;
            ans=min(ans,(max(max(a,b),c)-min(min(a,b),c)+1));
        }
        cout<<(ans>200000?0:ans)<<endl;
    }
}

( 法二:答案序列一定是abbb...c这样的， 否则，则一定能够去掉，满足首尾字母一定不同\ 我们只需要找到每一堆相同的数，在他左边又右边不断添加数，就能找到所有符合abbbc这样形式的序列，ans取所有序列长度的最小值即可 )

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define rep(i,a,n) for(int i=0;i<n;i++)//repeat 默认升序
#define per(i,a,n) for(int i=n;i>=0;i--)//per 对rep的颠倒，默认降序
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

typedef long long ll;

int main()
{
    IOS;
    int t;cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        vector<pair<char,int>>ans;
        for(auto x:s)
        {
            if(ans.empty()||x!=ans.back().first)
                ans.push_back(make_pair(x,1));
            else
                ans.back().second++;
        }
        int m=ans.size();
        ll res=1e9;
        for(int i=1;i<m-1;i++)
        {
            if(ans[i-1].first!=ans[i+1].first)
            {
                res=min(res,1ll*ans[i].second+2);
            }
        }
        cout<<(res>200000?0:res)<<endl;
    }
    return 0;
}