Codeforces 1220D. Alex and Julian
2024-09-05 16:38:47
首先考虑怎样的集合一定是合法的
发现全部是奇数的集合一定合法,因为每次都是奇数连偶数,偶数连奇数
然后考虑如果集合同时有奇数和偶数是否一定不合法,结论是一定不合法,证明如下:
设某个奇数为 $2x+1$ ,某个偶数为 $2y$,那么 $0$ 到 $(2x+1)*(2y)$ 就有两种路线,$2x+1$ 步和 $2y$ 步的,
这两条路线刚好构成一个奇环,所以一定不是二分图
所以一种合法方案就是全留奇数,但是还不够,因为可能删掉一些奇数和偶数以后只剩下偶数也是合法的,比如 $2,6$ 就是合法的
发现如果只剩下偶数,那么我们可以把所有偶数同时除以 $2$,这样并不影响集合的性质,证明的话可以这样考虑:
所有数都是偶数的情况下,编号为偶数的点只会连向编号为偶数的点,奇数点也只能连奇数点,那么我们可以把这两种点分开来
然后重新按原编号大小编号为 $0,1,...$,其实就是偶数点的编号全部除以 $2$,奇数点的编号全部 $-1$ 再除以 $2$
发现这样新的两个图其实是一样的并且就是原集合的数都除以 $2$ 以后构成的图,所以证明完毕
然后除以二以后发现又有些奇数有些偶数了,继续递归地考虑即可
所以,可能的方案应该是这样的:
1. 全留奇数
2. 把1.奇数都扔了,然后全留/2后是奇数的数
3. 把1.2.的奇数都扔了,全留/4后是奇数的数
...
然后直接模拟即可,复杂度 $O(n \log 10^{18})$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline ll read()
{
ll x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=2e5+;
ll n,a[][N],ans=-,p;
int main()
{
n=read();
for(int i=;i<=n;i++) a[][i]=read();
for(int i=;i<;i++)
{
ll res=; bool flag=;
for(int j=;j<=n;j++)
{
if(a[i][j]&) res++;
if(a[i][j]) flag=;
}
if(!flag) break;
if(res>ans) ans=res,p=i;
for(int j=;j<=n;j++)
{
if(a[i][j]&) a[i+][j]=;
else a[i+][j]=a[i][j]>>;
}
}
printf("%lld\n",n-ans);
for(int i=;i<=n;i++)
if((a[p][i]&)==) printf("%lld ",a[][i]);
if(n-ans) puts("");
return ;
}
最新文章
- Go项目结构和模块导入
- AngularJS------认识AngularJS
- Android Fragment (二) 实例1
- React Native填坑之旅--class(番外篇)
- JavaWeb项目的classpath说明
- HTML自动换行的问题
- log4j安装与简介
- elasticsearch 修改内存
- WebMatrix安装和使用
- Java.util.zip adding a new file overwrites entire jar?(转)
- Python中如何防止sql注入
- 改进SQL Server 性能 - 索引碎片重建
- 剑指offer 4.树 重建二叉树
- 《C#并发编程经典实例》学习笔记-关于并发编程的几个误解
- php面试题整理(三)
- [CQOI2018]九连环
- Gym 101194E / UVALive 7901 - Ice Cream Tower - [数学+long double][2016 EC-Final Problem E]
- echart中间显示固定的字
- php 自定义 分页函数
- DevExpress v17.2新版亮点—WPF篇(五)