吐槽

90+0+90

这套题……数据好弱，我两个错误算法出题人居然每个只卡了10pts……

题解

T1 合并奶牛

官方题解没看懂……自己瞎搞出了一个做法。

设$f[i][j]$表示第一个序列取前$i$个，第二个序列取前$j$个构成的序列的方案数。

假设所有数互不相同，那么显然

$$f[i][j]=f[i-1][j]+f[i][j-1]$$

考虑如何去重。先放式子

f[i][j]=f[i−1][j]+f[i][j−1]−∑a[i−k+1,i]=b[j−k+1,j]f[i−k][j−k]×cat[k−1] f[i][j]=f[i-1][j]+f[i][j-1]-\sum_{a[i-k+1,i]=b[j-k+1,j]} f[i-k][j-k]\times cat[k-1] f[i][j]=f[i−1][j]+f[i][j−1]−a[i−k+1,i]=b[j−k+1,j]∑​f[i−k][j−k]×cat[k−1]

其中$cat$表示卡特兰数，第$0$项到第$4$项分别为$1,1,2,5,14$。

如何证明？

显然对于两个序列都相同的情况，可以钦定第一个取走的个数一定大于第二个，可以转化成括号序列问题，那么答案就是$cat[n]$。

类似上面的情况，对于两个相等的部分，假设长度最长的公共部分长度为$L$，那么要去重就是这长度$L$用括号序列来保证没有重复。

那么上面减去的那个$\sum$后面的部分就是枚举括号序列的断点，使得后面的括号序列不可能产生合法的端点，假设为$k$，那么后面部分的方案数就是$cat[k-1]$，而前面部分的方案数就是$f[i-k][j-k]$，由于前面加的部分的特性使得不合法的方案必定等于合法的方案，因此上面式子是对的。

时间复杂度看起来像O(n3)O(n^3)O(n3)，但是实际上是O(n2)O(n^2)O(n2)的。（然而这个写法在时间空间代码量三个方面踩了标算）

T2 寻找规律

不会，会了再来填坑。

T3 牛奶装瓶

一种奇怪的线段树，整除直接除，有一个优化就是当一段区间的⌊maxv⌋=⌊minv⌋\lfloor\frac{max}{v}\rfloor =\lfloor\frac{min}{v}\rfloor⌊vmax​⌋=⌊vmin​⌋时直接变成区间加法。

底下的代码有一个非常奇怪的cov标记，不要管，那是我90pts代码的一部分……

代码

T1 合并奶牛

#include 
    
     #include 
     
      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=2000;const int mod=998244353;int n,a[maxn+10],b[maxn+10],f[maxn+10][maxn+10],cat[maxn+10];int main(){
      freopen("merge.in","r",stdin);  freopen("merge.out","w",stdout);  n=read();  for(int i=1; i<=n; ++i)    {
          a[i]=read();    }  for(int i=1; i<=n; ++i)    {
          b[i]=read();    }  cat[0]=1;  for(int i=1; i<=n; ++i)    {
          for(int j=0; j
      
       =mod)            {
                  f[i][j]-=mod;            }          for(int k=1; k<=std::min(i,j); ++k)            {
                  if(a[i-k+1]!=b[j-k+1])                {
                      break;                }              f[i][j]=(f[i][j]-1ll*cat[k-1]*f[i-k][j-k])%mod;              if(f[i][j]<0)                {
                      f[i][j]+=mod;                }            }        }    }  printf("%d\n",f[n][n]);  return 0;}
      
     
    

T3 牛奶装瓶

#include 
    
     #include 
     
      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=100000;const int inf=0x7fffffff;int n,q,st[maxn+10];int divide(int x,int y){
      if(x<0)    {
          return (x-y+1)/y;    }  return x/y;}namespace sgt{
      long long sum[maxn<<2];  int icov[maxn<<2],cov[maxn<<2],mn[maxn<<2],mx[maxn<<2],adt[maxn<<2];  int tl[maxn<<2],tr[maxn<<2];  int putadt(int x,int l,int r,int v)  {
        sum[x]+=1ll*(r-l+1)*v;    if(icov[x])      {
            cov[x]+=v;      }    else      {
            adt[x]+=v;      }    mn[x]+=v;    mx[x]+=v;    return 0;  }  int putcov(int x,int l,int r,int v)  {
        adt[x]=0;    icov[x]=1;    cov[x]=v;    sum[x]=1ll*(r-l+1)*v;    mn[x]=mx[x]=v;    return 0;  }  int pushdown(int x,int l,int r)  {
        int mid=(l+r)>>1;    if(icov[x])      {
            putcov(x<<1,l,mid,cov[x]);        putcov(x<<1|1,mid+1,r,cov[x]);      }    else      {
            putadt(x<<1,l,mid,adt[x]);        putadt(x<<1|1,mid+1,r,adt[x]);        adt[x]=0;      }    return 0;  }  int updata(int x)  {
        sum[x]=sum[x<<1]+sum[x<<1|1];    mn[x]=std::min(mn[x<<1],mn[x<<1|1]);    mx[x]=std::max(mx[x<<1],mx[x<<1|1]);    if(mn[x]==mx[x])      {
            icov[x]=1;        cov[x]=mn[x];      }    else      {
            icov[x]=0;      }    return 0;  }  int build(int x,int l,int r)  {
        if(l==r)      {
            putcov(x,l,r,st[l]);        return 0;      }    int mid=(l+r)>>1;    build(x<<1,l,mid);    build(x<<1|1,mid+1,r);    tl[x]=l;    tr[x]=r;    updata(x);    return 0;  }  int getmin(int x,int l,int r,int askl,int askr)  {
        if((askl<=l)&&(r<=askr))      {
            return mn[x];      }    pushdown(x,l,r);    int mid=(l+r)>>1,res=inf;    if(askl<=mid)      {
            res=std::min(res,getmin(x<<1,l,mid,askl,askr));      }    if(mid
      
       >1;    long long res=0;    if(askl<=mid)      {
            res+=getsum(x<<1,l,mid,askl,askr);      }    if(mid
       
        >1;    if(askl<=mid)      {
            add(x<<1,l,mid,askl,askr,v);      }    if(mid
        
         =-1)&&(mx[x]<=0))      {
            return 0;      }    if((askl<=l)&&(r<=askr)&&(icov[x]))      {
            putcov(x,l,r,divide(cov[x],v));        return 0;      }    if((askl<=l)&&(r<=askr)&&(divide(mx[x],v)-mx[x]==divide(mn[x],v)-mn[x]))      {
            putadt(x,l,r,divide(mx[x],v)-mx[x]);        return 0;      }    pushdown(x,l,r);    int mid=(l+r)>>1;    if(askl<=mid)      {
            div(x<<1,l,mid,askl,askr,v);      }    if(mid