星星博客 »  > 

CF-B. Ternary String (“ 高级做法 ”---vector+pair)很舒服~~

题址

  1. 题意:
    就是在一个序列里面找到含有1,2,3的最短子序列
  2. 解法:
    这里用了一个pair的骚操作,first代表类型(1 2 3),second代表其位置,后面判断其不同就行了,当然其实也没那么复杂几个判断就可以了,就是记录每个1,2,3的最新距离,求其最小

题面

#include<string>
#include<vector>
#include <iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

int main(){
	int t; cin >> t;
	for (int i = 0; i < t; i++)	{
		string s;cin >> s;
		int ans = int(1e9);
		int n = s.size();
		//           zhi   len
		vector<pair<char, int> > c;
		for (auto x : s){
			if (c.empty() || c.back().first != x)c.push_back(make_pair(x, 1));
			else c.back().second++; // 相同 len++
		}
		int m = c.size();
		for (int i = 1; i < m - 1; i++)
			if (c[i - 1].first != c[i + 1].first)//3项不同
				ans = min(ans, c[i].second + 2);
		if (ans > n) ans = 0;
		cout << ans << "\n";
	}
}

相关文章