第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组
注意!!!!!!!!!!这篇题解为赛时的个人做法,不代表是正确的,仅供参考。
更新:思路上应该都对,很多题都有细节错误,代码不用看了,太久没敲代码了(- -)
更新2:代码除了岛屿的都改好了,整数删除常数有点大,可能会t,赛时的代码一堆错误,还是对自己的文章负责,省赛打的太放松了,应该多自己造几组样例测得。最后两题lca,板子有一行脑抽了写错了居然没发现,然后求lca我是前一题复制到后一题,两题的样例都能过,结果两题都错了,把那一行代码改完就都a了,蓝桥杯给的样例是在是太水了。。。。。自己还是太久没敲代码,变菜了。(T . T)
试题 A: 日期统计
dfs+剪枝即可,因为前四位一定是2023,五六位一定是1-12月,七八为也要满足条件,所以实际上搜索的范围比较少
最终答案:235
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
typedef long long ll;
int a[N];
int mon[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
vector<int> now;
map<int,int> mp;
int ans = 0;
void dfs(int len,int dep){
if(len == 8){
int sum = 0;
int m = now[4]*10 + now[5];
int d = now[6]*10 + now[7];
if(m < 1 || m > 12) return ;
if(d < 1 || d > mon[m]) return ;
for(int i = 0;i < 8;i++){
sum *= 10;
sum += now[i];
}
if(!mp[sum]){
ans++;
mp[sum] = 1;
}
return ;
}
for(int i = dep;i <= 100;i++){
if(len == 0){
if(a[i] == 2){
now.push_back(a[i]);
dfs(len+1,i+1);
now.pop_back();
}
}else if(len == 1){
if(a[i] == 0){
now.push_back(a[i]);
dfs(len+1,i+1);
now.pop_back();
}
}else if(len == 2){
if(a[i] == 2){
now.push_back(a[i]);
dfs(len+1,i+1);
now.pop_back();
}
}else if(len == 3){
if(a[i] == 3){
now.push_back(a[i]);
dfs(len+1,i+1);
now.pop_back();
}
}else{
now.push_back(a[i]);
dfs(len+1,i+1);
now.pop_back();
}
}
}
void sol(){
for(int i = 1;i <= 100;i++){
scanf("%d",&a[i]);
}
dfs(0,1);
printf("%d",ans);
}
int main(){
sol();
return 0;
}
试题 B: 01 串的熵
枚举0的个数,因为0个数比1小,所以遍历到23333333/2即可
最终答案:11027421
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
typedef long long ll;
void sol(){
int n = 23333333;
for(int i = 0;i <= n/2;i++){
double ans = -1.0*i*i/n*log2(1.0*i/n)-1.0*(n-i)*(n-i)/n*log2(1.0*(n-i)/n);
if(abs(ans - 11625907.5798) <= 0.0001){
printf("%d",i);
}
}
}
int main(){
sol();
return 0;
}
试题 C: 冶炼金属
数论分块知识,用二分也可以
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
typedef long long ll;
int main(){
int n;
scanf("%d",&n);
int maxx = 1000000000,minn = 0;
for(int i = 1;i <= n;i++){
int a,b;
scanf("%d %d",&a,&b);
maxx = min(maxx,a/b);
minn = max(minn,(a+b+1)/(b+1));//比赛时手快分子少加了个1,麻了(代码已改过)
}
printf("%d %d",minn,maxx);
return 0;
}
试题 D: 飞机降落
因为N最多10,所以把所有飞机可能到达的顺序都检查一遍看看是否可行即可。复杂度O(T10!)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
typedef long long ll;
struct node{
int t,d,l;
}p[N];
int a[20];
void sol(){
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d %d %d",&p[i].t,&p[i].d,&p[i].l);
a[i] = i;
}
do{
int now = 0;
int flag = 1;
for(int i = 1;i <= n;i++){
int t = p[a[i]].t,d = p[a[i]].d,l = p[a[i]].l;
if(now > t + d){
flag = 0;
break;
}else{
if(t > now) now = t + l;
else now = now + l;
}
}
if(flag){
printf("YES\n");
return;
}
}while(next_permutation(a+1,a+1+n));
printf("NO\n");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
sol();
}
return 0;
}
试题 E: 接龙数列
dp,dp[i]表示以i为结尾最长可以组成多长,那么答案就是n-max(dp[0-9])
复杂度O(n)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
typedef long long ll;
struct node{
int t,w;
}p[N];
int dp[20];
void sol(){
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i++){
int x;
scanf("%d",&x);
p[i].w = x % 10;
while(x >= 10){
x/=10;
}
p[i].t = x;
}
// for(int i = 1;i <= n;i++){
// printf("%d %d\n",p[i].t,p[i].w);
// }
for(int i = 1;i <= n;i++){
dp[p[i].w] = max(dp[p[i].w],dp[p[i].t] + 1);
}
int ans = 1000000000;
for(int i = 0;i <= 9;i++){
ans = min(ans,n-dp[i]);
}
printf("%d",ans);
}
int main(){
sol();
return 0;
}
试题 F: 岛屿个数
首先dfs一次,把所有相连的岛屿都标上号。
一个个判断某一个岛屿是否被围住,如何判断,枚举所有的岛屿作为墙,当你从一个岛屿存在一个点,可以搜索走出n*m的棋盘就证明没有被围住,当所有其他岛屿作为墙,你都可以走出地图,那么这个岛屿就没有被围住。
复杂度O(n^4)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+9;
typedef long long ll;
int a[59][59];
int vis[59][59];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int fobid = 0;
int n,m;
int ans[N];
int nc = 0;
void dfs(int x,int y,int co){
vis[x][y] = co;
for(int i = 0;i <= 3;i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
if(vis[xx][yy]||a[xx][yy] == 0){
continue;
}
dfs(xx,yy,co);
}
}
int v[59][59];
void dfs2(int x,int y,int co){
v[x][y] = 1;
for(int i = 0;i <= 3;i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx < 1 || xx > n || yy < 1 || yy > m){
ans[co] = 1;
continue;
}
if(v[xx][yy] || vis[xx][yy] == fobid){
continue;
}
dfs2(xx,yy,co);
}
}
void sol(){
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
nc = 0;
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
scanf("%1d",&a[i][j]);
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(a[i][j]){
if(!vis[i][j]){
dfs(i,j,++nc);
}
}
}
}
for(fobid = 1;fobid <= nc;fobid++){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(vis[i][j] && fobid != vis[i][j]){
if(ans[vis[i][j]]) continue;
memset(v,0,sizeof(v));
dfs2(i,j,vis[i][j]);
}
}
}
}
int num = 0;
for(int i = 1;i <= nc;i++){
num += ans[i];
}
printf("%d\n",num);
}
int main(){
int t;
scanf("%d",&t);
while(t--)
sol();
return 0;
}
试题 G: 子串简写
对结尾字符出现次数做前缀和,枚举a字符开头的位置,假设s[i]是a字符,那么i+k-1以后的出现的b都可以作为答案。
复杂度O(n)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
typedef long long ll;
char s[N];
char a,b;
ll sum[N];
void sol(){
int k,n;
scanf("%d",&k);
scanf("%s",s+1);
n = strlen(s+1);
scanf(" %c",&a);
scanf(" %c",&b);
for(int i = 1;i <= n;i++){
if(s[i] == b) sum[i] = sum[i-1]+1;
else sum[i] = sum[i-1];
}
ll ans = 0;
for(int i = 1;i <= n;i++){
if(s[i] == a && i + k - 2 <= n){
ans += (sum[n] - sum[i+k-2]);
}
}
printf("%lld",ans);
}
int main(){
sol();
return 0;
}
试题 H: 整数删除
维护两个set,一个set先对值再对位置大小排序,另一个则相反。然后模拟即可。
复杂度O(nlogn+klogn)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
typedef long long ll;
struct nodevp{
int pos;
ll val;
bool operator < (const nodevp &p) const{
if(val == p.val) return pos < p.pos;
else return val < p.val;
}
bool operator == (const nodevp &p) const{
return pos == p.pos && val == p.val;
}
};
struct nodepv{
int pos;
ll val;
bool operator < (const nodepv &p) const{
if(pos == p.pos) return val < p.val;
else return pos < p.pos;
}
bool operator == (const nodepv &p) const{
return pos == p.pos && val == p.val;
}
};
ll a[N];
set<nodevp> svp;
set<nodepv> spv;
int n,k;
void changepv(nodepv a,nodepv b){
spv.erase(a);
spv.insert(b);
}
void changevp(nodevp a,nodevp b){
svp.erase(a);
svp.insert(b);
}
void sol(){
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
nodevp v;
v.val = a[i];
v.pos = i;
svp.insert(v);
nodepv p;
p.val = a[i];
p.pos = i;
spv.insert(p);
}
for(int i = 1;i <= k;i++){
nodevp v = *svp.begin();
// svp.erase(v);
ll add = v.val;
nodepv p;
p.val = v.val;
p.pos = v.pos;
auto apv = spv.find(p);
if(apv != spv.begin()){
apv--;
nodepv temp,nex;
temp.pos = apv->pos;
temp.val = apv->val;
nex.pos = temp.pos;
nex.val = temp.val + add;
nodevp temp2,nex2;
temp2.pos = apv->pos;
temp2.val = apv->val;
nex2.pos = temp2.pos;
nex2.val = temp2.val + add;
changepv(temp,nex);
changevp(temp2,nex2);
// apv++;
}
apv = spv.find(p);
apv++;
if(apv == spv.end()){
spv.erase(p);
svp.erase(v);
continue;
}
nodepv temp,nex;
temp.pos = apv->pos;
temp.val = apv->val;
nex.pos = temp.pos;
nex.val = temp.val + add;
nodevp temp2,nex2;
temp2.pos = apv->pos;
temp2.val = apv->val;
nex2.pos = temp2.pos;
nex2.val = temp2.val + add;
changepv(temp,nex);
changevp(temp2,nex2);
spv.erase(p);
svp.erase(v);
}
while(spv.size()){
nodepv p = *spv.begin();
printf("%lld ",p.val);
spv.erase(p);
}
}
int main(){
sol();
return 0;
}
// 5 3
// 4 1 2 8 7
// 5 4
// 1 4 2 8 7
试题 I: 景区导游
树上前缀和+lca。先算出不删除走完全称所需要的时间假设为asum。如何算,sum[i]代表从根走到i节点需要花多少时间,那么从u到v(后文表示为dis(u,v))则需要花sum[u]+sum[v]-sum[lca(u,v)]*2这么多时间,如果删去一个点i后,全程答案为 asum - dis(a[i],a[i+1]) - dis(a[i],a[i-1]) + dis(a[i-1],a[i+1]),删掉开头和结尾特判,入代码所示。
复杂度:O(nlogn)文章来源:https://www.toymoban.com/news/detail-446742.html
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
typedef long long ll;
int n,k;
int f[N][29];
int dep[N];
int a[N];
ll sum[N];
ll ans[N];
struct edge{
ll dis;
int to;
};
vector<edge> g[N];
int lca(int u,int v){
if(dep[u] < dep[v]) swap(u,v);
for(int i = 20;i >= 0;i--){
if(dep[f[u][i]] >= dep[v]) u = f[u][i];
}
if(u == v) return u;
for(int i = 20;i >= 0;i--){
if(f[u][i] != f[v][i]){
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
ll dis(int u,int v){
return (sum[u] + sum[v] - sum[lca(u,v)]*2);
}
void dfs(int now,int fa){
// sum[now] = sum[now] + sum[fa];
f[now][0] = fa;
dep[now] = dep[fa] + 1;
for(int i = 1;i <= 20;i++){
if(f[now][i-1]) f[now][i] = f[f[now][i-1]][i-1];
else break;
}
for(auto j : g[now]){
if(j.to == fa) continue;
sum[j.to] += sum[now] + j.dis;
dfs(j.to,now);
}
}
void sol(){
scanf("%d %d",&n,&k);
for(int i = 1;i <= n-1;i++){
int u,v;
ll dis;
scanf("%d %d %lld",&u,&v,&dis);
edge p;
p.dis = dis;p.to = v;
g[u].push_back(p);
p.to = u;
g[v].push_back(p);
}
dfs(1,0);
ll asum = 0;
for(int i = 1;i <= k;i++){
scanf("%d",&a[i]);
}
for(int i = 2;i <= k;i++){
asum += (sum[a[i-1]] + sum[a[i]] - sum[lca(a[i-1],a[i])]*2);
}
for(int i = 1;i <= k;i++){
if(i == 1){
ans[i] = asum - dis(a[i],a[i+1]);
}else if(i == k){
ans[i] = asum - dis(a[i],a[i-1]);
}else{
ans[i] = asum - dis(a[i],a[i+1]) - dis(a[i],a[i-1]) + dis(a[i-1],a[i+1]);
}
}
for(int i = 1;i <= k;i++){
printf("%lld ",ans[i]);
}
}
int main(){
sol();
return 0;
}
试题 J: 砍树
树上差分+lca。如果u到v想要断开,那么u到v路径上的任何一条边断开都可以,所以把u到v所经过的边权值加1,最后看那一条边的权值等于给出的无序对的个数,输出序号最大的那条边即可。文章来源地址https://www.toymoban.com/news/detail-446742.html
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
typedef long long ll;
int n,m;
int f[N][29];
int dep[N];
ll sum[N];
int ans = -1;
int fnum[N];
struct edge{
ll dis;
int to;
};
vector<edge> g[N];
int lca(int u,int v){
if(dep[u] < dep[v]) swap(u,v);
for(int i = 20;i >= 0;i--){
if(dep[f[u][i]] >= dep[v]) u = f[u][i];
}
if(u == v) return u;
for(int i = 20;i >= 0;i--){
if(f[u][i] != f[v][i]){
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
void dfs(int now,int fa){
// sum[now] = sum[now] + sum[fa];
f[now][0] = fa;
dep[now] = dep[fa] + 1;
for(int i = 1;i <= 20;i++){
if(f[now][i-1]) f[now][i] = f[f[now][i-1]][i-1];
else break;
}
for(auto j : g[now]){
if(j.to == fa) continue;
fnum[j.to] = j.dis;
dfs(j.to,now);
}
}
void dfs2(int now,int fa){
for(auto j : g[now]){
if(j.to == fa) continue;
dfs2(j.to,now);
sum[now] += sum[j.to];
}
if(sum[now] == m){
ans = max(ans,fnum[now]);
}
}
void sol(){
scanf("%d %d",&n,&m);
for(int i = 1;i <= n-1;i++){
int u,v;
scanf("%d %d",&u,&v);
edge p;
p.dis = i;p.to = v;
g[u].push_back(p);
p.to = u;
g[v].push_back(p);
}
dfs(1,0);
for(int i = 1;i <= m;i++){
int u,v;
scanf("%d %d",&u,&v);
sum[u]++;
sum[v]++;
sum[lca(u,v)]-=2;
}
dfs2(1,0);
printf("%d",ans);
}
int main(){
sol();
return 0;
}
到了这里,关于第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!