国赛C++ B组

以此文章纪念本人第一次蓝桥杯B组 省一 + 国二。

实力有限，题解仅供参考，仅保证部分解的正确性。 以下题解均为临场思路，没有答案，没有AC代码。

试题 A: 带宽

不会。

试题 B: 纯质数

20210605 暴力单独判断素数的话复杂度O(N^2)，欧拉筛预处理所有素数然后枚举每个素数逐位判断是否是素数(2，3，5，7)即可。

试题 C: 完全日期

判断闰年基础上枚举日期，判断完全平方数可用

if ((int)sqrt(x) * (int)sqrt(x) == x);

试题 D: 最小权值

我太菜，不会。

试题 E: 大写

根据题意把所有小写字母找到并且 (- 32) 或 (^ 32) 皆可。

试题 F: 123

分段长度位1，2，3 ...，预处理出前1e7(最大数据为1e12，根据等差数列前N项和 可知 最多包括不超过大约1e7个分段。)个分段的前缀和。第一个分段的前缀和为1，第二个分段的前缀和为 4，第三个分段的前缀和为 10 ... 对于每组数据的l, r， l - r 的数之和为前 r 项和 减去 前 l - 1 项和，通过二分求出分段个数并把剩余长度求一个等差数列前N项和分别求出 l - 1 和 r 对应的前缀和即可。

试题 G: 异或变换

我的思路可过80%数据。 观察(猜)可知当01串长度确定时，周期就确定了。 如 len = 5，周期为 8。 周期根据长度的变化呈倍增势，len <= 1000 时 周期不超过 1024； 根据01串的长度进行倍增算出周期，然后枚举 (t % 周期) 次异或变换即可。

试题 H: 二进制问题

对于任意N，设二进制位数为len， 二进制位数小于len的任何组合都小于N， 对答案的贡献为C(len - 1, k);注意此时前提是 len - 1 >= k。 当数字二进制长度为len时， 可以先算出N的二进制表示中有多少个位为1， 记为 cnt。 PS：若cnt = k， 对答案贡献为 1， 没记错的话我这里应该是忘记判断了。 从末位到首位依次枚举二进制数，枚举过的长度设为t，遇到 1 则将cnt --，若 cnt < k, 对答案的贡献为C(t, k - cnt)；若cnt == k, 对答案的贡献为 1(即C(t, 0))。直接输出以上对答案贡献的和即可。

试题 I: 翻转括号序列

暴力O(N ^ 2) 骗分即可过20%数据。 翻转用O(N)枚举模拟，判断也是双计数器(O(N))进行判断 (这个应该没人不会把???)。

试题 J: 异或三角

分析可知 a ^ b ^ c = 0 等同与 a ^ b = c。 由此推理即可暴力O(N ^ 2) 枚举 a, b 进行骗分通过20%的数据。