CF720 (Div. 2) 题解
[toc]
AC代码
A. Nastia and Nearly Good Numbers
给定正整数 $A,B$ ，询问能否构造一个互不相同的三元组满足：$x+y=z$ 且其中两个数只是 $A,B$ 其中之一的倍数，另一个数则同时为 $A,B$ 的倍数。
$A,B\leq 10^6$ 。
$x=A,y=(2B-1)A,z=2AB$ 。当且仅当 $B=1$ 时无解。
B. Nastia and a Good Array
给定一个大小为 $N$ 的正整数数列 $A$ ，你需要执行以下操作不超过 $N$ 次，使得数列中任意相邻两项互质，操作为：
- 给出一个四元组 $(i,j,x,y)$ ，令 $a_i=x,a_j=y$ ，该四元组必须满足 $\min(a_i,a_j)=\min(x,y)$ 。
$\sum N\leq 2\times 10^5$ 。
我们只需要令 $a_{2k+1}$ 全部变成大质数就行了，因此暴力找到足够的大质数，每次两个两个进行变换 $a_{2k}$ 不变，$a_{2k+1}$ 变成大质数。
C. Nastia and a Hidden Permutation
交互题，你需要通过两种询问来还原一个排列，操作为：
- 询问 $(1,i,j,x)$ ，交互端回答 $\max(\min(a_i,x),\min(a_j,x+1))$ ；
- 询问 $(2,i,j,x)$ ，交互端回答 $\min(\max(a_i,x),\min(a_j,x+1))$ 。
$\sum N\leq 2\times 10^4$ ，询问次数上限 $\lfloor\frac{3n}{2}\rfloor +30$ ，询问时 $i\neq j,1\leq x<n$。
本题关键就是列出每一种不同情况，想清楚再上去写，细节非常多！
可以得到的有用性质：
首先我们先确定某一项的数值，先询问 $(1,i=1,j=2,n-1)$ ，然后根据上方的不同情况分类讨论：
- 返回 $n$ ，此时必然是 $p_2=n$ ；
- 返回 $n-1$ ，有两种情况：$p_1=n$ 或者 $p_1=n-1$ 或者 $p_2=n-1$ ，需要继续询问以确定某一项，需要最多三次询问确定，具体参考代码；
- 返回值 $<n-1$ ，此时必定返回了 $\max(p_1,p_2)$ ，这时我们只需要询问 $(1,i=1,j=2,\max(p_1,p_2)-1)$ 就能确定 $p_1,p_2$ 中的某一项了。
上方最多需要 $3$ 次询问，然后我们考虑剩下的 $n-1$ 个不确定数，如何在 $O(\frac{3n}{2})$ 次询问内确定每一项，注意到上方的询问中，有两类操作可以让我们在一次操作中得到 $p_i,p_j$ 中某一项的具体数值，因此，我们可以根据我们已经得到的这个确定值是否 $>\frac{n+1}{2}$ ，对 $(p_{confirm},p_i)$ 进行询问，$p_{confirm}$ 代表确定值。
假设 $p_{confirm}>\frac{n+1}{2}$ ，那么我们就询问 $(2,i,confirm,1)$ ，这样我们有一半以上的概率可以一次性确定这个数，如果没有确定我们再反向询问即可。
反之亦然。因此总的询问次数是 $O(\frac{3n}{2})$ 的。
D. Nastia Plays with a Tree
给定一棵 $N$ 个节点的无权无向树，你需要执行最少次数的操作将其变成一条链。操作为：
- 选择两个存在连边的节点，断开他们的边；
- 选择两个不存在连边的节点，在他们之间连边。
$\sum N\leq 2\times 10^5$ 。
转化一下题意，实际上就是用最少的不相交链覆盖这棵树的所有节点，这有一个原题 CF618D 。想法是：
贪心地想，我们每一次都要尽可能地消去两个孤立的叶子节点（找到一个链，他的两个端点都是叶子节点），这可以直接dfs，如果找到叶子节点就返回1，然后其根节点的度数-1（根节点的度数最大为2），如果根节点度数归零则说明当前根节点需要与他的祖先断开，用并查集维护连通性即可。
最后构造只需要将dfs过程中得到的所有连通块连起来就行了。