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

这次比赛有些悲剧啊,3道题最后FST了两道,rating很受伤啊。

题目链接

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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注