A. Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Let’s denote asthe number of bits set (‘1’ bits) in the binary representation of the non-negative integerx.
You are given multiple queries consisting of pairs of integerslandr. For each query, find thex, such thatl≤x≤r, andis maximum possible. If there are multiple such numbers find the smallest of them.
Input
The first line contains integern— the number of queries (1≤n≤10000).
Each of the followingnlines contain two integersli,ri— the arguments for the corresponding query (0≤li≤ri≤1018).
Output
For each query print the answer in a separate line.
Sample test(s)
input
31 22 41 10
output
137
Note
The binary representations of numbers from 1 to 10 are listed below:
110=12
210=102
310=112
410=1002
510=1012
610=1102
710=1112
810=10002
910=10012
1010=10102
分两种情况考虑：
1.l和r的二进制拆分之后位数不同：
如果r是11111…那么答案就是r；否则是答案是11111..比l少1位
2.l和r的二进制拆分之后位数相同：
从前往后扫到不相同的那一位k，如果r从k以后全是1，答案就是r；否则答案是前k位+1111…(k+1位到最后一位都是1)
#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#include <iostream>#define LL long longusing namespace std;int a[3][1000],n;void chai(LL x,int k){a[k][0]=0;while (x){a[k][0]++;int s=a[k][0];if (x&1) a[k][s]=1;else a[k][s]=0;x>>=1;}}int main(){int n;cin>>n;while (n–){LL l,r;cin>>l>>r;if (l==r){cout<<l<<endl;continue;}chai(l,0);chai(r,1);if (a[0][0]<a[1][0]){LL ans=0,b=1;for (int i=1;i<a[1][0];i++)ans+=b,b<<=1LL;if (ans+b==r) ans=r;cout<<ans<<endl;}else{int k=0;for (int i=a[0][0];i;i–){if (a[0][i]!=a[1][i]){k=i;break;}}LL ans=0,b=1;for (int i=1;i<k;i++)ans+=b,b<<=1LL;int ok=1;for (int i=1;i<=k;i++){if (!a[1][i]) ok=0;}if (ok) ans+=b;b<<=1LL;for (int i=k+1;i<=a[0][0];i++)ans+=(b*a[0][i]),b<<=1;cout<<ans<<endl;}}return 0;}
B. Maximum Value
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given a sequenceaconsisting ofnintegers. Find the maximum possible value of(integer remainder ofaidivided byaj), where1≤i,j≤nandai≥aj.
Input
The first line contains integern— the length of the sequence (1≤n≤2·105).
The second line containsnspace-separated integersai(1≤ai≤106).
Output
Print the answer to the problem.
Sample test(s)
input
33 4 5
output
2
如果枚举ai，，复杂度是O(n^2)，那么我们可以枚举aj!
x=aj*k+b，k相同，要让b最大则让x最大。
我们枚举k，要找到>aj*k且<aj*(k+1)的最大数。
就相当于找最接近aj*(k+1)的数，那么我们预处理出m[i]表示<=i的最大数是几。
有本钱耍个性，离开睁眼闭眼看见的城市，逃离身边的纷纷扰扰，
