Gym 101911L Ray in the tube(思维题)

2023-10-12 19:20

文章标签 思维 gym ray tube 101911l

本文主要是介绍Gym 101911L Ray in the tube(思维题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题地址

题意：给出两根线,每根线上有若干个传感器,你可以选择任意一条射线,这条射线会在两根线内不断折射,求经过的最多的传感器数量

思路：在这里插入图片描述
可以发现在每个传感器的地方，我们并不要枚举每一个角度，观察上面的图可以发现，我们只需要枚举log条射线就可以覆盖所有的情况。

那么现在的问题就是如何快速求出每一条射线覆盖的传感器的数量。
假设枚举的射线的长度是len（就是一条折射的射线上在一条直线上相邻两个点的距离），那么所有mod len 相同的点就是可以覆盖到的点，这是一条直线的情况，而另外一条的线同理求所有 $(x+2/len)\equiv (y+2/len) \pmod {len}$

PS：wa79是因为ans的初始值要设为2，因为有上下两个传感器在同一条直线上的情况。

#include <bits/stdc++.h>#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define CLR(x, y) memset((x),y,sizeof(x))
#define fuck(x) cerr << #x << "=" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
ll a[maxn], b[maxn];
ll n, m;
map<ll, ll> mp1, mp2;int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endifint y1, y2;scanf("%lld%d", &n, &y1);for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);scanf("%lld%d", &m, &y2);for (ll i = 1; i <= m; i++) scanf("%lld", &b[i]);ll ans = 2;for (ll len = 2; len <=1e9; len *= 2LL) {mp1.clear();mp2.clear();for (ll i = 1; i <= n; i++) mp1[a[i] % len]++;for (ll i = 1; i <= m; i++) mp2[b[i] % len]++;for (ll i = 1; i <= n; i++) {ans = max(ans, mp1[a[i] % len] + mp2[(a[i] + len / 2) % len]);}for (ll i = 1; i <= m; i++) {ans = max(ans, mp2[b[i] % len] + mp1[(b[i] + len / 2) % len]);}}printf("%lld\n", ans);return 0;
}