Wannafly Camp Day 0
Wannafly Camp Day 0
今天是Camp的第一天，总共才做出来两道题，其中一道还几乎和我无关（捂脸。不过今天由于比较自闭，所以闲的没事几乎把所有题看了一下。其中有两题思路已经接近正确答案了，但是并没有继续推下去。。。今天最主要的问题还是对于题目的深挖，很多题目分析到后来便感觉无力，然后就放弃了。其中一个原因是到了后来没有毅力做下去，还有一个便是对题目的当前做法的可行性的分析不够准确。这是目前主要需要提高的地方。
题目及解析
A 机器人
题目来源: comet OJ
首先，这个题目给定的\(n\)的数据非常之大，所以我们首先要从此处着手。题目中给出的一个关键的性质是"agv只能在特殊站点掉头"，并且"agv只能通过这些特殊站点实现区与区之间的转换"。所以，我们可以看出，非特殊点的点其实是不具备节点的性质的，或者说，我们可以把他们缩为边的一部分。这样，我们便可以把它缩为200个结点的图。对于某个点必走的情况我们可以把他变成某个边必走的情况。
然后我们在这个图上根据实际情况进行分类讨论即可。然后对不同的情况直接求值即可。
B 吃豆豆
题目来源: comet OJ
首先我们来看\(C\)较小时(\(C=1018\))的做法。我们可以使用\(dp[i][j][k]\)来存储在第\(k\)秒时走到\((i,j)\)的收集到的糖果量，然后直接DP即可，转移方程如下：
\[ dp[i][j][k] = dp[i+ip[z]][j+jp[z]][k-1] + ( T[i][j]%k==0?1:0 ) \]
其中，\(ip[], jp[]\)存储了一次移动的位移。当\(dp[i][j][k] > C\)时，条件便满足了。
然后，当我们的\(C\)变为\(10^{18}\)时，我们便需要使用倍增的方法来实现。因为\(T[i][j] \leq 10\)，所以我们可以把所有的\(T[i][j]\)的最小公倍数的最大值\(2520\)当作一个大周期。这样的话我们便可以利用大的周期来倍增去掉\(C\)中的大部分，最后剩下小于\(2520\)的部分再按照上面的DP直接求即可。
C 拆拆拆树
题目来源: comet OJ
这道题我们队是按照构造题来做的，情况比较复杂，但是构造出来之后问题就不大了。其情况大致如下：
\[ ans = \left\{ \begin{aligned} n = 1, &&\ a_1 = x, && b_1 = y \ &\ (x,y互\ \ 质\ \ )\\ n = 2, &&\ a_1 = 2, a_2 = x - 2, && b_1 = y + 1 - x, b_2 = x - 1 \ &\ (x,y同\ \ 奇\ \ 或\ \ 同\ \ 偶\ \ ) \\ n = 2, &&\ a_1 = 2, a_2 = x - 2, && b_1 = y - 3, b_2 = 3 \ &\ (x奇\ \ y偶\ \ 且\ \ x\ mod\ 3 \neq 2)\\ n = 2, &&\ a_1 = 4, a_2 = x - 4, && b_1 = y - 3, b_2 = 3 \ &\ (x奇\ \ y偶\ \ 且\ \ x\ mod\ 3 = 2)\\ \end{aligned} \right. \]
实际情况下，还要根据\(x,y\)是否相等和是否会有为\(1\)的输出特殊判断，此外还要注意因为我们上式中假设了\(x\)奇\(y\)偶，若情况相反时swap()后输出要注意输出顺序。
D 超难的数学题
题目来源: comet OJ
这题并不会，当时讲的时候也没有听懂，留位置以用于补题。
E 流流流动
题目来源: comet OJ
这题当时想了很长时间，并没有想到树上DP的做法，甚至完全没有想到DP上去。因为给定的数字建出的图的特殊性质，该图实际上是一棵树，然后直接树上DP即可。
F 爬爬爬山
题目来源: comet OJ
这题其实就是一个建图题，难度在于如何建图，而且实际上也比较简单。因为wls体力不能低于\(0\)，所以最高的山也应该小于\(k+high[1]\)。这样的话，走最高的山就会有一个\((k+high[1]-high[i])^2\)的代价。我们可以将这个代价抽象为一条边，对这个节点进行拆电，然后跑一边最短路即可。
G 双重矩阵
题目来源: comet OJ
这题比赛时我们队伍是按照分类讨论的方法来想的，但是情况比较复杂，最后并没有分析出来。实际上利用我们要求的是最大的子矩阵的这个性质，我们完全可以暴力枚举一个举行的上、左、下三个边，然后由于我们只考虑比当前的答案更大的值，所以右边的边会只会向右移动而不会向左移动，所以并不会增加时间。此外加上一个树状数组或线段树来维护区间的gcd()，这样便能在给定时间内求出了。
H 我爱割葱
题目来源: comet OJ
这题当时做的时候便认为是DP，但是由于并没有写过这种递归类型的DP，所以只是认为需要找一个方程然后循环即可，所以并没能找到一个可用的DP方程。实际的做法应该为根据葱的底将从分为互不相连的几部分，然后递归的让他们计算出来，最后再用这些部分来更新当前部分的信息。
I 起起落落
题目来源: comet OJ
我们先分别存储到位置\(i\)的比\(j\)个数要小的数的个数，然后枚举所有的节点，按照下面的公式进行DP：
\[ dp[i] = \sum_1^{i-2} dp[k] * smaller[k][i] \]
不过该方程智能计算\(n\)较小时的情况，所以还需要进一步的优化。但是当时并没有听懂优化的具体写法。
J 夺宝奇兵
题目来源: comet OJ
首先朴素的想，我们可以枚举除wls外宝物最多的人有多少宝物。然后我们需要拿走所有大于该数量的宝物，此后直接贪心的拿更便宜的直至符合条件，这样便能算出最少需要的金币。
不过这个算法较为朴素，所以我们还需要进一步优化，不过这题的优化也没有听懂。。。
K 星球大战
题目来源: comet OJ
此题同D，完全不懂。