蓝桥杯-2025年C++B组国赛

P12830 [蓝桥杯 2025 国 B] 新型锁题目描述密码学家小蓝受邀参加国际密码学研讨会为此他设计了一种新型锁巧妙地融合了数学的严谨性与密码学的安全性。这把锁包含 2025 个连续的数字格每个格子需填入一个正整数从而形成一个长度为 2025 的序列 {a1​,a2​,…,a2025​}其中 ai​ 表示第 i 个格子上的数字。要想解锁该序列需满足以下条件任意两个相邻格子中的数字其最小公倍数LCM均为 2025。即对于所有的 i1≤i≤2024需满足LCM(ai​,ai1​)2025现在请你计算有多少个不同的序列能够解开这把锁。由于答案可能很大你只需输出其对 1097 取余后的结果即可。输入格式无输出格式这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。输入输出样例无实现代码#include bits/stdc.h using namespace std; #define int unsigned long long const int mod 1e9 7; int dp[2026][2][2]; signed main () { dp[1][0][0] 8; dp[1][0][1] 4; dp[1][1][0] 2; dp[1][1][1] 1; for (int i 2; i 2025; i) { dp[i][0][0] (dp[i - 1][1][1] 3) % mod; dp[i][0][1] ((dp[i - 1][1][0] dp[i - 1][1][1]) 2) % mod; dp[i][1][0] ((dp[i - 1][0][1] dp[i - 1][1][1]) 1) % mod; dp[i][1][1] (dp[i - 1][0][0] dp[i - 1][0][1] dp[i - 1][1][0] dp[i - 1][1][1]) % mod; } cout (dp[2025][0][0] dp[2025][0][1] dp[2025][1][0] dp[2025][1][1]) % mod; return 0; }P12831 [蓝桥杯 2025 国 B] 互质藏卡题目描述小蓝整理着阁楼上的旧物偶然发现了一个落满灰尘的卡片箱。打开箱子里面整齐地摆放着 17600 张卡片每张卡片上都写有一个数字恰好包含了从 1 到 17600 的所有正整数。儿时的他热衷于收集各种卡牌数量之多令人咋舌。如今再次翻阅这些尘封的记忆小蓝不禁感慨万千。他想起收藏家前辈的箴言“收藏的魅力在于精粹而非数量”。于是他决定从这些卡牌中选取 2025 张组成一套“互质藏卡”。“互质藏卡”的特点在于任意两张卡片上的数字之间互质即它们的最大公约数恒为 1。现在请你帮小蓝计算共有多少种不同的选取方案使得选出的 2025 张卡片满足“互质藏卡”的条件。由于答案可能很大你只需给出其对 1097 取余后的结果即可。注意两个选取方案被认为是不同的当且仅当它们所包含的数字集合不完全相同。即若存在至少一个数字出现在其中一个集合但不出现在另一个集合中则这两个方案被视为不同。输入格式无输出格式这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。输入输出样例无实现代码#include bits/stdc.h using namespace std; int main() { cout174149196; return 0; }P12832 [蓝桥杯 2025 国 B] 数字轮盘题目描述“数字轮盘”是一款益智游戏基于一个带有指针的圆形轮盘展开。轮盘边缘按顺时针刻有数字 1 至 N初始时指针指向 1。游戏分为两阶段旋转轮盘和恢复轮盘。第一阶段将轮盘顺时针旋转 K 次。每次旋转数字依次后移一位指针指向的数字随之改变。例如对于 N4 的轮盘初始状态为 1, 2, 3, 4指针指向 1旋转一次变为 4, 1, 2, 3指针指向 4再旋转一次变为 3, 4, 1, 2指针指向 3依此类推。第二阶段小蓝需通过操作恢复初始状态每次操作包含以下两步第一步翻转以指针为起点、顺时针方向的前 N−1 个数字的顺序。第二步翻转除指针外的 N−1 个数字的顺序。例如对 N4状态为 4, 1, 2, 3指针指向 4进行一次操作第一步翻转 4, 1, 2变为 2, 1, 4, 3指针指向 2。第二步翻转 1, 4, 3变为 2, 3, 4, 1指针指向 2。现在给定轮盘的数字个数 N 和旋转次数 K请计算小蓝最少需要几次操作才能恢复初始状态。如果无法恢复初始状态则输出 -1。输入格式输入的第一行包含一个整数 T表示测试用例的数量。接下来 T 行每行包含两个整数 N 和 K分别表示轮盘上的数字个数和旋转次数。输出格式输出共 T 行每行包含一个整数表示最少需要的操作次数。如果无法恢复初始状态则输出 −1。输入输出样例输入 #1复制2 3 2 4 1输出 #1复制2 -1说明/提示【评测用例规模与约定】对于 30% 的评测用例1≤T≤1022≤N≤5000≤K≤500。对于 100% 的评测用例1≤T≤1052≤N≤1090≤K≤109。实现代码#includebits/stdc.h using namespace std; int t,n,k; int main(){ cint; while(t--){ cinnk; int x(n-k%n)%n; if(x%20)coutx/2\n; else if((xn)%20)cout(xn)/2\n; else cout-1\n; } return 0; }P12833 [蓝桥杯 2025 国 B] 斐波那契字符串提交答案加入题单复制题目题目描述斐波那契字符串 S 是由 0 和 1 所组成的字符串其生成规则如下S1​0。S2​1。对于任意正整数 n(n≥3)Sn​Sn−2​Sn−1​“”表示字符串拼接。例如S3​01、S4​101、S5​01101。在斐波那契字符串 S 中定义逆序对为满足以下条件的整数对 (i,j):1≤ij≤∣S∣其中 ∣S∣ 表示 S 的长度。S[i]1第 i 个字符为 1并且 S[j]0第 j 个字符为 0。现在给定一个正整数 N请你计算出 SN​ 中所有逆序对 (i,j) 的总数。由于结果可能很大请输出其对 1097 取余后的值。输入格式输入的第一行包含一个整数 T表示测试用例的数量。接下来的 T 行每行包含一个整数 N表示要计算的斐波那契字符串的序号。输出格式对于每个测试用例输出一行包含一个整数表示 SN​ 中所有逆序对的总数对 1097 取余后的结果。输入输出样例输入 #1复制2 3 5输出 #1复制0 2说明/提示【样例说明】对于 N3S3​01逆序对总数为 0。对于 N5S5​01101逆序对为 (2,4)、(3,4)总数为 2。【评测用例规模与约定】对于 20% 的评测用例1≤T≤203≤N≤35。对于 100% 的评测用例1≤T≤1053≤N≤105。实现代码#include bits/stdc.h using namespace std; typedef long long ll; const int N 1e5 7; const ll Mod 1e9 7; int t, n; ll dp [N], Zero [N], One [N]; int main() { ios:: sync_with_stdio(0); cin.tie(0), cout.tie(0); Zero [1] 1, Zero [2] 0; One [1] 0, One [2] 1; dp [1] 0, dp [2] 0; for (int i 3; i N - 7; i) { Zero [i] (Zero [i - 1] Zero [i - 2]) % Mod; One [i] (One [i - 1] One [i - 2]) % Mod; dp [i] (dp [i - 1] dp [i - 2] Zero [i - 1] * One [i - 2]) % Mod; } cin t; while (t--) { cin n; cout dp [n] \n; } return 0; }P12834 [蓝桥杯 2025 国 B] 项链排列题目描述小蓝有 A 颗蓝珠用字符 L 表示和 B 颗桥珠用字符 Q 表示他打算用这些珠子串成一条项链。他认为项链的美感主要体现在其视觉“变化”上当项链中任意两个相邻的珠子种类不同时就记为产生了一次“变化”。为了系统地研究不同排列的美感小蓝将每一种项链的排列方式表示为一个长度为 AB 的字符串。这个字符串由 A 个字符 L 和 B 个字符 Q 组成。相应地一条项链的“变化次数”即为这个字符串中所有相邻且不相同的字符对的数目。例如如果项链的排列是“LLQLQ”那么第 1 个 L 和第 2 个 L 相同无变化。第 2 个 L 和第 3 个 Q 不同产生了 1 次变化。第 3 个 Q 和第 4 个 L 不同产生了 1 次变化。第 4 个 L 和第 5 个 Q 不同产生了 1 次变化。排列“LLQLQ”的总“变化次数”为 3。现在小蓝希望找到一种项链排列使其总“变化次数”恰好为 C。对此请你帮他在所有满足这一条件的排列中找出字典序最小的那一个。如果不存在任何满足条件的排列方式则输出 -1。输入格式输入仅一行包含三个整数 AB 和 C分别表示蓝珠数量、桥珠数量和目标变化次数。输出格式输出一个长度为 AB 的字符串表示字典序最小的满足条件的排列。如果不存在这样的排列则输出 −1。输入输出样例输入 #1复制2 2 2输出 #1复制LQQL输入 #2复制2 2 3输出 #2复制LQLQ输入 #3复制2 2 4输出 #3复制-1说明/提示【评测用例规模与约定】对于 20% 的评测用例0≤A,B,C≤1001≤AB≤200。对于 100% 的评测用例0≤A,B,C≤1061≤AB≤2×106。实现代码#include bits/stdc.h using namespace std; typedef long long ll; const int N 1e5 7; int a, b, c; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin a b c; if (!c) { if (a ! 0 b ! 0) { cout -1; } else { for (int i 1; i a; i) cout L; for (int i 1; i b; i) cout Q; } return 0; } int Lneed c / 2 1; int Qneed (c 1) / 2; if (a Lneed b Qneed) { for (int i 1; i a - Lneed; i) cout L; for (int i 1; i Lneed Qneed - 1; i) { if (i 1) cout L; else cout Q; } if ((Lneed Qneed) 1) { for (int i 1; i b - Qneed; i) cout Q; cout L; } else { cout Q; for (int i 1; i b - Qneed; i) cout Q; } } else { swap(Lneed, Qneed); if (a Lneed || b Qneed) { cout -1; return 0; } for (int i 1; i Qneed Lneed; i) { if (i 1) cout Q; else cout L; } for (int i 1; i b - Qneed; i) cout Q; } return 0; }P12836 [蓝桥杯 2025 国 B] 翻倍题目描述给定 n 个正整数 A1​,A2​,…,An​每次操作可以选择任意一个数翻倍。请输出让序列单调不下降也就是每个数都不小于上一个数最少需要操作多少次输入格式输入的第一行包含一个正整数 n。第二行包含 n 个正整数 A1​,A2​,…,An​。输出格式输出一个整数表示需要的最小操作次数。输入输出样例输入 #1复制6 4 3 2 1 7 9输出 #1复制8说明/提示【样例说明】可以将序列变为: 4,6,8,8,14,18总计需要 0123118 次操作。【评测用例规模与约定】对于 20% 的评测用例n≤10,Ai​≤100。对于 50% 的评测用例n≤5000,Ai​232保证存在操作可以在所有 Ai​ 小于 232 的情况下满足题目要求。对于 100% 的评测用例1≤n≤2×105,1≤Ai​232。实现代码#includebits/stdc.h #define int long long using namespace std; int a[200005]; signed main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n,ans0,sum0;cinn; for(int i1;in;i)cina[i]; for(int i2;in;i) { sumceil(log2(1.*a[i-1]/a[i])); sumsum0?0:sum; anssum; } coutans; return 0; }P12838 [蓝桥杯 2025 国 B] 子串去重题目描述给定一个字符串 S 以及若干组询问每个询问包含两个区间 (La​,Ra​), (Lb​,Rb​)你需要判定 SLa​​,SLa​1​,…,SRa​​ 与 SLb​​,SLb​1​,…,SRb​​ 去重后有多少个位置上的字符是不同的。这里的去重指的是每个子串对于每种字符只保留第一个出现的那个后续出现的直接丢弃。例如 aabcbac 在选中区间 [1,5] 时得到子串 aabcb去重后为 abc选中区间 [3,6] 时得到 bcba去重后为 bca。特别地两个长度不同的子串中较长串的多出的部分每个位置都视为不同。输入格式输入第一行包含一个字符串 S。第二行包含一个整数 m表示询问次数。接下来 m 行每行包含四个整数表示一次询问。输出格式输出共 m 行每行一个整数对应每次询问的答案。输入输出样例输入 #1复制aabcbabacdab 3 1 1 2 2 1 10 6 9 4 7 9 12输出 #1复制0 1 2说明/提示【评测用例规模与约定】对于 40% 的评测用例∣S∣≤10, m1。对于 60% 的评测用例∣S∣,m≤5000。对于 100% 的评测用例1≤∣S∣,m≤105, 1≤La​≤Ra​≤∣S∣, 1≤Lb​≤Rb​≤∣S∣。实现代码#include bits/stdc.h #define int long long using namespace std; int b[35][100005]; char a[100005], ans[2][35]; int m, len, l1, r1, l2, r2; struct num { char fc; int fi; } nit[35]; bool cmp (num a1, num b1) { return a1.fi b1.fi; } int igh (int l, int r, int cv) { l --, r --; int len0 0; for (int i 0; i 26; i ) { nit[i].fc a i; nit[i].fi b[i][l]; } sort(nit, nit 26, cmp); for (int i 0; i 26; i ) { if (nit[i].fi r) ans[cv][i] \0; else ans[cv][i] nit[i].fc, len0 ; } return len0; } int wes (int len1, int len2) { int mlen max(len1, len2), end 0; for (int i 0; i mlen; i ) end (ans[0][i] ! ans[1][i]); return end; } signed main () { scanf(%s, a); len strlen(a); for (int i 0; i 26; i ) b[i][len] len; for (int i len -1; i 0; i --) { for (int i1 0; i1 26; i1 ) b[i1][i] b[i1][i 1]; b[a[i] -a][i] i; } scanf(%lld, m); for (int i 0; i m; i ) { scanf(%lld %lld %lld %lld, l1, r1, l2, r2); printf(%lld\n, wes(igh(l1, r1, 0), igh(l2, r2, 1))); } return 0; }P12835 [蓝桥杯 2025 国 B] 蓝桥星数字题目描述地球上我们习惯用十进制数字来记录万物从个位、十位逐级向上构成了我们熟悉的自然数体系。然而在遥远的蓝桥星数字的排列和解读方式却与我们截然不同。蓝桥星人并不单纯地以数值大小来衡量一个数字他们更注重数字内部蕴含的“节奏感”。因此对他们而言任何一个有效的数字其从左到右每一位上的数字奇偶性都必须是交替出现的。例如对于 10 这个数字其十位是奇数 1个位是偶数 0呈现奇偶交替因此 10 是个有效的数字。而对于 13 这个数字其十位是奇数 1个位也是奇数 3不符合奇偶交替的条件因此 13 不是个有效的数字。根据这个规则蓝桥星的数字序列从 10 开始依次为 10,12,14,16,18,21,23,25,27,29,30,…。只不过随着文明的发展蓝桥星人需要一种方法来快速找到第 N 个符合这种奇偶交替规则的数字以满足其日益增长的数字处理需求。现在请你帮助蓝桥星人编写程序找出并输出第 N 个符合奇偶交替规则的数字。输入格式输入包含一个正整数 N表示需要查找第 N 个符合规则的数字。输出格式输出一个整数表示第 N 个符合奇偶交替规则的数字。输入输出样例输入 #1复制1输出 #1复制10输入 #2复制11输出 #2复制30说明/提示【评测用例规模与约定】对于 20% 的评测用例1≤N≤105。对于 100% 的评测用例1≤N≤1012。实现代码#includebits/stdc.h #define LL long long #define UInt unsigned int #define ULL unsigned long long #define LD long double #define pii pairint,int #define pLL pairLL,LL #define pDD pairLD,LD #define fr first #define se second #define pb push_back #define isr insert using namespace std; LL n,tmp,len,flag; LL read(){ LL su0,pp1;char chgetchar(); while(ch0||ch9){if(ch-)pp-1;chgetchar();} while(ch0ch9){susu*10ch-0;chgetchar();} return su*pp; } int main(){ nread(); tmp45,len2; while(ntmp)n-tmp,len,tmp*5; tmp/9; n--; flag(n/tmp1)%2; coutn/tmp1; n%tmp; for(int i1;ilen;i){ tmp/5; cout(n/tmp)*21-flag; flag1-flag; n%tmp; }cout\n; return 0; }