Hdu 6676 度度熊与运算式 1

度度熊与运算式 1

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6676


解题思路:开始想是不是把所有?都改成+会最大。后面才发现如果两个同样大的偶数异或之后就变小了，所以只有是不行的，那要使结果最小，显然要使每个串尽量组成没有组成过的2的幂次，那就先把?串全部存起来，这里面1的数量就是？个数加1，然后从大到小(从小到大会导致把大的拆了可能就无法组成最大结果)看能不能组成2的幂次，如果有超过2个串满足要求，那就意味这两个串就能组成当前和之后所有的2的幂次，那就不需要再找了，直接退出，最后算一下剩下的1的数量，如果是奇数的话就能把末尾的0异或成1，就还能再加一。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int len = s.length();
        priority_queue<int> q;
        int num = 0;
        for (int i = 0; i < len; i++) {
            if (s[i] == '^') {
                if (num != 0) {
                    q.push(num + 1);
                    num = 0;
                }
            } else if(s[i]=='?'){
                num++;
            }
        }
        if (num != 0) {
            q.push(num + 1);
            num = 0;
        }
        if (q.empty()) {
            if (len & 1)cout << "0" << endl;
            else cout << "1" << endl;
        } else {
            int res = 0;
            int val = 0;//题目说明长度在2的21次以内
            for (int i = 20; i >= 1; i--) {//能组成的最长串也不会到2的21次，所以最大为20次
                int sum = 0;
                while (!q.empty() && q.top() >= (1 << i)) {//找能有几个组成2的i次方长度的串
                    sum++;
                    val = q.top();
                    q.pop();
                }
                if (sum == 1) {//只有一个就把他分割成2的i次和剩下的数
                    res += (1<<i);
                    q.push(val - (1<<i) );//把减去2的i次剩下的数推回队列
                } else if (sum >= 2) {//如果不只一个串超过了2的i次
                    //那就意味着之后的串不需要再找了，因为2的i次可以组成所有低于他的次数的串
                    for (int j = 1; j <= i; j++) {
                        res += (1 << j);
                    }
                    break;//找完了那就可以直接退出
                }
            }
            int l = len - res + 1;//剩下的1个数
            if (l & 1) {//奇数个的话因为组好的串都是偶数，所以还能加1
                res++;
            }
            cout << res << endl;
        }
    }
    return 0;
}