about 4 years ago

logdown的blog都大约两个月没更新了。。 主要原因还是太弱~
Alright, rating涨了一点还是挺好的。

总的来说这场SRM还是偏简单的..

250PT:
题意大概是, 给你一个无向完全图,边权 <= 10 , 再给你一个参数T。若一条边在至少K对点间的最短路上,则答案加上这条边的权值。众所周知的 TC-STYLE,n <= 50. 于是算法就很显然了, 先求出每对点间的最短路(floyd), 再枚举每条边, 枚举每对点, 判断这条边是否可能在这对点间的最短路上, 然后更新答案就行了。。

500PT:
给你一棵带权树, 再给你一个参数MaxDist, 你可以通过砍掉某些边的方式来使这个树分裂成好多棵小的树, 需要满足最后所有的树的直径都不超过MaxDist。 你要让最后子树的个数尽可能小 (就是求最少需要切割的刀数)。 数据范围, 依旧TC-STYLE。
一眼的Tree-DP, 具体怎么处理呢: 设 F[i][j] 为将以第i个点为根的子树切割成合法方案最少需要的刀数, 其中i到与i相联通的部分最远的结点的距离为j。 每次转移的时候先枚举最长的距离源自i的哪个孩子(就是枚举i的哪个孩子的子树中贡献了最长路径j) 然后自己再画画图应该就能想出来转移的方程。 j = 0的情况需要特殊考虑。

900PT:
题意比较繁琐, 就不再简述了, 来说说我的做法吧。。
我的做法貌似比较奇葩。。 和 XYZ哥哥的做法好像不是很类似 (说不定本质是一样的。。 但至少看上去不太一样)

设 F[n][k] 为1 - n 所有数中第k位为1的个数, 有了这个,我们就能简单地通过奇偶性来算出最终的异或值。
设 Fib[i] 为第i个Fibonacci数
设MaxFib[n]为不大于n的最大的Fibonacci数,
这样就有比较显然的转移:
若fib[k] ≠ MaxFib[n] 那么 F[n][k] = F[n - MaxFib[n]][k] + F[MaxFib[n] - 1][k]
若fib[k] = MaxFib[n] 那么 F[n][k] = F[n - MaxFib[n]][k] + F[MaxFib[n] - 1][k] + n - Maxfib[n] + 1

由于 n <= 10^15, 直接这么递归下去显然是会T的.. 那么记忆化? …… 似乎不可行,因为n的范围太大了。。
……
仔细想想看, 记忆化实际上是可以的。 我们注意到式子中多次出现了 F[MaxFib[n] - 1][k], 由于10^15 之内的Fibonacci数只有72个, MaxFib[n] - 1 实际上也只有72个值。。 我初步想法是先把 F[MaxFib[n] - 1][k] 这个东西记忆化下来。。 至于某个数不是一个Fibonacci数减一的话就暴力往下递归,不储存它的值了。。。

……

然后? 惊人地发现极限数据秒出了。。 这是为什么。。 明明只部分记忆化了72个值。。

……

其实真相是这样的:
每次递归下去两部分 F[n - MaxFib[n]][k] 和 F[MaxFib[n] - 1][k]。
第二部分我们已经记忆化了,于是剩下的运算都在F[n - MaxFib[n]][k] 上面, 这样相当于每次递归都减去了一个MaxFib[n].
极限数据的递归深度就变成只有18层.. 也就是18个未被记忆化的O(1)运算, 其他递归的东西都被记忆化了。。

部分记忆化真是神奇呢。

← 单位根的妙用 PYXFIB & Guideposts ZJOI2015的那些事 →
 
comments powered by Disqus