Camp Day1 Div2

Jan 20, 2019 由 小羊

CCPC Wannafly Winter Camp 自闭总结系列

Problem B - 吃豆豆

当时确实有想到将时间 $t$ 作为一维，但是由于不敢确定 $t$ 的范围，所以换了种思路。

令 $dp[c][x][y]$ 为吃到 $c$ 颗豆豆并且当前坐标在 $(x,y)$ 时的时间。那么它可以由吃到 $c-1$ 颗豆豆时的算法转移过来，大概是这样的一个公式：

$dp[c][x][y] = \min\left\lbrace dp[c-1][x'][y']+|x'-x|+|y'-y|+\Delta t, dp[c-1][x][y]+T[x][y]\right\rbrace$

其中 $\Delta t$ 为 $(x,y)$ 处豆豆产生时间的一个取整。当然了，$c=1$ 和最后实际答案需要一个简单的转移。实际上这个吃到正好 $c$ 颗的说法是不准确的，因为可以在前来的路上吃到更多的豆豆，但是，如果可以吃到更多的豆豆，那么这个值会存在吃到实际豆豆数的那个状态里。描述应该改为“吃到至少 $c$ 颗豆豆”。时间复杂度是 $O(Cn^2m^2)$，可以说是很糟糕了。

那么最原始的思路便是处理 $dp[t][x][y]$ 了。可以从问题的实际意义也就是上下左右移动和不移动看出来：

$dp[t][x][y] = \min\left\lbrace dp[t-1][x'][y'] + \left[T[x][y]\% t==0\right] \right\rbrace$

利用这个公式，可以去做倍增来达到div1的 $10^{18}$ 数量级。这类题我将在之后认真研究，虽然有点咕的欲望但是我会找人监督我的！

在做这道题的过程中，出现了以下的锅：

• 由于没弄准确delta的意义，加错括号位置了。
• 没有注意到第一次处理时的公式写法，导致了一个鬼畜错误。

记录下来。

Problem C - 拆拆数

这题一开始简单设置了几个样例，计算了一下，然后猜的结论：互质是 $1$ 组，不互质是 $2$ 组。当时想，如果能够构造出来，那么就相当于证明了这一猜想的正确性。可惜想偏了，在往 $\gcd(A,B)$ 的方向想。

这题的正确证明需要用到一个性质：$100$ 以内的素数有很多个，相乘之后超过 $10^{18}$。由于 $A$ 和 $B$ 都不超过这个范围，不论有没有超过 $100$ 的素因子，那么必然存在一个 $100$ 以内的素数 $p$，那么 $p \nmid A \wedge p\nmid B$。

所以，构造的方案是 $(a_1, a_2, b_1, b_2)=(p, A - p, B - p, p)$ 即可。其中证明只需要用到 $\gcd(a,b)=\gcd(a-b,b)$。

那么没做出来的锅：

• 当时脑子里已经全是最大公约数构造，思路偏了。

Problem F - 爬爬爬山

挖山嘛，由于体力的势能那样的意义，其实只要把山挖到零势能面就可以啦，不需要继续往下挖。这题模型很容易让人联想到最短路，并且是无负权的图。既然是无负权图，那么一定不会走出一个环，即不会走到某个点两次。由无负权最短路联想到 dijkstra，由每个点只能走到一次莫名其妙想到了…网络流拆点。（？？？什么鬼脑洞）那么，如果有了拆点这个操作，入点与出点之间连接的边的意义就很明显了：dls挖山的花费。如果最短路会经过这座山，也就是经过这座山的入点和出点，那么挖山的费用也就加入了最短路的cost。

其中，拆点的具体做法是这样的：

将所有入边连接到 $i$ 号点，出边的起始点选为 $i+n$，然后在 $i$ 与 $i+n$ 之间连一条挖山花费的边就好了。是把一个无向图通过拆点变成了一个有向图呢！运行 dijkstra 堆优化版本即可通过。

那么多WA很多发的锅：

• 自己只有脑洞，却没有认真练习过做图论题，连现成用的熟悉的模板都找不到。
• 队友拆点连边错误没有看出来。
• 队友交代码前没有认真审阅，没有注意到爆int的可能，也因为他使用宏定义而没有立刻发现输入的问题。以后拒绝使用任何 #define。

寒假的时候要对图论类题目进行专项练习，不能和之前抱学长大腿的时候只会数论组合那样了，要成为一个全面型的选手，不然有组合题也不会dp计算（雾），有图论计数也不知道怎么整一个生成函数（呜呜呜）。