胡萝卜
不难发现无论发了多少根胡萝卜，所有兔子的期望体重之比都是恒定的，所以可以直接计算。
std：https://questoj.cn/submission/866
乘积的和
算法1
把这个矩阵先填出来再计算。
时间复杂度$O(nm)$，期望得分$30\rm{pts}$.
算法2
考虑如何由第$i$行的答案去推第$i+1$行的答案，发现只有两个数发生了修改，暴力做修改即可。
时间复杂度$O(m+n\log n)$或者$O(m+n)$，期望得分$70\rm{pts}$.
算法3
把最后的答案直接写出来：
$$ \begin{aligned} \rm{Answer}=&\sum{i=1}^n\frac{(m+i)!}{i!}\ =&m!\sum{i=1}^n \dbinom{m+i}{i}\ =&m!(\sum_{i=0}^n \dbinom{m+i}{i}-1)\ =&m!(\dbinom{n+m+1}{n+1}-1) \end{aligned} $$
这个组合数是可以在$O(m)$的时间内做出来的，故总时间复杂度是$O(m)$的，期望得分$100\rm{pts}$.
std：https://questoj.cn/submission/865
写规划
算法1
暴力枚举全排列/写一个状压dp，期望得分$10\rm{pts}$或$20\rm{pts}$.
算法2
考虑$k=n$的部分分。本质上$p$就是$1$到$n$的排列。
首先要发现一个性质：对于树上的三个点$u,v,w$, 有$\mathrm{dis}(u,v)\leq \mathrm{dis}(u,w)+\mathrm{dis}(v,w)$.
那么对于所求就有$\mathrm{Answer}\leq 2\sum_{i=1}^n\mathrm{dis}(i,u)$, 其中$u$是树上某个点。
注意到在树上使$\sum_{i=1}^n\mathrm{dis}(i,u)$最小的$u$就是树的重心，接下来如果我们能证明在$u$取重心的时候原不等式可以取等，那么我们就找到了$\mathrm{Answer}$的一个最大值。
证明的话考虑直接构造，我们以重心为根，只要保证相邻的$p_i$不在同一棵子树即可，然后我们又知道以重心为根的子树的$\mathrm{size}\leq\lfloor \frac{n}{2}\rfloor$，于是这样的排列一定是存在的。
总时间复杂度是$O(n)$的，能通过第$5$个$\rm{subtask}$.
算法3
直接计算原式的值显然不成立，我们考虑计算每条边经过的次数。
记$f_{u,i}$为以$u$为根的子树已经选取了$i$个点时的答案最大值，那么对于一条边$(u,v)$就要去考虑如何合并$dp$值，类似于算法2，我们可以让点在子树内外反复横跳来达到最大值，更具体的，这条边的最大经过次数就是$2w\times \min(j,k-j)$）（其中$j$为在子树$v$中选取的点数），时间复杂度是$O(n^3)$，期望得分$80\rm{pts}$.
并不存在的算法4
什么你居然不知道树形背包的复杂度是$O(n^2)$的？好的你现在知道了。
什么你问我为什么不出到$1\leq n\leq 5000$？你以为我会告诉你原本就是$5000$然后出题人发现long long运算的常数巨大才换成$2000$的么。
std：https://questoj.cn/submission/862
后记
验题的时候，好哥哥limstash一眼秒了这个题。于是出题人就想把这个题出成二合一，不过后来考虑到这场比赛主打的是小清新风格就作罢了（好吧事实是出题人直到比赛前两天才编出了$k=n$的部分分做法，不过相比于套路的tree dp我更喜欢这个更有思维难度的做法，但是发现后两个题都是思维题于是就放了这个套路题上去，求轻喷qwq.）
取石子游戏
（以下题解默认大家都已了解SG函数的相关知识，如有不了解的请自行百度，当然这个题需要的只是相当基础的知识了）
算法1
根据SG函数的那一套理论，我们需要知道每一堆石子的SG值，再将它们异或起来就完事了。
继续根据SG函数的那一套理论，大小为$a$的石子的SG值就是$a\%(x+1)$，这个由归纳法不难证得。
于是就有了一个$O(n^2)$的暴力枚举的做法了，期望得分$25\rm{pts}$.
算法2
根据异或的那一套理论，我们发现对于一些有着相同数目的石子的堆而言，假设有$p$堆，那么这$p$堆等价于$p\%2$堆同样数目的石子。
这样的话对于$a_i$均相同的数据，我们在枚举$x$的同时最多只需要计算$1$堆的SG值了，结合算法1期望得分为$32\rm{pts}$.
算法3
考虑一下这个题的本质：对每个$1\leq x\leq n$的正整数$x$，求$\oplus_{i=1}^na_i\%(x+1)$,其中$\oplus$为异或运算。
考虑如何加速这个计算过程，枚举$x$显然是无法避免的，但是之后枚举每一个位置显然很呆，考虑如何优化掉这部分。
记$y=x+1$，注意到对于$a_i\in[ky,(k+1)y)$中的$a_i$，它$\%y$的值就是$a_i-ky$，这启示我们可以将在这一个区间的数一起做，这样的话时间复杂度就是调和级数了，也就是$O(n\log n)$.
光枚举值域显然是不够的，我们还需要快速得到我们所枚举的每一个区间的数的异或值。如何快速得到不带修改的区间相关的信息呢？也许有什么高超的数据结构，但是这里简单的倍增就行了。
先按照算法2所述处理掉相同的$ai$，接下来仿照st表，我们记$f{p,i}$表示那些值在区间$[i,i+2^p-1]$中的数的异或和。计算$f_{p,i}$的话，首先$p-1$位上的贡献只取决于$[i,i+2^p-1]$的后半个区间上是否有数，剩下的位的贡献显然可以从两个子区间上继承。
那么对于一个询问$[l,r]$，我们直接倍增的跳左端点，同时记录下那些有用的高位的值即可，具体实现请参照std.总时间复杂度为$O(n\log^2 n)$
std：https://questoj.cn/submission/857
红黑图
算法0
直接提交sample_tree.cpp，期望得分$0\rm{pts}$.
算法1
利用$O(n^2)$个询问得到所有边的颜色，再使用一些方法找一棵符合条件的生成树即可，期望得分$25\rm{pts}$.
算法2
边不相交这个条件用文字阐述十分麻烦，注意到正如题面所述，这个条件等价于将所有点按顺序排列在圆周上，再按照树连边，要求所有的边互不相交。
注意到这个圆周就是一个天然的符合条件的结构，于是我们先把圆周问一遍，如果只有至多一条边不同色那么就已经找到了一组合法解。
当无法找到一组合法解的时候，肯定存在一个点$u$，满足与它相关的两条边$(u,v_1),(u,v_2)$是两条颜色不一样的边。考虑一个环向内坍缩的过程，即我们在环上删去边$(u,v_1),(u,v_2)$，再加上边$(v_1,v_2)$。我们得到的新图一定还是个环，假设在这个环上有一棵合法的生成树，接下来只要考虑如何利用这棵树来构造答案，也就是如何把$u$连向这棵生成树。这其实十分easy，考虑一下我们删去的两条边，它们一定不和当前的生成树相交，我们只要找到与生成树同色的那条边就可以了。
如果新环上仍然没有我们所需要的生成树，我们可以按照上述过程递归下去，不难发现我们的访问边均是互不相交的。
询问次数的话，一开始需要$n$次询问，最坏情况下我们会坍缩到一个只有$3$个点的环，每坍缩一次就需要询问$1$次，所以最多的询问次数为$2n-3$，可以通过此题。