写在前面

最后一届 NOIP。

没有退路了。

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

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

Link

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

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

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

T 组数据。

T≤3,1≤n,m≤105。

Link

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

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

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

t 组数据，输出方案。

1≤t≤104,1≤m,k≤105,∑m,k≤2×105。

Link

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

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

t 组数据。

1≤t≤104,2≤n≤105,∑n≤2×105。

Link

本题是一道交互题。

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

• max(min(x,pi),min(x+1,pj))。
• min(max(x,pi),max(x+1,pj)。

其中 x,i,j 由你决定，需要满足 i≠j,1≤x≤n−1。

你可以做出最多 ⌊3n2⌋+30 次询问，并确定这个排列每个位置上的数。

共有 t 组数据。

1≤t≤104,3≤n≤104,∑n≤2×104。

写在前面

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

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

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