Codeforces Round #509 (Div. 2) F. Ray in the tube(思维)

时间:2023-03-09 01:28:42
Codeforces Round #509 (Div. 2) F. Ray in the tube(思维)

题目链接:http://codeforces.com/contest/1041/problem/F

题意:给出一根无限长的管子,在二维坐标上表示为y1 <= y <= y2,其中 y1 上与 n 个点,y2 上有 m 个点,问在 y1 和 y2 上各选一个点,从其中一个点出发射到另外一个点并无限反射下去,可以触碰到 y1 和 y2 上的点和最大为多少。

题解:考虑射出去的线打到对面板上所需要走的距离dd,假设出发点为0,则打在自己这边上的点的坐标为{0,2d,4d,6d,8d,...}{0,2d,4d,6d,8d,...},打在对面板上的则是{d,3d,5d,7d,9d,...}{d,3d,5d,7d,9d,...}。若将距离改为k⋅d,则两个点集分别为{0,2kd,4kd,6kd,8kd,...}{0,2kd,4kd,6kd,8kd,...},{kd,3kd,5kd,7kd,9kd,...}{kd,3kd,5kd,7kd,9kd,...},可以发现若k为奇数,两个集合中的点都只会减少不会增加,kk为偶数时则有存在增减的情况,因此设k=2^l一定是最优的。

 #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define ull unsigned long long
#define mst(a,b) memset((a),(b),sizeof(a))
#define mp(a,b) make_pair(a,b)
#define pi acos(-1)
#define pii pair<int,int>
#define pb push_back
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const int MAXN = 1e5 + ;
const int MAXM = 2e6 + ;
const ll mod = 1e9 + ; int a[MAXN], b[MAXN];
map<ll,int>mp; int main()
{
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int n,m,y;
scanf("%d%d",&n,&y);
for(int i = ; i < n; i++) scanf("%d",&a[i]);
scanf("%d%d",&m,&y);
for(int i = ; i < m; i++) scanf("%d",&b[i]);
int ans = ;
ll d = , dd = ;
for(int i = ; i <= ; i++) {
mp.clear();
dd <<= ;
for(int j = ; j < n; j++) mp[a[j] % dd]++;
for(int j = ; j < m; j++) mp[(b[j] + d) % dd]++;
for(auto it : mp) ans = max(ans, it.second);
d <<= ;
}
printf("%d\n",ans);
return ;
}