CSDN竞赛12期题解-创新互联

已知一个字符串a，b。 字符串b中包含数量不等的特殊符号“.”,“*”（字符串存在没有特殊符号或者全由特殊符号组成的情 况）。 “.”表示该字符可以变成任意字符，“* ”表示该字符的前一个字符可以变成任意多个。 现在我们想知道b可否通过特 殊符号变成a。 a* 可以转化为a,aa,aaa,aaaa…

这道题对于会做的同学很简单，可以说能做出来的肯定做过这道题，因为如果连这么经典的题都没做过，那么一般做不出来这道题，对于第一次遇见这道题的同学来说，难度还是不小的。之前写的这道题的题解AcWing 30 正则表达式匹配。

这道题与正则表达式匹配还是有点区别的，因为正则表达式匹配中*可以使得前面字符出现0次，处理起来更加复杂，而本题指出了*前面字符至少出现一次，这样处理起来就简单了。

状态表示： f [ i ] [ j ] f[i][j] f[i][j]表示 a a a的前 i i i个字符与 b b b的前 j j j个字符是否匹配， t r u e true true表示匹配， f a l s e false false表示不匹配。

状态边界： f [ 0 ] [ 0 ] = t r u e f[0][0]=true f[0][0]=true表示两个字符串都是空的情况是匹配的。

状态转移方程：

• b [ j − 1 ]   ! =   ′ ∗ ′ b[j-1] \ !=\ '*' b[j−1] != ′∗′时，
  f [ i ] [ j ] = { f [ i − 1 ] [ j − 1 ] if  a [ i − 1 ] = = b [ j − 1 ]   o r   b [ j − 1 ] = = ′ . ′ f a l s e , a [ i − 1 ] ! = b [ j − 1 ]   a n d   b [ j − 1 ] ! = ′ . ′ f[i][j]= \begin{cases} f[i-1][j-1]& \text{if\ $a[i-1]==b[j-1]\ or\ b[j-1]=='.'$}\\ \\ false,& \text{$a[i-1]!=b[j-1]\ and\ b[j-1]!='.'$} \end{cases} f[i][j]=⎩⎪⎨⎪⎧​f[i−1][j−1]false,​if a[i−1]==b[j−1] or b[j−1]==′.′a[i−1]!=b[j−1] and b[j−1]!=′.′​

• b [ j − 1 ]   = =   ′ ∗ ′ b[j-1] \ ==\ '*' b[j−1] == ′∗′时，

f [ i ] [ j ] = { f a l s e , if  b [ j − 2 ]   ! =   a [ i − 1 ]  and  b [ j − 2 ]   ! =   ′ . ′ f [ i − 1 ] [ j ]   ∣   f [ i ] [ j − 1 ] , if  b [ j − 2 ]   = =   a [ [ i − 1 ]  or  b [ j − 2 ]   = =   ′ . ′ f[i][j]= \begin{cases} false, & \text{if\ $b[j-2]\ !=\ a[i-1]$\ and\ $b[j-2]\ !=\ '.'$}\\ \\ f[i-1][j]\ |\ f[i][j-1],& \text{if\ $b[j-2]\ ==\ a[[i-1]$\ or\ $b[j-2]\ ==\ '.'$} \end{cases} f[i][j]=⎩⎪⎨⎪⎧​false,f[i−1][j] ∣ f[i][j−1],​if b[j−2] != a[i−1] and b[j−2] != ′.′if b[j−2] == a[[i−1] or b[j−2] == ′.′​

由于状态的初始值是false，所以我们只需要考虑状态可能转移为true的情况。即：
f [ i ] [ j ] = { f [ i − 1 ] [ j − 1 ] if  a [ i − 1 ] = = b [ j − 1 ]   o r   b [ j − 1 ] = ′ . ′ f [ i − 1 ] [ j ]   ∣   f [ i ] [ j − 1 ] , if  b [ j − 1 ]   =   ′ ∗ ′  and ( b [ j − 2 ]   = =   a [ [ i − 1 ]  or  b [ j − 2 ]   = =   ′ . ′ ) f[i][j]= \begin{cases} f[i-1][j-1]& \text{if\ $a[i-1]==b[j-1]\ or\ b[j-1]='.'$}\\ \\ f[i-1][j]\ |\ f[i][j-1],& \text{if\ $b[j-1]\ =\ '*'$\ and\ ($b[j-2]\ ==\ a[[i-1]$\ or\ $b[j-2]\ ==\ '.'$)} \end{cases} f[i][j]=⎩⎪⎨⎪⎧​f[i−1][j−1]f[i−1][j] ∣ f[i][j−1],​if a[i−1]==b[j−1] or b[j−1]=′.′if b[j−1] = ′∗′ and (b[j−2] == a[[i−1] or b[j−2] == ′.′)​

以 a = ′ a a a a ′ , b = ′ a ∗ ′ a='aaaa',b='a*' a=′aaaa′,b=′a∗′为例，在求状态 f [ 4 ] [ 2 ] f[4][2] f[4][2]时，先考虑*前面字符出现一次的情况，即 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1]状态；再考虑*前面字符出现 n n n次的情况，此时如果匹配说明 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]也是匹配的，且匹配时*前面字符出现了 n − 1 n-1 n−1次，再加上 a [ i − 1 ] = = b [ j − 2 ]   o r   b [ j − 2 ] = ′ . ′ a[i-1]==b[j-2]\ or\ b[j-2]='.' a[i−1]==b[j−2] or b[j−2]=′.′的条件，足以使得 f [ i ] [ j ] f[i][j] f[i][j]匹配。

#include#include#includeusing namespace std;
const int N = 1005;
bool f[N][N];
std::string solution(std::string a, std::string b) {int n = a.size();
	int m = b.size();
	memset(f,false,sizeof f);
	f[0][0] = true;
	for(int i = 1; i<= n; i++) {for(int j = 1; j<= m; j++) {	if(a[i-1]==b[j-1] || b[j-1]=='.') f[i][j] = f[i-1][j-1];
			else if(b[j-1]=='*') {		if(b[j-2] == '.' || b[j-2] == a[i-1]) f[i][j] = f[i][j-1] | f[i-1][j];
			} else f[i][j] = false;
		}
	}
	if (f[n][m]) return "yes";
	else return "no";
}
int main() {std::string a;
	std::string b;
	getline(std::cin, a);;
	getline(std::cin, b);;
	std::string result = solution(a, b);
	std::cout<

#include#include#include#include#include#includeusing namespace std;
int fa[1005];
int find(int x) {if(x!=fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
int main() {int n;
	int m;
	std::cin>>n;
	std::cin>>m;
	int a,b;
	for(int i = 1; i<= 1000; i++) fa[i] = i;
	for(int i = 0; i< m; i++) {cin>>a>>b;
		if(fa[a] !=fa[b]) {	fa[find(a)] = find(b);
		}
	}
	sets;
	for(int i = 1; i<= 1000; i++) {fa[i] = find(i);
		s.insert(fa[i]);
	}
	int res = s.size() - 1 - (1000 - n);
	cout<

#include#include#include#include 
#includeusing namespace std;
int solution(int n, int m, std::vector& vec) {int res = 0;
	int t = 1e9;
	for(auto x : vec) {if (t<= m) {	int p = m / t * (x - t);
			res = max(res,p);
		}
		t = min(t,x);	
	}
	return res + m;
}
int main() {int n;
	int m;
	std::vectorvec;
	std::cin>>n;
	std::cin>>m;
	std::string line_0, token_0;
	getline(std::cin >>std::ws,line_0);
	std::stringstream tokens_0(line_0);
	while(std::getline(tokens_0, token_0, ' ')) {vec.push_back(std::stoi(token_0));
	}
	int result = solution(n, m,vec);
	std::cout<