杭二集训 diyiti(CF GYM 101597A)

思维好题

Posted by yjjr's blog on January 6, 2018

标签:数论,分治

题目

题目传送门

1.1 backgrounds 小O是一个很萌很萌的女孩子 1.2 content 作为一个很萌很萌的女孩子,小O有很多很多美丽的宝石。 有一天,小O将她的宝石排成了一排一共n堆,第一堆有1个宝石,之后 每一堆的宝石数目是前一堆的两倍。 但是小O发现她的宝石不够用了,于是小O决定将每堆的宝石数量对一 个正整数M取模。 趁小O出去玩的时候,小Y偷偷地把这n堆宝石的顺序打乱了。 现在小O想把这些珠子变回原来的顺序。 小O想知道M最小是多少。 数据保证一定有解。 1.3 input format 第一行包含一个整数n 第二行n个整数ai,表示打乱顺序后第i堆宝石的数量。 1.4 output format 一行一个正整数M,表示答案。 1.5 sample input 5 1 2 3 4 8 1.6 sample output 13 1.7 constraints 对于20% 的数据,保证n ≤ 10 对于另外30%的数据,保证答案一定为奇数。 对于100% 的数据,1 ≤ n ≤ 2×10^5 , 0 ≤ ai ≤ 10^18

分析

考试的时候我乱搞竟然得了80pts,震惊

还有人暴力+随机化判断是否合法AC的(早知道我也去试试运气了,貌似大概率正确)


首先令$M=2^pq$(p可以为0,q为奇数) 假设M中含有因子2。 那么ai中除了1,其他数均为偶数。(觉得不显然的可以手动弄几个M玩一玩) 那么我们把这个1去掉,并且其他数全除以2,那么就变成了一个n=n-1,M=M/2的子问题。 经过一番操作,变成了一个M为奇数的问题。 对于M是奇数,我们找出ai中最大的奇数,最大的偶数以及次大的偶数。 然后将(偶数2-奇数)作为M check一下,取最小的合法M。 为什么这样做: 我们考虑一下模M意义下,宝石堆的宝石数是怎么样的。 大约长这样 b1 b1*2 b1*4 …… b2 b2*2 b2*4 …… 其中 bi=b[i-1]2^x-M 我们按有没有撞顶分成若干个子列。 那么每个奇数就是每个子列的第一个。 我们找出最大的奇数,那么考虑这个奇数是怎么来的。 显然是由它前面一个子列的末尾那个偶数2-M得到的。 并且那个偶数一定是最大或者次大。(可以想一想为什么)

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=3e5+6;
ll a[maxn],b[maxn],c[maxn],ans;
int vis[maxn],n,m=0;
bool ok(ll ans){
	c[1]=1%ans;
	rep(i,2,n)c[i]=(c[i-1]*2)%ans;
	sort(c+1,c+n+1);
	rep(i,1,n)
		if(a[i]!=c[i])return 0;
	return 1;
}//判断当前答案是否合法
void doit(){
	ll ji=0,ou1=0,ou2=0;
	rep(i,1,m){
		if(b[i]&1)ji=max(ji,b[i]);
		else{//寻找最大的奇数,最大和次大的偶数
			if(ou1<b[i])ou2=ou1,ou1=b[i];
			else if(ou2<b[i])ou2=b[i];
		}
	}
	if(ou2!=0){
		ll Q=(ou2*2-ji);
		if(ok(Q*ans)){ans=Q*ans;return;}
	}
	if(ou1!=0){
	 	ll Q=(ou1*2-ji);
	 	if(ok(Q*ans)){ans=Q*ans;return;}
	}//找到一个最小的合法M
}
int check(int x){
	ll tmp=1LL<<x,y=tmp/2;int cnt=0,re=0,z=n; 
	rep(i,1,n)
		if(!vis[i])
			if(a[i]%tmp==y)cnt++;
	if(cnt==1)re=1;if(re!=1)return re;
	rep(i,1,n){
		if(vis[i]){z--;continue;}
		if(a[i]%tmp==y){vis[i]=true;z--;}
	}
	if(z==0)re=2;
	return re;
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	n=read();
	rep(i,1,n)a[i]=read();
	sort(a+1,a+1+n);
	if(a[1]==0){ans=1;if(a[n]!=0)ans=a[n]*2;cout<<ans<<endl;return 0;}//特判M为2^x的特殊情况 
	int now=0;
	while(1){
		int ret=check(now+1);
		if(ret==2){cout<<a[n]+1<<endl;return 0;}
		if(ret==1)now++;else break;
	}
	rep(i,1,n)
		if(!vis[i])b[++m]=a[i];
	ans=1LL<<now;
	rep(i,1,m)b[i]/=ans;//转化为奇数的子问题
	doit();
	cout<<ans<<endl;
	return 0;
}

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr