Cloud of Hashtags

&题意：

给你一个n,之后给出n个串,这些串的总长度不超过5e5,你要删除最少的单词(并且只能是后缀),使得这些串是按字典序排列的.

&题解：

这也是个水题,当然了,是在你能想到的情况下,然而我还是没想到.

首先你要推出一个结论:最后一行是绝对不可以删的.

你也许会想的这种情况:

#c

#c

#a

如果删了最后一个,那么前2个c就不用删了,但这是错的,因为空字符比a还要小,你如果把a删了,那么你就必须把前面2个c删了,这样才能符合条件.

如果你能推出这个,那就快a了这题了.

之后想到的就是,根据最后一个,向上两两比较,比较完后修改上面的那个,之后继续向上向上两两比较.

最后根据你记录的长度输出答案即可.

&代码：

#include <cstdio>

#include <cmath>

#include <iostream>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

using ll=long long;

const int maxn= 5e5 +9;

int n;

string s[maxn];

int v[maxn];

int main()

{

	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

//	freopen("C:\\Users\\Zmy\\Desktop\\in.txt", "r", stdin);

	cin>>n;

	for(int i=0;i<n;i++){

		cin>>s[i];

		v[i]=s[i].size();

	}

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

		string a=s[i],b=s[i-1];

		if(a<b){

			int p=min(v[i],v[i-1]);

			for(int j=0;j<p&&a[j]>=b[j];j++){

				v[i-1]=j+1;

			}

			s[i-1]=s[i-1].substr(0,v[i-1]);

		}

	}

	for(int i=0;i<n;i++){

		s[i].resize(v[i]);

		cout<<s[i]<<'\n';

	}

	return 0;

}

Hashtags

D Cloud of Hashtags Codeforces Round #401 (Div. 2)

Cloud of Hashtags