写在前面

终于站在了这个考场上，然而等待着我的是什么呢？

不如就此给自己一个解脱。

写题的稿纸，拿来水水题解可能不错？

题号就不写了，自己猜吧。

写在前面

最后一届 $NOIP$。

没有退路了。

$18Michael$ 搞的题目集锦，刷刷看？

以下均为一句话题解，加 $*$ 表示看了题解的部分。

$Link$

有一棵 $n$ 个节点的树，每条边都被染成黑色或白色，一开始所有的边都是白色。

有 $m$ 次操作，每次操作为以下两种操作之一：

• 给定两个点 $u,v$，对于 $u,v$ 间的路径上的所有的点 $x$（包括 $u$ 和 $v$），把所有和 $x$ 相邻的边染成白色，然后再把 $u,v$ 间的路径上所有的边染成黑色。
• 给定两个点 $u,v$，问 $u,v$ 间的路径上有几条黑色的边。

$T$ 组数据。

$T\le3,1\le n,m\le10^5$。

$Link$

你有 $m$ 个数，值域为 $[1,k]$，其中数 $i$ 有 $a_i$ 个。

你需要构造最小的 $n\times n$ 矩阵，其中包含这 $m$ 个数，剩下的位置为 $0$，并且对于任意的 $2\times2$ 子矩阵：

• 不是 $0$ 的位置数不超过 $3$。
• 对角线上的两个数不同。

$t$ 组数据，输出方案。

$1\le t\le10^4,1\le m,k\le10^5,\sum m,k\le2\times10^5$。

$Link$

你有一棵 $n$ 个点的树，每次操作你可以删除一条边，再添加一条边（删边加边合起来算一种操作）。

问最少需要多少次操作，可以让这棵树变成一条链，输出方案。

$t$ 组数据。

$1\le t\le10^4,2\le n\le10^5,\sum n\le2\times10^5$。

$Link$

本题是一道交互题。

有一个长度为 $n$ 的排列，你有两种询问：

• $\max(\min(x,p_i),\min(x+1,p_j))$。
• $\min(\max(x,p_i),\max(x+1,p_j)$。

其中 $x,i,j$ 由你决定，需要满足 $i\not=j,1\le x\le n-1$。

你可以做出最多 $\lfloor\frac{3n}{2}\rfloor+30$ 次询问，并确定这个排列每个位置上的数。

共有 $t$ 组数据。

$1\le t\le10^4,3\le n\le 10^4,\sum n\le2\times10^4$。

写在前面

啊哈垃圾 $Vxlimo$ 今年第二次参加同步赛！

对同步赛！（ $NOIP$ 又只有二等的屑

知乎：如何评价 $FJOI2021$？ $Vxlimo$ 的回答

$Link$

给定一个 $n$ 个点 $m$ 条边的简单无向连通图，其中图的前 $n-1$ 条边构成了图的一棵生成树。

你需要为每条边分配一个范围在 $[1,m]$ 的权值，且每种权值只能用一次。

定义一种分配方案的得分是这个图的最小生成树的权值和。

求所有可能的分配方案中，前 $n-1$ 条边是图的最小生成树的方案的得分和，对 $10^9+7$ 取模。

$2\le n\le20,n-1\le m\le\frac{n(n-1)}{2}$。