思维题

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

假设一次反射后前进的距离是\(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;//先排序,后求解
}
05-16 19:10