CF1041F Ray in the tube [枚举/map]

Author Avatar
空気浮遊 2018年09月16日
  • 在其它设备中阅读本文章
  • STL
  • 枚举
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

两根线平行于 x 轴,每根线有若干个传感器
随意发射激光,碰线反弹,问一个激光最多能碰多少个传感器

Solution

考虑步长。

步长为 6 可以分解为步长为 2(lowbit)。
因为 6 可以由 2 乘上奇数得来,因此 6 能到达的点 2 也能到。
对于所有数的 lowbit 都有此成立。

因此只需枚举 $2^k$ 步长即可。

考虑同一个线碰撞为两个坐标在膜两倍步长下同余。
不同线碰撞为一个坐标加上步长和另一个坐标膜两倍步长下同余。
map 统计即可。

注意激光可以垂直于 x 轴发射,一个巨大的坑。

Code

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;

typedef long long ll;
template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=1e5+10;
int u[N], d[N];
map<int, int> ma;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, na, m;
    gn(n), gn(na);
    for(int i=1;i<=n;i++) gn(u[i]);
    gn(m), gn(na);
    for(int i=1;i<=m;i++) gn(d[i]);
    int ans=0;
    for(int k=1;k<=1000000001;k<<=1) {
        ma.clear();
        for(int i=1;i<=n;i++) ma[u[i]%(k<<1)]++;
        for(int i=1;i<=m;i++) ma[(d[i]+k)%(k<<1)]++;
        for(auto x:ma) ans=max(ans, x.second);
    }
    ma.clear();
    for(int i=1;i<=n;i++) ma[u[i]]++;
    for(int i=1;i<=m;i++) ma[d[i]]++;
    for(auto x:ma) ans=max(ans, x.second);
    cout<<ans<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-cf1041f.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material