[CF1023X]Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

题目链接

http://codeforces.com/contest/1023

A. Single Wildcard Pattern Matching

大意

给出一个带有通配符的字符串，问其能否匹配另一个没有带通配符的字符串。

题解

这是一道经典的带通配符的字符串匹配问题。

问号的匹配比较容易，因为问号只能代替一个字符，遇到问号直接匹配即可。但星号却能代替 \(0\) 个或多个字符。

我们可以先判断 * 前的字符串，如果失配，显然可以输出 \(-1\)。

如果遇到 * 号的话，我们可以将星号的位置记录下来，然后从后往前扫描。

当 \(s\) 的长度 \(n\) 与 \(t\) 的长度 \(m\) 满足 \(n>m+1\) 时，说明匹配失败（因为即使 * 代替的内容为空， \(n\) 的最大长度也只是 \(m+1\)，当 * 代替的字符串不为空时，显然会满足 \(n \geq m\)）。

接下来从后往前扫描时，只要 \(s\) 与 \(t\) 对应的字母相等，当字符串 \(s\) 匹配到 * 时，说明匹配成功。

#include <stdio.h>
char s1[200005],s2[200005];
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 scanf("%s",s1);
 scanf("%s",s2);
 int flag=1;
 for(int i=0;i<=n;i++)
  if(s1[i]=='*')
  {
   flag=-1;
   break;
  }
  else if(s1[i]=='?')continue;
  else if(s1[i]!=s2[i])
  {
   flag=0;
   break;
  }
 if(flag==1)puts("YES");
 else if(flag==0)puts("NO");//比赛的时候这里少打了个else，结果fst了...
 else
 {
  for(int i=n-1,j=m-1;;i--,j--)
   if(s1[i]=='*')
   {
    if(i-1>j)flag=0;
    else flag=1;
    break;
   }
   else if(s1[i]=='?')continue;
   else if(s1[i]!=s2[j])
   {
    flag=0;
    break;
   }
  if(flag)puts("YES");
  else puts("NO");
 }
 return 0;
}

C. Bracket Subsequence

大意

给出一个合法的括号序列，怎样通过删除一些括号，得到一个长度为 \(k\) 的序列。

题解

由于刚开始给出的字符串一定合法，所以刚开始给出的字符串一定有左括号和右括号各 \(n/2\) 个。当然，我们生成的字符串也必须有 \(k/2\) 个左括号和右括号。

我们可以扫描一遍原字符串，如果遇到左括号，且左括号的数量 \(\leq k/2\) 时，就可以把左括号放入答案序列。

如果是右括号，我们需要确保在当前左括号数量小于右括号数量的情况下（左括号数量等于右括号的话，就不能再添加右括号了），在满足右括号数量 \(\leq k/2\) 的情况下，将右括号放入答案序列。

显然，这样的做法不会破坏原来括号的相对顺序，因而这样的做法是合法的。

#include <stdio.h>
char s[200005],res[200005];
int main()
{
 int n,k;
 scanf("%d%d",&n,&k);
 scanf("%s",s);
 if(n==k)printf("%s",s);
 else
 {
  int cntl=0,cntr=0,tot=0;
  for(int i=0;i<n;i++)
   if(s[i]=='(')
   {
    if(cntl!=k/2)
    {
     cntl++;
     res[tot++]='(';
    }
   }
   else
   {
    if(cntr!=k/2&&cntl>cntr)
    {
     cntr++;
     res[tot++]=')';
    }
   }
  printf("%s",res);
 }
 return 0;
}