温馨提示：这篇文章已超过464天没有更新，请注意相关的内容是否还可用！
摘要：第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学A组）是一场面向全国大学生的编程竞赛，旨在选拔和培养软件领域的优秀人才。该比赛涉及C/C++语言的编程和应用，要求参赛者展示扎实的编程基础、创新能力和问题解决能力。作为一场省级赛事，它吸引了众多优秀的大学生参赛，为软件行业发掘潜力新星，推动技术创新和发展。
蓝桥杯 2023年省赛真题
C/C++ 大学A组
- 试题 A: 幸运数
- 试题 B: 有奖问答
- 试题 C: 平方差
- 试题 D: 更小的数
- 试题 E: 颜色平衡树
- 试题 F: 买瓜
- 试题 G: 网络稳定性
- 试题 H: 异或和之和
- 试题 I: 像素放置
- 试题 J: 翻转硬币
试题 A: 幸运数
本题总分： 5 5 5 分
【问题描述】
小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 2314 2314 2314 是一个幸运数字，因为它有 4 4 4 个数位，并且 2 + 3 = 1 + 4 2 + 3 = 1 + 4 2+3=1+4。现在请你帮他计算从 1 1 1 至 100000000 100000000 100000000 之间共有多少个不同的幸运数字。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
4430091
根据插板法我们可知整数 n n n拆分成 k k k个非负部分的方案数为 C n + k − 1 k − 1 C_{n+k-1}^{k-1} Cn+k−1k−1，有下界， j j j个部分下界为 x x x时方案数为 C n + k − 1 − j x k − 1 C_{{n+k-1-jx}}^{k-1} Cn+k−1−jxk−1，那么根据容斥原理可知存在一个部分大于 x x x的拆分方案数为 ∑ i = 1 k ( − 1 ) i − 1 C n + i − 1 − i ( x + 1 ) i − 1 \sum_{i=1}^k(-1)^{i-1}C_{n+i-1-i(x+1)}^{i-1} ∑i=1k(−1)i−1Cn+i−1−i(x+1)i−1，记 p ( n , k ) p(n,k) p(n,k)为不存在部分大于 x x x的拆分方案数，有 p ( n , k ) = C n + k − 1 k − 1 − ∑ i = 1 k ( − 1 ) i − 1 C k i C n + i − 1 − i ( x + 1 ) i − 1 = ∑ i = 0 k ( − 1 ) i C k i C n + i − 1 − i ( x + 1 ) i − 1 . p(n,k)=C_{n+k-1}^{k-1}-\sum_{i=1}^k(-1)^{i-1}C_{k}^{i}C_{n+i-1-i(x+1)}^{i-1}=\sum_{i=0}^k(-1)^{i}C_{k}^{i}C_{n+i-1-i(x+1)}^{i-1}. p(n,k)=Cn+k−1k−1−i=1∑k(−1)i−1CkiCn+i−1−i(x+1)i−1=i=0∑k(−1)iCkiCn+i−1−i(x+1)i−1.考虑到幸运数字数位个数为偶，即不能有前缀 0 0 0，于是考虑将 p ( n − 1 , k ) p(n-1,k) p(n−1,k)看作最高位数字大于 1 1 1的方案数，但这样方案数里就包含了高位数字为 10 10 10的方案，显然不合法，所以减去不合法部分 p ( n − 10 , k − 1 ) p(n-10, k -1) p(n−10,k−1)，最终答案为 ∑ k = 1 4 ∑ n = 1 9 k ( p ( n − 1 , k ) − p ( n − 10 , k − 1 ) ) ⋅ p ( n , k ) . \sum_{k=1}^4\sum_{n=1}^{9k}\big(p(n-1,k)-p(n-10,k-1)\big)\cdot p(n,k). k=1∑4n=1∑9k(p(n−1,k)−p(n−10,k−1))⋅p(n,k).
#include long long C(int n, int m) { if (m > n || n试题 B: 有奖问答
本题总分： 5 5 5 分
【问题描述】
小蓝正在参与一个现场问答的节目。活动中一共有 30 30 30 道题目，每题只有答对和答错两种情况，每答对一题得 10 10 10 分，答错一题分数归零。
小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 100 100 100 分，所以到达 100 100 100 分时小蓝会直接停止答题。
已知小蓝最终实际获得了 70 70 70 分对应的奖项，请问小蓝所有可能的答题情况有多少种?
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
8335366
记 d p i , j dp_{i,j} dpi,j为第 i i i个问题小蓝获得 10 j 10j 10j分的方案数，显然 d p 0 , 0 = 1 dp_{0,0}=1 dp0,0=1，对于问题 i i i，如何小蓝回答错误，那么 d p i , 0 = ∑ j = 0 9 d p i − 1 , j dp_{i,0}=\sum_{j=0}^9dp_{i-1,j} dpi,0=∑j=09dpi−1,j，因为当小明有 10 ⋅ 10 10\cdot 10 10⋅10分时问答结束故不可转移，当小明回答对时则 d p i , j = d p i − 1 , j − 1 dp_{i,j}=dp_{i-1,j-1} dpi,j=dpi−1,j−1，最终，答案为 ∑ i = 1 30 d p i , 7 \sum_{i=1}^{30}dp_{i,7} ∑i=130dpi,7。
#include int ans = 0, dp[11] = { 1 }; int main() { for (int i = 1; i int loss = 0; for (int j = 10; j; --j) { loss += dp[j - 1]; dp[j] = dp[j - 1]; } dp[0] = loss; ans += dp[7]; } printf("%d", ans); } if (depth n) return; if (score == 100) return; if (score == target) ++ans; dfs(depth + 1, score + 10); dfs(depth + 1, 0); } int main() { printf("%d", (dfs(0, 0), ans)); }试题 C: 平方差
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 10 10 10 分
【问题描述】
给定 L , R L, R L,R，问 L ≤ x ≤ R L ≤ x ≤ R L≤x≤R 中有多少个数 x x x 满足存在整数 y , z y,z y,z 使得 x = y 2 − z 2 x = y^2 − z^2 x=y2−z2。
【输入格式】
输入一行包含两个整数 L, R，用一个空格分隔。
【输出格式】
输出一行包含一个整数满足题目给定条件的 x x x 的数量。
【样例输入】
1 5
【样例输出】
4
【样例说明】
1 = 1 2 − 0 2 ； 1 = 1^2 − 0^2； 1=12−02；
3 = 2 2 − 1 2 ； 3 = 2^2 − 1^2； 3=22−12；
4 = 2 2 − 0 2 ； 4 = 2^2 − 0^2； 4=22−02；
5 = 3 2 − 2 2 。 5 = 3^2 − 2^2 。 5=32−22。
【评测用例规模与约定】
对于 40 % 40\% 40% 的评测用例， L R ≤ 5000 L R ≤ 5000 LR≤5000；
对于所有评测用例， 1 ≤ L ≤ R ≤ 1 0 9 1 ≤ L ≤ R ≤ 10^9 1≤L≤R≤109。
基本数论
不知道基不基本，反正我老民科没见过，顺手推推。
对偶数 a a a ，平方数都可以表示成 2 2 ( a 2 ) 2 2^2(\frac a2)^2 22(2a)2，即 a 2 ≡ 0 ( m o d 4 ) a^2 \equiv 0\pmod 4 a2≡0(mod4)；对奇数 b b b ，平方数都可以表示成 ( b − 1 ) 2 + 2 b − 1 (b-1)^2+2b-1 (b−1)2+2b−1，即 b 2 ≡ 1 ( m o d 4 ) b^2 \equiv 1\pmod 4 b2≡1(mod4)；
那么就奇偶性而言 a − a 、 b − a 、 a − b a-a、b-a、a-b a−a、b−a、a−b 的结果为 0 、 1 、 3 ( m o d 4 ) 0、1、3\pmod 4 0、1、3(mod4)，容易得知 x x x 不可能被分解成 4 c + 2 4c + 2 4c+2 的形式。那么 4 c + k , 0 ≤ 4 c + k ≤ R , k ∈ { 0 , 1 , 3 } 4c+k,0\leq 4c+k\leq R,k\in\{0,1,3\} 4c+k,0≤4c+k≤R,k∈{0,1,3} 一定可以被 y , z , 0 ≤ z n u m ( l , r ) ∣ |inv[l,r]>num[l,r]|=|inv(l,r)>num(l,r)| ∣inv[l,r]>num[l,r]∣=∣inv(l,r)>num(l,r)∣，当 E E E 成立时， ∣ E ∣ = 1 |E|=1 ∣E∣=1，否则等于 0 0 0；
当 n u m [ r ] num[l] 的判别过程，有 i n v [ l , r ]
还没有评论，来说两句吧...