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

朴灿烈づ我的快乐病毒、 2021-12-01 14:24 205阅读 0赞

### 思维题 ###

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

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

转载于:https://www.cnblogs.com/chenxiaoran666/p/Contest20190715T1.html