开发者社区开发与运维文章正文

codeforces 305 C. Ivan and Powers of Two

2023-10-31 16

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 我的思路是这样的，由2^a+2^a = 2^(a+1)可知，如果有两个连续的数a，我们可以把他们合并为a+1放入集合中，使集合中没有重复的数，我可以用stl里的set。如果想要满足题目中的要求，集合中必须有最大那个数个元素，缺多少就可以计算出来了。

给出一个非减序的数组a[n], 然后得到s=2^a1+.……+2^an，要使s为2^v -1,需要在数组中添加几个数。

我的思路是这样的，由2^a+2^a = 2^(a+1)可知，如果有两个连续的数a，我们可以把他们合并为a+1放入集合中，使集合中没有重复的数，我可以用stl里的set。如果想要满足题目中的要求，集合中必须有最大那个数个元素，缺多少就可以计算出来了。

代码：

//codeforces 305 C. Ivan and Powers of Two
//2013-06-05-17.19
#include <stdio.h>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
set<int> s;
int main()
{
    int n, a;
    while (scanf("%d", &n) != EOF)
    {
        s.clear();
        int maxn = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a);
            while (s.count(a))
            {
                s.erase(a);
                a++;
            }
            s.insert(a);
            maxn = max(a, maxn);
        }
        printf("%d\n", maxn-s.size()+1);
    }
    return 0;
}