天梯赛 L1-058 6翻了

传送门：https://pintia.cn/problem-sets/994805046380707840/problems/1111914599408664577

这道字符串题，只是天梯赛L1的题，数据范围很小，一般就是暴力去做，但是要考虑将多个连续的6替换成其他的指定字符串，其实一开始的时候其实想不出来有什么比较好的思路可以去做。

感觉字符串题就是这样，明明没考啥东西，如果你基础够好，或者说有一些巧妙的方法的话，一下子就能解决，要不然你可能需要暴力写半天。

这道题后面想的思路是：找连续的6的话，我们肯定要知道这个连续的6的子串有多长，那么就可以联想到我们的最长上升子串问题，只不过这里是求一个所含有的字符都是6的子串的长度，并且是最长的“都是6子串”。

我们在最长上升子串中，如果第i个字符大于它前一个字符，dp【i】=dp【i-1】+1，否则dp【i】 = 1

A. 那在我们这个问题中，也可以这样，如果该字符不是6，则a【i】=0，如果是出现的第一个6，则a【i】=1，如果是连续出现的，那么就等于它前一个的值+1，即a【i】 = a【i-1】+1。

不过我们的问题在于，我们遇到这样一个子串的时候，是要得知它的长度的，要分小于3，在3和9中间，还有大于9三种情况来讨论。

怎么求这个的长度呢？上面A这句话的思路反过来就可以了，我们反向地对string s做一次遍历，做一次A的过程，然后在接下来正向遍历a数组的时候，在遇到这样的子串的第一个字符的位置的时候就可以立刻知道该子串有多长，然后直接不打印该子串，而是打印要替换的值，然后循环遍历i直接加上这个子串的长度，完美跳过该子串，继续打印下面该打印的字符。

题解代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100005;

const int INF = 0x3f3f3f3f;

int k,N,mlen = INF;

string s;

int a[1005];

int main(){

	#ifndef ONLINE_JUDGE

		//freopen("in.txt","r",stdin);

	#endif

	getline(cin,s);

	int len = s.length();

	memset(a,0,sizeof(a));

	for(int i=len-1;i>=0;i--){

		if(s[i] == '6' ){

			if(i == len-1) a[i] = 1;

			else if(s[i+1] == 0) a[i] = 1;

			else a[i] = a[i+1]+1;

		}

	}

	for(int i=0;i<len;){

		if(a[i] > 9){

			cout<<"27";

			i += a[i];

		}

		else if(a[i] > 3){

			cout<<"9";

			i += a[i];

		}

		else {

			cout<<s[i];

			i++;

		}

	}cout<<endl;

	return 0;

}

天梯赛 L1-058 6翻了的相关教程结束。