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;
}
更多推荐
【Codeforces】1041F. Ray in the tube
发布评论