比赛的奖品之一，文末有拍卖惊喜
# 一、赛前
很荣幸，在昨天，也就是8月3号，我参加了微信举办的编程比赛。
比赛之前吃饭的时候，我说：这种比赛，如果题会做，前两小时就做出来了。如果不会做，呆再久也做不出来。我做一段时间就可以出来了。
当然，这是我自己总结的一个观点。
这个观点不是绝对的，但是在专业比赛中大部分情况下都适合。
比如这次，我就再次遇到这种情况，之后的时间就全是沉没成本了，想走，又感觉我还行，还能做出一题，到最后还是没做出来。
# 二、赛中
比赛大概下午一点开始。
我本计划先往常的习惯倒着把所有题看一遍（大学时队友正着看），看了最后一道题后，我一想，还是不看题了。
先等几分钟，看榜单哪个题过的人多，我就做那道题就行了。
我对自己的个人能力很清楚，按照我之前的结论：前两个小时就能做完自己会的题，之后的题一般都做不出来。
那我现在看所有题其实没啥用，时间是完全充足的，需要做的就是静静的等三分钟。
果然，一会第一题就有人 AC 了。
原来第一题是签到题。
题意是输入几个单词，使用大写输出单词的第一个字母。
于是我就也 AC 了。
再看榜单，第二题有人 AC了。
题意是：有一个队列和栈。
我们可以随时出队，将出队的元素入栈。
也可以随时出栈，将出栈的元素入队。
原先给的序列在队列里，问能否经过若干次操作，把队列里序列调整为另一个序列。
简单一分析，如果两个序列组成相同时，一定可以，否则不可以。
推理：
第一步不断地出队出栈，直到遇到目标队列最后一个元素，此时这个元素不再出栈。
第二步用相同的方法把目标队列倒数第二的元素保留在栈里。
就这样， N 步后，栈里元素的顺序就是目标队列元素的顺序，依次出栈入队即可得到答案。
那怎么判断两个序列组成相同呢？我的做法是对两个序列排序，然后依次比较即可。
就这样，又 AC 了一道题。
此时看教室屏幕的榜单，其他题没人任何人做出来。
于是我看第三题，看清题意后，感觉需要复杂数学计算，不是简单题，果断放弃。
于是再第四题，发现题意特别简单，给一个简单的凸包多边形，一个线段可以把多边形分成两个相等的多边形。求最长线段和最短线段。
这道题思路很简单，枚举所有边，假设线段的端点在这条边，求出最大长度和最小长度。
由于是凸多边形，当端点从边的一端移动到另一端时，平分面积的线段长度是先增再减的，也就是求出抛物线，可以三分求出最大值以及最小值。
理论是美好的，几何题，在短时间内我是敲不出来，于是果断再次放弃。
接着看第五题，发现是我喜欢的数学题。
题意：给若干个数字区间，区间里的所有数字都和一个数取“与”操作，问剩余多少不同的数字。
简单分析后，发现从高到底依次按位运算，合并或拆分区间即可。
但是又一看，拆分的区间可能很多，会存不下，然后就没想法了，果断跳过（赛后看题解，区间不会很多）。
此时感觉教室的榜单不对劲，仔细一看，榜单不是总榜，是教室内的榜单。
赶紧浏览器找到总榜，一看 第七题有人过了。
题意：定义函数 f(str) 值为数字字符串 str 里面出现的最小数字。
给一个字符串 S，求 S 所有子串的 f 函数值的和。
简单一分析，发现是个简单的动态规划题。
只要就出第 i 位置的状态，就可以求出所有以 i 为后缀子串的答案和，而且 i 状态可以快速转移到 i+1状态。
这样一层循环就求出所有答案了，于是这道题就 AC 了。
状态转移的细节：
状态 state(i) 定义：以 i 为后缀的子串中，f 函数值分别是 0 ～ 9的个数。
状态转移：假设 i+1 位置的值是 val，在 0-9里面，小于等于 val 数字的个数不变。大于 val 数字的个数需要置为零（更优），个数转移到 数字 val 上。
i 为后缀子串的答案为：f 函数的数字值（0 - 9）乘以 个数。
# 三、沉默时间
到目前为止，比赛时间才不到两小时，我做出了三道题。
之后的时间想走又没走，本以为还可以做出一两道题，没想到后面的时间全是沉没成本。
此时看总榜，第六题和第八题都过了几个人。
于是我回头看第六题。
题意颇为复杂，树的直径什么的我都忘得差不多了。根据复杂度和数据量，这道题明显只能贪心，两棵树合并的公式我也推算出来了，但是考虑到哈夫曼编码，多颗树可能涉及结合顺序，那就涉及到选择一个标准来贪心了。
赛后看题解，发现原题的叉积没有括号，那只能从左到右就叉积，那就只有一种计算公式，直接枚举贪心即可。
好吧，这道题我看错题了。
当然，第六题虽然看错题了，但我没用多少时间就果断放弃了。
因为第八题过的人更多。
第八题实际上就是一个向量公式题，而且公式已经告诉我们了。
机器学习的公式
虽然大部分人可以敲出这道题公式的代码，但非专业人士不知道避免重复计算，会超时；专业人士虽没有超时，但是依旧过不了这道题。
比赛的时候，群里有人反馈如果使用 c++ 语言做这道题，没搞过机器学习的人根本过不了这道题。
我起初以为是在说缓存中间结果，避免超时。赛后才知道是中间计算会很大可能越界，需要使用 softmax 思想。
赛后看群里有人说，实际可以直接使用 long double 水过去。
第九题和第十题我也忘记了，这里就不说了。
# 四、赛后
赛后看总榜，个别人过了6道题，一小部分人过五道题，大部分过四道题，三道题的排名一百名了。
我还可以做的有三道题，一道是我喜欢的区间与运算，一道是树叉积运算，一道是机器学习公式。
最终我选择了表面上看着最简单的机器学习公式题，如果选择区间与运算的话，可以做出来的概率应该更大。
工作后，我再也没做过图论相关的题了，几何题即使大学比赛或训练时，我也没怎么做过。
我的水平也就这样啦。
我最擅长的还是数据结构题，你最擅长的是什么题呢？
最后，本想抽个奖送霸王洗发水。
但是点开了拍东西小程序，那就开一个拍卖吧。
随即又想东西还要邮寄，干脆来一个面基吃饭聊天吧，这样霸王洗发水你就可以直接拿走了。
