T1 T2 T3 T4 普及+/提高{\color{#52C41A} 普及+/提高}普及+/提高 提高+/省选−{\color{#3498DB} 提高+/省选− }提高+/省选− 省选/NOI−{\color{purple} 省选/NOI−}省选/NOI− NOI/NOI+/CTSC{\color{black} NOI/NOI+/CTSC }NOI/NOI+/CTSC
参赛网址：https://oj.33dai.cn/d/TYOI/contest/6899b750c5d9c2f14c1fd4cb
T1 小明与魔法【NOIP2025模拟赛T1】
题目传送门
题目难度：普及+/提高{\color{#52C41A} 普及+/提高}普及+/提高
算法标签：贪心
思路
> 特殊性质 AAA：存在 1≤i≤n1\le i\le n1≤i≤n，使得对任意 1≤j≤n1\le j\le n1≤j≤n，均有 ci,j=1c_{i,j}=1ci,j =1。
子问题 α\alphaα：当 特殊性质 AAA 的约束下，即至少有 111 行全是 111，所以可以直接用这一行去补全不是全 111 的列。
然后，在一般情况，我们考虑构造 全 111 行。
对于任意一行，每一个 000 都需要 111 次代价修改为 111。如上图。
可能有点难，就是让所有的0都通过转换制度变为1。
所以枚举每一行，然后判断每一行的 000 的个数，取最小值后转化成了 子问题 α\alphaα。我们就做完了
95 WRONG ANSWER
吗？
我们发现，当这一行全是 000 时，答案 ++++++。
AC CODE
T2 小明去旅游 6【NOIP2025模拟赛T2】
题目传送门
题目难度：提高+/省选−{\color{#3498DB} 提高+/省选− }提高+/省选−
算法标签：DP，树上DP
思路
算法选择：贪心，DP
很明显，如果是贪心，正常的 出题人会使 1≤k≤1051 \le k \le 10^51≤k≤105。
所以开始 DPDPDP。
考虑 dpi,j,0dp_{i,j,0}dpi,j,0 表示 iii 的子树中选 jjj 个连通块并且 iii 不在其子树的任意一个连通块里。
dpi,j,1dp_{i,j,1}dpi,j,1 表示 iii 的子树中选 jjj 个连通块并且 iii 在其子树的一个连通块里。
然后考虑：
* 开始状态：$\forall i \in [1,n] $ 满足 iii 是叶节点的 $ dp_{i,0,1}=0$
* 答案：∀i∈[1,n]\forall i \in [1,n]∀i∈[1,n] 满足 iii 不是叶节点的都可以是根，在开始是给定 rootrootroot
AC CODE
