比赛链接

https://codeforces.com/contest/1023

ABCDEF题解

A. Single Wildcard Pattern Matching

题目大意

给两个串$S,T$，$T$只有小写字母，$S$除了小写字母还有最多一个*字符，*字符能够匹配最多一个字符和空串。求$S$能否匹配$T$，$|S|,|T|\leq 2\times 10^5$。

题解

由于最多只有一个*，因此可以记录*左边的串和右边的串能不能与$T$匹配。

B. Pair of Toys

题目大意

一共有$n$个玩具标号为$1$到$n$，要选出一对玩具$(a,b)$，使得$a+b=k$，求满足条件的对数，注意玩具是无序的，$n,k\leq 10^{14}$

题解

就是解一个方程组

$$x\geq 1,x\leq n,x<k-x,k-x\geq 1,k-x\leq n$$
解得
$$x\geq \max(1,k-n),x\leq \min (n,\lfloor\frac{k-1}{2}\rfloor)$$

这题数据比较水，我用一个错误（有可能是正确）的方法也水过去了

C. Bracket Subsequence

题目大意

给一个括号序列$S$，求$S$的一个长度为$k$并且合法的子序列（显然这个子序列也是括号序列）。$|S|,k\leq 2\times 10^5$

题解

用一个栈维护括号，左括号入栈，右括号将栈顶弹出，如果弹出的左括号数量$=k$那么就可以输出了。

D. Array Restoration

题目大意

长度为$n$的序列，一共有$k$个操作，每次操作将区间$[l_i,r_i]$修改为$i$，每个位置至少被修改一次，操作的顺序是不可调换的。$n,k\leq 2\times 10^5$

现在知道操作完成后的序列，但是有一部分是丢失的。求能否通过上述操作得到这个序列，如果不能输出NO，能输出YES，然后输出一组可能的完整序列。

题解

输出NO的条件就是在两个$b$值之间有$a$值，其中$b>a$。这个很容易用栈来维护。

否则，由于$l_i\leq r_i$，序列中必须至少存在一个位置为$k$，其他0的位置就用这连续的一片0两侧的任何一个值来代替。

E. Down or Right

题目大意

交互题。

有一个$n\times n$的矩阵，一些位置能走，一些位置不能走。在这个矩阵中你只能向下或向右走。你不知道矩阵的具体情况，但是你可以询问，最多$4\times n$次，每次询问$(a,b)$到$(c,d)$能不能走通，$(a,b)$到$(c,d)$的曼哈顿距离必须$\leq n$。求$(1,1)$走到$(n,n)$的一种可行方案。$n\leq 500$

题解

从$(1,1)$出发尽量往下走，如果往下走不到$(n,n)$再向右走。从$(n,n)$倒着走，尽量往左走，如果往左走不通在往上走。可以证明最终两条路一定会相交。

F. Mobile Phone Network

题目大意

$n$个点要构成一棵树，你可以提供$k$条边，你的竞争对手能以每条边$v_i$的价格提供$m$条边，你现在的定价是不固定的。客户在价格相同的情况下会尽量多选择你提供的边，要求最小生成树中，你提供的所有边都能选上。在上述前提下，还要求你的获利尽量大。如果你的获利可以无限大那么输出-1，否则输出你最大可能的获利。$n,m\leq 5\times 10^5,k<n$

题解

首先假设你的每条边价格都是0，求出最小生成树。对于每条非树边，假设权值为$v$，它放在生成树上产生的环中，每条边的价格都必须$\leq v$。可以通过这个$O(n)$的解决这个问题。

代码

A. Single Wildcard Pattern Matching

#include <cstdio>

const int maxn=200000;

int n,m,l,r;
char s[maxn+10],t[maxn+10];

int main()
{
  scanf("%d%d%s%s",&n,&m,s+1,t+1);
  for(int i=1; i<=n; ++i)
    {
      if(s[i]=='*')
        {
          l=i;
          break;
        }
      if(s[i]!=t[i])
        {
          puts("NO");
          return 0;
        }
    }
  if(l==0)
    {
      puts((n==m)?"YES":"NO");
      return 0;
    }
  for(int i=n; i; --i)
    {
      if(s[i]=='*')
        {
          r=m-n+i+1;
          break;
        }
      if(s[i]!=t[m-n+i])
        {
          puts("NO");
          return 0;
        }
    }
  if(l>r)
    {
      puts("NO");
    }
  else
    {
      puts("YES");
    }
  return 0;
}

B. Pair of Toys

#include <cstdio>
#include <algorithm>

long long n,k,mn,mx;

int main()
{
  scanf("%I64d%I64d",&n,&k);
  mn=std::max(1ll,k-n);
  mx=std::min(n,(k-1)/2);
  printf("%I64d\n",std::max(mx-mn+1,0ll));
  return 0;
}

C. Bracket Subsequence

#include <cstdio>

const int maxn=200000;

int n,k,head,stack[maxn+10],instack[maxn+10],cnt;
char s[maxn+10],t[maxn+10];

int main()
{
  scanf("%d%d%s",&n,&k,s+1);
  for(int i=1; i<=n; ++i)
    {
      if(s[i]=='(')
        {
          stack[++head]=i;
          instack[i]=1;
        }
      else
        {
          instack[stack[head--]]=0;
          ++cnt;
          if(cnt*2==k)
            {
              break;
            }
        }
    }
  cnt=0;
  for(int i=1; i<=n; ++i)
    {
      if(instack[i])
        {
          continue;
        }
      if(s[i]==')')
        {
          ++cnt;
        }
      putchar(s[i]);
      if(cnt*2==k)
        {
          break;
        }
    }
  puts("");
  return 0;
}

D. Array Restoration

#include <cstdio>

int read()
{
  int x=0,f=1;
  char ch=getchar();
  while((ch<'0')||(ch>'9'))
    {
      if(ch=='-')
        {
          f=-f;
        }
      ch=getchar();
    }
  while((ch>='0')&&(ch<='9'))
    {
      x=x*10+ch-'0';
      ch=getchar();
    }
  return x*f;
}

const int maxn=200000;

int n,q,v[maxn+10],bin[maxn+10];
int stack[maxn+10],head;

int main()
{
  n=read();
  q=read();
  for(int i=1; i<=n; ++i)
    {
      v[i]=read();
      if(v[i]==0)
        {
          continue;
        }
      if(bin[v[i]]==0)
        {
          bin[v[i]]=1;
        }
      else if(bin[v[i]]==-1)
        {
          puts("NO");
          return 0;
        }
      while((head>0)&&(stack[head]>v[i]))
        {
          bin[stack[head--]]=-1;
        }
      if(stack[head]==v[i])
        {
          --head;
        }
      stack[++head]=v[i];
    }
  int fk=bin[q]?0:q;
  for(int i=1; i<=n; ++i)
    {
      if(v[i]==0)
        {
          if(fk!=0)
            {
              v[i]=fk;
              fk=0;
            }
          else if(v[i-1])
            {
              v[i]=v[i-1];
            }
          else
            {
              v[i]=1;
            }
        }
    }
  if(fk)
    {
      puts("NO");
      return 0;
    }
  puts("YES");
  for(int i=1; i<=n; ++i)
    {
      printf("%d ",v[i]);
    }
  puts("");
  return 0;
}

E. Down or Right

#include <cstdio>

const int maxn=500;

int get(int ax,int ay,int bx,int by)
{
  printf("? %d %d %d %d\n",ax,ay,bx,by);
  fflush(stdout);
  char s[5];
  scanf("%s",s);
  if(s[0]=='Y')
    {
      return 1;
    }
  return 0;
}

int n;
char s[maxn+10],t[maxn+10];

int main()
{
  scanf("%d",&n);
  int x=1,y=1;
  while(x+y<=n)
    {
      if((x+1<=n)&&(get(x+1,y,n,n)))
        {
          s[x+y]='D';
          ++x;
        }
      else
        {
          s[x+y]='R';
          ++y;
        }
    }
  x=y=n;
  while(x+y>n+1)
    {
      if((y>0)&&(get(1,1,x,y-1)))
        {
          t[x+y-n]='R';
          --y;
        }
      else
        {
          t[x+y-n]='D';
          --x;
        }
    }
  putchar('!');
  putchar(' ');
  for(int i=2; i<=n; ++i)
    {
      putchar(s[i]);
    }
  for(int i=2; i<=n; ++i)
    {
      putchar(t[i]);
    }
  puts("");
  return 0;
}

F. Mobile Phone Network

#include <cstdio>
#include <cstring>
#include <algorithm>

int read()
{
  int x=0,f=1;
  char ch=getchar();
  while((ch<'0')||(ch>'9'))
    {
      if(ch=='-')
        {
          f=-f;
        }
      ch=getchar();
    }
  while((ch>='0')&&(ch<='9'))
    {
      x=x*10+ch-'0';
      ch=getchar();
    }
  return x*f;
}

const int maxn=500000;
const int inf=0x3f3f3f3f;

struct data
{
  int u,v,w;

  data(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
};

data d[maxn*2+10];
int n,k,m,pre[maxn*2+10],now[maxn+10],son[maxn*2+10],fa[maxn+10];
int tot,val[maxn*2+10],deep[maxn+10],fv[maxn+10],tag[maxn+10];

namespace dsu
{
  int fa[maxn+10];

  int clear()
  {
    for(int i=1; i<=n; ++i)
      {
        fa[i]=i;
      }
    return 0;
  }

  int find(int x)
  {
    return (x^fa[x])?(x=fa[x]=find(fa[x])):x;
  }
}

int ins(int a,int b,int c)
{
  pre[++tot]=now[a];
  now[a]=tot;
  son[tot]=b;
  val[tot]=c;
  return 0;
}

int dfs(int u)
{
  int j=now[u];
  while(j)
    {
      int v=son[j];
      if(v!=fa[u])
        {
          fv[v]=val[j];
          deep[v]=deep[u]+1;
          fa[v]=u;
          dfs(v);
        }
      j=pre[j];
    }
  return 0;
}

int main()
{
  n=read();
  k=read();
  m=read();
  for(int i=1; i<=k; ++i)
    {
      int u=read(),v=read();
      d[i]=data(u,v,0);
    }
  for(int i=1; i<=m; ++i)
    {
      int u=read(),v=read(),w=read();
      d[i+k]=data(u,v,w);
    }
  dsu::clear();
  int need=n-1;
  for(int i=1; i<=k+m; ++i)
    {
      int x=dsu::find(d[i].u),y=dsu::find(d[i].v);
      if(x!=y)
        {
          --need;
          dsu::fa[x]=y;
          ins(d[i].u,d[i].v,d[i].w);
          ins(d[i].v,d[i].u,d[i].w);
          if(!need)
            {
              break;
            }
        }
    }
  dfs(1);
  dsu::clear();
  memset(tag,-1,sizeof tag);
  for(int i=k+1; i<=k+m; ++i)
    {
      int x=dsu::find(d[i].u),y=dsu::find(d[i].v);
      while(x!=y)
        {
          if(deep[y]>deep[x])
            {
              std::swap(x,y);
            }
          tag[x]=d[i].w;
          dsu::fa[x]=dsu::find(fa[x]);
          x=dsu::fa[x];
        }
    }
  long long ans=0;
  for(int i=2; i<=n; ++i)
    {
      if(!fv[i])
        {
          if(tag[i]==-1)
            {
              ans=-1;
              break;
            }
          ans+=tag[i];
        }
    }
  printf("%I64d\n",ans);
  return 0;
}