admin 管理员组

文章数量: 1087582

二分法应用

链接：
来源：牛客网

题目描述
Ann Logan is fascinated with finite sequences of integers. She is particularly interested in sequences of the form x1, x2, . . . , xn where:
• xi = (axi−1 + c) mod m,
• n, m, a, and c are positive integer constants,
• x0 is a non-negative integer constant, and
• all n values are unique.
For example, if n = 5, m = 8, a = 1, c = 3, and x0 = 3, the sequence is 6, 1, 4, 7, 2 (x1 = (1 · 3 + 3) mod 8 = 6, x2 = (1 · 6 + 3) mod 8 = 1, and so on). Note that she does not consider the initial value x0 to be part of the sequence.
Ann wants to be able to quickly determine, for any integer value, whether or not it appears within a finite sequence of this form. Given values of n, m, a, c, and x0, she plans to follow this list of steps:
1. Generate the sequence x1, · · · , xn and store it in an array.
2. Sort the array.
3. Perform a binary search of the array for each integer of interest to her.
Ann’s search algorithm, while not the most efficient possible, is pretty straightforward and understandable to anyone familiar with binary search: after calculating the midpoint mid at each step of the calculation (using mid = (low+high)/2), she first checks whether or not the value at location mid is equal to the search value x. If not, she then narrows the search according to whether x is strictly less than or strictly greater than the value at location mid.
Unfortunately, Ann is absent-minded and she lost her list of steps. She managed to remember the first and last step, but . . . she forgot to sort the array before performing her binary search! Needless to say, this means that many values that are in the (unsorted) array will not be found by a binary search, although surprisingly some can. In the example above, both 4 and 7 can be found with Ann’s binary search. How many values can be found for various sequences? Don’t botch it up!
输入描述:
Input consists of a line containing five integers n, m, a, c, and x0 (1 ≤ n ≤ 106 , 1 ≤ m, a, c ≤ 2 31 − 1, 0 ≤ x0 ≤ 2 31 − 1), where n is the length of the sequence x1, . . . , xn to be generated and m, a, c, and x0 are the constants used for generating the sequence. All values in the generated sequence are guaranteed to be unique.
输出描述:
Output the number of sequence values that could be found using Ann’s version of binary search, assuming she forgot to sort the sequence.
示例1
输入
复制
5 8 1 3 3
输出
复制
2
示例2
输入
复制
6 10 1234567891 1 1234567890
输出
复制
6
题解：本体没有代码操作上的难度，就是考察的对二分法的理解，题目中说可以找到，就先认为它可以找到，二分法查找，看能不能找到。代码没什么，就简单二分。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nl=1e6+5;//注意数组开的大小，不然容易Wa（段错误）
ll b[nl];
ll n,m,a,c,x0;
int main(){cin>>n>>m>>a>>c>>x0;ll i,j;b[0]=x0;for(i=1;i<=n;i++){b[i]=(a*b[i-1]+c)%m;//cout<<b[i]<<endl;} ll flag=0;ll sum=0;for(i=1;i<=n;i++){ll l=1,r=n;ll mid;flag=0;while(l<=r){mid=(l+r)/2;if(b[mid]<b[i]){l=mid+1;}else if(b[mid]>b[i]){r=mid-1;}else{flag=1;//cout<<b[i]<<endl;break;}}if(flag==1){sum++;}}cout<<sum;
}


题意：给出n,k。要求找出一个m，令m+m/k+m/(kk)…(直到（m/kk…）为零)。并且m要求最小。
思路：查找某个数，可以使用二分法，即从n以内（包括n）中找一个合适的数，二分法简单明了。为什么是从n以内找呢，因为如果n<k，直接输出n就好了，n>k时就不说了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nl=1e5+5;ll n,k;ll i,j;
bool cmp(ll x){ll num=x;while(1){if(x==0){break;}num+=x/k;x/=k;}if(num>=n){return true;}else{return false;}
}
int main(){cin>>n>>k;ll l=1,r=n;ll a=n;while(l<=r){ll mim;mim=(l+r)/2;if(cmp(mim)==true){//放置合理的条件r=mim-1;if(mim<a){a=mim;}}else{l=mim+1;}}cout<<a;
}

本文标签： 二分法应用

版权声明：本文标题：二分法应用 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700300627a386710.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。