补题-2020USST算法竞赛练习场3

【补题系列】2020USST算法竞赛练习场3

HDU 2369 Broken Keyboard

题解

比较典型的双指针题，比赛时AC了，但还是记录一下

题意：给定n和字符串s，要求求出s中字母种类数不超过n的最长子串的长度

算法：双指针

题目也就是要求维护一个特殊的队列，不断往队头加元素，当队列中字符种类数大于n时，队尾元素出队，循环直到队头指针到达字符串末尾

AC代码

#include<bits/stdc++.h> 
using namespace std;
int m[500]; 
int main() { 
    int n; 
    while(cin>>n&&n) { 
        int fr,en,len,cur=0,asd=0; 
        string ss;getline(cin,ss); 
        fr=en=0;
        memset(m,0,sizeof(m));
        len=ss.length(); 
        while(en<len) { 
            if(m[ss[en]]==0)//首次出现 
            { 
                m[ss[en]]=1;
                cur++;//种类增加 
            }else m[ss[en]]++; 
            while(cur>n)//出列pop 
            { 
                m[ss[fr]]--; 
                if(m[ss[fr]]==0)cur--;//更新种类 
                fr++; 
            }
            asd=max(asd,en-fr+1);//记录最大 
            en++; 
        }
        cout<<asd<<endl; 
    } 
}

HDU 5707 Combine String

题解

题意：给定三个字符串，判断是否存在一种拆分方案使得a、b分别组成c的子串

算法：dp

用dp[i][j]表示c的前i+j个字符创能否由a的前i个字符和b的前j个字符组成，状态转移方程为dp[i][j]=dp[i-1][j]&&a[i]==c[i+j]||dp[i][j-1]&&b[j]==c[i+j]

PS：代码中的|=代表两个状态满足其一即可，因为dp只有0和1两种状态

AC代码

#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005];
int main(){
	string a,b,c;
	while(cin>>a>>b>>c){
		int len1=a.length(),len2=b.length(),len3=c.length();
		if(len1+len2!=len3){
			cout<<"No"<<endl;
			continue;
		}
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=0;i<=len1;i++){
			for(int j=0;j<=len2;j++){
				if(i>0&&a[i-1]==c[i+j-1]) dp[i][j]|=dp[i-1][j];
				if(j>0&&b[j-1]==c[i+j-1]) dp[i][j]|=dp[i][j-1];
			}
		}
		cout<<(dp[len1][len2]?"Yes":"No")<<endl;
	}
	return 0;
}