首页 > 代码库 > BZOJ 4725: [POI2017]Reprezentacje ró?nicowe
BZOJ 4725: [POI2017]Reprezentacje ró?nicowe
Description
一个数列.
\(a_1=1,a_2=2\)
当 \(n>2\) 时
\(a_n\left\{\begin{matrix}2a_{n-1},\text{n is an odd number}\\a_{n-1}+r_{n-1},\text{ n is an even number }
\end{matrix}\right.\)
\(S_n=\{a_i-a_j,1 \leqslant j<i\leqslant n\}\)
\(r_n\) 为最小不在 \(S_n\) 中的非负整数.
给出 \(x\),求一对 \((p,q)\) 使得 \(a_p-a_q=x\)
Sol
打表+二分.
可以发现 \(\{a_n\}\) 是一个单调递增的数列,而且有 \(*2\) 的递推式存在,所以当 \(n>2log_2 10^9\) 的时候小于 \(10^9\) 的差只可能是相邻的两个数字.
对于前面几行的元素直接打表存起来,后面的就二分一下在表内的元素算一下就可以了.
Code
/************************************************************** Problem: 4725 User: BeiYu Language: C++ Result: Accepted Time:568 ms Memory:5280 kb****************************************************************/ #include <cstdio>#include <utility>#include <map>#include <iostream>using namespace std; #define mpr make_pairtypedef long long LL;typedef pair< LL,LL > pr;const int N = 505; LL p=1,n=65,m,T;map< LL,pr > mp;LL a[N][N];LL b[N*N]; inline LL in(LL x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; } void _add(LL x,pr y){ mp[x]=y; }LL _get(){ while(mp.count(p)) p++;return p; } int main(){ a[2][1]=1,mp[1]=mpr(2,1); for(int i=3;i<=n;i++){ if(i&1){ for(int j=1;j<i;j++) a[i][i-1]+=a[j][j-1]; a[i][i-1]+=1; }else{ a[i][i-1]=_get(); } _add(a[i][i-1],pr(i,i-1)); for(int j=1;j<i-1;j++){ a[i][j]=a[i-1][j]+a[i][i-1]; _add(a[i][j],pr(i,j)); } } for(map< LL,pr >::iterator it=mp.begin();it!=mp.end();it++) b[++m]=(*it).first; for(T=in();T--;){ LL l=1,r=m,mid,x; x=in(); if(mp.count(x)){ printf("%lld %lld\n",mp[x].first,mp[x].second);continue; } while(l<=r){ mid=(l+r)>>1; if(b[mid]<x) l=mid+1; else r=mid-1; } printf("%lld %lld\n",n+(x-r)*2-1,n+(x-r)*2-2); }return 0;}
BZOJ 4725: [POI2017]Reprezentacje ró?nicowe
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。