谁能想到今年的蓝桥杯会是这样呢

填空题

1

3181

直接数字拆位,没什么好说的

2

40257

直接暴力枚举点对,然后按k和b排序.去重后统计答案即可.为了省事可以先不计算斜率无限大的情况,最后再加上就好.

3

2430

先质因数分解,2021041820210418=2^1 + 3^3 + 17^1 + 131^1 + 2857^1 + 5882353^1.然后就是盒子放小球的模型了.各个质数相互独立,算出来的方案乘起来就是答案.

4

10266837

建图跑SPFA完事.

5

881012367360

比赛的时候没跑出来.脑子不清醒以为是折半爆搜加奇怪的优化.在最后一分钟才想到正解...

算是常见的状压DP模型.f[i][j]表示当前已经走过了i个点(用二进制表示状态),最后一次到达的点是j.然后用此状态去更新其他状态.总的时间复杂度为O(2^{20}*20).考场上挂一会还是能跑出来的.

注 : 以上填空题答案来自知乎.和我记忆中的答案基本上是一致的(除了第五题没算出来).如有错误欢迎指正.

编程题

6

没想到今年第一个大题就考DP.

假想多了n个负质量的砝码,它们的重量和正质量的砝码一一对应,接下来就是2n个物品的01背包问题了.

因为计算的中间结果可能是负数,所以物品总体积要加上100000作为偏移量.总时间复杂度为O(nm)

7

挺不错的博弈题.

先简单复述下题面 : 两个人玩游戏,一共有n个数.轮流操作,每次可以从剩余的数中选择一个数,异或到对面身上或者自己身上.每个人身上的数一开始都是0.每个数字用完之后就不能再用了.直到所有的数用光游戏结束,最后谁身上的数最大谁赢.问两人同时采取最优策略,游戏结果是什么?

• 平局情况 : 显然,所有数异或为0时必平局.因为所有数的异或值等于两个人身上的数的异或值.所以此时两个人身上的数必相等.
• 先手必胜情况 : 当所有数的异或结果p不为0时,就会分出胜负.不妨设p二进制下的非0最高位为第x位.高于x的位数不会对比赛结果产生任何影响(原理同平局情况),两个人一定会根据最后谁身上的数字的第x位是1来分出胜负.假如说,n个数中一共有k个数的第x位为1,根据n和k的奇偶性可以得到如下结果:

1. $k=1$,先手必胜.显然,因为第一个人把这个1拿走后,第二个人再怎么拿都不会让自己的第x位为1.
2. $k$为奇数,且$n-k$为偶数,先手必胜.先手先挑一个第$x$位为1的数给自己异或上.接下来无论后手怎么操作,先手重复其操作就可以了.例如后手挑了一个第x位为1的数异或给了自己,那么先手就再挑一个异或给他.最后先手身上的数的第x位就一定为1,后手的一定为0.故先手必胜.
3. $k$为奇数,$n-k$为奇数,后手必胜.思路和上面差不多.先手无论怎么拿,后手就拿一个第$x$位不为1的数随便异或一下.然后无论先手怎么操作,后手总可以让先手身上的数的第$x$位为0,自己的为1.

显然k一定是奇数,所以证明完了

8

个人觉得这个题和上面那个换下位置更合适.

树上DP裸题.设f[i]表示重构后以i为根的树的最大深度,那么有f[i]=max(f[son])+sum(son).其中sum(son)是i的儿子节点数量.简单来说就是把儿子中深度最大的放到最下面,其他节点都接到它的上面就可以了.

9

应该是区间DP加计数.考场上先写了一个DP求最少加几个括号,又写了一个DP求方案数,对了样例就糊弄过去了QAQ

也许上面的思路修正一下就可以过了?正解应该是DP+组合数学计数.

10

纯暴力莽了30分.

正解应该是奇奇怪怪的DP加优化?

反正目前我没搜到正经的题解,先坑着

总结

今年的题目难度与往年相比还是提升了不少的.每一个编程大题都做的不是很轻松.在考场上状态不是很好,导致前四个填空题错了三个...幸亏最后检查了一波才挽回了局面.博弈论那题一开始以为先手不败,但是后面自己构造了一个很强的Hack数据,卡掉了很多想法.然后才慢慢摸索出了正解.只能说长时间不做题导致竞赛状态下滑的比较厉害.于是直接导致考场上最后一分钟想出来了最后一个填空的正解,却没有时间去打.

最后混到了北京市的第十九名好像(咱也不知道是不是按成绩排的),如果最后一个填空做出来的话兴许排名会更好看一些吧.

当初参加这个比赛就是抱着混奖学金的心态去的,结果也还算满意,没有翻车.

奖学金夺取计划大成功

至于说国赛,那是什么?给钱吗,不给不去