【2019.7.15 NOIP模拟赛 T1】夹缝（mirror）（思维题）

思维题

此题应该是比较偏思维的。

假设一次反射后前进的距离是\(2^x(2y+1)\)，则显然，它可以看做是前进距离为\(2^x\)的光线经过了\((2y+1)\)次反射，两者是等价的，甚至后者可能还要更优。

因此，我们只需考虑前进距离为\(2^x\)的光线。

也就是说，我们枚举\(x\)，统计\((2^x+a_i)\% 2^{x+1}\)与\(b_i\%2^{x+1}\)中众数的出现次数的最大值。

关于众数的统计，我很\(naive\)地开了个\(map\)，实际上，似乎用排序可以得到更优秀的速度？

代码

#pragma GCC optimize(2)

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 150000

#define Gmax(x,y) (x<(y)&&(x=(y)))

#define swap(x,y) (x^=y^=x^=y)

using namespace std;

int n,m,h,a[N+5],b[N+5];

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		int f;char c,*A,*B,FI[FS];

	public:

		I FastIO() {A=B=FI;}

		Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;}

		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

}F;

class MultiSolver

{

	private:

		map<int,int> p;

	public:

		I void Solve()

		{

			unsigned k,kk,X;RI i,t,res=0,ans=0,mn=min(a[1],b[1]),mx;

			for(i=1;i<=n;++i) a[i]-=mn;for(i=1;i<=m;++i) b[i]-=mn;mx=max(a[n],b[m]);//初始化，全部取正

			for(t=0,i=1;i<=n;++i) a[i]&1&&++t;Gmax(ans,max(t,n-t));//若单独考虑一边

			for(t=0,i=1;i<=m;++i) b[i]&1&&++t;Gmax(ans,max(t,m-t));//同上

			for(i=1;i<=n;++i) t=++p[a[i]],Gmax(res,t);

			for(p.clear(),i=1;i<=m;++i) t=++p[b[i]],Gmax(ans,res+t);//考虑竖直情况

			for(k=1,kk=2;kk<=mx;k<<=1,kk<<=1)//枚举光线前进距离

			{

				for(X=kk-1,p.clear(),i=1;i<=n;++i) ++p[(k+a[i])&X];//统计众数

				for(i=1;i<=m;++i) t=++p[b[i]&X],Gmax(ans,t);//统计众数并更新答案

			}printf("%d",ans);//输出

		}

}S;

int main()

{

	freopen("mirror.in","r",stdin),freopen("mirror.out","w",stdout);

	RI i;for(F.read(n,m,h),i=1;i<=n;++i) F.read(a[i]);for(i=1;i<=m;++i) F.read(b[i]);//读入

	return sort(a+1,a+n+1),sort(b+1,b+m+1),S.Solve(),0;//先排序，后求解

}