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< return 0; } 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< 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 using namespace std; const int N=5e5+7; int n,k,mx=0,sz[N],dep[N],fa[N][25]; vector 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] } 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 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< 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)=∑imim，可以理解为 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 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< return 0; } F-互质 挺离谱的，一开始还以为随机乱搞，但是一个连续的范围怎么可能会有很多数跟一个 1 e 18 1e18 1e18的数互质，所以当然是直接找啦。 #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< }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 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< 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 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< 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 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 for(sy=1;sy 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< } cout<<"\n"; } return 0; } 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;i for(int j=0;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 for(int j=0;j cout< } cout<<"\n"; } for(int i=0;i } signed main(){ int t; cin>>t; while(t--){ solve(); } return 0; } 推荐链接
发表评论