初三奥赛模拟测试2

初三奥赛模拟测试2

\(T1\) 南 \(0pts\)

• 原题： luogu P4550 收集邮票

\(T2\) 昌 \(0pts\)

• 原题： CF1153D Serval and Rooted Tree
• 部分分
  • \(20pts\) ：生成 \(1 \sim k\) 的所有全排列依次填给叶节点，枚举每种情况即可。
• 正解

  • 设 \(g_{x}\) 表示第 \(x\) 个节点的权值，容易发现 \(\begin{cases} (\sum\limits_{y \in Son(x)}[g_{y} \ge g_{x}]) \ge 1 & a_{x}=1 \\ (\sum\limits_{y \in Son(x)}[g_{y} \ge g_{x}])=dout_{x} & a_{x}=0 \end{cases}\) ，即当 \(a_{x}=0\) 时，其所有子节点的权值都会影响该节点的值；当 \(a_{x}=1\) 时，可选择任意一个满足 \(g_{y} \ge g_{x}\) 的子节点来影响该节点的值。

  • 设 \(f_{x}\) 表示最少有多少个叶节点会影响第 \(x\) 个节点的值，状态转移方程为 \(f_{x}= \begin{cases} 1 & dout_{x}=0 \\ \min\limits_{y \in Son(x)} \{ f_{y} \} & dout_{x} \ne 0,a_{x}=1 \\ \sum\limits_{y \in Son(x)}f_{y} & dout_{x} \ne 0,a_{x}=0 \end{cases}\) 。

  • 对于影响第 \(1\) 个节点的 \(f_{1}\) 个叶节点，选择 \((k-f_{1}+1) \sim k\) 将其填入即可；又因为这 \(f_{1}\) 个节点的权值必须 \(\ge g_{1}\) ，故有 \(\max \{ g_{1} \}=k-f_{1}+1\) 。

    点击查看代码

    struct node
    {int nxt,to;
    }e[600010];
    int head[600010],a[600010],f[600010],dout[600010],cnt=0;
    void add(int u,int v)
    {cnt++;e[cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt;
    }
    void dfs(int x)
    {   f[x]=(dout[x]==0)?1:(a[x]==1?0x7f7f7f7f:0);for(int i=head[x];i!=0;i=e[i].nxt){dfs(e[i].to);f[x]=(a[x]==1)?min(f[x],f[e[i].to]):f[x]+f[e[i].to];    }
    }
    int main()
    {int n,k=0,u,v,i;cin>>n;for(i=1;i<=n;i++){cin>>a[i];}for(i=2;i<=n;i++){cin>>u;v=i;add(u,v);dout[u]++;}for(i=1;i<=n;i++){k+=(dout[i]==0);}dfs(1);cout<<k-f[1]+1<<endl;return 0;
    }
    

\(T3\) 起 \(0pts\)

• 部分分
  • \(Subtasks1(1pts)\)
    • 由于 \(n=1\) ，故不存在合法的衣服。
    • 对于每组询问输出 0 即可。

\(T4\) 义 \(0pts\)

• 原题： LibreOJ 6089. 小 Y 的背包计数问题

总结

后记