第十四届蓝桥杯CB组（2023年）题解

CDEFGHI题解目录C冶炼金属C冶炼金属最大值为每个a/b 的最小值最小值为每个a/b11 的最大值mx min (mx, a/b); mn max (mn, a/(b1)1);D飞机降落最多12个飞机dfs即可 通过回溯算法把n个飞机全排列计算能维护到最后一个飞机就return true否则return false 每次在访问i时通过vis数组标记i已经成功降落dfs结束后vis归0回溯到其没有访问的状态实现全排列st表示第i个飞机成功降落now表示当前的时间只有当前飞机燃油耗尽前这个时间比now 现在的时间加上降落时间 要晚 才能成功降落否则失败#includebits/stdc.h using namespace std; #define ll long long #define pii pairint, int #define all(a) a.begin(), a.end() #define auto(i, n) int i1; in; i const int N 500000; int n; bool v[12], can; struct plane { int a, b, c; }; vectorplane p(12); bool dfs(int st, int now) { if(st n) { return 1; } for(int i0; in; i) { if(v[i] || p[i].ap[i].b now) continue; v[i] 1; if(dfs(st1, max(now, p[i].a) p[i].c)) { return 1; } v[i] 0; } return 0; } void sol() { cin n; memset(v, 0, sizeof(v)); for(int i0; in; i) cin p[i].a p[i].b p[i].c; if(dfs(1, 0)) cout YES\n; else cout NO\n; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin t; while(t--) sol(); }E接龙数列一道dp题dp[i][j] 表示第i个数 j意思为第i个数以j结尾 frontback 分别表示 第一个数和最后一个数以下用两种方法解释1二维dpiback 与 i-1 front 相对应时 可以进行状态转移否者直接取上一步的值也就是第i个数的头要和第i-1的尾相接 对i-1 其尾为当前状态的front 而叠加后的状态应该累加的back上面也是就是以back结尾dp[i][back] max(dp[i-1][back], dp[i-1][front] 1);for (int j0; j9; j ) {if (j ! back) {dp[i][j] dp[i-1][j];}}能接上就去 加上i-1或者不加的最大值否则只能取上一步的值#includebits/stdc.h #define ll long long #define pii pairint,int #define pll pairll,ll using namespace std; const int N 2e5 5; int main() { int n; cin n ; vectorvectorint dp(n1,vectorint(10,0)); for (int i1; in; i) { string s; cin s; int front s[0] - 0; int back s[s.size() - 1] - 0; dp[i][back] max(dp[i-1][back], dp[i-1][front] 1); for (int j0; j9; j ) { if (j ! back) { dp[i][j] dp[i-1][j]; } } } int mx *max_element(dp[n].begin(), dp[n].end()); cout n - mx; }2一维dp发现后面的决策是在前面状态完成情况下进行转移的 不会影响到当前状态可以对状态进行压缩dp[i], 其中i为以i结尾的数能接的最大值开个0-9的dp就行 int dp[10],状态转移方程为dp[back] max(dp[back], dp[front]1);#includebits/stdc.h #includebitset #define ll long long #define pii pairint,int #define pll pairll,ll using namespace std; const int N 2e5 5; int main() { ios::sync_with_stdio(0); int n; cin n; vectorint dp(10, 0); int mx 0; for (int i0; in; i) { string s; cin s; int front s[0] - 0; int back s[s.size()-1] - 0; dp[back] max(dp[back], dp[front] 1); mx max(mx, dp[back]); } cout n - mx; }F岛屿个数以下有空更新对岛屿进行两次遍历第一次把岛屿联通第二次检查非岛中岛 注意水是可以8处蔓延的所以第一次bfs 是 dx[4], dy[4], 第二次是dx[8], dy[8], 然后我们让水从边界开始找如果能找到就是一个岛如果水斜着走都找不到就是岛中岛将每一个联通岛标记一个相同的数字 在第二次bfs时能标记到几个数字就是几个岛#includebits/stdc.h using namespace std; int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; int dx1[8] {0,0,1,-1,1,-1,1,-1}; int dy1[8] {1,-1,0,0,-1,1,1,-1}; void sol() { int n,m; cin n m; vectorvectorint mp(n20, vectorint(m20, 0)); for (int i1; in; i) for (int j1; jm; j) { char k; cin k; mp[i][j] (int)(k-0); } int have 1; functionvoid(int,int) dfs [](int i, int j) { mp[i][j] have; for (int k0; k4; k) { int xx i dx[k]; int yy j dy[k]; if (xx 1 || xx n || yy 1 || yy m) continue; if (mp[xx][yy] ! 1) continue; dfs(xx, yy); } }; for (int i1; in; i) { for (int j1; jm; j) { if (mp[i][j] 1) { have; dfs(i, j); } } } vectorvectorbool vis(n20, vectorbool(m20, false)); vectorbool find(have50, false); queuepairint,int q; q.push({0, 0}); vis[0][0] true; int ans 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int i0; i8; i) { int xx x dx1[i]; int yy y dy1[i]; if (xx 0 || yy 0 || xx n2 || yy m2) continue; if (vis[xx][yy]) continue; vis[xx][yy] true; if (mp[xx][yy] ! 0) { int c mp[xx][yy]; if (!find[c] c 2) { find[c] true; ans; } } else { q.push({xx, yy}); } } } cout ans endl; } int main() { int t; cin t; while (t--) sol(); }G子串简写前缀思想不再阐述#includebits/stdc.h #includebitset #define ll long long #define pii pairint,int #define pll pairll,ll using namespace std; const int N 2e5 5; string t; char a,b; long long res,len,k; int cnt[500005]; int main(){ cin k t a b ; len t.size(); cnt[0] 0; for(int i1; ilen; i){ cnt[i] cnt[i-1] (t[i-1]a); } for(int ik-1; ilen; i){ if(t[i]b){ res cnt[i-k2]; } } cout res; }H整数删除有空会更新解释 现在只放代码注意蓝桥杯样例是全对的洛谷有一个样例不过#include bits/stdc.h using namespace std; #define int long long const int N 5e5 10; struct st { int num, pos; }; struct cmp { bool operator()(st x, st y) { if (x.num y.num) return x.pos y.pos; return x.num y.num; } }; priority_queuest, vectorst, cmp q; int l[N], r[N]; int ans[N], add[N]; int n, k; signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin n k; for (int i1; in; i) { int x; cin x; q.push({x, i}); l[i] i - 1; r[i] i 1; } while (q.size() n - k) { auto [x, y] q.top(); q.pop(); if (add[y]) { q.push({x add[y], y}); add[y] 0; } else { int pl l[y], pr r[y]; add[pl] x; add[pr] x; l[pr] pl; r[pl] pr; } } while (q.size()) { auto [x, y] q.top(); q.pop(); ans[y] x add[y]; } for (int i1; in; i) if (ans[i]) cout ans[i] ; return 0; }