Codeforces Round #586 (Div. 1 + Div. 2) D.Alex and Julian 简单证明
2024-09-05 09:21:55
题意:在序列中删除最少元素使得得到的图是二分图。
其中点是整数域的点。
比如b1=2 那么a可以连b当且仅当|a-b|=2 同时这里的a,b是任意整数。
怎样判定一个序列是否合法呢?于是想到了二分图没有奇环的性质。
首先发现b序列中有一个奇数和一个偶数那么就会存在奇环。
因为假如从0点出发,0点到奇数和偶数的最小公倍数lcm
假如奇数是3 偶数是2 lcm=6
奇数 0-3-6
偶数0-2-4-6 这里涉及了0 2 3 4 6五个点所以是一个奇环。
这是因为 0到他们的lcm的步数肯定奇偶不同 。奇+偶=奇。
后来发现偶数 比如6 8 10 其实也是一个奇数,所以6 8 其实是可以变成 3 4 5 的奇数。
4 -6 不合法是因为4+4+4=6+6 0 4 8 12 6五个点。
最新文章
- mas_makeConstraints &;&; mas_remakeConstraints &;&; mas_updateConstraints 用法与注意事项
- C# 项目提交过程中感受
- 第14章 位图和位块传输_14.4 GDI位图对象(3)
- 每日一词【命令行CMD】
- Content-Type伪装 - 将jsp伪装成css
- jmeter实例演示
- Java Concurrent Topics
- C#随机取得可用端口号
- Android官方技术文档翻译——Gradle 插件用户指南(7)
- IDEA 代码生成插件 CodeMaker
- 洛谷P2000 拯救世界(生成函数)
- Elasticsearch学习总结 (Centos7下Elasticsearch集群部署记录)
- Python—合并两个有序列表
- Django models模型(1)
- advertisingIdentifier
- canvas制作原生的百分比圆形比例等
- oop klass
- Paper Reading - Deep Visual-Semantic Alignments for Generating Image Descriptions ( CVPR 2015 )
- Expect the Expected UVA - 11427(概率dp)
- Atcoder 2566 3N Numbers(优先队列优化DP)