第十五届蓝桥杯软件赛C/C++大学A组个人省赛题解
这是我第一次参加蓝桥杯。说实话蓝桥杯在中的含金量确实不算高（保研加分等都不看。。。），而且据说蓝桥杯获奖也比较容易，但我个人觉得蓝桥杯出的题中还是不乏很多好题的，包括蓝桥杯的算法双周赛，部分题目还是非常让人眼前一亮的，（比如兽之泪https://www.lanqiao.cn/problems/16999/learning/?contest_id=175和兽之泪IIhttps://www.lanqiao.cn/problems/17169/learning/?contest_id=181，感觉是今年遇到的最好的一套贪心类型的题目(可以理解为easy version和hard version)了）。
而昨天蓝桥杯省赛结果刚刚发布，我获得了北京赛区的省一等奖，并且晋级国赛，这里分享一下蓝桥杯A组较为靠前的一等奖大致做题情况，同时补上全部的个人题解，以供后来者参考。
今年题型改革，满分变为100分，我个人感觉北京赛区大致50分左右是省一线，题目难度感觉也比较合适，没有特别的困难，因为我但是考试是和高数考试撞了，所以5个小时的比赛我只做了3.5h，由于是OI赛制，不敢大意，又花了30min每道题都重新检查并提交了一遍才离开的考场，所以考场上难免有些犯浑，也希望国赛能拿到一个好成绩吧，（虽然好像又要撞期末考了......这个时间安排真得吐槽一下（（
3228
直接建立好数字与笔画的对应，然后按照蓝桥杯常见的日期问题写法开个大循环来进行模拟就好，要特别注意闰年的处理。
3126376
注意到题目要求我们求的是最终平局的局面，首先所有的局面我们都可以通过DFS来进行处理，一种种，我们要排除五子连珠的情况，并且要求黑子数为，白子数为，明确好这些以后就让计算机慢慢跑就好了。值得留意的是，我写题解的时候自家电脑跑得飞快，但是学校机房电脑确实不是很咋地，这题也跑了好一会儿。
#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;const int N = 1e5+5; int n, m, ans = 0;int a[6][6];inline int check(){ int res = 0; for(int i=1;i<=5;i++){ bool flag = 1; for(int j=1;j<=5;j++){ res += a[i][j]; if(j>1 && a[i][j]!=a[i][j-1]) flag = 0; } if(flag) return 0; } for(int j=1;j<=5;j++){ bool flag = 1; for(int i=1;i<=5;i++){ if(i>1 && a[i][j]!=a[i-1][j]) flag = 0; } if(flag) return 0; } if(a[1][1] == a[2][2] && a[2][2] == a[3][3] && a[3][3] == a[4][4] && a[4][4] == a[5][5]) return 0; if(a[5][1] == a[4][2] && a[4][2] == a[3][3] && a[3][3] == a[2][4] && a[2][4] == a[1][5]) return 0; return res == 13 ? 1 : 0;}inline void dfs(int idx){ if(idx==25){ a[5][5] = 0; ans += check(); a[5][5] = 1; ans += check(); return ; } int x = idx/5 + (idx%5==0 ? 0 : 1); int y = idx%5==0 ? 5 : idx%5; a[x][y] = 0; dfs(idx+1); a[x][y] = 1; dfs(idx+1); }signed main(){ IOS; dfs(1); cout << ans << endl; return 0;}
这题难度很小，考虑到一次的训练成本肯定是取，我们直接按照训练次数来统计一次训练下的人数，从而比较成本，结合下面的代码我们可以简化模拟过程，时间复杂度。
#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;const int N = 1e5+5; int n, S;int c[N];map<int,int> mp;signed main(){ IOS; cin >> n >> S; int p, sum = 0, ans = 0; for(int i=1;i<=n;i++){ cin >> p >> c[i]; mp[c[i]] += p; sum += p; } vector<pii> v(all(mp)); int now = 0; for(int i=0;i<v.size();i++){ ans += (v[i].first-now) * min(S, sum); sum -= v[i].second; now = v[i].first; } cout << ans << endl; return 0;}
这道题我个人觉得出得不错，首先考虑到两边 可能会超时，我们直接根据前缀相同这一限制条件来进行剪枝处理，故我们采用dfs(int u, int fu, int v, int fv, int dep)的形式来进行一次处理，只走相同路，每次来用dep更新ans就好，时间复杂度。
#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;const int N = 2e5+5; int n, m, ans = 0;int a[N], b[N];vector<int> A[N], B[N];inline void dfs(int u, int fu, int v, int fv, int dep){ ans = max(ans, dep); map<int,int> mp; for(int sonu:A[u]){ if(sonu==fu) continue; mp[a[sonu]] = sonu; } for(int sonv:B[v]){ if(sonv==fv) continue; if(mp.count(b[sonv])) dfs(mp[b[sonv]], u, sonv, v, dep+1); }}signed main(){ IOS; cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=m;i++) cin >> b[i]; int u, v; for(int i=1;i<n;i++){ cin >> u >> v; A[u].push_back(v); A[v].push_back(u); } for(int i=1;i<m;i++){ cin >> u >> v; B[u].push_back(v); B[v].push_back(u); } if(a[1]==b[1]) dfs(1,0,1,0,1); cout << ans << endl; return 0;}
首先不得不吐槽考场上看到这道题的叙述的时候真是两眼一黑，甚至怀疑是自己记错了方差公式，大雾（（。但是看题来分析，如果答案存在，答案肯定是一个介于的整数，我们直接利用二分来提高效率（但是我考场上好像用了直接暴力...），然后就是二分过后采用排序思想，利用方差公式展开，得到 ，这个技巧我们采用前缀和处理即可通过此题，时间复杂度大概为
#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;const int N = 1e5+5; int n, k;double T;int a[N], aa[N];int pref[N], pref_squ[N];inline bool check(int x){ sort(aa+1, aa+1+x); for(int i=1;i<=x;i++){ pref[i] = pref[i-1]+aa[i]; pref_squ[i] = pref_squ[i-1]+aa[i]*aa[i]; } for(int i=k;i<=x;i++){ double variance = 1.0 / k * pref_squ[i] - 1.0 / (k * k) * pref[i] * pref[i]; if(variance < T) return 1; } return 0;}signed main(){ IOS; cin >> n >> k >> T; for(int i=1;i<=n;i++){ cin >> a[i]; aa[i] = a[i]; } if(n<k) return cout << "-1\n", 0; int lo = k, hi = n; while(lo<hi){ int mid = lo + (hi-lo>>1); if(check(mid)) hi = mid; else lo = mid+1; for(int i=1;i<=mid;i++) aa[i] = a[i]; } if(check(lo)) cout << lo << endl; else cout << "-1\n"; return 0;}
这是一道非常困难的题，在考场上没什么思路，折腾了好一会儿还是决定拿四重循环暴力骗分......但是这道题的正确思路应该是考虑容斥：很明显，我们可以很快处理完“倍数-因数”二元组的个数，而四元组我们可以直接通过平方处理来简单得到一个初步答案，接下来一个一个考虑容斥部分，减去重复的，加上重复减去后又多减的部分就可以得到最后的答案了。不过貌似最极端的数据是可以卡出超long long的，因此可能还得用__int128来处理，下面代码在dotcpp上已经可以通过，就没有用__int128，不过下面的代码给出了__int128可以接受的输入和输出（即快速读入和快速写出read(T& X)、write(T x)），直接套用即可。
//考场上的30分题解#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;const int N = 1e5+5;int n;int a[N];signed main(){ IOS; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; sort(a+1,a+1+n); int ans = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(j==i) continue; for(int k=1;k<=n;k++){ if(k==i || k==j) continue; for(int l=1;k<=n;k++){ if(l==i || l==j || l==k) continue; if(a[k]%a[i]==0 && a[l]%a[j]==0) ++ans; } } } } cout << ans << endl; return 0;}//赛后100分题解#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;template <class T> inline void read(T& x) { x = 0; char c = getchar(); bool f = 0; for (; !isdigit(c); c = getchar()) f ^= (c == '-'); for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48); x = f ? -x : x; }template <class T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x < 10) putchar(x + 48); else write(x / 10), putchar(x % 10 + 48); }const int N = 1e5+5; int n, m;int h[N], f[N], g[N]; // f[i]为i的倍数个数， g[i]为i的因子个数signed main(){ IOS; cin >> n; int x; for(int i=1;i<=n;i++){ cin >> x; h[x]++; } int ans = 0; for(int i=1;i<N;i++){ for(int j=i;j<N;j+=i){ f[i] += h[j]; g[j] += h[i]; } ans += h[i]*(f[i]-1); //计算 倍数-因数 二元组的个数 } ans = ans*(ans-1); for(int i=1;i<N;i++){ ans -= h[i]*(f[i]-1)*(f[i]-2); ans -= h[i]*(g[i]-1)*(g[i]-2); ans -= h[i]*(f[i]-1)*(g[i]-1)*2; ans += h[i]*(h[i]-1); } cout << ans << endl; return 0;}
这是一道图论题，但是题目并不复杂，难度不算特别大。但是我考场上一眼以为是dijkstra最短路问题，结果发现权边都为，那就直接用普通bfs就可以了，但是题目是多次询问，考场上我直接纯bfs + 状态压缩 ＋ 记忆化搜索来处理的，估计只得了30分。那正确的思路应该是什么呢？
我们考虑用dfs来处理，后面寻路的时候采用倍增法求LCA，看到零食最大也就很容易想到状态压缩，所以我们的目标就是到与到的零食之和，我们可以开数组来帮助我们进行最多次的跳转，然后通过公共祖先来解决这个问题。
//考场上的30分题解#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;const int N = 1e5+5; int n, q;int c[N], dis[N];vector<int> g[N];map<pii,int> mp;inline int bfs(int S, int T){ for(int i=1;i<=n;i++) dis[i] = 1e18; queue<pii> q; q.push({S, 1<<c[S]}); dis[S] = 0; while(q.size()){ int now = q.front().first, st = q.front().second; q.pop(); if(now==T) return __builtin_popcountll(st); for(int nxt:g[now]){ if(dis[nxt]>dis[now]+1){ dis[nxt] = dis[now]+1; q.push({nxt, st | (1<<c[nxt])}); } } }}signed main(){ IOS; cin >> n >> q; for(int i=1;i<=n;i++) cin >> c[i]; int u, v; for(int i=1;i<n;i++){ cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } int S, T; while(q--){ cin >> S >> T; if(S>T) swap(S, T); if(!mp.count({S, T})) mp[{S, T}] = bfs(S, T); cout << mp[{S, T}] << endl; } return 0;}//赛后100分题解#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()using namespace std;const int N = 1e5+5;int n, q, c[N];int anc[N][21], col[N][21], dep[N];vector<int> g[N];inline void dfs(int u, int fa){ dep[u] = dep[fa]+1; anc[u][1] = fa; col[u][1] = 1LL<<c[u]; for(int i=1;i<20;i++){ if(!anc[u][i]) break; else{ anc[u][i+1] = anc[anc[u][i]][i]; col[u][i+1] = col[u][i] | col[anc[u][i]][i]; } } for(int v:g[u]){ if(v==fa) continue; dfs(v, u); }}inline int LCA(int u, int v){ int i; if(dep[u]<dep[v]) swap(u, v); for(int i=20;i>=1;i--){ if(dep[anc[u][i]]>=dep[v]) u = anc[u][i]; } if(u==v) return u; for(int i=20;i>=1;i--){ if(anc[u][i]!=anc[v][i]) u = anc[u][i], v = anc[v][i]; } return anc[u][1];}inline int get(int u, int v){ int ret = 0; for(int i=20;i>=1;i--){ if(dep[anc[u][i]]>=dep[v]) ret |= col[u][i], u = anc[u][i]; } return ret | (1LL<<c[v]);}signed main(){ IOS; cin >> n >> q; for(int i=1;i<=n;i++) cin >> c[i]; int u, v; for(int i=1;i<n;i++){ cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); while(q--){ cin >> u >> v; int x = LCA(u, v); cout << __builtin_popcountll(get(u, x) | get(v, x)) << endl; } return 0;}
贪心作为压轴，考场上的时候没啥感觉，瞎写了点东西，后面才发现这题隐藏的精妙之处——“字典序”最大，这意味着4 -1 4形式的答案不一定比4 3 -1更优，想到这一点时距离比赛结束还有一个半小时，考虑到下午还有高数考试，最后留了半小时来重新检查OI提交，保证答案万无一失，就没去再想这题了。现在再做起来感觉也不是很好做，的确是一道不错的压轴题。
很明显，我们得按位考虑，首先通过build函数建立整个数组的线段树。然后遍历数组，对于每个位置，执行如下步骤：
- 查询位置i到i+k范围内的最大值和次大值的位置。
- 根据查询结果更新答案数组ans[]，并相应修改原数组ele[]的值和更新线段树。
- 控制k的减少量以反映已使用的步数。
#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()#define ls(x) (x<<1)#define rs(x) (x<<1|1)using namespace std;const int N = 1e5+5;int n, k;int ele[N], ans[N];namespace SegmentTree{ struct Info{ int max_val, max_idx; int smax_val, smax_idx; Info(int MAX_VAL=-1e9, int MAX_IDX=0, int SMAX_VAL=-2e9, int SMAX_IDX=0){ max_val = MAX_VAL, max_idx = MAX_IDX; smax_val = SMAX_VAL, smax_idx = SMAX_IDX; } }; Info tr[N<<2]; inline Info combine(const Info& A, const Info& B){ Info ret; if(A.max_val > B.max_val){ ret = A; if(A.smax_val >= B.max_val){ ret.smax_val = A.smax_val; ret.smax_idx = A.smax_idx; }else{ ret.smax_val = B.max_val; ret.smax_idx = B.max_idx; } }else if(A.max_val < B.max_val){ ret = B; if(A.max_val >= B.smax_val){ ret.smax_val = A.max_val; ret.smax_idx = A.max_idx; }else{ ret.smax_val = B.smax_val; ret.smax_idx = B.smax_idx; } }else{ ret = A; if(A.smax_val >= B.smax_val){ ret.smax_val = A.smax_val; ret.smax_idx = A.smax_idx; }else{ ret.smax_val = B.smax_val; ret.smax_idx = B.smax_idx; } } return ret; } inline void build(int p, int pl, int pr){ if(pl==pr) return tr[p] = Info(ele[pl], pl), void(); int mid = pl+pr>>1; build(ls(p),pl,mid); build(rs(p),mid+1,pr); tr[p] = combine(tr[ls(p)], tr[rs(p)]); } inline Info query(int p, int pl, int pr, int l, int r){ if(l<=pl && pr<=r) return tr[p]; if(r<pl || pr<l) return Info(); int mid = pl+pr>>1; Info lq = query(ls(p), pl, mid, l, r); Info rq = query(rs(p), mid+1, pr, l, r); return combine(lq, rq); } inline void update(int p, int pl, int pr, int idx, int d){ if(pl==pr) return tr[p] = Info(d, idx), void(); int mid = pl+pr>>1; if(idx <= mid) update(ls(p),pl,mid,idx,d); else update(rs(p),mid+1,pr,idx,d); tr[p] = combine(tr[ls(p)], tr[rs(p)]); }}using namespace SegmentTree;signed main(){ IOS; cin >> n >> k; for(int i=1;i<=n;i++) cin >> ele[i]; build(1,1,n); for(int i=1;i<=n;i++){ int pos = query(1,1,n,i,min(n,i+k)).max_idx; if(ele[pos]==-1){ ans[i] = -1; continue; } if(ans[i-1]==-1 || ele[pos]!=ans[i-1]){ ans[i] = ele[pos]; ele[pos] = -1; k -= pos-i; update(1,1,n,pos,-1); }else{ pos = query(1,1,n,i,min(n,i+k)).smax_idx; if(ele[pos]==-1){ ans[i] = -1; continue; } ans[i] = ele[pos]; ele[pos] = -1; k -= pos-i; update(1,1,n,pos,-1); } } for(int i=1;i<=n;i++){ cout << ans[i] << " \n"[i==n]; } return 0;}
#蓝桥杯#
虾皮信息二面24人在聊