第十四届蓝桥杯大赛软件赛国赛Java大学B组题解

0玩具 - 蓝桥云课 (lanqiao.cn)

简单贪心每次用最大的乘以最小的就是答案

void solve() { cin>>n; n*=2; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); int x=0; for(int i=1,j=n;i<j;i++,j--) { x+=(a[i]*a[j]); } cout<<x<<endl; } 

0不完整的算式 - 蓝桥云课 (lanqiao.cn)

小模拟题，只要看？的位置在哪然后模拟运算即可

void solve() { string s; cin>>s; vector<string>stk; for(int i=0;i<s.size();i++) { int j=0; while(s[i+j]>='0'&&s[i+j]<='9')j++; string t=s.substr(i,j); if(t[0]>='0'&&t[0]<='9')stk.push_back(t); if((i+j)<s.size()) { string ttt; ttt+=s[i+j]; stk.push_back(ttt); } i=i+j; } if(stk[4]=="?") { if(stk[1]=="+") cout<<atoi(stk[0].c_str())+atoi(stk[2].c_str())<<endl; else if(stk[1]=="-") cout<<atoi(stk[0].c_str())-atoi(stk[2].c_str())<<endl; else if(stk[1]=="*") cout<<atoi(stk[0].c_str())*atoi(stk[2].c_str())<<endl; else cout<<atoi(stk[0].c_str())/atoi(stk[2].c_str())<<endl; } else if(stk[2]=="?") { if(stk[1]=="+") cout<<atoi(stk[4].c_str())-atoi(stk[0].c_str())<<endl; else if(stk[1]=="-") cout<<atoi(stk[0].c_str())+atoi(stk[4].c_str())<<endl; else if(stk[1]=="*") cout<<atoi(stk[4].c_str())/atoi(stk[0].c_str())<<endl; else cout<<atoi(stk[0].c_str())/atoi(stk[4].c_str())<<endl; } else if(stk[1]=="?") { int a=atoi(stk[0].c_str()); int b=atoi(stk[2].c_str()); int c=atoi(stk[4].c_str()); if(a+b==c) cout<<"+"<<endl; else if(a/b==c) cout<<"/"<<endl; else if(a*b==c) cout<<"*"<<endl; else if(a-b==c) cout<<"-"<<endl; } else if(stk[0]=="?") { if(stk[1]=="+") cout<<atoi(stk[4].c_str())-atoi(stk[2].c_str())<<endl; else if(stk[1]=="-") cout<<atoi(stk[2].c_str())+atoi(stk[4].c_str())<<endl; else if(stk[1]=="*") cout<<atoi(stk[4].c_str())/atoi(stk[2].c_str())<<endl; else cout<<atoi(stk[2].c_str())*atoi(stk[4].c_str())<<endl; } } 

0星球 - 蓝桥云课 (lanqiao.cn)

我写的是dfs只拿了3分，不太会做

double dist(Node a,Node b) { int x=(a.x-b.x); int y=(a.y-b.y); int z=(a.z-b.z); return sqrt(x*x+y*y+z*z); } void dfs(Node&p,int d,double s) { if(s>res)return; if(d>=n) { res=min(res,s); return; } for(int i=1;i<=n;i++) { if(!st[i]) { st[i]=true; s+=dist(p,a[i])*a[i].w; dfs(a[i],d+1,s); st[i]=false; s-=dist(p,a[i])*a[i].w; } } } void solve() { cin>>n; for(int i=1;i<=n;i++) { int x,y,z,w; cin>>x>>y>>z>>w; a[i]={x,y,z,w}; } res=0x7fffffff; for(int i=1;i<=n;i++) { memset(st,0,sizeof st); st[i]=true; dfs(a[i],1,0); } printf("%.2lf\n",res); } 

0序列 - 蓝桥云课 (lanqiao.cn)

推公式然后分类讨论

因为$b_n$是等差数列，而且是以$d$为首项$d$为公差的等差数列，要让$a_i|b_i$，$b_i$被$a_i$整除。

首先我们看$b_n$的通项公式$b_i=i\ast d$，根据整除的性质，我们可以分开来讨论

第一种情况当$i$可以被$a_i$整除，这时候$[1,n]\ast i$都可以被$a_i$整除也就是说有这一项答案有$n$个

其他情况只要找到$i,a_i$ 的最小公倍数即可

第$i$项的最大数是$i\ast n$只要让$lcm(i,a_i)\ast t$，其中$t$是倍数，小于等于$i\ast n$即可

void solve() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; int res=0; for(int i=1;i<=n;i++) if(i%a[i]==0) res+=n; else if(__gcd(i,a[i])==1) { res+=(i*n)/(a[i]*i); } else if(__gcd(i,a[i])!=1) { int t=__gcd(i,a[i]); res+=(i*n)/(a[i]*(i/t)); } cout<<res<<endl; } 

0电动车 - 蓝桥云课 (lanqiao.cn)

最小生成树的模板题

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=,M=2*N; struct edge{ int a,b,w; bool operator<(const edge&t)const { return w<t.w; } }e[M]; int p[N]; int n,m; int ans; int find(int x) { if(p[x]!=x)p[x]=find(p[x]); return p[x]; } int kruskal() { int res=0,cnt=0; for(int i=0;i<m;i++) { int a=find(e[i].a),b=find(e[i].b),w=e[i].w; if(a!=b) { p[a]=b; res+=w; ans=max(w,ans); cnt++; } } if(cnt==n-1)return res; return 0x3f3f3f3f; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)p[i]=i; for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); e[i]={a,b,c}; } sort(e,e+m); int t = kruskal(); if(t!=0x3f3f3f3f) printf("%d",ans); else printf("-1\n"); return 0; } 

0游戏 - 蓝桥云课 (lanqiao.cn)

思路是求区间最大值和最小值，然后求${\sum }_{i=1}^n{\sum }_{j=1}^n{P}_i-Q_j/(n-k+1{)}^2$即可

将上面公式化简得到

${\sum }_{i=1}^n{\sum }_{j=1}^n{P}_i-Q_j=n\ast {\sum }_{i=1}^n{P}_i-n\ast {\sum }_{j=1}^n{Q}_i$

区间最大值最小用线段树(也可以用单调队列)来做就行了

struct Node{ int l,r; int v,v1; }tr[4*N]; int a[N]; int n,m,k; void push_up(int u) { tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v); tr[u].v1=min(tr[u<<1].v1,tr[u<<1|1].v1); } void build(int u,int l,int r) { tr[u]={l,r}; if(l==r) { tr[u].v=a[l]; tr[u].v1=a[l]; return; } int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); push_up(u); } int query1(int u,int l,int r) { if(l<=tr[u].l&&r>=tr[u].r)return tr[u].v; int mid=tr[u].l+tr[u].r>>1; int v=0; if(mid>=l)v=query1(u<<1,l,r); if(mid<r)v=max(v,query1(u<<1|1,l,r)); return v; } int query2(int u,int l,int r) { if(l<=tr[u].l&&r>=tr[u].r)return tr[u].v1; int mid=tr[u].l+tr[u].r>>1; int v=0x3f3f3f3f; if(mid>=l)v=query2(u<<1,l,r); if(mid<r)v=min(v,query2(u<<1|1,l,r)); return v; } void solve() { cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; build(1,1,n); vector<int>t,t1; for(int i=k;i<=n;i++) { int l=i-k+1,r=i; t.push_back(query1(1,l,r)); t1.push_back(query2(1,l,r)); } int res=0; int s1=0,s2=0; for(int i=0;i<t.size();i++) s1+=t[i]; for(int i=0;i<t.size();i++) s2+=t1[i]; int s=s1*t1.size()-s2*t1.size(); double ans=(s*1.0)/(t1.size()*t1.size()); printf("%.2lf\n",ans); }