=====A - Captain Flint and Crew Recruitment=====

====问题描述====

给出一个$n$，问$n$能不能分成四个不同的数，其中至少三个是伪质数，伪质数指存在质数$p,q$满足$p < q$且$p \times q = x$的$x$，如果可以构造方案

====数据范围====

多组数据，$1 \le T \le 1000$，$1 \le n \le 2 \times 10^5$

====解题思路====

最小的三个伪质数是6，10，14，所以30以下的肯定不可以，30以上的除了36，40，44一定可以因为可以分成6、10、14和一个与它们都不同的数，我们再单独特判这三个数的构造方案即可

=====B - Captain Flint and a Long Voyage=====

====问题描述====

定义$f(x)$为把$x$的每一位数字写成二进制并把这些二进制依次接起来，例如$f(729)=111101001$，现在要求一个最小的$x$，使得它是一个$n$位十进制数且$f(x)$去掉后$n$位以后最大

====数据范围====

多组数据，$1 \le T \le 1000$，$1 \le n \le 10^5$，$\sum n \le 2 \times 10^5$

====解题思路====

首先$f(x)$要尽量位数多，所以$x$中一定不是8就是9，又因为要最小化$x$，所以要尽量放8，所以我们尽量把8放后放使得它们贡献出的二进制会因为在后$n$位去掉即可，具体来说是放$(n / 4) + (n\ mod\ 4 != 0)$个8，前面都放9

=====C - Uncle Bogdan and Country Happiness=====

====问题描述====

一个国家有$n$个城市，它们组成一棵树，有$m$个公民，他们都在1号节点上班，下班后他们会沿着最短路径回到自己居住的城市。每个城市都有一个心理医生，他们会观察所有在下班途中经过这个城市的公民并计算出$h_i$代表其中高兴的人数量减去不高兴的人数量的值，已知所有公民在回家途中心情都有可能变坏且一旦变坏就不会变好，初始情况（即所有人都在1号节点）未知，给出一组$h_1$到$h_n$，询问这组数据是否可能有错

====数据范围====

多组数据，$1 \le T \le 10000$，$1 \le n \le 10^5$，$\sum n \le 2 \times 10^5$，$1 \le m \le 10^9$，$-10^9 \le h_i \le 10^9$

====解题思路====

通过经过某个点的人数和它的$h_i$我们可以算出这个点有多少个人高兴多少个人不高兴，只要这个点高兴的人数大于等于它所有子节点高兴的人数即可，所有点都满足就说明数据没有错，另外还有一些细节要处理，但是不难

=====D - Captain Flint and Treasure=====

====问题描述====

有两个长度为$n$的数组$a,b$，每次可以对某一个位置$i(1 \le i \le n)$进行操作，获得$a_i$分，并且如果$b_i \ne -1$，则$a_{a_{b_i}} += a_i$，要求对每个位置做恰好一次操作，最大化得分并且构造出操作方式，要注意保证按照$i \rightarrow b_i$的顺序走不会成环，一定会走到一个-1

====数据范围====

$n \le 2 \times 10^5$，$-10^6 \le a_i \le 10^6$，$b_i = -1$或$1 \le b_i \le n$

====解题思路====

我们每次把点$i$作为点$b_i$的儿子（$b_i \ne -1$时），由题目保证可知我们得到了一个森林，按照贪心的想法，我们dfs两次，第一次从下往上，一旦找到正的值就取并且把它的值累加到父亲，遇到负的就不管，第二次从上往下，遇到负的就取，这样一定可以使结果最优，至于输出方法直接在取得时候放到栈里最后输出即可

<del>E没看懂</del>