CJ考试题集锦

考试

4.9T2($林克卡特树lct$)

给一颗有负边的树，询问在经过k次割边与任意连上边权为0的边后，链上边权最大和。

此题甚火，正解不敢想象，于是yy一波部分分

• 对于10% 的数据，k = 0 ;
• 对于另外10% 的数据，k = 1 ;
• 对于另外15% 的数据，k = 2 ;
• 对于另外25% 的数据，k <= 100 ;

10pts算法($k<=0$)

树的直径

20pts算法($k<=1$)

枚举割哪条边，分别给割后产生的两颗树算直径，加起来即可
送分结束

35pts算法($k<=2$)

看来是分类讨论啊，然而并不知道应如何讨论（请求大佬的指教QAQ)

60pts算法($k<=100$)

分类讨论到此为止啦，显然只有树形DP才做的动。。。
任意连上边权为0的边？？？这是什么操作？？？这边有意义吗？？？
看来没有啊，那就把它忽略掉吧。
于是，问题就变成了最大化$k+1$条不相交的链的链上边权总和
经典树形DP。
设状态$f[0/1/2][u][k]$表示以u为根的子树（且u的度数为$0/1/2$）中，选k条链的最优解。
顺便加个大前提：强制每个点对应其父边。
我们可以列出几个状态转移方程式：($v\in u的儿子$)($i,j\in(0,k)$)

• 当u点度数为0时，说明这个点不在链上，于是直接合并一下子树里的最优解即可。

  $f[0][u][i]=max(f[0][u][i],f[0][u][j]+f[0][v][i-j]);$

• 当u点度数为1时，说明这个点是一条链的端点，我们分 自己本身有一条链 和 儿子有一条链 两种情况取大即可，若自己本来不在链上，要加上边权。

  $f[1][u][i]=max(f[1][u][i],max(f[0][u][j]+f[1][v][i-j]+e[i].w,f[1][u][o]+f[0][v][i-j]));$

• 当u点度数为2时，说明这个点在一条链中间，我们可以认为这种情况是因 自己和儿子都是一条链的端点 或 自己本来就在一条链中间 而形成的，注意此时第一种情况由于连上当前父子之间的边而多了一条链和一个边权。

  $f[2][u][i]=max(f[2][u][i],max(f[1][u][j]+f[1][v][i-j-1]+e[i].w,f[2][u][j]+f[0][v][i-j]));$

• 还有边界情况（调代码时调出的锅）

• 最后合并答案

  $f[0][u][i]=max(f[0][u][i],max(f[1][u][i-1],f[2][u][i]));$

答案就是$f[0][1][k]$

il void dfs(re int u,re int fa)
{
  f[0][u][0]=f[1][u][0]=f[2][u][0]=0;
  for(re int i=h[u];i+1;i=e[i].next)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u);
      fq(j,k,1)
    {
      f[1][u][j]=max(f[1][u][j],f[0][u][j]+f[1][v][0]+e[i].w);
    fq(o,j-1,0)
    {
      f[0][u][j]=max(f[0][u][j],f[0][u][o]+f[0][v][j-o]);
      f[1][u][j]=max(f[1][u][j],max(f[0][u][o]+f[1][v][j-o]+e[i].w,f[1][u][o]+f[0][v][j-o]));
      f[2][u][j]=max(f[2][u][j],max(f[1][u][o]+f[1][v][j-o-1]+e[i].w,f[2][u][o]+f[0][v][j-o]));
    }
    }
      f[1][u][0]=max(f[1][u][0],f[1][v][0]+e[i].w);
    }
  f[0][u][1]=max(0,f[0][u][1]);
  fp(i,1,k) f[0][u][i]=max(f[0][u][i],max(f[1][u][i-1],f[2][u][i]));
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();k=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi(),w=gi();
      add(u,v,w);add(v,u,w);
    }
  memset(f,-63,sizeof(f));
  k++;dfs(1,0);
  printf("%d\n",f[0][1][k]);
  return 0;
}

100pts算法($k<=3*10^5$)

辛辛苦苦想出的树形DP废了。。。
假如你是个秒出60pts的巨佬，即将AK之时闲来无事输出选了k条链的最优解，你就会发现：最优解数组是一个上凸函数！！！
这个函数以k的值为x轴，以最优解为y轴。
我们想找到的点，就是$(k,best[k])$。
于是考虑用一条直线去切这个函数，由此我们可以枚举一个斜率，用60分的DP来算出切点。（这好像是个套路?)
算出切点后，我们可以根据切点在k的左右，来缩小斜率范围。
二分？于是复杂度降到$O(nlogn)$，皆大欢喜。

struct dat
{
    ll x,y;
    il bool operator < (const dat &o) const {return x==o.x? y>o.y : x<o.x;}
    il dat operator + (const dat &o) const {return (dat){x+o.x,y+o.y};}
    il dat operator + (re int o) {return (dat){x+o,y};}
}dp[3][N];
il dat upd(dat o){return (dat){o.x-mid,o.y+1};}
il void dfs(re int u,re int fa)
{
    dp[2][u]=max(dp[2][u],(dat){-mid,1});
    for(re int i=h[u];i+1;i=e[i].next)
    {
        re int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        dp[2][u]=max(dp[2][u]+dp[0][v],upd(dp[1][u]+dp[1][v]+e[i].w));
        dp[1][u]=max(dp[1][u]+dp[0][v],dp[0][u]+dp[1][v]+e[i].w);
        dp[0][u]=dp[0][u]+dp[0][v];
    }
    dp[0][u]=max(dp[0][u],max(upd(dp[1][u]),dp[2][u]));
}
int main()
{
    memset(h,-1,sizeof(h));
  n=gi();k=gi();++k;
  fp(i,1,n-1)
  {
     re int u=gi(),v=gi(),w=gi();tot+=abs(w);
     add(u,v,w);add(v,u,w);
  }
  l=-tot,r=tot;
  while(l<=r)
  {
      mid=l+r>>1;
      memset(dp,0,sizeof(dp));
      dfs(1,0);
      if(dp[0][1].y<=k) r=mid-1;
      else l=mid+1;
  }
  memset(dp,0,sizeof(dp));
  mid=l;dfs(1,0);
  printf("%lld\n",l*k+dp[0][1].x);
  return 0;
}

4.7T2($社会人socialman$)

一个 n ∗ m 的网格中,任意相邻两格点之间有 p 的概率没有边,1 − p 的概率有一条边。询问（1, 1) 与 (n, m) 连通的概率。

• 对于 70% 的数据,n, m ≤ 4。
  显然可以暴搜，然而我不会。。。
  大部分人都是打表过的，只有巨佬yl秒出正确暴搜，他果然是坠强的。
  本来想每次dfs枚举到右，下两点的边的连通性，觉得这样乘十几下精度起飞就没打。
  发现我傻逼了？？？这样没事？？？
  应该一一枚举边的连通性，若联通则将两端并入并查集（但若本来就在一个并查集就不动）。

struct Data{
    int x, y;
    double p;
    IL int operator <(RG Data B) const{
        if(x != B.x) return x < B.x;
        if(y != B.y) return y < B.y;
        return p < B.p;
    }
};
map <Data, double> mp;
IL int Find(RG int x){
    return fa[x] == x ? x : Find(fa[x]);
}
IL void Dfs(RG int x, RG double s){
    if(Find(num) == Find(1)){
        ans += s;
        return;
    }
    if(x > cnt) return;
    RG int fx = Find(edge[x].u), fy = Find(edge[x].v), tmp = fa[fx];
    if(fx != fy) fa[fx] = fy;
    Dfs(x + 1, s * (1.0 - p));
    if(fx != fy) fa[fx] = tmp;
    Dfs(x + 1, s * p);
}
int main(RG int argc, RG char *argv[]){
    File("socialman");
    for(Input(T); T; --T){
        Input(n), Input(m), scanf("%lf", &p);
        ans = mp[(Data){n, m, p}], cnt = num = 0;
        if(ans != 0){
            printf("%.10lf\n", ans - 1);
            continue;
        }
        for(RG int i = 1; i <= n; ++i)
            for(RG int j = 1; j <= m; ++j)
                id[i][j] = ++num;
        for(RG int i = 1; i <= n; ++i)
            for(RG int j = 1; j <= m; ++j){
                if(i < n) edge[++cnt] = (Edge){id[i][j], id[i + 1][j]};
                if(j < m) edge[++cnt] = (Edge){id[i][j], id[i][j + 1]};
            }
        for(RG int i = 1; i <= num; ++i) fa[i] = i;
        Dfs(1, 1);
        mp[(Data){n, m, p}] = ans + 1;
        printf("%.10lf\n", ans);
    }
    return 0;
}

4.11T1（括号序列再战猪猪侠$brackets$)

题面

已知一个长度为$2n$的括号序列,给了你$m$个信息,第$i$个信息形如$a_i$,$b_i$ ,表示 第$i$个左括号对应的右括号 在 第$j$个左括号对应的右括号的前面,要你还原这个序列。（给出的限制不一定合法）

解析

考虑区间DP。
我们可以设$dp[i][j]$表示为将$[i,j]$这一段区间构成合法括号序列的方案数。
其中$i$表示第$i$个左括号，$j$同理。

如何转移？

看看括号序列的定义($A$、$B$均代表一个合法的括号序列）

• （）是括号序列，表明$dp[i][i]=1$
• （$A$）是括号序列，表明$dp[i+1][j]$可以为$dp[i][j]$贡献方案。此时$A$由$[i+1,j]$构成，转移条件是$[i+1,j]$中没有要求在$i$前面的。
• （$AB$）是括号序列，表明$dp[i+1][k]*dp[k+1][j]$可以为$dp[i][j]$贡献方案。此时$A$由$[i+1,k]$,B由$[k+1,j]$构成，转移条件是$[i+1,j]$中没有要求在$i$前面的、$[k+1,j]$中没有要求比$[i+1,j]$中某个早的，$[k+1][j]$中没有要求比$i$早的。

如何快速判断限制条件？

可以用$sum[a_i][b_i]=1$表示限制条件。
然后像处理矩阵一样维护二维前缀和。
这样就可以$O(1)$查询限制条件了。
举个栗子，要查询$[i+1,j]$中有没有要求在$i$前面的点，只需要查询一下左上角为$(i,i+1)$,右下角为$(i,j)$中的矩阵有没有值即可。
横坐标代表在前面那个区间，纵坐标代表在后面那个区间（就像你一开始赋值时的意义一样）。
于是，把两维交换一下就可以表示XX在XX后面。

如何处理不合法条件?

两种情况：

• $a_i=b_i$,开头特判（不过谁想得到呢）
• $a_1=1,b_1=2;a_2=2,b_2=3;a_3=3,b_3=1$云云，发现无法转移

il int check(re int A,re int B,re int C,re int D)
{
  return a[C][D]-a[A-1][D]-a[C][B-1]+a[A-1][B-1];
}
il ll DP()
{
  fp(i,1,n)
    if(check(i,i,i,i)) return 0;
  memset(dp,0,sizeof(dp));
  fq(i,n,1)
    {
      dp[i][i]=1;
      fp(j,i+1,n)
    {
      if(!check(i,i+1,i,j)) (dp[i][j]+=dp[i+1][j])%=mod;
      if(!check(i+1,i,j,i)) (dp[i][j]+=dp[i+1][j])%=mod;
      fp(k,i+1,j-1)
        if(!check(i,i+1,i,k)&&!check(k+1,i,j,i)&&!check(k+1,i+1,j,k))
          (dp[i][j]+=dp[i+1][k]*dp[k+1][j]%mod)%=mod;
    }
    }
  return dp[1][n];
}
int main()
{
  T=gi();
  while(T--)
    {
      memset(a,0,sizeof(a));
      n=gi();m=gi();
      fp(i,1,m)
    {
      re int u=gi(),v=gi();
      a[u][v]=1;
    }
      fp(i,1,n)
    fp(j,1,n)
    a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
      DP();
      printf("%lld\n",DP());
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

4.11T3$tower$

题面

你要用$n$个积木拼成一个塔,第$i$个积木长度是$a_i$ 。
给定$D$,积木$i$能搭在积木$j$上面,当且仅当$a_i−a_j<=D$。
求合法的搭积木方案数。

• 对于45%,有$n≤20$
• 对于100%,有$n≤700000$

解析

45pts算法

直接状压DP，状态为$f[i][j]$表示$i$状态下最底下为第$j$个积木的方案数。

100pts算法

我们都把题目想复杂了
需要一个很显然的性质：假设一个塔合法,去掉他的最长的积木后还是合法的。
于是，我们设$dp[i]$表示选前$i$块积木搭塔的方案数。
sort一边$a[i]$,从$1$枚到$n$,看他能加到以哪些积木结尾的塔中。

int main()
{
  n=gi();d=gi();
  fp(i,1,n) a[i]=gi();
  sort(a+1,a+1+n);
  dp[1]=1;
  for(re int i=2,pos=1;i<=n;i++)
    {
    while(pos<i&&a[i]-a[pos]>d) ++pos;
  dp[i]=dp[i-1]*(i-pos+1)%mod;
    }
  printf("%lld\n",dp[n]);
  return 0;
}

4.11T2$match$

题面

有$n$个人来参加比赛,要求进行恰好$m$轮,要你规划比赛方式。
允许出现$m$轮后有多人胜利的情况,即我们并不需要决出冠军。
一轮比赛可以这么理解:假设当前还剩$n$个人,我们把$n$个人分成若
干份（强制连续分组）,但不允许某一份只有一个人(因为不能不战而胜),然后每一份的人
就会进行比赛,最后只会留下一个人晋级。
那么给定$n$,$m$,要你求合法的比赛过程的方案数。

• 对于 40% 的数据,保证$n\leq 20$
• 对于 70% 的数据,保证$n\leq1000$
• 对于 100% 的数据,保证$n\leq10^{15}$

解析

40pts算法

预处理$a[i][j]$表示$i$个人分为$j$组的方案数，枚举当前分为几组，直接暴搜即可。

cf[0]=1;
  fp(i,1,n) cf[i]=(cf[i-1]<<1)%mod;
  fp(i,2,n) a[i][1]=1;
  fp(i,4,n) a[i][2]=i-3;
  fp(i,3,n/2)
    fp(j,4,n)
    fp(k,2,j-2)
    (a[j][i]+=a[j-k][i-1])%=mod;

Update:
我原来打的是$O(n^3)$的预处理，现在来普及一下$O(n^2)$
$f_{i,j}$实际表示将$i$拆分为$j$个大于等于$2$的整数的方案数。
转移考虑其是 与前面的合并 还是新建一组
$f_{i,j}=f_{i-1,j}+f_{i-2,j-1}$

70pts算法

加个记忆化
不过我要吐槽一下，我连暴搜都不会
某智障原来考场爆零写法

il ll dfs(re ll n,re ll k,re ll tot)
{
  if(n<cf[k]) return 0;
  if(!k||n==cf[k]) return tot;
  if(dp[n][k]) return dp[n][k];
  re ll res=0;
  fp(i,1,n/2)
    (res+=dfs(i,k-1,tot*a[n][i]%mod))%=mod;
  return dp[n][k]=res;
  }

递归的本质是将当前问题化为更小的子问题，返回的也是子问题结果。
结果我在最小的子问题返回tot？？？
如dfs返回值，我们应该在最小问题下返回$1$,然后只在对应大问题层面乘上值，为了合并答案。
如不返回，才可以一直乘到底，为了统计答案。

il ll dfs(re ll n,re ll k)
{
  if(n<cf[k]) return 0;
  if(!k||n==cf[k]) return 1;
  if(dp[n][k]) return dp[n][k];
  re ll res=0;
  fp(i,1,n/2)
    (res+=a[n][i]*dfs(i,k-1)%mod)%=mod;
  return dp[n][k]=res;
}

100pts算法

发现$n$很大，$m$很小，因此，我们考虑n递增，进行矩阵加速。
假设当前加入人$i$，对于之前的$i−1$个人
考虑第$i−1$个人参加的每组比赛，假设已经超过了两个人则将这组比赛设为$1$，否则则是$0$
那么，第$i$个人添加到这组序列中，它能够改变一些比赛的状态
$i$可以添加到从第一轮开始，连续的超过两个人对决中的任意一个，此时相当于后面的若干轮的状态不变
$i$也可以新开一组，使得最低那轮的0可以变成1
这样子我们发现状态是$2^m$的，可以矩阵快速幂转移。
我还是很懵逼啊

struct Matrix
{
    int s[100][100];
    void clear(){memset(s,0,sizeof(s));}
    int * operator [](int x){return a[x];}
    void init(){clear();for(int i=0;i<=N;++i)s[i][i]=1;}
}A,B;
Matrix operator*(Matrix a,Matrix b)
{
    Matrix c;c.clear();
    for(int i=0;i<=N;++i)
        for(int j=0;j<=N;++j)
            for(int k=0;k<=N;++k)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%MOD;
    return c;
}
Matrix fpow(Matrix a,ll b)
{
    Matrix s;s.init();
    while(b){if(b&1)s=s*a;a=a*a;b>>=1ll;}
    return s;
}
int main()
{
    cin>>n>>m;N=1<<m;--N;
    A.s[0][0]=1;
    for(int i=0;i<=N;++i)
        for(int j=0;j<m;++j)
        {
            int x=i|(1<<j);x^=(1<<j)-1;
            B.s[i][x]++;
            if(!(i&(1<<j)))break;
        }
    B.s[N][0]+=1;
    B=fpow(B,n-1);A=A*B;
    printf("%d\n",A.s[0][N]);
    return 0;
}

4.7T1贪婪人$greedhead$

题面

$H$行$W$列的网络中,每个格子有权值。要从最左上角的格子走到最右下角的格子,每次只能向下或者向右行走。一条合法路径的权值为路过所有格子的权值之和。
$Antetokunompo$每次会选择权值较大的格子走过去。如果右侧与下侧格子权值相同,则会向右走。如果已经走到了网络的下边界或者右边界,则$Antetokunompo$会向终点方向行走。
已知网络左上角格子权值为$0$,其他格子的权值范围在$[0,S]$中,都为整数。求有多少种不同的网络,$Antetokunompo$走过的路径权值恰好为$S$。

• 对于 70% 的数据,$H,W\leq100$。
• 对于 100% 的数据,$H,W\leq2500,S\leq100$。

解析

考场直接爆零，我果然好菜啊

如何设状态

设$f[x][y][w]$表示在$n*m$的网格中路径权值为$w$的方案数

边界

• 这是带值$DFS$，我们应该在满足条件的最终状态返回$1$
• 为区分$0$和没走过，$f$初始状态为$-1$

如何转移

• 当该点在最底下一层时，其会无条件向右走
  所以走后其正上方$n-1$层的点会有$(S+1)^{n-1}$种方案
• 当该店在最右边一层时，其会无条件往下走
  所以走后其正左方$m-1$层的点会有$(S+1)^{m-1}$种方案
• 当其不在边界时
  它可以向右走，开始和在边界的处理相同。
  但是此时其下面的点会有限制，而我们第一次到达这一列时已经认为该点有$S+1$种方案。
  所以我们应该除个$S+1$，再乘上下面那个点在当前限制下的方案数。
  向下走同。

il ll dfs(re int x,re int y,re int z)
{
  if(~f[x][y][z]) return f[x][y][z];re ll res=0;
  if(x==n)
    {
      fp(i,z,S)
    (res+=dfs(x,y+1,i)*c[n-1])%=mod;
      return f[x][y][z]=res;
    }
  if(y==m)
    {
      fp(i,z,S)
    (res+=dfs(x+1,y,i)*c[m-1])%=mod;
      return f[x][y][z]=res;
    }
  fp(i,z,S) 
  (res+=dfs(x,y+1,i)*c[x-1]%mod*(i-z+1)%mod*c[mod-2]%mod)%=mod;
  fp(i,z+1,S) 
  (res+=dfs(x+1,y,i)*c[y-1]%mod*(i-z)%mod*c[mod-2]%mod)%=mod;
  return f[x][y][z]=res;
}
int main()
{
  n=gi();m=gi();S=gi();
  c[0]=1;fp(i,1,mod) c[i]=c[i-1]*(S+1)%mod;
  memset(f,-1,sizeof(f));
  memset(f[n][m],0,sizeof(f[n][m]));
  f[n][m][S]=1;
  printf("%lld\n",dfs(1,1,0));
  return 0;
}