题解 CF1204B 【Mislove Has Lost an Array】
引领天下
2019-08-21 16:37:03
这个题实际上就是贪心
思路:先取2的0到l-1次方,保证至少有l个不同的数,算出基本答案;
然后对于最小的答案,剩下的n-l个数全部填1,对于最大的答案,我们补全2的r-1次方,然后对于剩下的n-r个数全部填$2^{r-1}$
代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,l,r,cnt=1,ansn,ansx;//注意,防爆int
int main(){
cin>>n>>l>>r;
for (int i=1;i<=l;i++)ansn+=cnt,cnt*=2;
ansx=ansn,ansn+=n-l;//计算出基本答案后直接算出最小答案
for (int i=l+1;i<=r;i++)ansx+=cnt,cnt*=2;
cnt/=2;
ansx+=(n-r)*cnt;//补上n-r个数
cout<<ansn<<' '<<ansx;
}
```