目录前记斐波那契字符串题目思路关键代码总代码项链排列题目大意思路总代码翻倍题目大意思路总代码子串去重题目大意思路总代码前记本题解只包含了四道我认为赛时可以做出来的题目第一道编程题太简单我没加进去正常比赛中如果做对这五道题其他题的暴力再打满差不多有90多分国二肯定没问题国一也差不多。斐波那契字符串题目斐波那契字符串 S 是由 0 和 1 所组成的字符串其生成规则如下S10。S21。对于任意正整数 n(n≥3)SnSn−2Sn−1“”表示字符串拼接。例如S301、S4101、S501101。在斐波那契字符串 S 中定义逆序对为满足以下条件的整数对 (i,j):1≤ij≤∣S∣其中 ∣S∣ 表示 S 的长度。S[i]1第 i 个字符为 1并且 S[j]0第 j 个字符为 0。现在给定一个正整数 N请你计算出 SN 中所有逆序对 (i,j) 的总数。由于结果可能很大请输出其对 1097 取余后的值。对于 20% 的评测用例1≤T≤203≤N≤35。对于 100% 的评测用例1≤T≤3≤N≤。思路NT都很大如果对于每一个t都重新求出对于的斐波那契字符串然后再求其逆序对数的话定然得不了全分此时我们就开始想优化很明显一个思路方向是每个新字符串都是由前两个字符串得来的那么每个新字符串的逆序对数是否也和前两个字符串有关系呢答案是显而易见的必然有关系新字符串的逆序对数前一个字符串的逆序对数前二个字符串的逆序对数两个字符串合体之后新增的逆序对数现在关键就是要确定两个字符串合体之后新增的逆序对数求出之后直接递推即可新增逆序对数很明显就是前二个字符串中1的个数*前一个字符串中0的个数现在问题又变成了求各个字符串中0和1的个数。这个还是很好求的也是直接递推上去就行。关键代码for(int i3; iN; i) { cnt0[i] (cnt0[i-1] cnt0[i-2]) % mod; cnt1[i] (cnt1[i-1] cnt1[i-2]) % mod; } for(int i3; iN; i) { dp[i] (dp[i-1] dp[i-2]) % mod; dp[i] (dp[i] (cnt1[i-2] * cnt0[i-1]) % mod) % mod; }总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N1e510; int dp[N]; int cnt0[N],cnt1[N]; void solve(){ int n; cinn; cout dp[n]%mod endl; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; cint; dp[1]dp[2]0; cnt0[1]1, cnt1[1]0; cnt0[2]0, cnt1[2]1; for(int i3; iN; i) { cnt0[i] (cnt0[i-1] cnt0[i-2]) % mod; cnt1[i] (cnt1[i-1] cnt1[i-2]) % mod; } for(int i3; iN; i) { dp[i] (dp[i-1] dp[i-2]) % mod; dp[i] (dp[i] (cnt1[i-2] * cnt0[i-1]) % mod) % mod; } while(t--) solve(); }项链排列题目大意给定a个‘L’b个‘Q’让你拼接成一个字符串L和Q如果相邻放置则该字符串变化次数1例如LQ的变化次数是1LQL的变化次数是2LQQLLQ的变化次数是3现在给你一个指定变化次数c问你如何对这个字符串进行排列才能确保该字符串的变化次数为c输出字典序最小的那个字符串思路本题是一道贪心我们先来看一下有哪几种情况会增加变化次数如上图所示共有两大种情况每种情况又分为两种小情况因为题目要求字典序最小所以肯定是第一种情况最优那么此时就需要确定什么时候才满足第一种情况什么时候满足第二种情况通过观察很明显发现第一种情况所需的L数第二种情况的L数但是Q数却正好相反那么巨头到底L数和Q数的满足条件是什么呢通过找几个例子就能得到int lneed1c/21,qneed1(c1)/2; int lneed2(c1)/2,qneed2c/21;对于满足第一种的此时可能会有多出的L和多出的Q此时再考虑安置这些多出来字符此时需要分两种小情况例如图中对于第一种小情况多出来的L直接插到最前面即可多出来的Q需要插到最后一个Q的后面也就是最后的字符L前面而对于第二种小情况L直接插到最前面不变此时Q直接插到最后面即可对于不满足第一种却满足第二种的此时我们发现定然不会存在多出来的L否则定然满足第一种条件此时只需插入多出的Q即可此时也需分为两种小情况第一个小情况定然不会存在因为可以转换成LQLQ只会存在第二种小情况此时多出来的Q直接插到最后即可不满足第一种也不满足第二种的直接输出-1注意需要特判c0的情况总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N1e510; void solve(){ int a,b,c; cin a b c; if (c0) { if (a0b0) { cout -1; return ; } for (int i0;ia;i) { cout L; } for (int i0;ib;i) { cout Q; } return ; } int lneed1c/21,qneed1(c1)/2; int lneed2(c1)/2,qneed2c/21; if (alneed1bqneed1) { int cnt0; vectorcharans; ans.push_back(L); ans.push_back(Q); cnt; int nmax(a,b)*2; a--,b--; for(int i2;in;i) { if (cntc) { break; } if (i%20) { ans.push_back(L),a--,cnt; } else ans.push_back(Q),b--,cnt; } if (ans.back()Q) { // cout 123244 endl; for (int i0;ia;i) { cout L; } for (int i0;ians.size();i) { cout ans[i]; } for (int i0;ib;i) { cout Q; } }else { for (int i0;ia;i) { cout L; } for (int i0;ians.size();i) { if (i!ans.size()-1) cout ans[i]; else { for (int j0;jb;j) { cout Q; } cout L; i; } } } }else if(alneed2bqneed2) { int cnt0; vectorcharans; ans.push_back(Q); ans.push_back(L); cnt; int nmax(a,b)*2; a--,b--; for(int i2;in;i) { if (cntc) { break; } if (i%20) { ans.push_back(Q),b--,cnt; // cout 1323 endl; }else ans.push_back(L),a--,cnt; } for (int i0;ians.size();i) { if (i!ans.size()-1) cout ans[i]; else { for (int j0;jb;j) { cout Q; } cout Q; i; } } }else { cout -1 ; } } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; // cint; while(t--) solve(); }翻倍题目大意给定一个长度为n正整数序列每次操作可以使得其中一个数翻倍问你最低操作多少次可以使得该序列整体非递减。思路暴力思路很好想直接遍历整个数组如果该数小于前面的数那么该数就一直循环倍增直至大于等于前面的数int ans 0; for(int i 2; i n; i) { while(a[i] a[i - 1]) { ans; a[i] * 2; } } cout ans endl;但这个肯定得不了满分我们此时考虑一下优化优化的主要部分就是这个while循环我们仔细一想会发现当前数翻倍的次数只与前一个数有关为了保证两数的相对大小关系不变前面的数翻多少倍那么后面的数同样翻多少倍此时就会出现一个问题后面的数有可能多翻好多倍也有可能少翻了好多倍此时我们再对倍数进行调整多翻了就循环--少翻了就循环注意是翻倍所以调整的过程时间复杂度是log级别的for (int i1;in;i) { cnt[i]cnt[i-1]; 继承前面数的翻倍情况保证相对大小不变 int xa[i],ya[i-1]; while (xy*2) { if (!cnt[i])break; cnt[i]--; y*2; } 注意循环条件只有xy*2时才会存在多翻的情况 while (xy) { cnt[i]; x*2; } xy代表少翻了还得继续翻倍 }总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N2e510; int a[N],cnt[N]; void solve(){ int n; cin n; for (int i0;in;i) { cin a[i]; } for (int i1;in;i) { cnt[i]cnt[i-1]; int xa[i],ya[i-1]; while (xy*2) { if (!cnt[i])break; cnt[i]--; y*2; } while (xy) { cnt[i]; x*2; } } int ans0; for (int i0;in;i) { anscnt[i]; } cout ans endl; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; // cint; while(t--) solve(); }子串去重题目大意给定一个字符串和m次询问每次询问给两个区间问你两个区间去重之后有多少个对应位置的字符不同字符串全是小写字母思路我们可以发现去重之后两个被询问的字串长度定然26此时就可以直接遍历求得答案主要是如何去重。我们从字串长度必然小于等于26这个地方起手我们可以不遍历区间而是从0-25遍历每个字符看这个字符在该区间第一次出现的位置我们需要提前预处理一个二维数组a[i][j]:从i开始字符j第一次出现的位置vectorvectorinta(n2,vectorint(26,n1)); for (int in;i1;i--) { a[i]a[i1]; a[i][s[i]-a]i; }求出来之后即可完成上面的想法如果第一次出现的位置区间右端点便可以插入到数组里int l1,l2,r1,r2; cin l1 r1 l2 r2; vectornodea1,a2; for (int i0;i26;i) { if (a[l1][i]r1) a1.emplace_back(i,a[l1][i]); } for (int i0;i26;i) { if (a[l2][i]r2) a2.emplace_back(i,a[l2][i]); }注意插入完需要根据位置进行排序总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N2e510; int n; struct node { int aa,bb; node(int a, int b) : aa(a), bb(b) {} }; bool cmp(struct node a,struct node b) { return a.bbb.bb; } void solve() { string s; cin s; s s; int m; ns.size()-1; vectorvectorinta(n2,vectorint(26,n1)); cin m; for (int in;i1;i--) { a[i]a[i1]; a[i][s[i]-a]i; } while (m--) { int l1,l2,r1,r2; cin l1 r1 l2 r2; vectornodea1,a2; for (int i0;i26;i) { if (a[l1][i]r1) a1.emplace_back(i,a[l1][i]); } for (int i0;i26;i) { if (a[l2][i]r2) a2.emplace_back(i,a[l2][i]); } sort(a1.begin(),a1.end(),cmp); sort(a2.begin(),a2.end(),cmp); int ans0; for (int i0;imin(a1.size(),a2.size());i) { if (a1[i].aa!a2[i].aa)ans; } ansmax(a1.size(),a2.size())-min(a1.size(),a2.size()); cout ans endl; } } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; // cint; while(t--) solve(); }
2025第十六届蓝桥杯c/c++B组国赛题解
目录前记斐波那契字符串题目思路关键代码总代码项链排列题目大意思路总代码翻倍题目大意思路总代码子串去重题目大意思路总代码前记本题解只包含了四道我认为赛时可以做出来的题目第一道编程题太简单我没加进去正常比赛中如果做对这五道题其他题的暴力再打满差不多有90多分国二肯定没问题国一也差不多。斐波那契字符串题目斐波那契字符串 S 是由 0 和 1 所组成的字符串其生成规则如下S10。S21。对于任意正整数 n(n≥3)SnSn−2Sn−1“”表示字符串拼接。例如S301、S4101、S501101。在斐波那契字符串 S 中定义逆序对为满足以下条件的整数对 (i,j):1≤ij≤∣S∣其中 ∣S∣ 表示 S 的长度。S[i]1第 i 个字符为 1并且 S[j]0第 j 个字符为 0。现在给定一个正整数 N请你计算出 SN 中所有逆序对 (i,j) 的总数。由于结果可能很大请输出其对 1097 取余后的值。对于 20% 的评测用例1≤T≤203≤N≤35。对于 100% 的评测用例1≤T≤3≤N≤。思路NT都很大如果对于每一个t都重新求出对于的斐波那契字符串然后再求其逆序对数的话定然得不了全分此时我们就开始想优化很明显一个思路方向是每个新字符串都是由前两个字符串得来的那么每个新字符串的逆序对数是否也和前两个字符串有关系呢答案是显而易见的必然有关系新字符串的逆序对数前一个字符串的逆序对数前二个字符串的逆序对数两个字符串合体之后新增的逆序对数现在关键就是要确定两个字符串合体之后新增的逆序对数求出之后直接递推即可新增逆序对数很明显就是前二个字符串中1的个数*前一个字符串中0的个数现在问题又变成了求各个字符串中0和1的个数。这个还是很好求的也是直接递推上去就行。关键代码for(int i3; iN; i) { cnt0[i] (cnt0[i-1] cnt0[i-2]) % mod; cnt1[i] (cnt1[i-1] cnt1[i-2]) % mod; } for(int i3; iN; i) { dp[i] (dp[i-1] dp[i-2]) % mod; dp[i] (dp[i] (cnt1[i-2] * cnt0[i-1]) % mod) % mod; }总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N1e510; int dp[N]; int cnt0[N],cnt1[N]; void solve(){ int n; cinn; cout dp[n]%mod endl; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; cint; dp[1]dp[2]0; cnt0[1]1, cnt1[1]0; cnt0[2]0, cnt1[2]1; for(int i3; iN; i) { cnt0[i] (cnt0[i-1] cnt0[i-2]) % mod; cnt1[i] (cnt1[i-1] cnt1[i-2]) % mod; } for(int i3; iN; i) { dp[i] (dp[i-1] dp[i-2]) % mod; dp[i] (dp[i] (cnt1[i-2] * cnt0[i-1]) % mod) % mod; } while(t--) solve(); }项链排列题目大意给定a个‘L’b个‘Q’让你拼接成一个字符串L和Q如果相邻放置则该字符串变化次数1例如LQ的变化次数是1LQL的变化次数是2LQQLLQ的变化次数是3现在给你一个指定变化次数c问你如何对这个字符串进行排列才能确保该字符串的变化次数为c输出字典序最小的那个字符串思路本题是一道贪心我们先来看一下有哪几种情况会增加变化次数如上图所示共有两大种情况每种情况又分为两种小情况因为题目要求字典序最小所以肯定是第一种情况最优那么此时就需要确定什么时候才满足第一种情况什么时候满足第二种情况通过观察很明显发现第一种情况所需的L数第二种情况的L数但是Q数却正好相反那么巨头到底L数和Q数的满足条件是什么呢通过找几个例子就能得到int lneed1c/21,qneed1(c1)/2; int lneed2(c1)/2,qneed2c/21;对于满足第一种的此时可能会有多出的L和多出的Q此时再考虑安置这些多出来字符此时需要分两种小情况例如图中对于第一种小情况多出来的L直接插到最前面即可多出来的Q需要插到最后一个Q的后面也就是最后的字符L前面而对于第二种小情况L直接插到最前面不变此时Q直接插到最后面即可对于不满足第一种却满足第二种的此时我们发现定然不会存在多出来的L否则定然满足第一种条件此时只需插入多出的Q即可此时也需分为两种小情况第一个小情况定然不会存在因为可以转换成LQLQ只会存在第二种小情况此时多出来的Q直接插到最后即可不满足第一种也不满足第二种的直接输出-1注意需要特判c0的情况总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N1e510; void solve(){ int a,b,c; cin a b c; if (c0) { if (a0b0) { cout -1; return ; } for (int i0;ia;i) { cout L; } for (int i0;ib;i) { cout Q; } return ; } int lneed1c/21,qneed1(c1)/2; int lneed2(c1)/2,qneed2c/21; if (alneed1bqneed1) { int cnt0; vectorcharans; ans.push_back(L); ans.push_back(Q); cnt; int nmax(a,b)*2; a--,b--; for(int i2;in;i) { if (cntc) { break; } if (i%20) { ans.push_back(L),a--,cnt; } else ans.push_back(Q),b--,cnt; } if (ans.back()Q) { // cout 123244 endl; for (int i0;ia;i) { cout L; } for (int i0;ians.size();i) { cout ans[i]; } for (int i0;ib;i) { cout Q; } }else { for (int i0;ia;i) { cout L; } for (int i0;ians.size();i) { if (i!ans.size()-1) cout ans[i]; else { for (int j0;jb;j) { cout Q; } cout L; i; } } } }else if(alneed2bqneed2) { int cnt0; vectorcharans; ans.push_back(Q); ans.push_back(L); cnt; int nmax(a,b)*2; a--,b--; for(int i2;in;i) { if (cntc) { break; } if (i%20) { ans.push_back(Q),b--,cnt; // cout 1323 endl; }else ans.push_back(L),a--,cnt; } for (int i0;ians.size();i) { if (i!ans.size()-1) cout ans[i]; else { for (int j0;jb;j) { cout Q; } cout Q; i; } } }else { cout -1 ; } } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; // cint; while(t--) solve(); }翻倍题目大意给定一个长度为n正整数序列每次操作可以使得其中一个数翻倍问你最低操作多少次可以使得该序列整体非递减。思路暴力思路很好想直接遍历整个数组如果该数小于前面的数那么该数就一直循环倍增直至大于等于前面的数int ans 0; for(int i 2; i n; i) { while(a[i] a[i - 1]) { ans; a[i] * 2; } } cout ans endl;但这个肯定得不了满分我们此时考虑一下优化优化的主要部分就是这个while循环我们仔细一想会发现当前数翻倍的次数只与前一个数有关为了保证两数的相对大小关系不变前面的数翻多少倍那么后面的数同样翻多少倍此时就会出现一个问题后面的数有可能多翻好多倍也有可能少翻了好多倍此时我们再对倍数进行调整多翻了就循环--少翻了就循环注意是翻倍所以调整的过程时间复杂度是log级别的for (int i1;in;i) { cnt[i]cnt[i-1]; 继承前面数的翻倍情况保证相对大小不变 int xa[i],ya[i-1]; while (xy*2) { if (!cnt[i])break; cnt[i]--; y*2; } 注意循环条件只有xy*2时才会存在多翻的情况 while (xy) { cnt[i]; x*2; } xy代表少翻了还得继续翻倍 }总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N2e510; int a[N],cnt[N]; void solve(){ int n; cin n; for (int i0;in;i) { cin a[i]; } for (int i1;in;i) { cnt[i]cnt[i-1]; int xa[i],ya[i-1]; while (xy*2) { if (!cnt[i])break; cnt[i]--; y*2; } while (xy) { cnt[i]; x*2; } } int ans0; for (int i0;in;i) { anscnt[i]; } cout ans endl; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; // cint; while(t--) solve(); }子串去重题目大意给定一个字符串和m次询问每次询问给两个区间问你两个区间去重之后有多少个对应位置的字符不同字符串全是小写字母思路我们可以发现去重之后两个被询问的字串长度定然26此时就可以直接遍历求得答案主要是如何去重。我们从字串长度必然小于等于26这个地方起手我们可以不遍历区间而是从0-25遍历每个字符看这个字符在该区间第一次出现的位置我们需要提前预处理一个二维数组a[i][j]:从i开始字符j第一次出现的位置vectorvectorinta(n2,vectorint(26,n1)); for (int in;i1;i--) { a[i]a[i1]; a[i][s[i]-a]i; }求出来之后即可完成上面的想法如果第一次出现的位置区间右端点便可以插入到数组里int l1,l2,r1,r2; cin l1 r1 l2 r2; vectornodea1,a2; for (int i0;i26;i) { if (a[l1][i]r1) a1.emplace_back(i,a[l1][i]); } for (int i0;i26;i) { if (a[l2][i]r2) a2.emplace_back(i,a[l2][i]); }注意插入完需要根据位置进行排序总代码#includebits/stdc.h using namespace std; #define int long long #define endl \n const int mod1e97; const int N2e510; int n; struct node { int aa,bb; node(int a, int b) : aa(a), bb(b) {} }; bool cmp(struct node a,struct node b) { return a.bbb.bb; } void solve() { string s; cin s; s s; int m; ns.size()-1; vectorvectorinta(n2,vectorint(26,n1)); cin m; for (int in;i1;i--) { a[i]a[i1]; a[i][s[i]-a]i; } while (m--) { int l1,l2,r1,r2; cin l1 r1 l2 r2; vectornodea1,a2; for (int i0;i26;i) { if (a[l1][i]r1) a1.emplace_back(i,a[l1][i]); } for (int i0;i26;i) { if (a[l2][i]r2) a2.emplace_back(i,a[l2][i]); } sort(a1.begin(),a1.end(),cmp); sort(a2.begin(),a2.end(),cmp); int ans0; for (int i0;imin(a1.size(),a2.size());i) { if (a1[i].aa!a2[i].aa)ans; } ansmax(a1.size(),a2.size())-min(a1.size(),a2.size()); cout ans endl; } } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t1; // cint; while(t--) solve(); }
