Edu-CF-178-E. Unpleasant Strings

思路讲解

首先贪心的，我们在每个位置上总归想跳的最远，且在每个位置上都跳的最远，得到的一定是最少跳跃次数的。

那么这个每个位置上通过加一个字母能够一次跳到的最远位置怎么得到的那？其实就是所有合法字母中上一次出现的位置最远的字母的位置（如果有一个合法字母前面没出现过，那我们就认为他直接跳出去结束了）。

ROF(i,N-1,0){
	FOR(j,0,K-1){
		if(Pos[j].empty()){
			JumpFar[i]=N;
			JumpCh[i][j]=N;
		}else{
			JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
			JumpCh[i][j]=Pos[j].back();
		}
	}
	Pos[S[i]-'a'].pb(i);
}

然后知道了在这个位置上最远能跳多远，那么我们知道最多要跳多少次那？可以通过记忆化搜索。

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}

	ROF(i,N-1,0){
		dp[i]=dfs(i);
	}

最后这个串需要用多少位原串需要跳跃处理，否则会 $TLE$，最坏 $O(NQ)$ 时间复杂度。

AC代码

https://codeforces.com/contest/2104/submission/317799371

源代码

// Problem: E. Unpleasant Strings
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,Q,K,T;
char S[MAXN];
// ll Cnt[MAXN][35];
ll JumpFar[MAXN];
ll JumpCh[MAXN][35];
ll dp[MAXN];
vector<ll> Pos[35];

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}


inline void solve(){
	cin>>N>>K;
	FOR(i,0,N-1){
		cin>>S[i];
		// ++Cnt[S[i]-'a'];
	}
	// ROF(i,N-1,0){
		// FOR(j,0,30){
			// Cnt[i][j]=Cnt[i+1][j];
		// }
		// ++Cnt[i][S[i-1]-'a'];
	// }
	
	// JumpFar[N-1]=1;
	// Pos[S[N-1]-'a'].pb(N-1);
	ROF(i,N-1,0){
		FOR(j,0,K-1){
			if(Pos[j].empty()){
				JumpFar[i]=N;
				JumpCh[i][j]=N;
			}else{
				JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
				JumpCh[i][j]=Pos[j].back();
			}
		}
		Pos[S[i]-'a'].pb(i);
	}
	ROF(i,N-1,0){
		dp[i]=dfs(i);
// #ifdef LOCAL
    // cerr << "i:"<<i<<" dp:"<<dp[i] << '\n';
// #endif
	}
	
// #ifdef LOCAL
    // FOR(i,0,N-1){
    	// cerr<<dp[i]<<" ";
    // }
    // cerr<<"\n";
// #endif

	cin>>Q;
	while(Q--){
		// 要在末尾加几个合法字母，才能让这个字符串s不是S的子集
		string s;
		cin>>s;
		if(SZ(s)>N){
			cout<<0<<"\n";
			continue;
		}
		ll idx=0,idxs=0,bp=-INF;
		while(idxs<N){
			if(idx>=SZ(s)) {
				break;
			}
			// assert(idx<SZ(s));
			if(s[idx]==S[idxs]){
				bp=idxs;
				++idx;
				idxs=JumpCh[idxs][s[idx]-'a'];
			}else{
				idxs=JumpCh[idxs][s[idx]-'a'];
			}
		}
		if(idx<SZ(s)){
			cout<<"0\n";
			continue;
		}
		
// #ifdef LOCAL
    // cerr << "Q: "<<Q<<" bp:"<<bp<<" idx:"<<idx << '\n';
// #endif

		cout<<dp[bp]<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2104/submission/317799371
*/

心路历程（WA，TLE，MLE……）

https://codeforces.com/contest/2104/submission/317796467

对比对部分没有优化。

源代码

// Problem: E. Unpleasant Strings
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,Q,K,T;
char S[MAXN];
ll Cnt[MAXN][35];
ll JumpFar[MAXN];
ll dp[MAXN];
vector<ll> Pos[35];

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}

inline void solve(){
	cin>>N>>K;
	FOR(i,0,N-1){
		cin>>S[i];
		// ++Cnt[S[i]-'a'];
	}
	// ROF(i,N-1,0){
		// FOR(j,0,30){
			// Cnt[i][j]=Cnt[i+1][j];
		// }
		// ++Cnt[i][S[i-1]-'a'];
	// }
	
	// JumpFar[N-1]=1;
	// Pos[S[N-1]-'a'].pb(N-1);
	ROF(i,N-1,0){
		FOR(j,0,K-1){
			if(Pos[j].empty()){
				JumpFar[i]=N;
				break;
			}else{
				JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
			}
		}
		Pos[S[i]-'a'].pb(i);
	}
	ROF(i,N-1,0){
		dp[i]=dfs(i);
#ifdef LOCAL
    cerr << "i:"<<i<<" dp:"<<dp[i] << '\n';
#endif
	}
	
#ifdef LOCAL
    FOR(i,0,N-1){
    	cerr<<dp[i]<<" ";
    }
    cerr<<"\n";
#endif

	cin>>Q;
	while(Q--){
		// 要在末尾加几个合法字母，才能让这个字符串s不是S的子集
		string s;
		cin>>s;
		if(SZ(s)>N){
			cout<<0<<"\n";
			continue;
		}
		ll idx=0,bp=-INF;
		FOR(i,0,N-1){
			if(idx>=SZ(s)) {
				break;
			}
			// assert(idx<SZ(s));
			if(s[idx]==S[i]){
				bp=i;
				++idx;
			}
		}
		if(idx<SZ(s)){
			cout<<"0\n";
			continue;
		}
#ifdef LOCAL
    cerr << "Q: "<<Q<<" bp:"<<bp<<" idx:"<<idx << '\n';
#endif
		cout<<dp[bp]<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/