【Codeforces】1041F. Ray in the tube

Codeforces】1041F. Ray in the tube"/>

【Codeforces】1041F. Ray in the tube

F. Ray in the tube

【题目大意】

一束光从A开始沿B方向射出，经过镜面反射，能经过的点的数量。

【题解】

首先间距没有用。

我们只要知道反射长度就可以了。

我们发现一束光经过奇数次反射会反射到另一面镜子，也可以经过一次反射，所以我们之间除掉所有奇数因子，所以最后反射长度为 2 x 2^x 2x就可以包含所有答案。

只需要枚举 x x x ，然后计算就可以了。

ps：有一个天大的坑，只有两个对称点。

【代码如下】

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=300005;
int n,m,Ans,K;
struct xcw{int x,f;bool operator <(const xcw b)const{return (x&K)<(b.x&K);}
}a[MAXN];
#include<cctype>
int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;return f?ret:-ret;
}
int main(){n=read();read();for(int i=1;i<=n;i++) a[i]=(xcw){read(),0};m=read();read();for(int i=1;i<=m;i++) a[i+n]=(xcw){read(),1};n+=m;Ans=2;for(int i=0;i<=30;i++){K=(1<<i)-1;sort(a+1,a+1+n);for(int j=1,k=1;j<=n;j=k){for(k=j+1;(a[j].x&K)==(a[k].x&K)&&k<=n;k++);int cnt=0;for(int p=j;p<k;p++)cnt+=((a[p].x>>i)&1)^a[p].f;Ans=max(Ans,max(cnt,k-j-cnt));}}printf("%d\n",Ans);return 0;
}