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

news/2024/7/20 22:07:13 标签: 算法, 图论, 深度优先, c++, 动态规划

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-伟大奋斗

#include<bits/stdc++.h>
using namespace std;

signed main(){
	int n;
	cin>>n;
	int ans=n-(2022-73);
	cout<<ans<<"\n";
	return 0;
}

B-可莉的五子棋

枚举每个点作为起点向下统计就行了。

#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]就是这一段的深度差。

#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​

#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 %.8lf\n",ans1,ans2);
	return 0;
}

E-病毒危机

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

#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的数互质，所以当然是直接找啦。

#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-栈与公约数

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

#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-图的分割

读懂了就可以直观感受到他要求一个最小/大生成树，因为克鲁斯卡尔枚举边的过程时，最后一条边保证是把图分成两块并且边权最大值最小的，符合题目要求。

#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的正方形了，接下来就模拟一下堆积木的过程。

#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<<"NO\n";
		return 0;
	}
	cout<<"YES\n";
	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-画画

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

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

http://www.niftyadmin.cn/n/907.html

相关文章

VDT (virtual device on tcp) 基于tcp通信的虚拟设备工具集

VDT (virtual device on tcp) 基于tcp通信的虚拟设备工具集

概要 VDT (virtual device on tcp) 基于tcp通信的虚拟设备工具集 DOT (device on tcp) 创建虚拟字符设备&#xff0c;通过tcp收发来读写。DTT (device to tcp) 打开字符设备&#xff0c;通过tcp来读写。NOD (net on device) 创建虚拟网卡设备&#xff0c;通过字符设备读写来收…
阅读更多...
基于STM32F469 discovery kit 开发板的开发1

基于STM32F469 discovery kit 开发板的开发1

目录基于STM32F469 discovery kit 开发板的开发开发板简介开发环境搭建安装st-link驱动基于STM32F469 discovery kit 开发板的开发 意法半导体推出的基于STM32F469 cpu的这款开发板&#xff0c;整合高性能的Cortex-M4处理器&#xff0c;其Chrom-ART Accelerator技术大大提升了…
阅读更多...
TCP/IP协议

TCP/IP协议

目录 1. 应用层 2. 传输层 2.1 UDP协议 2.2 TCP协议&#xff08;*三次握手四次挥手重点&#xff01;&#xff01;&#xff01;&#xff09; 2.2.1 确认应答机制 2.2.2 超时重传 2.2.3 连接管理 2.2.4 滑动窗口 2.2.5 流量控制 2.2.6 拥塞控制 2.2.7 延迟应答 …
阅读更多...
嵌入式开发--CubeMX使用入门教程

嵌入式开发--CubeMX使用入门教程

嵌入式开发–CubeMX使用入门教程 CubeMX简介 传统的单片机开发时&#xff0c;需要针对片上外设做各种初始化的工作&#xff0c;相当麻烦。 CubeMX是ST公司出品的一款图形化代码生成工具&#xff0c;通过图形化界面&#xff0c;可以非常直观的配置好各种片上外设&#xff0c;时…
阅读更多...
渗透学习—靶场篇—墨者学院—SQL注入漏洞测试(参数加密)

渗透学习—靶场篇—墨者学院—SQL注入漏洞测试(参数加密)

文章目录总结打开靶场&#xff0c;发现在登录框下方有一个可以点击的地方&#xff1a; 此处&#xff0c;点击后我们就可以发现一个新的页面了&#xff01;&#xff01;然后我们在这个页面中呢&#xff0c;我们仔细观察以下url的特征&#xff0c;发现其是利用id xxx 进行查询的…
阅读更多...
傅里叶变换+频域滤波

傅里叶变换+频域滤波

傅里叶变换频域滤波cv2.imread()基本参数介绍傅里叶变换什么是频域傅里叶变换的由来傅里叶变换算法 DFT, FFT灰度图这个博客记得看看 cv2.imread()基本参数介绍 Mat cv::imread(const String & filename, int flags IMREAD_COLOR) retval cv.imread(filename[, flags]…
阅读更多...
Pytest+Unittest+Git+Jenkins企业级CICD自动化测试平台建设方案

Pytest+Unittest+Git+Jenkins企业级CICD自动化测试平台建设方案

随着持续集成的引入&#xff0c;项目中的自动化测试用例越来越多&#xff0c;每轮执行所消耗的时间也越来越久。 要提高自动化测试用例执行的效率&#xff0c;以下几点是需要考虑的根本点。 &#xff08;1&#xff09;公司项目的交付策略如何 首先&#xff0c;测试团队服务于…
阅读更多...
改进YOLOv5系列：增加Swin-Transformer小目标检测头

改进YOLOv5系列：增加Swin-Transformer小目标检测头

&#x1f4a1;统一使用 YOLOv5 代码框架&#xff0c;结合不同模块来构建不同的YOLO目标检测模型。&#x1f31f;本项目包含大量的改进方式,降低改进难度,改进点包含【Backbone特征主干】、【Neck特征融合】、【Head检测头】、【注意力机制】、【IoU损失函数】、【NMS】、【Loss…
阅读更多...
最新文章

Copyright @ 2022~2023