2022 年辽宁省大学生程序设计竞赛 个人题解
创始人
2024-03-31 07:19:35
0次
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
using namespace std;signed main(){int n;cin>>n;int ans=n-(2022-73);cout< B-可莉的五子棋
枚举每个点作为起点向下统计就行了。
#include
#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< C-消除死域点
先默认1为根，处理树上的祖先、大小和深度信息，如何第二遍dfs统计答案，假设最开始不删边的答案是ansansans，在xxx点与父亲之间删一条边，对答案减少的贡献是f[x]f[x]f[x],那么答案就是ans−max(fi)ans-max(f_i)ans−max(fi)，对于f[x]f[x]f[x]可以考虑求向上sizesizesize不超过kkk的段，那么整一段切给xxx显然是最优的，并且下面的答案也不会改变，f[x]f[x]f[x]就是这一段的深度差。
#include
using namespace std;
const int N=5e5+7;int n,k,mx=0,sz[N],dep[N],fa[N][25];
vectorG[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]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;icin>>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< D-七圣召唤
假设有nnn次抽卡机会和mmm种卡
集齐mmm张卡的期望抽取次数是E(m)=∑immiE(m)=\sum_i^m{\frac{m}{i}}E(m)=∑imim，可以理解为im\frac{i}{m}mi的概率抽到第iii种，因此期望次数就是它的倒数。
抽nnn次的期望种数是F(n)=F(n−1)+m−F(n−1)mF(n)=F(n-1)+\frac{m-F(n-1)}{m}F(n)=F(n−1)+mm−F(n−1)，可以理解为在n−1n-1n−1抽期望为xxx种的基础上，抽到新的一种的概率为m−xm\frac{m-x}{m}mm−x
#include
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
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< F-互质
挺离谱的，一开始还以为随机乱搞，但是一个连续的范围怎么可能会有很多数跟一个1e181e181e18的数互质，所以当然是直接找啦。
#include
#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
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<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
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< K-俄罗斯方块
不难想，打表可以发现有解的条件是n%8==7∣∣n%8==0n\%8==7||n\%8==0n%8==7∣∣n%8==0，在纸上画一画就可以得到7∗77*77∗7的三角形、8∗88*88∗8的三角形的构造（下面代码有），那么把他们拼在一块就变成了8∗88*88∗8的正方形了，接下来就模拟一下堆积木的过程。
#include
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<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(;sxfor(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(;sxfor(sy=1;syfor(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< M-画画
贪心把同时不符合行和列的奇偶性的格子改掉，必然是最优的。
#include
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;ifor(int j=0;jmp[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;ifor(int j=0;jcout<int t;cin>>t;while(t--){solve();}return 0;
}
相关内容
热门资讯
监控摄像头接入GB28181平...
流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
Windows10添加群晖磁盘...
在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer...
目录 目录 什么是protocol buffer 1.protobuf 1.1安装 1.2使用...
在Word、WPS中插入AxM...
引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
Fluent中创建监测点
1 概述某些仿真问题，需要创建监测点，用于获取空间定点的数据...
MySQL下载和安装（Wind...
前言：刚换了一台电脑，里面所有东西都需要重新配置，习惯了所...
MFC文件操作
MFC提供了一个文件操作的基类CFile，这个类提供了一个没有缓存的二进制格式的磁盘...
有效的括号
一、题目 给定一个只包括 '('，')'，'{'，'}'...
【PdgCntEditor】解...
一、问题背景 大部分的图书对应的PDF，目录中的页码并非PDF中直接索引的页码...