CodeForces-GYM-101466E Text Editor 题解

这题很有趣，一开始我总是 WA，最后发现其实是我对于 cin.getline()的使用不熟练导致的。
原题链接
当然，尴尬的是到今天 ACM 训练结束我都没有优化完，这个代码到 16 个点就超时了。

#include<bits\stdc++.h>

char seq[200004];
char seq_c[200004];
int n,ans;
using namespace std;

int main()
{
	memset(seq,0,sizeof(seq));
	memset(seq_c,0,sizeof(seq_c));
	//scanf("%s",seq);
	//scanf("%s",seq_c);
	cin.getline(seq,200000,'\n');
	cin.getline(seq_c,200000,'\n');
	cin >> n;
	int k;
	for(k=strlen(seq_c);k>=1;k--)
	{
		ans=0;
		seq_c[k]=0;
		for(int i=0;i<strlen(seq);i++)
		{
			if(seq[i]==seq_c[0])
			{
				int j;
				for(j=1;j<strlen(seq_c);j++)
				{
					if(seq[i+j]!=seq_c[j])break;
				}
				if(j==strlen(seq_c))ans++;
			}
		}
		if(ans>=n)break;
	}
	if(k)
	{
		for(int i=0;i<strlen(seq_c);i++)cout << seq_c[i];
	}
	else cout << "IMPOSSIBLE";
	cout << endl;
	return 0;
}

于是今天早上我加了一个优化开关，然并卵。

if(strlen(seq_c) > strlen(seq)-i) break;

随后我把序列反过来，用一个数组存储前一次的满足值，并去查找。

#include<bits\stdc++.h>

char seq[200004];
char seq_c[200004];
int init_seq[200004];
int n,ans,flag;
using namespace std;

int main()
{
	memset(seq,0,sizeof(seq));
	memset(seq_c,0,sizeof(seq_c));
	memset(init_seq,0,sizeof(init_seq));
	cin.getline(seq,200000,'\n');
	cin.getline(seq_c,200000,'\n');
	for(int i=0;i<strlen(seq);i++)init_seq[i]=i;
	cin >> n;
	int k,init_seq_len=strlen(seq);
	for(k=1;k<=strlen(seq_c);k++)
	{
		ans=0;
		flag=0;
		for(int i=0;i<init_seq_len;i++)
		{
			if(k > strlen(seq)-init_seq[i]) break;
			if(seq[init_seq[i]]==seq_c[0])
			{
				init_seq[flag]=init_seq[i];
				flag++;
				//上面先更新下 init_seq，下面再执行对比 
				int j;
				for(j=1;j<k;j++)
				{
					if(seq[init_seq[i]+j]!=seq_c[j])break;
				}
				if(j==k)ans++;
			}
		}
		if(ans<n)
		{
			k--;
			break;
		}
		init_seq_len=flag;
	}
	if(k==strlen(seq_c)+1)k--;
	if(k)
	{
		for(int i=0;i<k;i++)cout << seq_c[i];
	}
	else cout << "IMPOSSIBLE";
	cout << endl;
	return 0;
}

然而还是在第 16 个点炸了。
我的最新思路是用二分的方法去查找，原理类似猜数字，先用一半去试，如果大了就是 4/3，否则 1/4，如此操作。
值得注意的是，得到一个相等并不能得出答案，还需到找出最长的一个相等的。
因此二分查找的第一个小于的，而不是第一个等于的。