Codeforces 512E - Fox And Polygon(构造)
2024-09-08 13:54:18
中规中矩的构造题一道。
首先考虑将两张图都向一个中间状态转化。方便起见我们取所有点都连向 \(1\) 号点的情形作为中间状态。
考虑怎样从初始状态向我们这个中间状态转化。显然我们要将所有不与 \(1\) 相连的对角线都变得与 \(1\) 相连对吧,那我们就考虑从 \(2\) 开始枚举每一个点 \(x\) 以及一个与 \(x\) 相连的边 \((x,y)(x<y)\),满足 \(y\) 与 \(1\) 有边,如果 \(|x-y|>2\) 说明这条对角线不符合要求,我们就找出 \(x,y\) 所在的四边形,显然一个端点是 \(1\),另一个端点枚举一下即可找出,假设为 \(z\),那么我们就操作 \(1,x,y,z\) 构造的四边形,将 \((x,y)\) 变成 \((1,z)\)。如果我们找不到这样的 \(y\) 说明不存在与 \(x\) 相连的不合法的边,我们就继续进入到下一个 \(x\) 即可。容易发现每次操作会恰好使一个不合法的边变得合法,而总边数最多只有 \(n-1\),因此总操作次数的上限为 \(2n-2\)。
时间复杂度 \(\mathcal O(n^2)\)。
事实上本题如果用 bitset
优化数据范围可以出到 \(5\times 10^4\),具体解法就是对每个点开一个 bitset
存储与其相连的点,然后用 bitset
的取并和 _Find_first()
函数找出符合要求的 \(y\),再用 bitset
的取并找出 \(x,y\) 对应的 \(z\)。
const int MAXN=1000;
int n;
struct solver{
vector<pii> op;int tp,a[MAXN+5][MAXN+5];
void read(){int u,v;scanf("%d%d",&u,&v);a[u][v]=a[v][u]=1;}
void work(){
for(int i=1;i<=n;i++) a[i%n+1][i]=a[i][i%n+1]=1;
for(int i=2;i<n;i++) if(a[1][i]){
while(1){
int ps=n;
for(int j=i+1;j<=n;j++) if(a[1][j]){ps=j;break;}
if(ps==i+1) break;
for(int j=i+1;j<ps;j++) if(a[ps][j]&&a[i][j]){
a[j][1]=a[1][j]=1;a[i][ps]=a[ps][i]=0;
(tp)?op.pb(mp(i,ps)):op.pb(mp(1,j));break;
}
}
}
}
} s1,s2;
int main(){
scanf("%d",&n);
for(int i=1;i<=n-3;i++) s1.read();
for(int i=1;i<=n-3;i++) s2.read();
s1.tp=1;s1.work();s2.work();printf("%d\n",s1.op.size()+s2.op.size());
for(int i=0;i<s1.op.size();i++) printf("%d %d\n",s1.op[i].fi,s1.op[i].se);
for(int i=(int)(s2.op.size())-1;~i;i--) printf("%d %d\n",s2.op[i].fi,s2.op[i].se);
return 0;
}
最新文章
- 关于web前端开发学习的顺序
- AngularJs + Web API 页面开发(一)
- 8VC Venture Cup 2016 - Elimination Round
- MFC各种控件的常见操作(逐步添加中......)
- 利用 a 标签自动解析 url
- 重温CSS之背景、文本样式
- fqrouter让安卓手机登陆facebook成为可能
- struts2传递参数值的3中方式
- [转]比较 Rational Unified Process (RUP) 和 Microsoft Solutions Framework (MSF)
- struts2学习笔记(4)——数据类型转换
- Linux 时间同步配置(转)
- Gephi——使用map of countries和Geo Layout实现包含地理坐标的数据可视化
- 14.命令模式(Command Pattern)
- No mapping found for HTTP request with URI [/webapp/] in DispatcherServlet with name &#39;SpringMVC&#39;
- 06建造者模式Builder
- HTML标记 2 ——表格
- PHP 设计模式六大原则
- linux 如何删除文件夹下面的文件和文件夹,只保留两个文件
- oracle中for循环
- ORACLE生成唯一标识函数
热门文章
- 分布式全局ID与分布式事务
- 原生js-返回顶部
- [源码解析] PyTorch如何实现前向传播(3) --- 具体实现
- python反序列化1(__reduce__)
- 第3次 Beta Scrum Meeting
- CSS 奇技淫巧 | 巧妙实现文字二次加粗再加边框
- Go并发编程--Mutex/RWMutex
- 大型DELETE(删除大量数据)的一种解决方案
- 最短路计数(SPFA&#215; Dijkstra√)
- Can&#39;t open PID file /run/zabbix/zabbix_agentd.pid