【超好懂的比赛题解】“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解

---

title : “学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解
tags : ACM,练习记录
date : 2022-5-29
author : Linno

---

“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解

题目链接：https://ac.nowcoder.com/acm/contest/44821

补题进度：9/12

题目比较水，没啥好说的。

A-国家德比

#include
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;	
}
1
2
3
4
5
6
7
8
9
10
11

B-吉利数

直接枚举则数就行了。

#include
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;	
}
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

C-咖啡杯

考察高中数学，把式子退出来直接做就行了，特地找了台体体积公式。

#include
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<
	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("%.10lf\n",tl);
	return 0;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

D-数字谜题I

显然每次操作可以按lowbit来搞，那么我们把加的答案和减的答案统计一下就行了。

#include
#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<
		if(__builtin_popcount(n)==2) cout<<min(ans1,ans2)<<"\n";
		else cout<<ans1<<"\n";
	}
	return 0;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

E-数字谜题II

我们让x成为最小的那个能到达的数肯定是最优的，二分y下一个加的数就行了。

#include
#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;	
}
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

F-区间计数

枚举右端点，并且记录当前加入的对，那么目前区间最多向左延申到当前加入的最右边的左端点。

#include
#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<
	}
	cout<<ans<<"\n";
	return 0;	
}
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

G-密码专家

看数据一眼区间Dp，转移注意边界。

#include
#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;
}
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

H-戏团演出

这是个好题，树链剖分后转化为序列上的差分操作，然后用一个map存当前dfs序位置要修改的操作，然后再一个数组记下颜色的数量，然后再套个线段树求最大值即可。

#include
#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<
	} 
	for(int i=1;i<=n;++i){
		if(!cnt[i]) puts("0");
		else printf("%d\n",ans[i]);
	}
	return 0;
} 
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

I-寻宝任务

感觉题意不是很清楚，就是求最短路，然后选一个能够到达的位置并且获得的权值是最大的。

#include
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;
}
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