CF1710D Recover theTree
2022/8/27 6:23:13
本文主要是介绍CF1710D Recover theTree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
给定每个区间是不是连通块,还原这棵树。(\(n\leqslant 2000\))
题解:
我肯定是做不出来,也不理解是怎么想的。不如直接讲做法,然后证明正确性,也是对 wc 题解的补充。
先贴个代码:
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; const int mod=1e9+7; #define inf 1e9 inline int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; } const int N=2005; int T,n,m,ok[N][N],L[N]; inline void solve(){ n=read(); for(int i=1;i<=n;i++){ string s;cin>>s;L[i]=i; for(int j=1;j<=n-i+1;j++) ok[i][j+i-1]=s[j-1]-'0'; } for(int r=1;r<=n;r++) for(int l=r-1;l>=1;l--){ if(!ok[l][r]||L[l]==L[r])continue; if(L[L[r]-1]==L[l])printf("%d %d\n",l,r); else{ printf("%d %d\n",l,L[r]-1); printf("%d %d\n",l,r); for(int j=l+1;j<L[L[r]-1];++j) if(L[j]==j)printf("%d %d\n",j,r); } for(int j=l;j<=r;j++)L[j]=L[l]; } } int main(){ T=read(); while(T--)solve(); return 0; }
这篇关于CF1710D Recover theTree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享