CF 1041F Ray in the tube

题目描述

https://codeforces.com/problemset/problem/1041/F

简要题意：下边界有 $n$ 个给定点，上边界有 $m$ 个给定点，可以从任意一个点发出一条激光，激光碰到边界会反射，激光到达边界必须打到整数点，问最多可以打到几个给定点

$n,m\le 10^5$

Solution

能够发现当固定起始点之后只需要确定间距 $T$

注意到当 $T$ 含有大于 $1$ 的质因子的时候将其除掉之后一定能有更多的反射点

所以我们只需要枚举间距点为 $2$ 的幂即可

时间复杂度 $O(n\log^2 n)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <tuple>
#include <map> 
#define maxn 100010
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;

int n, m, a[maxn], b[maxn]; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int y1, y2, ans = 0;
    map<int, int> mp; 
    cin >> n >> y1;
    for (int i = 1; i <= n; ++i) cin >> a[i], ++mp[a[i]]; 
    cin >> m >> y2;
    for (int i = 1; i <= m; ++i) cin >> b[i], ++mp[b[i]];
    for (auto u : mp) ans = max(ans, u.second); 
    for (unsigned int s = 1; s <= 2147483647; s *= 2) {
        map<int, int> mp;
        for (int i = 1; i <= n; ++i) ++mp[a[i] % (2 * s)];
        for (int i = 1; i <= m; ++i) ++mp[(b[i] + s) % (2 * s)];
        for (auto u : mp) ans = max(ans, u.second); 
    } cout << ans << "\n"; 
    return 0;
}