第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组
目录
试题 A: 日期统计 .本题总分：5 分
试题 B: 01 串的熵.本题总分：5 分
试题 C: 冶炼金属.本题总分：10 分
试题 D: 飞机降落.本题总分：10 分
试题 E: 接龙数列 .本题总分：15 分
试题 F: 岛屿个数 .本题总分：15 分
试题 G: 子串简写 .本题总分：20 分
试题 H: 整数删除.本题总分：20 分
试题 I: 景区导游 .本题总分：25 分
试题 J: 砍树 .本题总分：25 分
试题 A: 日期统计 .本题总分：5 分
相同的日期你只需要统计一次即可，直接dfs剪枝跑就可以了 我的答案235
试题 B: 01 串的熵.本题总分：5 分
二分，l=1,r=23333333>>1 ,我的答案11027421
试题 C: 冶炼金属.本题总分：10 分
对于最大值，可以根据整除分块定理2知道是a/b,然后取个min就是最大值，对于最小值，二分求，复杂度O（nlogn）
然后其实知道r=a/b,那么也不难推出l是前一个块的r+1，也就是l=a/(b+1)+1 复杂度O(N)
#include
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e4+10;int n;
ll a[maxn],b[maxn];void solve()
{cin>>n;ll ma=-1,mi=-1;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];ll now=a[i]/b[i];if(ma==-1||ma>now){ma=now;}mi=max(mi,(a[i]/(b[i]+1))+1);}cout<>tn;while(tn--){solve();}return 0;
} 试题 D: 飞机降落.本题总分：10 分
贪心寄了，还是全排列暴力~~~~~
还是dfs剪枝暴力吧，t<=10,n<=10
#include
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e2+10;struct node
{int t,d,l;
} ;
int n;
node a[maxn];
int f[maxn];
int flag;
void dfs(int len,int last)
{if(len==n){flag=1;return;}for(int i=1;i<=n&&!flag;i++){if(f[i])continue;auto [t,d,l]=a[i];if(last<=t+d){f[i]=1;dfs(len+1,max(last+l,t+l));f[i]=0;}}
}
void solve()
{cin>>n;flag=0;for(int i=1;i<=n;i++){cin>>a[i].t>>a[i].d>>a[i].l;f[i]=0;}dfs(0,-1);if(flag)cout<<"YES"<>tn;while(tn--){solve();}return 0;
}
试题 E: 接龙数列 .本题总分：15 分
考虑dp, dp[i],表示以i结尾的子序列最大长度，当前数字开头为j结尾为i，那么dp[i]=max(dp[i],dp[j]+1);,最后n-最长子序列就可以了，复杂度O(N)
#include
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e5+10;int n;
int dp[10];
/*
5
11 121 22 12 2023
1
*/
void solve()
{cin>>n;for(int i=1,j;i<=n;i++){cin>>j;int f=j,d=j%10;while(f>=10)f/=10;dp[d]=max(dp[d],dp[f]+1);}int ma=1;for(int i=0;i<10;i++){ma=max(ma,dp[i]);//cout<>tn;while(tn--){solve();}return 0;
} 试题 F: 岛屿个数 .本题总分：15 分
先从最外海水跑图，记录外部海水数量，岛的4周海水得有1个方向等于外部海水.否则就是环岛的子岛屿；
跑海水从8个方向染色；
然后跑周围是外部海水的岛屿，四个方向染++cnt，最后输出cnt就是答案
0(N*N)
#include
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 55;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;char map_[MAX][MAX]; // 地图
bool track[MAX][MAX] = {false}; // 访问标记
bool outsea[MAX][MAX] = {false}; // 外海标记
struct XY {int x, y;
} nxt[] = {{1, 0},{-1, 0},{0, 1},{0, -1},{1, 1},{-1, 1},{1, -1},{-1, -1},
};void solve() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> map_[i];}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {track[i][j] = false;outsea[i][j] = false;}}// 预处理外海for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map_[i][j] == '1' or track[i][j]) continue;bool yep = false;queue que, arr;track[i][j] = true;que.push({i, j});arr.push({i, j}); // 记录搜索到的所有海域while (not que.empty()) {XY pos = que.front();que.pop();// 注意：海域搜索可以往八个方向走，陆地搜索只能朝四个方向for (int i = 0; i < 8; i++) {XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {if (map_[nw.x][nw.y] == '0' and track[nw.x][nw.y] == false) {track[nw.x][nw.y] = true;que.push(nw);arr.push(nw);}} else {yep = true; // 如果有一次搜索到地图外，标记此次搜索的所有区域为外海}}}if (yep) {while (not arr.empty()) {XY pos = arr.front();arr.pop();outsea[pos.x][pos.y] = true; // 标记搜索到的海域为外海}}}}// 别忘了清空访问标记for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {track[i][j] = false;}}// 处理岛屿int cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map_[i][j] == '0' or track[i][j]) continue;bool yep = false;queue que;track[i][j] = true;que.push({i, j});while (not que.empty()) {XY pos = que.front();que.pop();for (int i = 0; i < 4; i++) {XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {if (map_[nw.x][nw.y] == '1') {if (track[nw.x][nw.y] == false) {track[nw.x][nw.y] = true;que.push(nw);}} else {if (outsea[nw.x][nw.y]) {yep = true; // 搜索到外海为外岛}}} else {yep = true; // 搜索到边界外为外岛}}}if (yep) {cnt++; // 外岛计数}}}cout << cnt << endl;
}int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t;cin >> t;while (t--)solve();return 0;
} 试题 G: 子串简写 .本题总分：20 分
把c1的位置存起来，对于每个c2位置二分找最小符合的位置，ans加上这个位置下标就可以了
也可以双指针暴力
#include
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
#define pii pair
const int maxn=5e5+10;
int n,k;
char s[maxn],a,b;
/*
4
abababdb a b
4
ba a b
*/
void solve()
{cin>>k;cin>>s+1;cin>>a>>b;n=strlen(s+1);vectorva,vb;for(int i=1;i<=n;i++){if(s[i]==a){va.pd(i);}if(s[i]==b){vb.pd(i);}}va.pd(n+1);vb.pd(n+1);ll ans=0;for(int i=0;ivb[i]-k+1){r--;}ans+=r+1;//cout<>tn;while(tn--){solve();}return 0;
} 试题 H: 整数删除.本题总分：20 分
线段树+并查集
对于每个点并查集维护左父亲和右父亲。对于每次操作线段树找到最左侧最小下标，然后返回，
这个点的左父亲等于这个点左边的点的左父亲，右同理，然后线段树修改值即可
复杂度 O(KlogN)
可以也采用set存点值和下标，然后+并查集
复杂度也是O(KlogN)
#include
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
#define pii pair
const int maxn=5e5+10;int n,k;
ll a[maxn];
int l[maxn],r[maxn],f[maxn];
int findl(int x)
{return x==l[x]?x:l[x]=findl(l[x]);
}
int findr(int x)
{return x==r[x]?x:r[x]=findr(r[x]);
}ll tr[maxn<<4];
void up(int rt)
{tr[rt]=min(tr[rt<<1],tr[rt<<1|1]);
}
void build(int rt,int l,int r)
{tr[rt]=a[l];if(l==r)return;int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);up(rt);
}
pii cha(int rt,int l,int r)
{if(l==r){return {l,tr[rt]};}int mid=l+r>>1;pii ans;if(tr[rt<<1]<=tr[rt<<1|1]){ans=cha(rt<<1,l,mid);}else{ans=cha(rt<<1|1,mid+1,r);}return ans;
}
void add(int rt,int l,int r,int id,ll val)
{if(id==l&&id==r){tr[rt]+=val;a[l]=tr[rt];return;}int mid=l+r>>1;if(l<=id&&id<=mid)add(rt<<1,l,mid,id,val);else if(id>mid&&id<=r)add(rt<<1|1,mid+1,r,id,val);up(rt);
}
/*
5 3
1 4 2 8 7
5 4
1 4 2 8 7
5 5
1 4 2 8 7
*/
void solve()
{cin>>n>>k;l[0]=0;l[n+1]=0;r[0]=0;r[n+1]=0;for(int i=1;i<=n;i++){cin>>a[i];l[i]=i;r[i]=i;f[i]=1;}build(1,1,n);while(k--){ll mi=1e18,id=-1;
// for(int i=1;i<=n;i++)//可用线段树优化
// {
// if(mi>a[i])
// {
// mi=a[i];
// id=i;
// }
// }pii i=cha(1,1,n);id=i.x;mi=i.y;f[id]=0;l[id]=findl(l[id-1]);r[id]=findr(r[id+1]);if(l[id]>=1)add(1,1,n,l[id],mi);if(r[id]<=n)add(1,1,n,r[id],mi);add(1,1,n,id,1e17);
// a[l[id]]+=a[id];
// a[r[id]]+=a[id];
// a[id]=1e18;
// for(int i = 1; i <= n; i++)
// {
// if(f[i])
// {
// cout << a[i] << " ";
// }
// }
// cout<>tn;while(tn--){solve();}return 0;
}
试题 I: 景区导游 .本题总分：25 分
倍增，由于要按顺序去游览点，考虑起点那么只有A1,A2，对于2-k的点都是以A1为起点，那么其实路都差不多，假设在这之中p点不去，减去p-1到p的路径值减去p到p+1的路径值，加上p-1到p+1的路径值即可
复杂度O(NlogN+KlogN)
对于加减路径值也可以用树链剖分或lct 复杂度O(NlogN+KlogN)
#include
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int h[N], e[N], w[N], ne[N], idx = 0;
int lg[N], p[N][20], deep[N], a[N];
ll dis[N], n, k, sum = 0;
void dfs(int lst, int now) {deep[now] = deep[lst] + 1;p[now][0] = lst;for (int i = 1; (1 << i) <= deep[now]; i++)p[now][i] = p[p[now][i - 1]][i - 1];for (int i = h[now]; i; i = ne[i]) {int to = e[i], cost = w[i];if (to != lst) {dis[to] = dis[now] + cost;dfs(now, to);}}
}
int lca(int u, int v) {if (deep[u] < deep[v]) swap(u, v);while (deep[u] > deep[v])u = p[u][lg[deep[u] - deep[v]]];if (u == v) return u;else {for (int i = lg[deep[u]]; i >= 0; i--) {if (p[u][i] != p[v][i])u = p[u][i], v = p[v][i];}}return p[u][0];
}
inline void add(int u, int v, int t) {e[++idx] = v, w[idx] = t, ne[idx] = h[u], h[u] = idx;
}
inline ll ask(int u, int v) {if (u == 0 || v == 0) return 0;else return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}
inline ll query(int i) {return ask(a[i - 1], a[i + 1]) - ask(a[i - 1], a[i]) - ask(a[i], a[i + 1]);
}
int main() {cin >> n >> k;for (int i = 1; i < n; i++) {int u, v, t;cin >> u >> v >> t;add(u, v, t);add(v, u, t);}for (int i = 2; i <= n; i++)lg[i] = lg[i >> 1] + 1;dfs(0, 1);for (int i = 1; i <= k; i++)cin >> a[i];for (int i = 2; i <= k; i++)sum += ask(a[i - 1], a[i]);for (int i = 1; i <= k; i++)cout << sum + query(i) << ' ';
} 试题 J: 砍树 .本题总分：25 分
倍增+树上差分，对于一个数对，我们对数对路径上的值＋1，最后看是否有一条边的左右点的点值相等
复杂度O(NlogN+N)
其实要对于数对路径值+1，也可以使用树链剖分来写，这样复杂度也是O(NlogN)
#include
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
#define pii pair
const int maxn=1e5+10;struct beizeng
{int dp[22][maxn],deep[maxn];int val[maxn];vectorv[maxn];void add(int a,int b){v[a].pd(b);v[b].pd(a);}void dfs(int x,int fa){//dft[op]=x;//df[x]=op++;deep[x]=deep[fa]+1;dp[0][x]=fa;for(int i=1;(1<deep[b])swap(a,b);for(int i=20;i>=0;i--){if(deep[a]<=deep[b]-(1<=0;i--){if(dp[i][a]!=dp[i][b]){a=dp[i][a];b=dp[i][b];}}return dp[0][a];}
}tree;
int n,m;
int a[maxn],b[maxn];
void solve()
{cin>>n>>m;for(int i=1;i>a[i]>>b[i];tree.add(a[i],b[i]);}tree.dfs(1,0);for(int i=1;i<=m;i++){int x,y;cin>>x>>y;int c=tree.lca(x,y);tree.val[x]++;tree.val[y]++;tree.val[c]--;tree.val[tree.dp[0][c]]--;}tree.dfs2(1,0);int ans=-1;for(int i=n-1;i>=1;i--){if(tree.val[a[i]]==m&&tree.val[b[i]]==m){ans=i;break;}}cout<>tn;while(tn--){solve();}return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！