Camp Day1 Div2

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}。由于 AB 都不超过这个范围,不论有没有超过 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,然后在 ii+n 之间连一条挖山花费的边就好了。是把一个无向图通过拆点变成了一个有向图呢!运行 dijkstra 堆优化版本即可通过。

那么多WA很多发的锅:

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注