menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[结论+暴力]Codeforces1041F【Ray in the tube】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论

题目概述

一个管道,从一端向另一端发射一条射线,问最多能够经过多少两端指定的点。

解题报告

可能很斯波……隐约会感觉到有用的发射间距 $d$ 很少……实际上真的很少……因为只有 $d=2^k$ 有用。

为什么?因为如果 $d=t2^k$ 其中 $t$ 是奇数的话还不如 $2^k$ ,因为 $2^k$ 射奇数次回到同一端,覆盖了所有 $t2^k$ 能够覆盖到的点。

所以爆枚就好了,map大法好。

示例程序

特殊情况:上下两端都只有一个点且对称,只需要把最小答案赋值为 $2$ 就好了。

#include<cstdio>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int maxn=100000;

int n,a[maxn+5],m,b[maxn+5],ans;unordered_map<int,int> f;unordered_map<int,int>::iterator it;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%*d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d%*d",&m);for (int i=1;i<=m;i++) scanf("%d",&b[i]);ans=2;
    for (int d=1;d<=1e9;d<<=1){
        f.clear();for (int i=1;i<=n;i++) f[a[i]%(d<<1)]++;for (int i=1;i<=m;i++) f[(b[i]+d)%(d<<1)]++;
        for (it=f.begin();it!=f.end();it++) ans=max(ans,(*it).second);
    }return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up