1. 首页
  2. 文章中心
  3. 数学

2022 年辽宁省大学生程序设计竞赛 个人题解2022 年辽宁省大学生程序设计竞赛

103 阅读 0 评论
我是靠谱客的博主 冷傲舞蹈，这篇文章主要介绍2022 年辽宁省大学生程序设计竞赛 个人题解2022 年辽宁省大学生程序设计竞赛，现在分享给大家，希望可以做个参考。

title : 2022 年辽宁省大学生程序设计竞赛
date : 2022-10-25
tags : ACM,练习记录
author : Linno

2022 年辽宁省大学生程序设计竞赛

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

进度：10/13

质量比较差的场，后三题是错的，D题spj也是错的，其他nt题也多。

文章目录

  • 2022 年辽宁省大学生程序设计竞赛
      • A-伟大奋斗
      • B-可莉的五子棋
      • C-消除死域点
      • D-七圣召唤
      • E-病毒危机
      • F-互质
      • G-栈与公约数
      • I-图的分割
      • K-俄罗斯方块
      • M-画画

A-伟大奋斗

复制代码
1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;

signed main(){
	int n;
	cin>>n;
	int ans=n-(2022-73);
	cout<<ans<<"n";
	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
33
34
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1007;
int n,m,ans[5];
char mp[N][N];

int check(int x,int y,char ch){
	int res=0;
	if(y+4<=m&&mp[x][y+1]==ch&&mp[x][y+2]==ch&&mp[x][y+3]==ch&&mp[x][y+4]==ch) ++res;
	if(x+4<=n&&mp[x+1][y]==ch&&mp[x+2][y]==ch&&mp[x+3][y]==ch&&mp[x+4][y]==ch) ++res;
	if(x+4<=n&&y+4<=m&&mp[x+1][y+1]==ch&&mp[x+2][y+2]==ch&&mp[x+3][y+3]==ch&&mp[x+4][y+4]==ch) ++res;
	if(x-4>=1&&y+4<=m&&mp[x-1][y+1]==ch&&mp[x-2][y+2]==ch&&mp[x-3][y+3]==ch&&mp[x-4][y+4]==ch) ++res;
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>mp[i][j];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			ans[mp[i][j]-'0']+=check(i,j,mp[i][j]);
		}
	}
	cout<<ans[1]<<" "<<ans[2]<<"n";
	return 0;
}

C-消除死域点

先默认1为根，处理树上的祖先、大小和深度信息，如何第二遍dfs统计答案，假设最开始不删边的答案是 a n s ans ans，在 x x x点与父亲之间删一条边，对答案减少的贡献是 f [ x ] f[x] f[x],那么答案就是 a n s − m a x ( f i ) ans-max(f_i) ans−max(fi​)，对于 f [ x ] f[x] f[x]可以考虑求向上 s i z e size size不超过 k k k的段，那么整一段切给 x x x显然是最优的，并且下面的答案也不会改变， f [ x ] f[x] f[x]就是这一段的深度差。

复制代码
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
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7;

int n,k,mx=0,sz[N],dep[N],fa[N][25];
vector<int>G[N];

void dfs(int x,int f){   //处理树上每个结点的信息 
	sz[x]=1;dep[x]=dep[f]+1;
	fa[x][0]=f;
	for(int i=1;i<=20;++i) fa[x][i]=fa[fa[x][i-1]][i-1]; 
	for(auto to:G[x]){
		if(to==f) continue;
		dfs(to,x);
		sz[x]+=sz[to];
	}
}

void dfs2(int x,int f){
	if(sz[f]-1>=k){  //如果f的子树大小大于k 
		int p=x;
		for(int i=20;i>=0;--i){   //从x出发向上找一段 
			if(fa[p][i]&&sz[fa[p][i]]-sz[x]<k+1) p=fa[p][i]; 
		}
		mx=max(mx,dep[x]-dep[p]); //以x为新根，这一段的结点对答案贡献删除 
	}
	for(auto to:G[x]){
		if(to==f) continue;
		dfs2(to,x);
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=n;++i){
		if(sz[i]-1>=k) ++ans;
	}
	dfs2(1,0);
	cout<<ans-mx<<"n";
	return 0;
}

D-七圣召唤

假设有 n n n次抽卡机会和 m m m种卡

集齐 m m m张卡的期望抽取次数是 E ( m ) = ∑ i m m i E(m)=sum_i^m{frac{m}{i}} E(m)=∑im​im​，可以理解为 i m frac{i}{m} mi​的概率抽到第 i i i种，因此期望次数就是它的倒数。

抽 n n n次的期望种数是 F ( n ) = F ( n − 1 ) + m − F ( n − 1 ) m F(n)=F(n-1)+frac{m-F(n-1)}{m} F(n)=F(n−1)+mm−F(n−1)​，可以理解为在 n − 1 n-1 n−1抽期望为 x x x种的基础上，抽到新的一种的概率为 m − x m frac{m-x}{m} mm−x​

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int n,m;

signed main(){
	cin>>n>>m;
	double ans1=0,ans2=0;
	for(int i=1;i<=m;++i) ans1+=double(m)/i;
	for(int i=1;i<=n;++i) ans2+=(m-ans2)/m;
	printf("%.8lf %.8lfn",ans1,ans2);
	return 0;
}

E-病毒危机

直接暴力找交集就可以了。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;

int n,m,k,is[N],yes[N];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	cin>>k;for(int i=1,x;i<=k;++i) cin>>x,is[x]=1;
	for(int i=2;i<=n;++i){
		cin>>k;
		for(int j=1,x;j<=k;++j){
			cin>>x;
			if(is[x]) yes[i]=1;
		}
	}
	int ans=1;
	for(int i=1;i<=n;++i) if(yes[i]) ++ans;
	cout<<ans<<"n"; 
	return 0;
}

F-互质

挺离谱的，一开始还以为随机乱搞，但是一个连续的范围怎么可能会有很多数跟一个 1 e 18 1e18 1e18的数互质，所以当然是直接找啦。

复制代码
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
#include<bits/stdc++.h>
#define int long long 
using namespace std;

int n,T;

int read(){	int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

inline int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

void solve(){
	n=read();
	int L=(n+3)/4,R=n/2;
	for(int i=L;i<=min(R,L+25ll);++i){
		if(gcd(n,i)==1){
			write(i);putchar('n');
			return;
		}
	}
	puts("-1");		

}

signed main(){
	T=read();
	while(T--){
		solve();
	} 
	return 0;
}

G-栈与公约数

单点修改、单点查询、区间修改、区间查询，所以是线段树裸题。

复制代码
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
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;

inline int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

int n;
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
int tr[N<<2],tg[N<<2];

void pushdown(int p,int l,int r){
	if(tg[p]){
		tr[ls]=tr[rs]=tg[ls]=tg[rs]=tg[p];
		tg[p]=0;
	}
}

void update(int p,int l,int r,int pos,int v){
	if(l==r){tr[p]=v;return;}
	pushdown(p,l,r);
	if(pos<=mid) update(ls,l,mid,pos,v); 	
	else update(rs,mid+1,r,pos,v);
	tr[p]=gcd(tr[ls],tr[rs]);
}

int query(int p,int l,int r,int pos){
	if(l==r) return tr[p];
	pushdown(p,l,r);
	if(pos<=mid) return query(ls,l,mid,pos);
	else return query(rs,mid+1,r,pos);
}

int query_gcd(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tr[p];
	pushdown(p,l,r);
	if(ql>mid) return query_gcd(rs,mid+1,r,ql,qr);
	else if(qr<=mid) return query_gcd(ls,l,mid,ql,qr);
	else return gcd(query_gcd(ls,l,mid,ql,qr),query_gcd(rs,mid+1,r,ql,qr));
}

void modify(int p,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr){
		tg[p]=tr[p]=v;
		return;
	}
	pushdown(p,l,r);
	if(ql<=mid) modify(ls,l,mid,ql,qr,v);
	if(qr>mid) modify(rs,mid+1,r,ql,qr,v);
	tr[p]=gcd(tr[ls],tr[rs]);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	int idx=0;
	for(int i=1,op,x,k;i<=n;++i){
		cin>>op;
		if(op==1){
			cin>>x;
			++idx;
			update(1,1,n,idx,x);
		}else if(op==2){
			update(1,1,n,idx,0);
			--idx;
		}else if(op==3){
			cout<<query(1,1,n,idx)<<"n";
		}else{
			cin>>k;
			int md=query_gcd(1,1,n,idx-k+1,idx);
			modify(1,1,n,idx-k+1,idx,md);
		}
	}
	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
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
struct E{
	int u,v,w,nxt;
	friend bool operator <(E A,E B){
		return A.w>B.w;
	}
}e[N];
int cnt=0,head[N];
inline void addedge(int u,int v,int w){
	e[++cnt]=(E){u,v,w,head[u]};head[u]=cnt;
}

int n,m,ans,num=0,fa[N];
inline int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]); 
}

signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1,u,v,w;i<=n;++i){
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w); 
	}
	stable_sort(e+1,e+1+cnt);
	for(int i=1;i<=cnt;++i){
		int fx=find(e[i].u),fy=find(e[i].v);
		if(fx!=fy){
			++num;
			fa[fx]=fy;
			if(num==n-1){ //剩下一个点没有合并 
				ans=e[i].w;
				break;
			}
		}
	}
	cout<<ans<<"n";
	return 0;
}

K-俄罗斯方块

不难想，打表可以发现有解的条件是 n % 8 = = 7 ∣ ∣ n % 8 = = 0 n%8==7||n%8==0 n%8==7∣∣n%8==0，在纸上画一画就可以得到 7 ∗ 7 7*7 7∗7的三角形、 8 ∗ 8 8*8 8∗8的三角形的构造（下面代码有），那么把他们拼在一块就变成了 8 ∗ 8 8*8 8∗8的正方形了，接下来就模拟一下堆积木的过程。

复制代码
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
#include<bits/stdc++.h>
using namespace std;

int n,idx=0,mp[1005][1005]; 

int tri1[10][10]={
{1},
{1,1},
{1,2,2},
{3,2,2,4},
{3,3,4,4,4},
{3,5,6,6,6,7},
{5,5,5,6,7,7,7}
};

int tri2[10][10]={
{1},
{1,1},
{1,2,2},
{3,2,2,4},
{3,3,4,4,4},
{3,6,6,6,7,7},
{5,5,6,8,7,7,9},
{5,5,8,8,8,9,9,9}
};

int rct[10][10]={
{1,10,10,10,11,12,12,12},
{1,1,10,11,11,11,12,13},
{1,2,2,14,14,14,13,13},
{3,2,2,4,14,15,15,13},
{3,3,4,4,4,15,15,16},
{3,6,6,6,7,7,16,16},
{5,5,6,8,7,7,9,16},
{5,5,8,8,8,9,9,9}
};


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
//	for(int i=1;i<=n;++i) frac[i]=frac[i-1]+i;
//	for(int i=1;i<=n;++i) cout<<i<<" "<<frac[i]<<" "<<frac[i]%4<<" !!n";
	if(n%8!=7&&n%8!=0){
		cout<<"NOn";
		return 0;
	}
	cout<<"YESn";
	int sx=1,sy=1,idx=0;
	if(n%8==7){
		for(int i=0;i<7;++i){
			for(int j=0;j<=i;++j){
				mp[sx+i][sy+j]=tri1[i][j]+idx;
			}
		}
		idx+=7;sx=8;sy=1;
		for(;sx<n;sx+=8){
			for(sy=1;sy<=sx;sy+=8){
				for(int i=0;i<8;++i){
					for(int j=0;j<8;++j){
						mp[sx+i][sy+j]=rct[i][j]+idx;
					}
				}
				idx+=16;
			}
			for(int i=0;i<7;++i){
				for(int j=0;j<=i;++j){
					mp[sx+i+1][sy+j]=tri1[i][j]+idx;
				}
			}
			idx+=7;
		}
	}else{
		for(int i=0;i<8;++i){
			for(int j=0;j<=i;++j){
				mp[sx+i][sy+j]=tri2[i][j]+idx;
			}
		}
		idx+=9;sx=9;sy=1;
		for(;sx<n;sx+=8){
			for(sy=1;sy<sx;sy+=8){
				for(int i=0;i<8;++i){
					for(int j=0;j<8;++j){
						mp[sx+i][sy+j]=rct[i][j]+idx;
					}
				}
				idx+=16;
			}
			for(int i=0;i<8;++i){
				for(int j=0;j<=i;++j){
					mp[sx+i][sy+j]=tri2[i][j]+idx;
				}
			}
			idx+=9;
		}		
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			//printf("%2d ",mp[i][j]);
			cout<<mp[i][j]<<" ";
		}
		cout<<"n";
	}
	return 0;
}

M-画画

贪心把同时不符合行和列的奇偶性的格子改掉，必然是最优的。

复制代码
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
#include<bits/stdc++.h>
using namespace std;
const int N=1007;

int n,numx[N],numy[N];
char mp[N][N];

void solve(){
	cin>>n;
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			mp[i][j]='1';
			++numx[i];++numy[j];
		}
	}
	for(int i=n-1;i>=0;--i){
		for(int j=n-1;j>=0;--j){
			if((numx[i]&1)!=(i&1)&&(numy[j]&1)!=(j&1)){
				--numx[i];--numy[j];
				mp[i][j]='0';
			}
		}
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			cout<<mp[i][j];
		}
		cout<<"n";
	}
	for(int i=0;i<n;++i) numx[i]=numy[i]=0;
}

signed main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0; 
}

最后

以上就是冷傲舞蹈最近收集整理的关于2022 年辽宁省大学生程序设计竞赛 个人题解2022 年辽宁省大学生程序设计竞赛的全部内容，更多相关2022内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(68)

相关文章

第八届ACM趣味程序设计竞赛第三场（正式赛）官方题解
第八届ACM趣味程序设计竞赛第三场（正式赛）官方题解
2020 年百度之星·程序设计大赛部分题解DecCovidCarIntersection
2020 年百度之星·程序设计大赛部分题解DecCovidCarIntersection
【超好懂的比赛题解】“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解
【超好懂的比赛题解】“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解
2019年安徽省程序设计大赛题解
2019年安徽省程序设计大赛题解
2022 年辽宁省大学生程序设计竞赛 个人题解2022 年辽宁省大学生程序设计竞赛
2022 年辽宁省大学生程序设计竞赛 个人题解2022 年辽宁省大学生程序设计竞赛
2017第一届河北省大学生程序设计竞赛题解超级密码考研声之形春游秋游自动签到机奇妙糖果屋商品清算奇异旅馆
2017第一届河北省大学生程序设计竞赛题解超级密码考研声之形春游秋游自动签到机奇妙糖果屋商品清算奇异旅馆
输出，loss出现-inf 或者nan
输出，loss出现-inf 或者nan
c语言输出 inf是什么意思,cuffdiff 输出文件中的inf和nan的意思
c语言输出 inf是什么意思,cuffdiff 输出文件中的inf和nan的意思

评论列表共有 0 条评论

立即
投稿
返回
顶部