我是靠谱客的博主 傲娇老虎，这篇文章主要介绍【超好懂的比赛题解】“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解，现在分享给大家，希望可以做个参考。
title : “学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解
tags : ACM,练习记录
date : 2022-5-29
author : Linno
“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解
题目链接：https://ac.nowcoder.com/acm/contest/44821
补题进度：9/12
题目比较水，没啥好说的。
A-国家德比
复制代码
1
2
3
4
5
6
7
8
9
10
11
12#include<bits/stdc++.h> using namespace std; signed main(){ int x,y; scanf("%d:%d",&x,&y); if(x>y) puts("Hala Madrid!"); else if(x<y) puts("Vamos Barca!"); else puts("Draw..."); return 0; }
B-吉利数
直接枚举则数就行了。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include<bits/stdc++.h> using namespace std; int f1,f2; void check(int x){ f1=0,f2=0; int sum=0; while(x){ if(x%10==6) f1=1; sum+=x%10; x/=10; } if(sum%6==0) f2=1; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,ans1=0,ans2=0; cin>>n; for(int i=1;i<=n;++i){ check(i); if(f1&&f2){ ++ans1; ans2=i; } } cout<<ans1<<" "<<ans2<<"n"; return 0; }
C-咖啡杯
考察高中数学，把式子退出来直接做就行了，特地找了台体体积公式。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#include<bits/stdc++.h> using namespace std; const double pi=acos(-1); signed main(){ int r,s,h,m,d; scanf("%d%d%d%d%d",&r,&s,&h,&m,&d); double rp=1.0*(r*h+s*d-r*d)/h; //d/h = r double S1=1.0*pi*s*s,S2=1.0*pi*r*r,S3=1.0*pi*rp*rp; // d/h = sqrt(S3/S1) //cout<<S1<<" "<<S3<<" "<<S2<<" S Area!!n"; double Vol=1.0*(S1+S2+sqrt(S1*S2))*h/3.0; double Vl=1.0*(S1+S3+sqrt(S1*S3))*(h-d)/3; double ts=1.0*Vol*m/Vl; // Vl/m=Vol/ts double tl=ts-m; printf("%.10lfn",tl); return 0; }
D-数字谜题I
显然每次操作可以按lowbit来搞，那么我们把加的答案和减的答案统计一下就行了。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include<bits/stdc++.h> #define int long long #define lb(x) (x&-x) using namespace std; signed main(){ int n; while(cin>>n){ int ans1=0,ans2=0,tmp=n; while(__builtin_popcount(tmp)>2){ ans1+=lb(tmp); tmp+=lb(tmp); } while(__builtin_popcount(tmp)!=2) ++ans1,++tmp; while(__builtin_popcount(n)>2){ ans2+=lb(n); n-=lb(n); } // cout<<ans1<<" "<<ans2<<"!!n"; if(__builtin_popcount(n)==2) cout<<min(ans1,ans2)<<"n"; else cout<<ans1<<"n"; } return 0; }
E-数字谜题II
我们让x成为最小的那个能到达的数肯定是最优的，二分y下一个加的数就行了。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#include<bits/stdc++.h> #define int long long #define lb(x) (x&-x) using namespace std; signed main(){ int n; while(cin>>n){ int x=0,y=0,ans=0,j,sum=0,L,R,M; //初始化这两个数 while(x<=n){ L=x+1,R=1e9+7; while(R-L>1){ M=((R+L)>>1); if(M*M>y) R=M; else L=M; } if(L*L>y) R=L; if(R>n) break; y+=R*R; ++ans; //操作次数 x=R; } cout<<ans<<"n"; } return 0; }
F-区间计数
枚举右端点，并且记录当前加入的对，那么目前区间最多向左延申到当前加入的最右边的左端点。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e6+7; int n,m,a[N],l[N],r[N],pos[N]; vector<int>ed[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; //for(int i=1;i<=n;++i) a[i]=i,pos[a[i]]=i; for(int i=1;i<=n;++i) cin>>a[i],pos[a[i]]=i; for(int i=1;i<=m;++i){ cin>>l[i]>>r[i]; int ql=min(pos[l[i]],pos[r[i]]),qr=max(pos[l[i]],pos[r[i]]); ed[qr].emplace_back(ql); //在右端点打个标记 } int mx=0,ans=0; for(int i=1;i<=n;++i){ for(auto p:ed[i]) mx=max(mx,p); //mx+1 是最左边能到达的位置 ans+=i-mx; //cout<<i<<" "<<ans<<" "<<mx<<"!!n"; } cout<<ans<<"n"; return 0; }
G-密码专家
看数据一眼区间Dp，转移注意边界。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include<bits/stdc++.h> #define int long long using namespace std; const int N=305; int n,dp[N][N],w[10][10],a[N]; string str; int check(int i,int j,int k){ int ans=0; if(k-1>=i) ans+=dp[i][k-1]; if(k+1<=j) ans+=dp[k+1][j]; if(i-1>=1) ans+=w[a[i-1]][a[k]]; if(j+1<=n) ans+=w[a[j+1]][a[k]]; return ans; } void solve(){ for(int i=1;i<=5;++i){ for(int j=1;j<=5;++j){ cin>>w[i][j]; } } cin>>n; cin>>str; for(int i=1;i<=n;++i) a[i]=str[i-1]-'a'+1; memset(dp,0x3f,sizeof(dp)); for(int len=1;len<=n;++len){ for(int i=1;i+len-1<=n;++i){ int j=i+len-1; for(int k=i;k<=j;++k){ dp[i][j]=min(dp[i][j],check(i,j,k)); } } } cout<<dp[1][n]<<"n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; }
H-戏团演出
这是个好题，树链剖分后转化为序列上的差分操作，然后用一个map存当前dfs序位置要修改的操作，然后再一个数组记下颜色的数量，然后再套个线段树求最大值即可。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#include<bits/stdc++.h> #define pb emplace_back #define pii pair<int,int> #define mk make_pair #define F first #define S second using namespace std; const int N=1e5+7; inline int read(){ int x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x; } int n,m,ans[N]; vector<int>G[N]; int sz[N],fa[N],son[N],dep[N]; int dfn[N],idfn[N],idx=0,bel[N],cnt[N]; unordered_map<int,int>mp[N]; #define mid ((l+r)>>1) #define inf (1e9+7) int tot=0,rt; struct Tr{ int ls,rs,mx,mxid; }tr[N<<5]; void update(int &p,int l,int r,int pos,int val){ if(!p) p=++tot; if(l==r){ tr[p].mx+=val; tr[p].mxid=pos; return; } tr[p].mx=tr[p].mxid=0; if(pos<=mid) update(tr[p].ls,l,mid,pos,val); else update(tr[p].rs,mid+1,r,pos,val); if(tr[p].ls&&tr[tr[p].ls].mx>tr[p].mx){ tr[p].mx=tr[tr[p].ls].mx; tr[p].mxid=tr[tr[p].ls].mxid; } if(tr[p].rs&&tr[tr[p].rs].mx>tr[p].mx){ tr[p].mx=tr[tr[p].rs].mx; tr[p].mxid=tr[tr[p].rs].mxid; } } inline void dfs1(int x,int f){ sz[x]=1; for(auto to:G[x]){ if(to==f) continue; fa[to]=x;dep[to]=dep[x]+1; dfs1(to,x); sz[x]+=sz[to]; if(sz[son[x]]<sz[to]) son[x]=to; } } void dfs2(int x,int tp){ dfn[x]=++idx; idfn[idx]=x; bel[x]=tp; if(son[x]) dfs2(son[x],tp); for(auto to:G[x]){ if(to==son[x]||to==fa[x]) continue; dfs2(to,to); } } void modify(int x,int y,int z){ mp[x][z]++; mp[y+1][z]--; //使用map来差分颜色 } bool cmp(const pii lf,const pii rg){ if(lf.S!=rg.S) return lf.S<rg.S; return lf.F>rg.F; } signed main(){ n=read();m=read(); for(int i=1,u,v;i<n;++i){ u=read();v=read(); G[u].pb(v);G[v].pb(u); } dfs1(1,0); dfs2(1,1); for(int i=1,u,v,w;i<=m;++i){ u=read();v=read();w=read(); while(bel[u]!=bel[v]){ if(dep[bel[u]]<dep[bel[v]]) swap(u,v); modify(dfn[bel[u]],dfn[u],w); u=fa[bel[u]]; } if(dep[u]<dep[v]) swap(u,v); modify(dfn[v],dfn[u],w); } for(int i=1;i<=n;++i){ //for(auto it=mp[i].begin();it!=mp[i].end();++it) now[(it->F)]+=(it->S); for(auto it=mp[i].begin();it!=mp[i].end();++it) update(rt,1,inf,(it->F),(it->S)); ans[idfn[i]]=(tr[1].mxid);cnt[idfn[i]]=(tr[1].mx); // cout<<i<<" "<<tr[1].mxid<<" "<<tr[1].mx<<"!!n"; } for(int i=1;i<=n;++i){ if(!cnt[i]) puts("0"); else printf("%dn",ans[i]); } return 0; }
I-寻宝任务
感觉题意不是很清楚，就是求最短路，然后选一个能够到达的位置并且获得的权值是最大的。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include<bits/stdc++.h> using namespace std; const int N=505; const int dx[]={-1,-1,-1,0,1,1,1,0},dy[]={-1,0,1,1,1,0,-1,-1}; int n,m,sx,sy,ep,ans=0,vis[N][N],mp[N][N]; struct Nod{ int x,y,d; bool operator <(const Nod& p)const{ return d>p.d; } }; void dijkstra(){ memset(vis,-1,sizeof(vis)); priority_queue<Nod>q; q.emplace((Nod){sx,sy,0}); while(q.size()){ Nod fro=q.top(); q.pop(); if(vis[fro.x][fro.y]!=-1) continue; if(fro.d>ep) break; if(mp[fro.x][fro.y]>0){ ans=max(ans,mp[fro.x][fro.y]); continue; } vis[fro.x][fro.y]=fro.d; for(int i=0;i<8;++i){ int nx=fro.x+dx[i],ny=fro.y+dy[i]; if(nx<1||ny<1||nx>n||ny>m) continue; q.emplace((Nod){nx,ny,fro.d+(i+1)}); } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m>>sx>>sy>>ep; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ cin>>mp[i][j]; } } dijkstra(); cout<<ans<<"n"; return 0; }
最后
以上就是傲娇老虎最近收集整理的关于【超好懂的比赛题解】“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解的全部内容，更多相关【超好懂的比赛题解】“学佳澳杯”湖北文理学院第一届程序设计竞赛内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复