最小字典序

很容易发现，1 能在出现在字符串的任意位置,要考虑字典序最小，那么我们只需要将所有的 1 都放在第一个 2 前面即可，但是因为 0 和 2的位置是不会发生改变的，所以具体做法就是先把所有的 1 提出来，然后遍历原字符串，如果遇到 1 则不输出，如果遇到的不是第一个 2 就按照原字符串输出 , 如果遇到第一个 2 则先把字符串里所有的 1 输出，之后输出 2 即可，但是要考虑字符串中没有 2 这种情况特判即可.

这是一道博弈题

最暴力的做法就是记录这条边不能通过然后跑一次最短路算法，用迪杰斯特拉算法求时间复杂度是$O(M(N+M)logN)O(M(N+M)logN)$的,这个时间复杂度是过不去的，注意到这里边权为$11$，因此可以用$BFSBFS$代替迪杰斯特拉求最短路，但这也只能去掉一个$logNlogN$,也无法在要求的时间内通过此题。

这里给出一种解法是先求出点$11$到点$nn$的一条最短路，并标记这条路径上的边，显然最多标记$n-1n\; -\; 1$条边。然后对于要删除的边不是那些被标记的边，那么直接输出先前所求出的最短路即可，如果要删除的边是被标记的边，那么就记录这条边不能通过，然后跑一次最短路输出答案。也就是说只有要删除的边是被标记的边的时候我们才会跑一次$BFSBFS$求最短路，也就是我们最多跑$n-1n\; -\; 1$次$BFSBFS$，因此时间复杂度变成了$O(N(N+M))O(N(N\; +\; M))$，可以在$1s1s$内通过此题。

删点游戏

该题的解法是树形 $dpdp$ ，你可以直接求删除最少的点的个数。或者求保留最多的点的个数再，用总点数减去保留最多的点的个数。我的解法是第二种.

首先分析题目，每一个点要求只能保留一条边，所以对于一个点来说，要么删除这个点，要么保留这个点，在保留这个节点的情况下，再分情况，第一种，保留它的父亲和它，如果保留了它的父亲和它，那么意味着与它相连的除了它父亲以外的其它点全部都要删去，或者删除它的父亲则它可以保留一个或者不保留与它直接相连的孩子节点。

所以我们设立三种 $dpdp$ 状态，

$dp[i][0]dp[i][0]$ 表示删除 $ii$ 点之后 能保留的点的最大值。 $dp[i][1]dp[i][1]$ 表示不删除 $ii$ 节点 ，并且保留一个与 $ii$ 相连儿子 或者 直接不保留与 $ii$ 相连的儿子 能保留的点的最大值。 $dp[i][2]dp[i][2]$ 表示保留 $ii$ 点并且不保留与 $ii$ 直接相连的儿子 能保留的点的最大值。

$dp[i][0]dp[i][0]$ 的转移: 我们如果删除 $ii$ 节点，那么对于 $ii$ 节点的孩子来说，可以保留也可以不保留，那么我们就从 $ii$ 的每个孩子的所有状态中选择一个最大的来进行转移即可。

$dp[i][2]dp[i][2]$ 的转移: 对于保留 $ii$ 节点，并且不保留与 $ii$ 相连的孩子来说，该状态可以加上所有的不保留 $ii$ 的孩子的状态，所以我们直接把 $ii$ 的孩子不保留自身的值全加上即可。

$dp[i][1]dp[i][1]$ 的转移: 对于保留 $ii$ 节点并且保留一个与之 $ii$ 相连的节点或者不保留来说，首先如果我们不保留 $ii$ 节点的所有孩子的话，那么$dp[i][1]dp[i][1]$ 的值应该是和 $dp[i][2]dp[i][2]$ 是一样的，所以我们求 $dp[i][1]dp[i][1]$ 可以直接从 $dp[i][2]dp[i][2]$ 入手，从 $ii$ 点的所有孩子中找出保留该孩子和删除该孩子的差值的最大值，让 $dp[i][2]dp[i][2]$ 直接加上这个值就是 $dp[i][1]dp[i][1]$ 的值。

最后从所选根节点的三个 $dpdp$ 状态中取出最大值即可算出答案

最大子序列和

该题看完之后即可想到 $dpdp$

我们先设 $dp[i][0\mathrm{/}1][0\mathrm{/}1]dp[i][0/1][0/1]$ $ii$ 表示当前进行到第 $ii$ 位 ,第二维表示所选的数是偶数或奇数，第三维表示所选数的颜色是红色或蓝色，所选的子序列最大值。

那么现在思路就清晰起来了，对于第 $ii$ 个位置来说，如果当前是偶数，那么它的上一个位置只能选奇数，如果它的颜色是蓝色，那么它的颜色就只能是红色。我们设当前数的颜色位 $pos1pos1$ ,当前数的奇偶为 $pos2pos2$ 那么我们选这一个数的状态转移方程为

dp[i][pos1][pos2] = dp[i-1][pos1^1][pos2^2]+a[i]

对于其他的三个状态则可以直接继承 $i-1i-1$。

字符串矩阵变换

该题进行模拟即可

上贡

对于本题，我们首先考虑如果不进行修改操作，那么该题就很简单了，只用进行一次递归，然后硬统计一下每个点看是否都能满足条件即可，但是加了修改操作之后我们怎么办呢，其实也是一样的只需要修改完再统计，那么难点就在于如果硬模拟统计该题是会超时的，所以只需要用树上差分或者其他数据结构维护一下再做统计即可

一鱼几吃

该题考虑二分答案，以时间为答案，根据该时间内鱼能吃的人数是否大于总人数来返回$truetrue$ 或者 $falsefalse$ 即可

Apex game题解

签到题，只需要分别沿着两边都走一遍，看看是否能满足条件即可