题解 CF1204B 【Mislove Has Lost an Array】

发表于 更新于 阅读次数： Waline： 阅读次数：
CF1204B 【Mislove Has Lost an Array】题解。

这个题实际上就是贪心

思路：先取2的0到l-1次方，保证至少有l个不同的数，算出基本答案；

然后对于最小的答案，剩下的n-l个数全部填1，对于最大的答案，我们补全2的r-1次方，然后对于剩下的n-r个数全部填$2^{r-1}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#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;
}