---

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统计答案，假设最开始不删边的答案是$ans$，在$x$点与父亲之间删一条边，对答案减少的贡献是$f[x]$,那么答案就是$ans-max(f_i)$，对于$f[x]$可以考虑求向上$size$不超过$k$的段，那么整一段切给$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$次抽卡机会和$m$种卡

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

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

#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-互质

挺离谱的，一开始还以为随机乱搞，但是一个连续的范围怎么可能会有很多数跟一个$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$，在纸上画一画就可以得到$7\ast 7$的三角形、$8\ast 8$的三角形的构造（下面代码有），那么把他们拼在一块就变成了$8\ast 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; 
}