2021蓝桥杯括号序列_蓝桥杯是a类竞赛还是b类

2023年第十四届蓝桥杯国赛JavaB组题解　　UPD6.16：蓝桥杯出成绩了，写个感想吧　　跟预估的情况一样，又差一名国特了，跟去年蓝桥杯一模一样的排名

　　看样子确实是又输填空题了，经典10分全错，估分122.5分应该是确定了。确实自己策略不是很优，随机应变能力不到位。天不逢时，遇到这么简单没有区分度的卷子，不亚于北京中考评细心程度。询问了下国特的队友，看样子他估分<132.5分　　除了最后一个J题以外，其余题目都太简单了，没什么区分度。自己也应该想到在这种情况下，细心才是最重要的。　　还剩95分钟的时候，剩下2道填空以及J题没有做，花了10分钟写完填空题题。85分钟时，只剩下J题没写，我赛时决策花了15分钟检查几道编程题，却对很简单的填空题置之不理，明明自己明确知道自己的弱点是填空题了，属实活该了。最后还剩70分钟的时候死磕J题了　　J题大模拟+思维，赛时我想写的60%分数做法，最后能达到140分的做法，该做法甚至有可能优化到100%分数。因为下一个分数档就是150分，我认为全场没有人能在OI赛制下AK，只要拿了140分就一定是国特，于是就先写60%分数做法，而30%分数做法只需要暴力dfs，15分钟左右就可以搞定。　　自己低估了J题的难写程度，不亚于一道天梯L3-1，这难度梯度变化太大了。咖啡就喝了1/3瓶最后一小时药效退了，脑子不清晰，这时有点后悔喝少了，感觉大脑一直短路。到最后10分钟我发现，我发现可能还需要结束后多5分钟才可以敲好这个60%做法，我索性直接改30%做法，12:58草草交卷。　　赛后对了填空题发现全错了，132.5分变成了122.5分。赛时最优决策应该是70分钟分配15分钟检查填空题变成125分，15分钟敲J题30%做法132.5分收尾，最后40分钟罚坐就行了。现在想想那个60%做法其实能想到的人几乎没几个，甚至30%的难写程度也没多少人可以写出来的。　　连续两年国第二了，有机会再战吧，再会蓝桥杯回答那边我的答案貌似被屏蔽了，我重新发一次　　JAVAB组，估分122.5分除了最后一题全部都往正解写了只写了一题对拍，可能有点悬会掉几分考完预估132.5分（填空题全错典中典），卷子个人期望最好能考140分　　简单概括了题意，方便各位大佬阅读　　今年喝了咖啡，状态在线了去年自己态度恶劣有点活该了。不熟悉java语法，外加做课设到4点睡来第二天直接梦游　　（来完善题解了，欢迎纠正　　A题　　求解
$[1,2023^{2023}]$ 中和
互质的数的个数，答案取模
。　　注意到
$2023=7\times 17^2$ 　　考虑容斥原理，只需要针对质因子即可，与
不互质的数的个数为
$\cfrac{2023^{2023}}{7}+\cfrac{2023^{2023}}{17}-\cfrac{2023^{2023}}{7\times 17}$ 　　所以互质的数的个数为
$2023^{2023}-(\cfrac{2023^{2023}}{7}+\cfrac{2023^{2023}}{17}-\cfrac{2023^{2023}}{7\times 17})$ 　　只要涉及到的质因子，所以跟2次方没有关系　　B题　　给了一个素数
（具体我记不清楚，
开头的
位数字），求解
每个数逆的异或和　　费马小定理
$inv(a)\equiv a^{p-2}\pmod p$ 暴力跑逆求和即可　　题目求的异或和　　正确答案是这个：　　C题　　有一个等式
$a \ op\ b=c$ ，其中
中的一个现在将
某个替换为
，然后给出这个字符串，让你求解
是什么，保证唯一解　　分类讨论，String截取即可　　D题　　给定数组
$a[1\cdots 2n](n \le 10^5)$ ，每次不放回的取出两个数，得到
$a[i]\times a[j]$ 的积分，求解最小的总积分　　排序后，让
$a[i]\times a[2n+1-i]$ 搭配即是最小答案　　时间复杂度为
$O(n\log n)$ 　　E题　　给定
$n\le 18$ 个星球，第
个星球的坐标为
，每个星球有一个防御值
，需要占领全部的星球，从星球走到星球的花费是
$dis(i,j)\times w_j$ ，其中
为两个星球的直线距离，初始可以位于任意星球　　状态压缩DP，
表示经过的星球集合为
，最终停在
的最小花费　　预处理出
，然后刷表法进行DP即可　　时间复杂度为
$O(n^2\times 2^n)$ 　　F题　　我转化一下题意：给定一个数组
$a[1\cdots n](n\le 10^5)$ 求解
$\sum_{d=1}^n\sum_{i=1}^n [a_i\mid i\times d]$ 的值，其中
$[\ ]$ 表示艾弗森括号里面表达式为真返回1否则返回0，
$\mid$ 表示整除　　按照算贡献的思路，对每个数单独考虑　　交换下求和顺序，对每个
单独考虑，设
求解出
$g=\gcd(a_i, d)$ 然后
$l=\text{lcm}(a_i,d)=\cfrac{a_i\times d}{g}$ 然后
即是这个数的贡献　　这题我赛时写了对拍，应该是没问题（　　G题　　给定一个数组
$a[1\cdots n]$ ，以及一个正整数
$k(k\le n\le 2\times 10^6)$ 每次熊大等概率选取一个连续的长度为
的区间，将该区间最大值赋值给
熊二等概率选取一个连续的长度为
的区间，将该区间最小值赋值给
求解
的期望　　容易知道二熊的操作是独立的，我们只需要单独求出
的期望，相减即是答案　　于是就是单调队列，求出所有区间最大值之和，以及区间最小值之和，二者差值除以
即是期望　　时间复杂度为
　　H题　　给定一个拥有个
$n(1\le n\le 10^6)$ 点
$m(1\le m\le 2\times 10^6)$ 条边的无向带权图从任意一个点
出发，能到达所有点（独立考虑）的所经过的边权的最小的最大值
。求解
$\max_{i=1}^n t_i$ ，不连通输出-1 　　考虑Kruscal最小生成树，维护一个每个连通块的大小，合并
集合时，合并后若集合
大小为n时，当前边权
即是答案　　时间复杂度为
$O(m\log m)$ 　　I题　　给定两个正整数
$n,m(m\le n\le 35)$ ，求解非对称二叉树的方案数量其定义是这样的，对于每个节点
，需要满足
$\max(h_{l_i},h_{r_i})\ge m\times \min(h_{l_i},h_{r_i})$ ，其中
$l_{x_i},r_{x_i}$ 表示其左右儿子，
表示以
为根的子树的高度，如果为空视为高度为0 　　考虑dp 　　设状态f[i][j]表示有i个节点并且高度为j的非对称二叉树数量，枚举左右儿子的大小和高度
$mx=\max(h_j,h_k)$
$mi=\min(h_j,h_k)$
$f[i][mx+1]=\sum_{mx \ge m \times mi} f[j][h_j]\times f[k][h_k]$ 　　时间复杂度为
枚举
然后直接得到
再枚举
其实这是一个很松的上界　　J题　　题目太长了，难以概括。。。　　太逆天了，又码农又思维　　最后写一半状压，没时间改暴力了预估7.5分　　我的原思路是，状态压缩10个数的选取方案，并且每个方案选择的数的长度为len，总和为sum，然后开一个三维数组记录总和为sum且选了len个数有哪些状压方案　　这样就解决了重复和总和为灰色格子的行条目问题　　然后每个条目的拿到这个方案之后，枚举选择状压方案中的哪个数，消掉哪一位之后丢给下一个位置　　最后判断是否合法，感觉这个思路可以优化掉很多

2021蓝桥杯括号序列_蓝桥杯是a类竞赛还是b类

相关推荐