活動地址：?？痛赫兴㈩}訓(xùn)練營 - 編程打卡活動

Easy 字符串字符匹配

簡要題意

給定字符串 ，問所有 中出現(xiàn)字母是否都在 中出現(xiàn)。

Solution

記錄一下每個字母是否在 中出現(xiàn)，若在 中出現(xiàn)再消去標(biāo)記，最后看有無標(biāo)記剩余就好。

Code

void R()
{
	string s,t;
	cin>>s>>t;
	vector<int> vis(26);
	for (char c:s)
		vis[c-'a']=1;
	for (char c:t)
		vis[c-'a']=0;
	if (count(vis.begin(),vis.end(),1))
		cout<<"false";
	else cout<<"true";
	return;
}

Medium 小紅的區(qū)間構(gòu)造

簡要題意

構(gòu)造區(qū)間 ，使得 ，且區(qū)間內(nèi)恰有 個 的倍數(shù)，或報告無解。

Solution

先構(gòu)造 和長度都最小，且區(qū)間內(nèi)恰有 個 的倍數(shù)的區(qū)間 。

之后 最多向左延伸 ， 最多向右延伸 。

當(dāng) 時嘗試延伸，若延伸后仍有 或 越界則無解。

Code

void R()
{
	i64 n,k,x;
	cin>>n>>k>>x;
	i64 l=x,r=n*x;
	k-=r-l+1;
	i64 t=min(k,x-1);
	l-=t,k-=t;
	t=min(k,x-1);
	r+=t,k-=t;
	if (k||r>=2e9) cout<<-1;
	else cout<<l<<' '<<r;
	return;
}

Hard 最長公共子序列(一)

簡要題意

給定兩個字符串，求它們的最長公共子序列。

Solution

感覺空間復(fù)雜度 并不現(xiàn)實，因為你存字符串也是要空間的。

存第一個串在線處理第二個還好說，如果 ，意味著你得到完整的第二個串時前面第一個串只能保留 的信息，就很困難了。

下面給一個 空間復(fù)雜度的做法：

先把第一個串讀入，一邊讀入第二個串的字母一邊 dp 。

記 為第一個串的 前綴與當(dāng)前第二個串已讀入部分的最長公共子序列長度。

在讀入字符 時有轉(zhuǎn)移：

數(shù)組中最大值就是答案。

Code

void R()
{
	int n,m;
	string s;
	cin>>n>>m>>s;
	vector<int> dp(n);
	for (int i=0;i<m;i++)
	{
		char c;
		cin>>c;
		int mx=0;
		for (int j=0;j<n;j++)
		{
			int t=mx;
			mx=max(mx,dp[j]);
			if (s[j]==c)
				dp[j]=max(dp[j],t+1);
		}
	}
	cout<<*max_element(dp.begin(),dp.end());
	return;
}