Day 1

上周五的英文赛打的还可以，因此获得了这周一参加牛客寒假训练营的机会。第一次三个人组队一起做题，一共 AC 了五道。其实也许可以罚时更少、AC 更多，但是我们确实被出题人精心设计的诈骗给误导了。回过头看，题都是好题，并没有因为被诈骗而太失落，反而有了一种“下次一定可以看破题目，做对更多”的自信。

B. 现在是，学术时间（1）

题意:

H 指数用于粗略的评估一位教授的学术水平。一位教授可以发表多篇论文，每篇论文有一个引用量。定义一位教授的 H 指数为使得”该教授发表的所有论文中，有至少 H 篇论文的引用量大于等于 H”这一命题成立的最大的 H。现有 n 个教授和已知引用量的 n 篇论文，如何分配使得 $\sum_{i=1}^{n}H_i$ 最大。

思路：

思考分为实现和优化，如果你能够看透题目的本质（或者找到特殊情况及其与一般情况的关系），你就会发现：对于任意 H，都必须消耗 H 篇引用量 大于等于 H 的论文。也就是说，除了引用量为 0 的特殊情况，每篇论文的平均贡献值都可以达到且不可能超过 1。因此，无论如何分配，都不可能优于每篇贡献 1 点的分配方式，毫无疑问，直接每篇 1 点（0 引用量除外）的策略的时间复杂度、空间复杂度和代码复杂度都是最优的，属于是好处都给你占完了，这就是看透题目所有可能情况的优势。

H. 本题主要考察了DFS

题意：

PTA 的拼图由 n * n 个大小为 1 * 1的拼图块组成，每个拼图块都是在正方形的 1 * 1拼图块基础上生成的，生成方法为：对于每一条边，可以选择不变、向里削出一个半圆形的缺口、向外补上一个半圆形的凸出三种操作之一。因此，一个拼图块可以由一个长度为 4 的字符串描述，四个字符分别表示上、右、下、左四条边进行的操作，上述三种操作依次记为 0,1,2。

每块拼图还有一个制作成本 p，制作成本正比于面积，而拼图中削去的缺口和补上的凸出面积又相同，因此对于一块削去了 x 个半圆、补上了 y 个半圆的 1 * 1拼图，其制作成本 $p=10−x+y$。

现在，PTA 会从所有拼图中随机隐藏一块，并打乱剩下的 $n^2-1$ 块拼图，告诉了你它们的形状对应的字符串表示（由于拼图上绘制了可供辨识的图案，因此给出的拼图形状都是各拼图块正面朝上、未经旋转的正确形状）。PTA 需要你完成这一拼图游戏，还原拼图原来的样子。你需要回答隐藏起来的那块拼图的制作成本来证明你成功完成了拼图。

思路：

我这种萌新一看到 DFS 就想跳过了，然而标题主打的就是一个诈骗，更可恶的是，我的队友花两个小时现学 DFS 也不会有任何眉目，因为这题跟 DFS 没有半毛钱关系。题中要求：先“还原拼图”，再“找出缺失那块的形状”，最后“给出缺失那块的制作成本”。然而 OJ 只要制作成本，能不能跳过前面繁琐的步骤，直接求出成本呢？当然可以，成本只与面积有关，总面积减去已知拼图的面积就可以求出缺失拼图的面积，也就可以求出其成本。为了误导做题的人，还大费周章地说什么“正面朝上”，“未经旋转”。现实问题中，哪怕没有人来欺骗我们，我们也可能被自己蒙蔽了双眼，跳过中间的弯弯绕绕，直击问题本质，这样好过束手无策。

Day 2

题单：SMU Winter 2023 Round #6 (Div.2)

一次常规的模拟赛，虽然有很多题没做出来，但没有什么让人耳目一新的题，也没有太多值得深思回味的。

Day 3

今天也是牛客营的比赛，难度也比平时大一些。有些思维题应该挺有意思的，但我比较感兴趣的是一道 DFS 的模板题，我发现我从来都没有写过类似暴力计算的题，但这种类型的问题出现的频率应该很高。这恰恰是计算机的优势所在，要知道，DFS 加剪枝可以轻易解决数学王子高斯都没做出来的「八皇后问题」。

G. 严肃古板的秩序

题意：

给出一个形如 $a_1?a_2?\cdots ?a_n=b$ 的式子，其中 n 小于等于 13。定义 a # b = pow(a, a) % b ， 用 + - # 三种符号填在 ? 的位置，且式子从左到右运算，使得等式成立。若有多个答案，给出一个即可；若没有答案则输出 -1。

思路：

很直接地会想到 DFS、回溯之类的暴力算法，而且复杂度 $3^{12}$ 的时间复杂约为 5 万，可以接受。但是问题在于我没写过 DFS 的模板，一开始想用树的结构，由于不会用树，只能开了一个十二维的数组，实在夸张。

总结

如果处理不好与题目之间的关系，那些原本值得深思的好题只会变成精神上的束缚，这难道是题目的问题吗？

  • 博客写得精简一些，少点废话。写的时候要当作是给别人看的文章；
  • 列出要整理的题目和 deadline，不要纠缠不休。