Google Code Jam 2022 Qualification Round

本文主要是介绍Google Code Jam 2022 Qualification Round，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Punched Cards

字符串模拟。

3D Printing

对于每一个颜色分量，因为3个打印机都要可行，所以取3个打印机中的最小值。

如果4个分量的最小值之和大于等于\(10^6\)，那么可行，输出方案的话就是能加就加，反正只要求和为\(10^6\)；否则无解。

d1000000

排个序，贪心用小的骰子去填小的坑，能填就填。

Chain Reactions

前3题有点水，这题难度一下子上来了。

Test Set 1

\(O(n!)\)枚举，然后模拟一下。

Test Set 2

首先，给出来的关系图其实是一个森林，每棵树都可以单独解决，然后答案相加。

然后考虑动态规划解决每棵树的问题。

记\(dp_u\)为以\(u\)为子树的答案，然后子树可以先选择一个叶子节点，然后不断向上跳到根，产生多个可以递归解决的子树，还有一个触发这个叶子节点产生的贡献，两个部分相加即为此时子树的答案。

可以枚举子树所有的叶子节点，执行上述操作，然后取最大值就是\(dp_u\)。这样结合记忆化搜索，复杂度大概是\(O(n^2)\)，对于这个测试集够了。

Test Set 3

我们可以将每个节点的答案看成两个部分，第一次触发产生的贡献，和触发过程中产生的新的子树。

上一个测试集是枚举了第一个部分，但是其实可以不用枚举，因为从\(u\)到其儿子之间的转移，其实就是选一个儿子，然后利用\(u\)去优化子树。这一步如果贪心地选择第一部分更小的儿子的话，可以最好的利用\(u\)。

这样就可以直接\(O(n)\)树形DP做了。

Twisty Little Passages

GCJ就是会有这种奇奇怪怪但是有意思的题目。

直接随机化，每次随机tp到一个节点，然后记录他的度数。这其实就是一个采样，然后就可以用样本估计全局，就是样本的平均度数约等于全局的平均度数，这样就可以估计出没有访问到的节点的度数和。然后对于无向图，边数等于度数和的一半，这样就估计出了全局边数了。

但是这样的话，会有一个问题，就是有极少部分点他偏离比较大，少到随机到这部分点的概率很低，这种情况就可能会出问题。具体有两种可能，可能绝大部分点的度数很大但少部分很少，或者反过来。

对于第一种情况，其实还好，因为题目是可以有误差的，然后他度数小吧对答案的影响也小，所以可以忽略。

对于第二种情况，这种情况就没办法忽略了。但是，注意到，因为这种点的度数大，所以很容易随机到它的邻接节点。然后如果从它的邻接节点随机走一步是很容易走到它的。考虑重复tp到同一个点\(C\)次，每次tp完再随机走一步。\(C\)随便取了个30就过了。

这样就覆盖所有情况了。

这篇关于Google Code Jam 2022 Qualification Round的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！