首页 > 代码库 > POJ 3484 Showstopper（二分答案）
POJ 3484 Showstopper（二分答案）
【题目链接】 http://poj.org/problem?id=3484
【题目大意】
给出n个等差数列的首项末项和公差。求在数列中出现奇数次的数。题目保证至多只有一个数符合要求。
【题解】
因为只有一个数符合要求，所以在数列中数出现次数的前缀和必定有奇偶分界线，
所以我们二分答案，计算前缀和的奇偶性进行判断，得到该数的位置。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long LL;const int N=500010;const LL inf=1LL<<33;LL X[N],Y[N],Z[N];char s[60];int n; LL cal(LL x){ LL ans=0,t; for(int i=1;i<=n;i++){ if(x<X[i])continue; t=min(x,Y[i]); ans+=(t-X[i])/Z[i]+1; }return ans; }int main(){ while(gets(s)){ X[n=1]=0; sscanf(s,"%lld %lld %lld",&X[n],&Y[n],&Z[n]); if(!X[n])continue; memset(s,0,sizeof(s)); while(gets(s),*s)n++,sscanf(s,"%lld %lld %lld",&X[n],&Y[n],&Z[n]),memset(s,0,sizeof(s)); LL l=1,r=inf,ans=0; while(l<=r){ LL mid=(l+r)>>1; if(cal(mid)&1LL)r=mid-1,ans=mid; else l=mid+1; }if(!ans)puts("no corruption"); else printf("%lld %lld\n",ans,cal(ans)-cal(ans-1)); }return 0;}
POJ 3484 Showstopper（二分答案）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。