©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>2020蓝桥杯成绩
其实成绩昨天就出来了，只是今天才想到可以发这么一篇博客来水水。
我的蓝桥杯国赛成绩是国一（数了一下大概100多名的样子）
其实也挺出乎我自己的预料的，因为我很多题其实并不能确定是对的（或者说4-5题就国一了？）。还有一个主要原因：我上一次才省二awa
。接下来就讲一下我比赛途中在干嘛吧。
<>国赛准备
根据今年的省赛难度来说，我根本不觉得国赛很难，以为也可以轻松搞个七八题的样子。但是直到国赛前几天，我做了2019国赛的真题之后，把我做自闭了。我记得倒数第二题好像是主席树来着，然后我花了2天时间学了一波
主席树。感觉会考字符串，然后星期五的晚上又看了一下KMP、马拉车等等。甚至星期六的早上7点多又担心dp不会，看了下背包和LIS（
LIS还确实考了，如果我写的没错的话）。
<>比赛过程
<>注意
声明一下，以下所描述的仅凭自己的记忆，并不代表是正确的题目或者正确的答案，仅供参考。
<>第一题：暴力
好像就是要求1 - 2020的数中包含数字2的数的个数，直接暴力找就行了。
<>第二题：BFS
有一说一，那个叫Dev什么的IDE太不智能了，我想敲个unordered_map都不能帮我自动补全，搞的我直接把所有点的x+2020,y+2020，然后开了一个6500
x 6500的标记数组（还好没炸）。
这题就是类似于细胞扩散，直接广搜就行了。
<>第三题：基本数论
每一个数都可以拆分为若干个质数的乘积，例如 100 = 2 2 ∗ 5 2 100 = 2^2*5^2 100=22∗52（其中2和5是质数）
那么100的约数的个数就是 ( 2 + 1 ) ∗ ( 2 + 1 ) = 9 (2+1)*(2+1)=9 (2+1)∗(2+1)=9
一个数 x = a b c d . . . y z 的 约 数 个 数 就 是 ( b + 1 ) ( d + 1 ) . . . ( z + 1 )
x=a^bc^d...y^z的约数个数就是(b+1)(d+1)...(z+1)x=abcd...yz的约数个数就是(b+1)(d+1)...(z+1)
那我们就先记录1 - 100的每个数的质数幂的和，然后乘起来就完事了，没记错的话最后的答案d的数量级有1e16，别忘了开long long。
<>第四题：DP
我好像是开了个二维dp倒推写的，dp[ i ][ j ]表示最后i位以字母j开头的最长上升子序列的个数，转移方程就是dp[ i ][ j ] = dp[ i
+ 1 ][ k ] ( k >= j )
仅供参考，可能是错的（或者记错了？）
<>第五题：DFS
好家伙，感觉这题比上题简单，直接对每个点进行深度为16的深搜即可。
<>第六题：分治+高精度模拟
我做到这题的时候好像已经过了40分钟多了，一看到这题就感觉像分治，但是找规律找了半天。大概想了十分钟就溜了，因为我看到了3100
，看到高精度直接溜。再看这题就是2小时多的时候（后面能写的都写的）。
我写的是把这两个点的距离看做| (第一个点到右上角的距离 - 第二个点到右上角的距离) |，那就变成写一个函数求一个点到右上角的距离。
我们每次都可以把这个大的图分为9个小图，直到他的边长为3的时候直接求值即可。
9个小图里面有2个标记对求值有影响：正还是反，向上还是向下。
考虑这几点就差不多了。
<>第七题：单调队列求LIS
这题就先特殊处理把所有的人的名字处理出来，此时我们可以联想到普通的求LIS。只不过一个是比较数值大小，一个是比较字典序最小罢了。
想一下单调队列的求解过程，遍历一遍原数组，如果当前的字符串比队尾的还要大，那就直接入队。否则就用lower_bound二分查找第一个大于或等于的位置，替换掉原来的大值。【如果此处替换的大值为队尾的那个元素，那么这个可能就是答案】
最后的答案是：最后一次 入队或者是替换掉队尾元素 的那个 遍历点 的队列。
<>第八题：贪心+排序
这题就要看排序的依据对不对，我推了一下好像是按 a+b+c 来排序，小的在前即可。相等的情况貌似不用处理？
<>第九题：？？？
题目太长，看了下题目就溜了。
<>第十题：DP骗分
三维的一个DP，当数据只有200的时候，完全可以骗到50%的分。
总结一下：比赛时写了的题有：一、二、三、四、五、六（50%）、七、八、十（50%），应该不会错很多吧。
不管了，拿到了国一还是挺开心的，加油~